nips nips2004 nips2004-31 knowledge-graph by maker-knowledge-mining

31 nips-2004-Blind One-microphone Speech Separation: A Spectral Learning Approach

Source: pdf

Author: Francis R. Bach, Michael I. Jordan

Abstract: We present an algorithm to perform blind, one-microphone speech separation. Our algorithm separates mixtures of speech without modeling individual speakers. Instead, we formulate the problem of speech separation as a problem in segmenting the spectrogram of the signal into two or more disjoint sets. We build feature sets for our segmenter using classical cues from speech psychophysics. We then combine these features into parameterized afﬁnity matrices. We also take advantage of the fact that we can generate training examples for segmentation by artiﬁcially superposing separately-recorded signals. Thus the parameters of the afﬁnity matrices can be tuned using recent work on learning spectral clustering [1]. This yields an adaptive, speech-speciﬁc segmentation algorithm that can successfully separate one-microphone speech mixtures. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Blind one-microphone speech separation: A spectral learning approach Francis R. [sent-1, score-0.688]

2 edu Abstract We present an algorithm to perform blind, one-microphone speech separation. [sent-7, score-0.526]

3 Our algorithm separates mixtures of speech without modeling individual speakers. [sent-8, score-0.597]

4 Instead, we formulate the problem of speech separation as a problem in segmenting the spectrogram of the signal into two or more disjoint sets. [sent-9, score-1.106]

5 We build feature sets for our segmenter using classical cues from speech psychophysics. [sent-10, score-0.861]

6 We also take advantage of the fact that we can generate training examples for segmentation by artiﬁcially superposing separately-recorded signals. [sent-12, score-0.213]

7 Thus the parameters of the afﬁnity matrices can be tuned using recent work on learning spectral clustering [1]. [sent-13, score-0.324]

8 This yields an adaptive, speech-speciﬁc segmentation algorithm that can successfully separate one-microphone speech mixtures. [sent-14, score-0.702]

9 1 Introduction The problem of recovering signals from linear mixtures, with only partial knowledge of the mixing process and the signals—a problem often referred to as blind source separation— is a central problem in signal processing. [sent-15, score-0.397]

10 It has applications in many ﬁelds, including speech processing, network tomography and biomedical imaging [2]. [sent-16, score-0.526]

11 , when there are no more signals to estimate (the sources) than signals that are observed (the sensors), generic assumptions such as statistical independence of the sources can be used in order to demix successfully [2]. [sent-19, score-0.384]

12 ” In this paper we present an algorithm that is a blind separation algorithm—our algorithm separates speech mixtures from a single microphone without requiring models of speciﬁc speakers. [sent-28, score-0.902]

13 Our approach involves a “discriminative” approach to the problem of speech separation. [sent-29, score-0.526]

14 That is, rather than building a complex model of speech, we instead focus directly on the task of separation and optimize parameters that determine separation performance. [sent-30, score-0.308]

15 We work within a time-frequency representation (a spectrogram), and exploit the sparsity of speech signals in this representation. [sent-31, score-0.68]

16 That is, although two speakers might speak simultaneously, there is relatively little overlap in the time-frequency plane if the speakers are different [5, 4]. [sent-32, score-0.306]

17 We thus formulate speech separation as a problem in segmentation in the time-frequency plane. [sent-33, score-0.824]

18 In principle, we could appeal to classical segmentation methods from vision (see, e. [sent-34, score-0.182]

19 Thus we must design features for segmenting speech from ﬁrst principles. [sent-38, score-0.628]

20 In particular, we exploit the fact that in speech we can generate “training examples” by artiﬁcially superposing two separately-recorded signals. [sent-40, score-0.566]

21 Making use of our earlier work on learning methods for spectral clustering [1], we use the training data to optimize the parameters of a spectral clustering algorithm. [sent-41, score-0.489]

22 This yields an adaptive, “discriminative” segmentation algorithm that is optimized to separate speech signals. [sent-42, score-0.67]

23 We highlight one other aspect of the problem here—the major computational challenge involved in applying spectral methods to speech separation. [sent-43, score-0.741]

24 Thus a major part of our effort has involved the design of numerical approximation schemes that exploit the different time scales present in speech signals. [sent-46, score-0.748]

25 In Section 3 we describe our approach to feature design based on known cues for speech separation [8, 9]. [sent-49, score-0.927]

26 Section 4 shows how parameterized afﬁnity matrices based on these cues can be optimized in the spectral clustering setting. [sent-50, score-0.501]

27 2 Speech separation as spectrogram segmentation In this section, we ﬁrst review the relevant properties of speech signals in the timefrequency representation and describe how our training sets are constructed. [sent-52, score-1.333]

28 1 Spectrogram The spectrogram is a two-dimensional (time and frequency) redundant representation of a one-dimensional signal [10]. [sent-54, score-0.452]

29 The spectrogram is deﬁned through windowed Fourier transforms and is commonly referred to as a short-time Fourier transform or as Gabor analysis [10]. [sent-59, score-0.35]

30 The value (U f )mn of the spectroT −1 gram at time window n and frequency m is deﬁned as (U f )mn = √1 t=0 f [t]w[t − M na]ei2πmt/M , where w is a window of length T with small support of length c. [sent-60, score-0.301]

31 The spectrogram is thus an N × M image which provides a redundant time-frequency representation of time signals1 (see Figure 1). [sent-63, score-0.436]

32 Inversion Our speech separation framework is based on the segmentation of the spectrogram of a signal f [t] in S 2 disjoint subsets Ai , i = 1, . [sent-64, score-1.25]

33 For a speech sample of length 4 sec, we have T = 22, 000 samples and then N = 407, which makes ≈ 2 × 105 spectrogram pixels. [sent-78, score-0.911]

34 We now need to ﬁnd S speech signals fi [t] such that each Ui is the spectrogram of fi . [sent-82, score-1.076]

35 Normalization and subsampling There are several ways of normalizing a speech signal. [sent-88, score-0.526]

36 In this paper, we chose to rescale all speech signals as follows: for each time window n, we compute the total energy en = m |U fmn |2 , and its 20-point moving average. [sent-89, score-0.82]

37 In order to reduce the number of spectrogram samples to consider, for a given prenormalized speech signal, we threshold coefﬁcients whose magnitudes are less than a value that was chosen so that the distortion is inaudible. [sent-91, score-0.886]

38 2 Generating training samples Our approach is based on a learning algorithm that optimizes a segmentation criterion. [sent-93, score-0.207]

39 The training examples that we provide to this algorithm are obtained by mixing separatelynormalized speech signals. [sent-94, score-0.596]

40 That is, given two volume-normalized speech signals f1 , f2 of the same duration, with spectrograms U1 and U2 , we build a training sample as U train = U1 + U2 , with a segmentation given by z = arg min{U1 , U2 }. [sent-95, score-0.916]

41 3 Features and grouping cues for speech separation In this section we describe our approach to the design of features for the spectral segmentation. [sent-98, score-1.078]

42 We base our design on classical cues suggested from studies of perceptual grouping [11]. [sent-99, score-0.227]

43 Each of these cues is associated with a speciﬁc time scale, which we refer to as “small” (less than 5 frames), “medium” (10 to 20 frames), and “large” (across all frames). [sent-101, score-0.184]

44 1 Non-harmonic cues The following non-harmonic cues have counterparts in visual scenes and for these cues we are able to borrow from feature design techniques used in image segmentation [7]. [sent-106, score-0.659]

45 Continuity Two time-frequency points are likely to belong to the same segment if they are close in time or frequency; we thus use time and frequency directly as features. [sent-107, score-0.187]

46 Common fate cues Elements that exhibit the same time variation are likely to belong to the same source. [sent-109, score-0.224]

47 The onset and offset maps are built using oriented energy ﬁlters as used in vision (with one vertical orientation). [sent-113, score-0.148]

48 These are obtained by convolving the spectrogram with derivatives of Gaussian windows [7]. [sent-114, score-0.326]

49 Another form of the common fate cue is frequency co-modulation, the situation in which frequency components of a single source tend to move in sync. [sent-115, score-0.311]

50 Those features act mainly at a medium time scale. [sent-117, score-0.177]

51 2 Harmonic cues This is the major cue for voiced speech [12, 9, 8], and it acts at all time scales (small, medium and large): voiced speech is locally periodic and the local period is usually referred to as the pitch. [sent-119, score-1.616]

52 If S pitches are sought, the output that we obtain from the pitch extractor is, for each time frame n, the S pitches ωn1 , . [sent-122, score-0.594]

53 , ωnS , as well as the strength ynms of the s-th pitch for each frequency m. [sent-125, score-0.455]

54 Timbre The pitch extraction algorithm presented in Appendix A also outputs the spectral envelope of the signal [12]. [sent-126, score-0.567]

55 This can be used to design an additional feature related to timbre which helps integrate information regarding speaker identiﬁcation across time. [sent-127, score-0.307]

56 Timbre can be loosely deﬁned as the set of properties of a voiced speech signal once the pitch has been factored out [8]. [sent-128, score-0.934]

57 We add the spectral envelope as a feature (reducing its dimensionality using principal component analysis). [sent-129, score-0.284]

58 Building feature maps from pitch information We build a set of features from the pitch information. [sent-130, score-0.692]

59 Given a time-frequency point (m, n), let s(m, n) = ynms arg maxs ( denote the highest energy pitch, and deﬁne the features ωns(m,n) , y )1/2 m nm s y y nms(m,n) nms(m,n) ynms(m,n) , m ynm s(m,n) , and ( 1/2 . [sent-131, score-0.244]

60 We use a partial m ynm s(m,n) m ynm s(m,n) )) normalization with the square root to avoid including very low energy signals, while allowing a signiﬁcant difference between the local amplitude of the speakers. [sent-132, score-0.197]

