1 Expectation-Maximization (EM) Framework For
Expectation-Maximization (EM) Framework forMultiple Speaker Localization and TrackingSharon GannotJoint work with Ofer Schwartz, Yuval Dorfan & Gershon HazanFaculty of Engineering, Bar-Ilan University, IsraelThe 3rd Annual Underwater Acoustics SymposiumTel-Aviv University, June 19th, 2014S. GannotEM Localization & Tracking1 / 17
IntroductionPrefaceMultiple Speaker Localization using a Network of Microphone Pairs12Tracking algorithm for moving sources (centralized processing).Localization algorithm for static sources (distributed processing):Constrained communication bandwidth.Limited Computation capabilities at the nodes.OutlineProblem formulation &Maximum Likelihood (ML).Expectation-Maximization (EM).Recursive EM (REM).Distributed EM (DEM).Simulation results.S. GannotEM Localization & Tracking2 / 17
Problem FormulationStatistical ModelReceived Data @microphone pair m1zm(t, k)1zmSTFT12j[ (zm) (zm)]φm(t, k)e2(t, k)zm2zmSTFTz1m & z2m - Signals @microphone 1 & 2 of node m.Pzim (t, k) Ss 1 aism (t, k) · bs (t, k) nim (t, k).Pair-wise relative complex phase ratio (PRP): φm (t, k) ,S. GannotEM Localization & Trackingz1m (t,k)z2m (t,k)· z2m (t,k) . z1m (t,k) 3 / 17
Problem FormulationStatistical ModelProbabilistic Model @node mAssumptionsDefine a grid of positions in the region of interest: p P.TDOA from any grid point to the microphone pair:21 mτm (p) , p pm p p.cEach T-F bin is solely dominated by one speaker (W-disjoint).Phase @node m as Mixture of Gaussian (MoG)f (φm ) YXt,kτmψτm · N c (φm (t, k); φ̃km (τm ), σ 2 )φ̃km (p) - Mean of phase differences pre-calculated for all grid positions p.σ 2 - Known and constant variance of the Gaussians.ψτm - Probability that φm , vect,k ({φm (t, k)}) originates from TDOA τm .S. GannotEM Localization & Tracking4 / 17
Problem FormulationStatistical ModelProbabilistic Model from Array PerspectiveDefinitions & Relationsφ vecm (φm ).Multiple source positions give rise to the same TDOA.ψp - Probability that φ originates from position p.ZXψp0ψp0 p0 ψτm p0 τmp0 τmAugmented Phase as Mixture of Gaussian (MoG)f (φ) YXt,k,m pψp · N c (φm (t, k); φ̃km (τm (p)), σ 2 )S. GannotEM Localization & Tracking5 / 17
Problem FormulationMaximum likelihood (ML)Maximum LikelihoodStraightforward MLLet ψ vecp ({ψp }):YXf (φ) ψp · N c (φm (t, k); φ̃km (p), σ 2 )t,k,m pψ̂ argmax log f (φ; ψ)ψGoalEstimate the most probable grid points that “explains” the received phases.S. GannotEM Localization & Tracking6 / 17
Expectation-Maximization (EM)BatchIterative Solution using EM [Dempster et al., 1977]Estimate-Maximize ProcedureSolving the ML is a cumbersome task.Selecting a hidden data x that can simplify the solution.noE-step: Q(ψ ψ̂ ( 1) ) , E log (f (φ, x; ψ)) φ; ψ̂ ( 1) .M-step: ψ̂ ( ) argmaxψ Q(ψ ψ̂ ( 1) ).Hidden Data [Mandel et al., 2007, Schwartz and Gannot, 2014]x(t, k, p) It,k (p) (Speech sparsity assumption)It,k (p) - Indicator that bin (t, k) belongs to a (single) speaker@position p.S. GannotEM Localization & Tracking7 / 17
Expectation-Maximization (EM)BatchBatch EME-stepnoµ( 1) (t, k, p) ,E x(t, k, p) φ(t, k); ψ̂ ( 1) ( 1) Qc φ (t, k); φ̃k (p), σ 2ψ̂pNmmm P( 1) Qc φ (t, k); φ̃k (p), σ 2mmp ψ̂pmNM-step( )ψ̂pP t,kµ( 1) (t, k, p)T ·KT : # of frames and K : # of frequencies.S. GannotEM Localization & Tracking8 / 17
Expectation-Maximization (EM)Recursive Expectation-Maximization (REM)Recuesive EM [Schwartz and Gannot, 2014]ProceduresReplace iteration index with time index.Execute one iteration per time index.Recursively estimate Q [Cappé and Moulines, 2009]:(t 1)(t)QR (ψ ψR ) QR (ψ ψR(t 1)ψRih(t 1)(t)) γt Q(ψ ψR ) QR (ψ ψR ) .(t) argmaxψ QR (ψ ψR ).Maximize using Newton’s method [Titterington, 1984] (with constraints[Schwartz and Gannot, 2014]).Solution (for both recursive procedures!))(t 1)ψR(t)(t) ψR γt (ψ (t 1) ψR )S. GannotEM Localization & Tracking9 / 17
Expectation-Maximization (EM)Distributed Expectation-Maximization (DEM)Distributed EM [Dorfan et al., 2014]Centralized ComputationEstimating the global hidden data depends on the availability of all PRPsin one point.Requires: powerful fusion center, communication bandwidth, .Local Hidden Data Global Hidden Datay(t, k, τm (p)) ,It,k,m (τm (p))Yx(t, k, p) y(t, k, τm (p))mMultiple positions p can induce the same τm .S. GannotEM Localization & Tracking10 / 17
Expectation-Maximization (EM)Distributed Expectation-Maximization (DEM)Incremental EM [Neal and Hinton, 1998] - Ring Topologyψp(i)E-step: Global Hidden(i)μ (t, k, p)Node m-1μNode m(i 1)(t, k, p)Node m 1µ(i)n(t, k, p) ,o(i 1).E x(t, k, p) φ(t, k); ψpi ( 1)M m;m 0, . . . , M 1.Becomes sparse after fewiterations.M-Step: GlobalParameter EstimationNode 0Node M-1S. Gannot(i)ψpEM Localization & TrackingP t,kµ(i) (t, k, p)T ·K11 / 17
Expectation-Maximization (EM)Distributed Expectation-Maximization (DEM)Increment @Node mφm (t, k)(i M )υm1(t,k,τm (p))(i)υm(t, k, τm(p))μ(i)(t, k, p)M-Step ψp(i)E-Step(partial)μ(i 1)(t, k, p)XM-Step: Global Parameter Estimation (Reminder)(i)ψτm (p)Z,(i)p0 τm (p)S. Gannotψp0 dp0EM Localization & Tracking12 / 17
Expectation-Maximization (EM)Distributed Expectation-Maximization (DEM)Increment @Node mφm (t, k)1(t,k,τm (p))(i)υm(t, k, τm(p))μ(i)(t, k, p)M-Step ψp(i)(i M )υmE-Step(partial)μ(i 1)(t, k, p)XE-step: Local Hiddenon(i)υm(i) (t, k, τm (p)) ,E y(t, k, τm (p)) φm (t, k); ψp (i)ψτm (p) N c φm (t, k); φ̃km (τm (p)), σ 2 P(i)ck2φm (t, k); φ̃m (τm (p)), στm (p) ψτm (p) NS. GannotEM Localization & Tracking12 / 17
Simulation resultsSimulation SetupDistributed Localization2D setup: 10 10 cm grid.Randomly located sources.12 nodes.TrackingInter-microphone pair: 50 cm.2D setup: 10 10 cm grid.Trajectory: line, arc.12 nodes.Inter-microphone pair: 20 cm.T60 0.3 Sec.Performance criteria:Detection rate.False Alarm (FA) rate.Mean Square Error (MSE).T60 0.7 Sec.Performance criterion: curve fit.S. GannotEM Localization & Tracking13 / 17
Simulation resultsDEMSimulation Results: Distributed EM608000605570005550 2000506000454550004040003530300025200020y axis (decimeter)y axis (decimeter) 100035 40003025 500020100015 30004015010 600010 100051020304050605 200010(a) Delay & Sum BF# Sources122030405060 7000(b) Distributed EMDetection[%]10098FA[%]226.5MSE[cm]3.97.1Table : Results for 100 Monte-Carlo simulationsS. GannotEM Localization & Tracking14 / 17
Simulation resultsREM60605050504040403020100y axis (decimeter)60y axis (decimeter)y axis (decimeter)Simulation Results: Recursive EM302010010203040x axis (decimeter)5006020100(c) γ 0.110203040x axis (decimeter)500 1060505050404040302010y axis (decimeter)60302010010203040x axis (decimeter)(f) γ 0.11050600203040x axis (decimeter)5060(e) γ 16000(d) γ 0.560y axis (decimeter)y axis (decimeter)30302010010203040x axis (decimeter)50600 10(g) γ 0.5S. GannotEM Localization & Tracking010203040x axis (decimeter)5060(h) γ 115 / 17
SummarySummaryRecursive EM Algorithm for Tracking1Speech sparsity utilized to derive EM-based Localization.2Two versions of tracking algorithms were proposed based on[Cappé and Moulines, 2009],[Titterington, 1984].3A Constrained version of [Titterington, 1984] was derived.Distributed EM Algorithm for Localization1No central processing unit required.2Decomposing the global hidden data to local hidden data is the key stepin distributed algorithm derivation.3Detection and localization of multiple concurrent sources with minimala priori information.4Only two global iterations required in our simulations.5No significant dependency on initial conditions observed.S. GannotEM Localization & Tracking16 / 17
BibliographyReferences ICappé, O. and Moulines, E. (2009).On-line expectationmaximization algorithm for latent data models.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 71(3):593–613.Dempster, A., Laird, N., and Rubin, D. (1977).Maximum likelihood from incomplete data via the EM algorithm.Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1–38.Dorfan, Y., Hazan, G., and Gannot, S. (2014).Multiple acoustic sources localization using distributed Expectation-Maximization algorithm.In The 4th Joint Workshop on Hands-free Speech Communication and Microphone Arrays (HSCMA), Nancy, France.best student paper award.Mandel, M., Ellis, D., and Jebara, T. (2007).An EM algorithm for localizing multiple sound sources in reverberant environments.Advances in Neural Information Processing Systems, 19:953.Neal, R. and Hinton, G. (1998).A view of the EM algorithm that justifies incremental, sparse, and other variants.Learning in graphical models, 89:355–368.Schwartz, O. and Gannot, S. (2014).Speaker tracking using recursive EM algorithms.IEEE/ACM Transactions on Audio, Speech, and Language Processing, 22(2):392–402.Titterington, D. (1984).Recursive parameter estimation using incomplete data.J. Roy. Statist. Soc. Ser. B, 46:257–267.S. GannotEM Localization & Tracking17 / 17
Maximum Likelihood (ML). Expectation-Maximization (EM). Recursive EM (REM). Distributed EM (DEM). Simulation results. S. Gannot EM Localization & Tracking 2 / 17. Problem Formulation Statistical Model Received Data @microphone pair m STFT . (ML) Maximu
Expectation Maximization We first focus on the analysis of the convergenceproperties of the Expectation-Maximization (EM) algorithm. Con-sider a probabilistic model of observed data x which uses latent variables z. The log-likelihood (objective function
Machine Learning for Computer Vision Expectation-Maximization EM is an elegant and powerful method for MLE problems with latent variables Main idea: model parameters and latent variables are estimated iteratively, where average over the latent variables (expectation) A typical exam
Mathematical Expectation Properties of Mathematical Expectation I The concept of mathematical expectation arose in connection with games of chance. In its simplest form, mathematical expectation is the product of the amount a player stands to win and the probability that the player would win.
Maximum Likelihood (ML), Expectation Maximization (EM) Pieter Abbeel UC Berkeley EECS Many slides adapted from Thrun, Burgard and Fox, Probabilistic Robotics TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAAAAAAAAAAA!File Size: 2MB
Expectation-Maximization Algorithm and Applications Eugene Weinstein Courant Institute of Mathematical Sciences . Can prove is the maximum-likelihood estimate of θ Differentiate with respect to θ, set equal to 0. 5/31 EM Motivation So, to solve any ML-type p
The expectation maximization (EM) algorithm computes maximum likelihood (ML) estimates of unknown parameters in probabilistic models involving latent avriables Z1. An instructive way of thinking about EM is to think of it as a systematic way o
Maximum Lq-Likelihood Estimation via the Expectation-Maximization Algorithm: A Robust Estimation of Mixture Models Yichen QIN and Carey E. PRIEBE We introduce a maximum Lq-likelihood estimation (MLqE) of mixture models using our proposed expectation-maximization (EM) al- gorithm, namely the EM algorithm with Lq-likelihood (EM-Lq).
main idea of the rough paths theory is to introduce a much stronger topology than the convergence in p-variation. This topology, that we now explain, is related to the continuity of lifts of paths in free nilpotent Lie groups. Let G N(Rd) be the free N-step nilpotent Lie group with dgenerators X 1; ;X d. If x: [0;1] !Rd is continuous with bounded variation, the solution x of the equation x(t .
