Learning Spectral Clustering, With Application To Speech Separation

Abstract

Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive new cost functions for spectral clustering based on measures of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing these cost functions with respect to the partition leads to new spectral clustering algorithms. Minimizing with respect to the similarity matrix leads to algorithms for learning the similarity matrix from fully labelled data sets. We apply our learning algorithm to the blind one-microphone speech separation problem, casting the problem as one of segmentation of the spectrogram.

References

1. K. Achan, S. Roweis, and B. Frey. Probabilistic inference of speech signals from phaseless spectrograms. In Advances in Neural Information Processing Systems 16. MIT Press, 2003.
2. F. R. Bach and M. I. Jordan. Discriminative training of hidden Markov models for multiple pitch tracking. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2005.
3. A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning distance functions using equivalence relations. In International Conference on Machine Learning (ICML), 2003.
4. K.-J. Bathe and E. L. Wilson. Numerical Methods in Finite Element Analysis. Prentice Hall, 1976.
5. D. Bertsimas and J. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
6. M. Blatt, M. Wiesman, and E. Domany. Data clustering using a model granular magnet. Neural Computation, 9:1805-1842, 1997.
7. A. S. Bregman. Auditory Scene Analysis: The Perceptual Organization of Sound. MIT Press, 1990.
8. G. J. Brown and M. P. Cooke. Computational auditory scene analysis. Computer Speech and Language, 8:297-333, 1994.
9. P. K. Chan, M. D. F. Schlag, and J. Y. Zien. Spectral K-way ratio-cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 13(9):1088-1096, 1994.
10. F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
11. P. Comon and G. H. Golub. Tracking a few extreme singular values and vectors in signal processing. Proceedings of the IEEE, 78(8):1327-1343, 1990.
12. M. Cooke and D. P. W. Ellis. The auditory organization of speech and other sources in listeners and computational models. Speech Communication, 35(3-4):141-177, 2001.
13. T. Cour, N. Gogin, and J. Shi. Learning spectral graph segmentation. In Workshop on Artificial Intelligence and Statistics (AISTATS), 2005.
14. N. Cristianini, J. Shawe-Taylor, and J. Kandola. Spectral kernel methods for clustering. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
15. I. Dhillon, Y. Guan, and B. Kulis. A unified view of kernel k-means, spectral clustering and and graph cuts. Technical Report #TR-04-25, University of Texas, Computer Science, 2004.
16. C. Ding, X. He, and H. D. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the SIAM International Conference on Data Mining (SDM), 2005.
17. A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20(2):303-353, 1999.
18. C. Fowlkes, S. Belongie, and J. Malik. Efficient spatiotemporal grouping using the Nyström method. In IEEE conference on Computer Vision and Pattern Recognition (ECCV), 2001.
19. B. Gold and N. Morgan. Speech and Audio Signal Processing: Processing and Perception of Speech and Music. Wiley Press, 1999.
20. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
21. A. G. Gray and A. W. Moore. N-Body problems in statistical learning. In Advances in Neural Information Processing Systems, 13. MIT Press, 2001.
22. D. W. Griffin and J. S. Lim. Signal estimation from modified short-time Fourier transform. IEEE Transactions on Acoustics, Speech and Signal Processing, 32(2):236-243, 1984.
23. M. Gu, H. Zha, C. Ding, X. He, and H. Simon. Spectral relaxation models and structure analysis for K-way graph clustering and bi-clustering. Technical report, Penn. State Univ, Computer Science and Engineering, 2001.
24. D. Higham and M. Kibble. A unified view of spectral clustering. Technical Report 02, University of Strathclyde, Department of Mathematics, 2004.
25. L. J. Hubert and P. Arabie. Comparing partitions. Journal of Classification, 2:193-218, 1985.
26. A. Hyvärinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, 2001.
27. G.-J. Jang and T.-W. Lee. A maximum likelihood approach to single-channel source separation. Journal of Machine Learning Research, 4:1365-1392, 2003.
28. A. Jourjine, S. Rickard, and O. Yilmaz. Blind separation of disjoint orthogonal signals: Demixing N sources from 2 mixtures. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2000.
29. S. D. Kamvar, D. Klein, and C. D. Manning. Spectral learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2003.
30. D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems, 12. MIT Press, 2000.
31. J. R. Magnus and H. Neudecker. Matrix differential calculus with applications in statistics and econometrics. John Wiley, 1999.
32. S. Mallat. A Wavelet Tour of Signal Processing. Academic Press, 1998.
33. D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In International Conference on Computer Vision (ICCV), 2001.
34. M. Meila and D. Heckerman. An experimental comparison of several clustering and initialization methods. Machine Learning, 42(1):9-29, 2001.
35. M. Meila and J. Shi. Learning segmentation by random walks. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
36. M. Meila and L. Xu. Multiway cuts and spectral clustering. Technical report, University of Washington, Department of Statistics, 2003.
37. A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
38. M. L. Overton and R. S. Womersley. Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrics. Mathematical Programming, 62:321-357, 1993.
39. S. T. Roweis. One microphone source separation. In Advances in Neural Information Processing Systems, 13. MIT Press, 2001.
40. G. L. Scott and H. C. Longuet-Higgins. Feature grouping by relocalisation of eigenvectors of the proximity matrix. In British Machine Vision Conference, 1990.
41. N. Shental, A. Zomet, T. Hertz, and Y. Weiss. Learning and inferring image segmentations using the gbp typical cut algorithm. In International Conference on Computer Vision (ICCV), 2003.
42. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000.
43. M. Szummer and T. Jaakkola. Partially labeled classification with Markov random walks. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
44. N. Tishby and N. Slonim. Data clustering by Markovian relaxation and the information bottleneck method. In Advances in Neural Information Processing Systems, 13. MIT Press, 2001.
45. U. von Luxburg, O. Bousquet, and M. Belkin. Limits of spectral clustering. In Advances in Neural Information Processing Systems, 17. MIT Press, 2005.
46. K. Wagstaff, C. Cardie, S. Rogers, and S. Schrödl. Constrained K-means clustering with background knowledge. In International Conference on Machine Learning (ICML), 2001.
47. G. Wahba. Spline Models for Observational Data. SIAM, 1990.
48. Y. Weiss. Segmentation using eigenvectors: a unifying view. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 1999.
49. E. P. Xing and M. I. Jordan. On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical Report UCB/CSD-03-1265, EECS Department, University of California, Berkeley, 2003.
50. E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems, 15. MIT Press, 2003.
51. S. X. Yu and J. Shi. Grouping with bias. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
52. S. X. Yu and J. Shi. Multiclass spectral clustering. In International Conference on Computer Vision (ICCV), 2003.
53. H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for K-means clustering. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.
54. M. Zibulevsky, P. Kisilev, Y. Y. Zeevi, and B. A. Pearlmutter. Blind source separation via multinode sparse representation. In Advances in Neural Information Processing Systems, 14. MIT Press, 2002.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Natural language processing

      • Speech recognition

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Hardware

  • Communication hardware, interfaces and storage

    • Signal processing systems