61 Those features all come with some form of energy level and all features involving pitch values ω should take this energy into account when the afﬁnity matrix is built in Section 4. [sent-133, score-0.576]

62 Indeed, the values of the harmonic features have no meaning when no energy in that pitch is present. [sent-134, score-0.469]

63 4 Spectral clustering and afﬁnity matrices Given the features described in the previous section, we now show how to build afﬁnity (i. [sent-135, score-0.246]

64 , similarity) matrices that can be used to deﬁne a spectral segmenter. [sent-137, score-0.256]

65 1 Spectral clustering Given P data points to partition into S 2 disjoint groups, spectral clustering methods use an afﬁnity matrix W , symmetric of size P × P , that encodes topological knowledge about the problem. [sent-140, score-0.395]

66 We prefer spectral clustering methods over other clustering algorithms such as K-means or mixtures of Gaussians estimated by the EM algorithm because we do not have any reason to expect the segments of interest in our problem to form convex shapes in the feature representation. [sent-144, score-0.438]

67 2 Parameterized afﬁnity matrices The success of spectral methods for clustering depends heavily on the construction of the afﬁnity matrix W . [sent-146, score-0.36]

68 2, such training data are easily obtained in the speech separation setting. [sent-150, score-0.709]

69 Thus, if fa is the value of the feature for data point a, we use a basis afﬁnity matrix deﬁned as Wab = exp(−||fa − fb ||β ), where β > 1. [sent-156, score-0.223]

70 For our application to speech separation, we consider a sum of K = 3 matrices, one matrix for each time scale. [sent-160, score-0.612]

71 3 Approximations of afﬁnity matrices The afﬁnity matrices that we consider are huge, of size at least 50,000 by 50,000. [sent-163, score-0.188]

72 On a small time scale, W has a small bandwidth; for a medium time scale, the band is larger but still small compared to the total size of the matrix, while for large scale effects, the matrix W has no band structure. [sent-168, score-0.309]

73 Note that the bandwidth B can be controlled by the coefﬁcient of the radial basis function involving the time feature n. [sent-169, score-0.238]

74 5 Experiments We have trained our segmenter using data from four different speakers, with speech signals of duration 3 seconds. [sent-189, score-0.77]

75 There were 28 parameters to estimate using our spectral learning algorithm. [sent-190, score-0.162]

76 For testing, we have use mixes from ﬁve speakers that were different from those in the training set. [sent-191, score-0.182]

77 In Figure 2, for two speakers from the testing set, we show on the left part an example of the segmentation that is obtained when the two speech signals are known in advance (obtained as described in Section 2. [sent-192, score-0.949]

78 Although some components of the “black” speaker are missing, the segmentation performance is good enough to obtain audible signals of reasonable quality. [sent-194, score-0.35]

79 The speech samples for this example can de downloaded from www. [sent-195, score-0.56]

80 On this web site, there are additional examples of speech separation, with various speakers, in French and in English. [sent-199, score-0.526]

81 As mentioned earlier, there was a major computational challenge in applying spectral methods to single microphone speech separation. [sent-201, score-0.771]

82 coded in Matlab and C, it takes 30 minutes to separate 4 seconds of speech on a 1. [sent-205, score-0.526]

83 6 Conclusions We have presented an algorithm to perform blind source separation of speech signals from a single microphone. [sent-207, score-0.946]

84 To do so, we have combined knowledge of physical and psychophysical properties of speech with learning methods. [sent-208, score-0.526]

85 The former provide parameterized afﬁnity matrices for spectral clustering, and the latter make use of our ability to generate segmented training data. [sent-209, score-0.328]

86 The result is an optimized segmenter for spectrograms of speech mixtures. [sent-210, score-0.648]

87 We have successfully demixed speech signals from two speakers using this approach. [sent-211, score-0.837]

88 Second, there are multiple applications where speech has to be separated from a non-stationary noise; we believe that our method can be extended to this situation. [sent-215, score-0.553]

89 Third, our framework is based on segmentation of the spectrogram and, as such, distortions are inevitable since this is a “lossy” formulation [6, 4]. [sent-216, score-0.47]

90 Finally, while running time and memory requirements of our algorithm are linear in the duration of the signal to be separated, the resource requirements remain a concern. [sent-218, score-0.218]

91 Pitch estimation Pitch estimation for one pitch In this paragraph, we assume that we are given one time slice s of the spectrogram magnitude, s ∈ RM . [sent-221, score-0.651]

92 Since the speech signals are real, the spectrogram is symmetric and we can consider only M/2 samples. [sent-223, score-0.978]

93 We ˜ impose a constraint on the harmonic strengths (xh ), namely, that they are samples at hω M/2 (2) of a function g with small second derivative norm 0 |g (ω)|2 dω. [sent-235, score-0.155]

94 The function g can be seen as the envelope of the signal and is related to the “timbre” of the speaker [8]. [sent-236, score-0.21]

95 The explicit consideration of the envelope and its smoothness is necessary for two reasons: (a) it will provide a timbre feature helpful for separation, (b) it helps avoid pitch-halving, a traditional problem of pitch extractors [12]. [sent-237, score-0.511]

96 Pitch estimation for several pitches If we are to estimate S pitches, we estimate them recursively, by removing the estimated harmonic signals. [sent-244, score-0.205]

97 In this paper, we assume that the number of speakers and hence the maximum number of pitches is known. [sent-245, score-0.272]

98 Note, however, that since all our pitch features are always used with their strengths, our separation method is relatively robust to situations where we try to look for too many pitches. [sent-246, score-0.476]

99 The auditory organization of speech and other sources in listeners and computational models. [sent-316, score-0.619]

100 Discriminative training of hidden Markov models for multiple pitch tracking. [sent-339, score-0.304]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('speech', 0.526), ('spectrogram', 0.326), ('pitch', 0.275), ('nity', 0.25), ('af', 0.226), ('spectral', 0.162), ('separation', 0.154), ('speakers', 0.153), ('segmentation', 0.144), ('cues', 0.134), ('signals', 0.126), ('pitches', 0.119), ('timbre', 0.114), ('blind', 0.097), ('matrices', 0.094), ('frequency', 0.087), ('harmonic', 0.086), ('speaker', 0.08), ('medium', 0.08), ('segmenter', 0.068), ('ynm', 0.068), ('ynms', 0.068), ('clustering', 0.068), ('voiced', 0.067), ('signal', 0.066), ('envelope', 0.064), ('fa', 0.064), ('energy', 0.061), ('feature', 0.058), ('bach', 0.058), ('window', 0.057), ('design', 0.055), ('microphone', 0.054), ('spectrograms', 0.054), ('sources', 0.054), ('cue', 0.054), ('bandwidth', 0.052), ('duration', 0.05), ('time', 0.05), ('fi', 0.049), ('xh', 0.048), ('bump', 0.048), ('features', 0.047), ('mixtures', 0.047), ('ui', 0.047), ('demix', 0.046), ('nms', 0.046), ('source', 0.043), ('parameterized', 0.043), ('mixing', 0.041), ('fate', 0.04), ('hanning', 0.04), ('superposing', 0.04), ('mn', 0.039), ('auditory', 0.039), ('classical', 0.038), ('build', 0.037), ('fb', 0.036), ('wab', 0.036), ('matrix', 0.036), ('strengths', 0.035), ('segments', 0.035), ('sensors', 0.035), ('samples', 0.034), ('approximation', 0.034), ('francis', 0.034), ('band', 0.034), ('appendix', 0.034), ('disjoint', 0.034), ('successfully', 0.032), ('offset', 0.032), ('redundant', 0.032), ('ya', 0.032), ('ns', 0.032), ('frame', 0.031), ('frames', 0.031), ('onset', 0.03), ('scales', 0.03), ('complexity', 0.03), ('cially', 0.029), ('periodic', 0.029), ('spline', 0.029), ('training', 0.029), ('basis', 0.029), ('major', 0.029), ('discriminative', 0.028), ('representation', 0.028), ('partition', 0.027), ('separated', 0.027), ('requirements', 0.026), ('length', 0.025), ('strength', 0.025), ('wj', 0.025), ('radial', 0.025), ('scale', 0.025), ('built', 0.025), ('involved', 0.024), ('involving', 0.024), ('referred', 0.024), ('separates', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000007 31 nips-2004-Blind One-microphone Speech Separation: A Spectral Learning Approach

Author: Francis R. Bach, Michael I. Jordan

2 0.40880996 5 nips-2004-A Harmonic Excitation State-Space Approach to Blind Separation of Speech

Author: Rasmus K. Olsson, Lars K. Hansen

Abstract: We discuss an identiﬁcation framework for noisy speech mixtures. A block-based generative model is formulated that explicitly incorporates the time-varying harmonic plus noise (H+N) model for a number of latent sources observed through noisy convolutive mixtures. All parameters including the pitches of the source signals, the amplitudes and phases of the sources, the mixing ﬁlters and the noise statistics are estimated by maximum likelihood, using an EM-algorithm. Exact averaging over the hidden sources is obtained using the Kalman smoother. We show that pitch estimation and source separation can be performed simultaneously. The pitch estimates are compared to laryngograph (EGG) measurements. Artiﬁcial and real room mixtures are used to demonstrate the viability of the approach. Intelligible speech signals are re-synthesized from the estimated H+N models.

3 0.35583708 152 nips-2004-Real-Time Pitch Determination of One or More Voices by Nonnegative Matrix Factorization

Author: Fei Sha, Lawrence K. Saul

Abstract: An auditory “scene”, composed of overlapping acoustic sources, can be viewed as a complex object whose constituent parts are the individual sources. Pitch is known to be an important cue for auditory scene analysis. In this paper, with the goal of building agents that operate in human environments, we describe a real-time system to identify the presence of one or more voices and compute their pitch. The signal processing in the front end is based on instantaneous frequency estimation, a method for tracking the partials of voiced speech, while the pattern-matching in the back end is based on nonnegative matrix factorization, an unsupervised algorithm for learning the parts of complex objects. While supporting a framework to analyze complicated auditory scenes, our system maintains real-time operability and state-of-the-art performance in clean speech.

4 0.17822772 79 nips-2004-Hierarchical Eigensolver for Transition Matrices in Spectral Methods

Author: Chakra Chennubhotla, Allan D. Jepson

Abstract: We show how to build hierarchical, reduced-rank representation for large stochastic matrices and use this representation to design an efﬁcient algorithm for computing the largest eigenvalues, and the corresponding eigenvectors. In particular, the eigen problem is ﬁrst solved at the coarsest level of the representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy. A small number of power iterations are employed at each stage to correct the eigen solution. The typical speedups obtained by a Matlab implementation of our fast eigensolver over a standard sparse matrix eigensolver [13] are at least a factor of ten for large image sizes. The hierarchical representation has proven to be effective in a min-cut based segmentation algorithm that we proposed recently [8]. 1 Spectral Methods Graph-theoretic spectral methods have gained popularity in a variety of application domains: segmenting images [22]; embedding in low-dimensional spaces [4, 5, 8]; and clustering parallel scientiﬁc computation tasks [19]. Spectral methods enable the study of properties global to a dataset, using only local (pairwise) similarity or afﬁnity measurements between the data points. The global properties that emerge are best understood in terms of a random walk formulation on the graph. For example, the graph can be partitioned into clusters by analyzing the perturbations to the stationary distribution of a Markovian relaxation process deﬁned in terms of the afﬁnity weights [17, 18, 24, 7]. The Markovian relaxation process need never be explicitly carried out; instead, it can be analytically expressed using the leading order eigenvectors, and eigenvalues, of the Markov transition matrix. In this paper we consider the practical application of spectral methods to large datasets. In particular, the eigen decomposition can be very expensive, on the order of O(n 3 ), where n is the number of nodes in the graph. While it is possible to compute analytically the ﬁrst eigenvector (see §3 below), the remaining subspace of vectors (necessary for say clustering) has to be explicitly computed. A typical approach to dealing with this difﬁculty is to ﬁrst sparsify the links in the graph [22] and then apply an efﬁcient eigensolver [13, 23, 3]. In comparison, we propose in this paper a specialized eigensolver suitable for large stochastic matrices with known stationary distributions. In particular, we exploit the spectral properties of the Markov transition matrix to generate hierarchical, successively lower-ranked approximations to the full transition matrix. The eigen problem is solved directly at the coarsest level of representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy, using a small number of power iterations to correct the solution at each stage. 2 Previous Work One approach to speeding up the eigen decomposition is to use the fact that the columns of the afﬁnity matrix are typically correlated. The idea then is to pick a small number of representative columns to perform eigen decomposition via SVD. For example, in the Nystrom approximation procedure, originally proposed for integral eigenvalue problems, the idea is to randomly pick a small set of m columns; generate the corresponding afﬁnity matrix; solve the eigenproblem and ﬁnally extend the solution to the complete graph [9, 10]. The Nystrom method has also been recently applied in the kernel learning methods for fast Gaussian process classiﬁcation and regression [25]. Other sampling-based approaches include the work reported in [1, 2, 11]. Our starting point is the transition matrix generated from afﬁnity weights and we show how building a representational hierarchy follows naturally from considering the stochastic matrix. A closely related work is the paper by Lin on reduced rank approximations of transition matrices [14]. We differ in how we approximate the transition matrices, in particular our objective function is computationally less expensive to solve. In particular, one of our goals in reducing transition matrices is to develop a fast, specialized eigen solver for spectral clustering. Fast eigensolving is also the goal in ACE [12], where successive levels in the hierarchy can potentially have negative afﬁnities. A graph coarsening process for clustering was also pursued in [21, 3]. 3 Markov Chain Terminology We ﬁrst provide a brief overview of the Markov chain terminology here (for more details see [17, 15, 6]). We consider an undirected graph G = (V, E) with vertices vi , for i = {1, . . . , n}, and edges ei,j with non-negative weights ai,j . Here the weight ai,j represents the afﬁnity between vertices vi and vj . The afﬁnities are represented by a non-negative, symmetric n × n matrix A having weights ai,j as elements. The degree of a node j is n n deﬁned to be: dj = i=1 ai,j = j=1 aj,i , where we deﬁne D = diag(d1 , . . . , dn ). A Markov chain is deﬁned using these afﬁnities by setting a transition probability matrix M = AD −1 , where the columns of M each sum to 1. The transition probability matrix deﬁnes the random walk of a particle on the graph G. The random walk need never be explicitly carried out; instead, it can be analytically expressed using the leading order eigenvectors, and eigenvalues, of the Markov transition matrix. Because the stochastic matrices need not be symmetric in general, a direct eigen decomposition step is not preferred for reasons of instability. This problem is easily circumvented by considering a normalized afﬁnity matrix: L = D −1/2 AD−1/2 , which is related to the stochastic matrix by a similarity transformation: L = D −1/2 M D1/2 . Because L is symmetric, it can be diagonalized: L = U ΛU T , where U = [u1 , u2 , · · · , un ] is an orthogonal set of eigenvectors and Λ is a diagonal matrix of eigenvalues [λ1 , λ2 , · · · , λn ] sorted in decreasing order. The eigenvectors have unit length uk = 1 and from the form of A and D it can be shown that the eigenvalues λi ∈ (−1, 1], with at least one eigenvalue equal to one. Without loss of generality, we take λ1 = 1. Because L and M are similar we can perform an eigen decomposition of the Markov transition matrix as: M = D1/2 LD−1/2 = D1/2 U Λ U T D−1/2 . Thus an eigenvector u of L corresponds to an eigenvector D 1/2 u of M with the same eigenvalue λ. The Markovian relaxation process after β iterations, namely M β , can be represented as: M β = D1/2 U Λβ U T D−1/2 . Therefore, a particle undertaking a random walk with an initial distribution p 0 acquires after β steps a distribution p β given by: p β = M β p 0 . Assuming the graph is connected, as β → ∞, the Markov chain approaches a unique n stationary distribution given by π = diag(D)/ i=1 di , and thus, M ∞ = π1T , where 1 is a n-dim column vector of all ones. Observe that π is an eigenvector of M as it is easy to show that M π = π and the corresponding eigenvalue is 1. Next, we show how to generate hierarchical, successively low-ranked approximations for the transition matrix M . 4 Building a Hierarchy of Transition Matrices The goal is to generate a very fast approximation, while simultaneously achieving sufﬁcient accuracy. For notational ease, we think of M as a ﬁne-scale representation and M as some coarse-scale approximation to be derived here. By coarsening M further, we can generate successive levels of the representation hierarchy. We use the stationary distribution π to construct a corresponding coarse-scale stationary distribution δ. As we just discussed a critical property of the ﬁne scale Markov matrix M is that it is similar to the symmetric matrix L and we wish to preserve this property at every level of the representation hierarchy. 4.1 Deriving Coarse-Scale Stationary Distribution We begin by expressing the stationary distribution π as a probabilistic mixture of latent distributions. In matrix notation, we have (1) π = K δ, where δ is an unknown mixture coefﬁcient vector of length m, K is an n × m non-negative n kernel matrix whose columns are latent distributions that each sum to 1: i=1 Ki,j = 1 and m n. It is easy to derive a maximum likelihood approximation of δ using an EM type algorithm [16]. The main step is to ﬁnd a stationary point δ, λ for the Lagrangian: m n i=1 m Ki,j δj + λ πi ln E≡− j=1 δj − 1 . (2) j=1 An implicit step in this EM procedure is to compute the the ownership probability r i,j of the j th kernel (or node) at the coarse scale for the ith node on the ﬁne scale and is given by ri,j = δj Ki,j . m k=1 δk Ki,k (3) The EM procedure allows for an update of both δ and the latent distributions in the kernel matrix K (see §8.3.1 in [6]). For initialization, δ is taken to be uniform over the coarse-scale states. But in choosing kernels K, we provide a good initialization for the EM procedure. Speciﬁcally, the Markov matrix M is diffused using a small number of iterations to get M β . The diffusion causes random walks from neighboring nodes to be less distinguishable. This in turn helps us select a small number of columns of M β in a fast and greedy way to be the kernel matrix K. We defer the exact details on kernel selection to a later section (§4.3). 4.2 Deriving the Coarse-Scale Transition Matrix In order to deﬁne M , the coarse-scale transition matrix, we break it down into three steps. First, the Markov chain propagation at the coarse scale can be deﬁned as: q k+1 = M q k , (4) where q is the coarse scale probability distribution after k steps of the random walk. Second, we expand q k into the ﬁne scale using the kernels K resulting in a ﬁne scale probability distribution p k : p k = Kq k . (5) k Finally, we lift p k back into the coarse scale by using the ownership probability of the j th kernel for the ith node on the ﬁne grid: n qjk+1 = ri,j pik i=1 (6) Substituting for Eqs.(3) and (5) in Eq. 6 gives n m qjk+1 = i=1 n Ki,t qtk = ri,j t=1 i=1 δj Ki,j m k=1 δk Ki,k m Ki,t qtk . (7) t=1 We can write the preceding equation in a matrix form: q k+1 = diag( δ ) K T diag K δ −1 Kq k . (8) Comparing this with Eq. 4, we can derive the transition matrix M as: M = diag( δ ) K T diag K δ −1 (9) K. It is easy to see that δ = M δ, so δ is the stationary distribution for M . Following the deﬁnition of M , and its stationary distribution δ, we can generate a symmetric coarse scale afﬁnity matrix A given by A = M diag(δ) = diag( δ ) K T diag K δ −1 Kdiag(δ) , (10) where we substitute for the expression M from Eq. 9. The coarse-scale afﬁnity matrix A is then normalized to get: L = D−1/2 AD−1/2 ; D = diag(d1 , d2 , · · · , dm ), (11) where dj is the degree of node j in the coarse-scale graph represented by the matrix A (see §3 for degree deﬁnition). Thus, the coarse scale Markov matrix M is precisely similar to a symmetric matrix L. 4.3 Selecting Kernels For demonstration purpose, we present the kernel selection details on the image of an eye shown below. To begin with, a random walk is deﬁned where each pixel in the test image is associated with a vertex of the graph G. The edges in G are deﬁned by the standard 8-neighbourhood of each pixel. For the demonstrations in this paper, the edge weight ai,j between neighbouring pixels xi and xj is given by a function of the difference in the 2 corresponding intensities I(xi ) and I(xj ): ai,j = exp(−(I(xi ) − I(xj ))2 /2σa ), where σa is set according to the median absolute difference |I(xi ) − I(xj )| between neighbours measured over the entire image. The afﬁnity matrix A with the edge weights is then used to generate a Markov transition matrix M . The kernel selection process we use is fast and greedy. First, the ﬁne scale Markov matrix M is diffused to M β using β = 4. The Markov matrix M is sparse as we make the afﬁnity matrix A sparse. Every column in the diffused matrix M β is a potential kernel. To facilitate the selection process, the second step is to rank order the columns of M β based on a probability value in the stationary distribution π. Third, the kernels (i.e. columns of M β ) are picked in such a way that for a kernel Ki all of the neighbours of pixel i which are within the half-height of the the maximum value in the kernel Ki are suppressed from the selection process. Finally, the kernel selection is continued until every pixel in the image is within a half-height of the peak value of at least one kernel. If M is a full matrix, to avoid the expense of computing M β explicitly, random kernel centers can be selected, and only the corresponding columns of M β need be computed. We show results from a three-scale hierarchy on the eye image (below). The image has 25 × 20 pixels but is shown here enlarged for clarity. At the ﬁrst coarse scale 83 kernels are picked. The kernels each correspond to a different column in the ﬁne scale transition matrix and the pixels giving rise to these kernels are shown numbered on the image. Using these kernels as an initialization, the EM procedure derives a coarse-scale stationary distribution δ 21 14 26 4 (Eq. 2), while simultaneously updating the kernel ma12 27 2 19 trix. Using the newly updated kernel matrix K and the 5 8 13 23 30 18 6 9 derived stationary distribution δ a transition matrix M 28 20 15 32 10 22 is generated (Eq. 9). The coarse scale Markov matrix 24 17 7 is then diffused to M β , again using β = 4. The kernel Coarse Scale 1 Coarse Scale 2 selection algorithm is reapplied, this time picking 32 kernels for the second coarse scale. Larger values of β cause the coarser level to have fewer elements. But the exact number of elements depends on the form of the kernels themselves. For the random experiments that we describe later in §6 we found β = 2 in the ﬁrst iteration and 4 thereafter causes the number of kernels to be reduced by a factor of roughly 1/3 to 1/4 at each level. 72 28 35 44 51 64 82 4 12 31 56 19 77 36 45 52 65 13 57 23 37 5 40 53 63 73 14 29 6 66 38 74 47 24 7 30 41 54 71 78 58 15 8 20 39 48 59 67 25 68 79 21 16 2 11 26 42 49 55 60 75 32 83 43 9 76 50 17 27 61 33 69 80 3 46 18 70 81 34 10 62 22 1 25 11 1 3 16 31 29 At coarser levels of the hierarchy, we expect the kernels to get less sparse and so will the afﬁnity and the transition matrices. In order to promote sparsity at successive levels of the hierarchy we sparsify A by zeroing out elements associated with “small” transition probabilities in M . However, in the experiments described later in §6, we observe this sparsiﬁcation step to be not critical. To summarize, we use the stationary distribution π at the ﬁne-scale to derive a transition matrix M , and its stationary distribution δ, at the coarse-scale. The coarse scale transition in turn helps to derive an afﬁnity matrix A and its normalized version L. It is obvious that this procedure can be repeated recursively. We describe next how to use this representation hierarchy for building a fast eigensolver. 5 Fast EigenSolver Our goal in generating a hierarchical representation of a transition matrix is to develop a fast, specialized eigen solver for spectral clustering. To this end, we perform a full eigen decomposition of the normalized afﬁnity matrix only at the coarsest level. As discussed in the previous section, the afﬁnity matrix at the coarsest level is not likely to be sparse, hence it will need a full (as opposed to a sparse) version of an eigen solver. However it is typically the case that e ≤ m n (even in the case of the three-scale hierarchy that we just considered) and hence we expect this step to be the least expensive computationally. The resulting eigenvectors are interpolated to the next lower level of the hierarchy by a process which will be described next. Because the eigen interpolation process between every adjacent pair of scales in the hierarchy is similar, we will assume we have access to the leading eigenvectors U (size: m × e) for the normalized afﬁnity matrix L (size: m × m) and describe how to generate the leading eigenvectors U (size: n × e), and the leading eigenvalues S (size: e × 1), for the ﬁne-scale normalized afﬁnity matrix L (size: n × n). There are several steps to the eigen interpolation process and in the discussion that follows we refer to the lines in the pseudo-code presented below. First, the coarse-scale eigenvectors U can be interpolated using the kernel matrix K to generate U = K U , an approximation for the ﬁne-scale eigenvectors (line 9). Second, interpolation alone is unlikely to set the directions of U exactly aligned with U L , the vectors one would obtain by a direct eigen decomposition of the ﬁne-scale normalized afﬁnity matrix L. We therefore update the directions in U by applying a small number of power iterations with L, as given in lines 13-15. e e function (U, S) = CoarseToFine(L, K, U , S) 1: INPUT 2: L, K ⇐ {L is n × n and K is n × m where m n} e e e e 3: U /S ⇐ {leading coarse-scale eigenvectors/eigenvalues of L. U is of size m × e, e ≤ m} 4: OUTPUT 5: U, S ⇐ {leading ﬁne-scale eigenvectors/eigenvalues of L. U is n × e and S is e × 1.} x 10 0.4 3 0.96 0.94 0.92 0.9 0.35 2.5 Relative Error Absolute Relative Error 0.98 Eigen Value |δλ|λ−1 −3 Eigen Spectrum 1 2 1.5 1 5 10 15 20 Eigen Index (a) 25 30 0.2 0.15 0.1 0.5 0.88 0.3 0.25 0.05 5 10 15 20 Eigen Index (b) 25 30 5 10 15 20 Eigen Index 25 30 (c) Figure 1: Hierarchical eigensolver results. (a) comparing ground truth eigenvalues S L (red circles) with multi-scale eigensolver spectrum S (blue line) (b) Relative absolute error between eigenvalues: |S−SL | (c) Eigenvector mismatch: 1 − diag |U T UL | , between SL eigenvectors U derived by the multi-scale eigensolver and the ground truth U L . Observe the slight mismatch in the last few eigenvectors, but excellent agreement in the leading eigenvectors (see text). 6: CONSTANTS: TOL = 1e-4; POWER ITERS = 50 7: “ ” e 8: TPI = min POWER ITERS, log(e × eps/TOL)/ log(min(S)) {eps: machine accuracy} e 9: U = K U {interpolation from coarse to ﬁne} 10: while not converged do 11: Uold = U {n × e matrix, e n} 12: for i = 1 to TPI do 13: U ⇐ LU 14: end for 15: U ⇐ Gram-Schmidt(U ) {orthogonalize U } 16: Le = U T LU {L may be sparse, but Le need not be.} 17: Ue Se UeT = svd(Le ) {eigenanalysis of Le , which is of size e × e.} 18: U ⇐ U Ue {update the leading eigenvectors of L} 19: S = diag(Se ) {grab the leading eigenvalues of L} T 20: innerProd = 1 − diag( Uold U ) {1 is a e × 1 vector of all ones} 21: converged = max[abs(innerProd)] < TOL 22: end while The number of power iterations TPI can be bounded as discussed next. Suppose v = U c where U is a matrix of true eigenvectors and c is a coefﬁcient vector for an arbitrary vector v. After TPI power iterations v becomes v = U diag(S TPI )c, where S has the exact eigenvalues. In order for the component of a vector v in the direction Ue (the eth column of U ) not to be swamped by other components, we can limit it’s decay after TPI iterations as TPI follows: (S(e)/S(1)) >= e×eps/TOL, where S(e) is the exact eth eigenvalue, S(1) = 1, eps is the machine precision, TOL is requested accuracy. Because we do not have access to the exact value S(e) at the beginning of the interpolation procedure, we estimate it from the coarse eigenvalues S. This leads to a bound on the power iterations TPI, as derived on the line 9 above. Third, the interpolation process and the power iterations need not preserve orthogonality in the eigenvectors in U . We ﬁx this by Gram-Schmidt orthogonalization procedure (line 16). Finally, there is a still a problem with power iterations that needs to be resolved, in that it is very hard to separate nearby eigenvalues. In particular, for the convergence of the power iterations the ratio that matters is between the (e + 1) st and eth eigenvalues. So the idea we pursue is to use the power iterations only to separate the reduced space of eigenvectors (of dimension e) from the orthogonal subspace (of dimension n − e). We then use a full SVD on the reduced space to update the leading eigenvectors U , and eigenvalues S, for the ﬁne-scale (lines 17-20). This idea is similar to computing the Ritz values and Ritz vectors in a Rayleigh-Ritz method. 6 Interpolation Results Our multi-scale decomposition code is in Matlab. For the direct eigen decomposition, we have used the Matlab program svds.m which invokes the compiled ARPACKC routine [13], with a default convergence tolerance of 1e-10. In Fig. 1a we compare the spectrum S obtained from a three-scale decomposition on the eye image (blue line) with the ground truth, which is the spectrum SL resulting from direct eigen decomposition of the ﬁne-scale normalized afﬁnity matrices L (red circles). There is an excellent agreement in the leading eigenvalues. To illustrate this, we show absolute relative error between the spectra: |S−SL | in Fig. 1b. The spectra agree mostly, except for SL the last few eigenvalues. For a quantitative comparison between the eigenvectors, we plot in Fig. 1c the following measure: 1 − diag(|U T UL |), where U is the matrix of eigenvectors obtained by the multi-scale approximation, UL is the ground-truth resulting from a direct eigen decomposition of the ﬁne-scale afﬁnity matrix L and 1 is a vector of all ones. The relative error plot demonstrates a close match, within the tolerance threshold of 1e-4 that we chose for the multi-scale method, in the leading eigenvector directions between the two methods. The relative error is high with the last few eigen vectors, which suggests that the power iterations have not clearly separated them from other directions. So, the strategy we suggest is to pad the required number of leading eigen basis by about 20% before invoking the multi-scale procedure. Obviously, the number of hierarchical stages for the multi-scale procedure must be chosen such that the transition matrix at the coarsest scale can accommodate the slight increase in the subspace dimensions. For lack of space we are omitting extra results (see Ch.8 in [6]). Next we measure the time the hierarchical eigensolver takes to compute the leading eigenbasis for various input sizes, in comparison with the svds.m procedure [13]. We form images of different input sizes by Gaussian smoothing of i.i.d noise. The Gaussian function has a standard deviation of 3 pixels. The edges in graph G are deﬁned by the standard 8-neighbourhood of each pixel. The edge weights between neighbouring pixels are simply given by a function of the difference in the corresponding intensities (see §4.3). The afﬁnity matrix A with the edge weights is then used to generate a Markov transition matrix M . The fast eigensolver is run on ten different instances of the input image of a given size and the average of these times is reported here. For a fair comparison between the two procedures, we set the convergence tolerance value for the svds.m procedure to be 1e-4, the same as the one used for the fast eigensolver. We found the hierarchical representation derived from this tolerance threshold to be sufﬁciently accurate for a novel min-cut based segmentation results that we reported in [8]. Also, the subspace dimensionality is ﬁxed to be 51 where we expect (and indeed observe) the leading 40 eigenpairs derived from the multi-scale procedure to be accurate. Hence, while invoking svds.m we compute only the leading 41 eigenpairs. In the table shown below, the ﬁrst column corresponds to the number of nodes in the graph, while the second and third columns report the time taken in seconds by the svds.m procedure and the Matlab implementation of the multi-scale eigensolver respectively. The fourth column reports the speedups of the multi-scale eigensolver over svds.m procedure on a standard desktop (Intel P4, 2.5GHz, 1GB RAM). Lowering the tolerance threshold for svds.m made it faster by about 20 − 30%. Despite this, the multi-scale algorithm clearly outperforms the svds.m procedure. The most expensive step in the multi-scale algorithm is the power iteration required in the last stage, that is interpolating eigenvectors from the ﬁrst coarse scale to the required ﬁne scale. The complexity is of the order of n × e where e is the subspace dimensionality and n is the size of the graph. Indeed, from the table we can see that the multi-scale procedure is taking time roughly proportional to n. Deviations from the linear trend are observed at speciﬁc values of n, which we believe are due to the n 322 632 642 652 1002 1272 1282 1292 1602 2552 2562 2572 5112 5122 5132 6002 7002 8002 svds.m 1.6 10.8 20.5 12.6 44.2 91.1 230.9 96.9 179.3 819.2 2170.8 871.7 7977.2 20269 7887.2 10841.4 15048.8 Multi-Scale 1.5 4.9 5.5 5.1 13.1 20.4 35.2 20.9 34.4 90.3 188.7 93.3 458.8 739.3 461.9 644.2 1162.4 1936.6 Speedup 1.1 2.2 3.7 2.5 3.4 4.5 6.6 4.6 5.2 9.1 11.5 9.3 17.4 27.4 17.1 16.8 12.9 variations in the difﬁculty of the speciﬁc eigenvalue problem (eg. nearly multiple eigenvalues). The hierarchical representation has proven to be effective in a min-cut based segmentation algorithm that we proposed recently [8]. Here we explored the use of random walks and associated spectral embedding techniques for the automatic generation of suitable proposal (source and sink) regions for a min-cut based algorithm. The multiscale algorithm was used to generate the 40 leading eigenvectors of large transition matrices (eg. size 20K × 20K). In terms of future work, it will be useful to compare our work with other approximate methods for SVD such as [23]. Ack: We thank S. Roweis, F. Estrada and M. Sakr for valuable comments. References [1] D. Achlioptas and F. McSherry. Fast Computation of Low-Rank Approximations. STOC, 2001. [2] D. Achlioptas et al Sampling Techniques for Kernel Methods. NIPS, 2001. [3] S. Barnard and H. Simon Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems. PPSC, 627-632. [4] M. Belkin et al Laplacian Eigenmaps and Spectral Techniques for Embedding. NIPS, 2001. [5] M. Brand et al A unifying theorem for spectral embedding and clustering. AI & STATS, 2002. [6] C. Chennubhotla. Spectral Methods for Multi-scale Feature Extraction and Spectral Clustering. http://www.cs.toronto.edu/˜chakra/thesis.pdf Ph.D Thesis, Department of Computer Science, University of Toronto, Canada, 2004. [7] C. Chennubhotla and A. Jepson. Half-Lives of EigenFlows for Spectral Clustering. NIPS, 2002. [8] F. Estrada, A. Jepson and C. Chennubhotla. Spectral Embedding and Min-Cut for Image Segmentation. Manuscript Under Review, 2004. [9] C. Fowlkes et al Efﬁcient spatiotemporal grouping using the Nystrom method. CVPR, 2001. [10] S. Belongie et al Spectral Partitioning with Indeﬁnite Kernels using Nystrom app. ECCV, 2002. [11] A. Frieze et al Fast Monte-Carlo Algorithms for ﬁnding low-rank approximations. FOCS, 1998. [12] Y. Koren et al ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs IEEE Symp. on InfoVis 2002, pp. 137-144 [13] R. B. Lehoucq, D. C. Sorensen and C. Yang. ARPACK User Guide: Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods. SIAM 1998. [14] J. J. Lin. Reduced Rank Approximations of Transition Matrices. AI & STATS, 2002. [15] L. Lova’sz. Random Walks on Graphs: A Survey Combinatorics, 1996, 353–398. [16] G. J. McLachlan et al Mixture Models: Inference and Applications to Clustering. 1988 [17] M. Meila and J. Shi. A random walks view of spectral segmentation. AI & STATS, 2001. [18] A. Ng, M. Jordan and Y. Weiss. On Spectral Clustering: analysis and an algorithm NIPS, 2001. [19] A. Pothen Graph partitioning algorithms with applications to scientiﬁc computing. Parallel Numerical Algorithms, D. E. Keyes et al (eds.), Kluwer Academic Press, 1996. [20] G. L. Scott et al Feature grouping by relocalization of eigenvectors of the proximity matrix. BMVC, pg. 103-108, 1990. [21] E. Sharon et al Fast Multiscale Image Segmentation CVPR, I:70-77, 2000. [22] J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, August, 2000. [23] H. Simon et al Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications SIAM J. of Sci. Comp. 21(6):2257-2274, 2000. [24] N. Tishby et al Data clustering by Markovian Relaxation NIPS, 2001. [25] C. Williams et al Using the Nystrom method to speed up the kernel machines. NIPS, 2001.

5 0.1720594 161 nips-2004-Self-Tuning Spectral Clustering

Author: Lihi Zelnik-manor, Pietro Perona

Abstract: We study a number of open issues in spectral clustering: (i) Selecting the appropriate scale of analysis, (ii) Handling multi-scale data, (iii) Clustering with irregular background clutter, and, (iv) Finding automatically the number of groups. We ﬁrst propose that a ‘local’ scale should be used to compute the afﬁnity between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the ﬁnal randomly initialized k-means stage is eliminated. 1

6 0.14463474 120 nips-2004-Modeling Conversational Dynamics as a Mixed-Memory Markov Process

7 0.13653372 97 nips-2004-Learning Efficient Auditory Codes Using Spikes Predicts Cochlear Filters

8 0.1216099 13 nips-2004-A Three Tiered Approach for Articulated Object Action Modeling and Recognition

9 0.11298747 132 nips-2004-Nonlinear Blind Source Separation by Integrating Independent Component Analysis and Slow Feature Analysis

10 0.09804941 103 nips-2004-Limits of Spectral Clustering

11 0.084798187 115 nips-2004-Maximum Margin Clustering

12 0.082045481 198 nips-2004-Unsupervised Variational Bayesian Learning of Nonlinear Models

13 0.080160387 75 nips-2004-Heuristics for Ordering Cue Search in Decision Making

14 0.078323834 174 nips-2004-Spike Sorting: Bayesian Clustering of Non-Stationary Data

15 0.0768352 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

16 0.075416707 20 nips-2004-An Auditory Paradigm for Brain-Computer Interfaces

17 0.071544975 200 nips-2004-Using Random Forests in the Structured Language Model

18 0.070910811 124 nips-2004-Multiple Alignment of Continuous Time Series

19 0.070693038 61 nips-2004-Efficient Out-of-Sample Extension of Dominant-Set Clusters

20 0.06998767 27 nips-2004-Bayesian Regularization and Nonnegative Deconvolution for Time Delay Estimation

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.222), (1, 0.01), (2, -0.077), (3, -0.262), (4, -0.34), (5, -0.323), (6, 0.218), (7, 0.142), (8, -0.06), (9, 0.024), (10, -0.096), (11, 0.005), (12, -0.109), (13, 0.175), (14, -0.174), (15, -0.006), (16, -0.027), (17, -0.006), (18, -0.069), (19, 0.086), (20, 0.015), (21, 0.146), (22, 0.104), (23, -0.069), (24, 0.117), (25, -0.022), (26, 0.094), (27, -0.039), (28, -0.015), (29, -0.009), (30, 0.006), (31, -0.054), (32, -0.008), (33, -0.011), (34, -0.014), (35, -0.014), (36, 0.05), (37, -0.019), (38, -0.031), (39, -0.054), (40, -0.056), (41, -0.028), (42, 0.073), (43, -0.021), (44, -0.05), (45, 0.004), (46, -0.006), (47, -0.13), (48, -0.0), (49, -0.0)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97350621 31 nips-2004-Blind One-microphone Speech Separation: A Spectral Learning Approach

Author: Francis R. Bach, Michael I. Jordan

2 0.87378973 152 nips-2004-Real-Time Pitch Determination of One or More Voices by Nonnegative Matrix Factorization

Author: Fei Sha, Lawrence K. Saul

3 0.78660679 5 nips-2004-A Harmonic Excitation State-Space Approach to Blind Separation of Speech

Author: Rasmus K. Olsson, Lars K. Hansen

4 0.68070161 120 nips-2004-Modeling Conversational Dynamics as a Mixed-Memory Markov Process

Author: Tanzeem Choudhury, Sumit Basu

Abstract: In this work, we quantitatively investigate the ways in which a given person influences the joint turn-taking behavior in a conversation. After collecting an auditory database of social interactions among a group of twenty-three people via wearable sensors (66 hours of data each over two weeks), we apply speech and conversation detection methods to the auditory streams. These methods automatically locate the conversations, determine their participants, and mark which participant was speaking when. We then model the joint turn-taking behavior as a Mixed-Memory Markov Model [1] that combines the statistics of the individual subjects' self-transitions and the partners ' cross-transitions. The mixture parameters in this model describe how much each person 's individual behavior contributes to the joint turn-taking behavior of the pair. By estimating these parameters, we thus estimate how much influence each participant has in determining the joint turntaking behavior. We show how this measure correlates significantly with betweenness centrality [2], an independent measure of an individual's importance in a social network. This result suggests that our estimate of conversational influence is predictive of social influence. 1

5 0.41244105 79 nips-2004-Hierarchical Eigensolver for Transition Matrices in Spectral Methods

Author: Chakra Chennubhotla, Allan D. Jepson

6 0.3919614 161 nips-2004-Self-Tuning Spectral Clustering

7 0.38688102 27 nips-2004-Bayesian Regularization and Nonnegative Deconvolution for Time Delay Estimation

8 0.37528297 97 nips-2004-Learning Efficient Auditory Codes Using Spikes Predicts Cochlear Filters

9 0.35375425 103 nips-2004-Limits of Spectral Clustering

10 0.34467027 132 nips-2004-Nonlinear Blind Source Separation by Integrating Independent Component Analysis and Slow Feature Analysis

11 0.31770772 13 nips-2004-A Three Tiered Approach for Articulated Object Action Modeling and Recognition

12 0.30637458 75 nips-2004-Heuristics for Ordering Cue Search in Decision Making

13 0.26841184 61 nips-2004-Efficient Out-of-Sample Extension of Dominant-Set Clusters

14 0.25866359 199 nips-2004-Using Machine Learning to Break Visual Human Interaction Proofs (HIPs)

15 0.25657412 150 nips-2004-Proximity Graphs for Clustering and Manifold Learning

16 0.24589548 20 nips-2004-An Auditory Paradigm for Brain-Computer Interfaces

17 0.23819254 115 nips-2004-Maximum Margin Clustering

18 0.23646684 104 nips-2004-Linear Multilayer Independent Component Analysis for Large Natural Scenes

19 0.23036216 124 nips-2004-Multiple Alignment of Continuous Time Series

20 0.22559458 174 nips-2004-Spike Sorting: Bayesian Clustering of Non-Stationary Data

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.097), (15, 0.171), (26, 0.05), (31, 0.019), (33, 0.235), (35, 0.033), (39, 0.049), (50, 0.03), (65, 0.139), (76, 0.025), (82, 0.012), (94, 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97415918 202 nips-2004-VDCBPI: an Approximate Scalable Algorithm for Large POMDPs

Author: Pascal Poupart, Craig Boutilier

Abstract: Existing algorithms for discrete partially observable Markov decision processes can at best solve problems of a few thousand states due to two important sources of intractability: the curse of dimensionality and the policy space complexity. This paper describes a new algorithm (VDCBPI) that mitigates both sources of intractability by combining the Value Directed Compression (VDC) technique [13] with Bounded Policy Iteration (BPI) [14]. The scalability of VDCBPI is demonstrated on synthetic network management problems with up to 33 million states.

same-paper 2 0.9406451 31 nips-2004-Blind One-microphone Speech Separation: A Spectral Learning Approach

Author: Francis R. Bach, Michael I. Jordan

3 0.89793122 60 nips-2004-Efficient Kernel Machines Using the Improved Fast Gauss Transform

Author: Changjiang Yang, Ramani Duraiswami, Larry S. Davis

Abstract: The computation and memory required for kernel machines with N training samples is at least O(N 2 ). Such a complexity is signiﬁcant even for moderate size problems and is prohibitive for large datasets. We present an approximation technique based on the improved fast Gauss transform to reduce the computation to O(N ). We also give an error bound for the approximation, and provide experimental results on the UCI datasets. 1

4 0.89705724 178 nips-2004-Support Vector Classification with Input Data Uncertainty

Author: Jinbo Bi, Tong Zhang

Abstract: This paper investigates a new learning model in which the input data is corrupted with noise. We present a general statistical framework to tackle this problem. Based on the statistical reasoning, we propose a novel formulation of support vector classiﬁcation, which allows uncertainty in input data. We derive an intuitive geometric interpretation of the proposed formulation, and develop algorithms to efﬁciently solve it. Empirical results are included to show that the newly formed method is superior to the standard SVM for problems with noisy input. 1

5 0.89657599 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

Author: Xiaojin Zhu, Jaz Kandola, Zoubin Ghahramani, John D. Lafferty

Abstract: We present an algorithm based on convex optimization for constructing kernels for semi-supervised learning. The kernel matrices are derived from the spectral decomposition of graph Laplacians, and combine labeled and unlabeled data in a systematic fashion. Unlike previous work using diffusion kernels and Gaussian random ﬁeld kernels, a nonparametric kernel approach is presented that incorporates order constraints during optimization. This results in ﬂexible kernels and avoids the need to choose among different parametric forms. Our approach relies on a quadratically constrained quadratic program (QCQP), and is computationally feasible for large datasets. We evaluate the kernels on real datasets using support vector machines, with encouraging results. 1

6 0.89506012 19 nips-2004-An Application of Boosting to Graph Classification

7 0.89432478 2 nips-2004-A Direct Formulation for Sparse PCA Using Semidefinite Programming

8 0.89300466 16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

9 0.89184803 145 nips-2004-Parametric Embedding for Class Visualization

10 0.89181483 125 nips-2004-Multiple Relational Embedding

11 0.89142299 131 nips-2004-Non-Local Manifold Tangent Learning

12 0.8911804 127 nips-2004-Neighbourhood Components Analysis

13 0.89078248 187 nips-2004-The Entire Regularization Path for the Support Vector Machine

14 0.89065802 161 nips-2004-Self-Tuning Spectral Clustering

15 0.89032429 142 nips-2004-Outlier Detection with One-class Kernel Fisher Discriminants

16 0.89005727 167 nips-2004-Semi-supervised Learning with Penalized Probabilistic Clustering

17 0.88980466 44 nips-2004-Conditional Random Fields for Object Recognition

18 0.88930917 174 nips-2004-Spike Sorting: Bayesian Clustering of Non-Stationary Data

19 0.88916552 163 nips-2004-Semi-parametric Exponential Family PCA

20 0.88761282 102 nips-2004-Learning first-order Markov models for control