组合霍奇理论与信息处理（PPT讲稿）Combinatorial Hodge Theory and Information Processing

Combinatorial Hodge Theory and Information Processing l898 姚远 2010.3.25

Combinatorial Hodge Theory and Information Processing 姚 远 2010.3.25

Hodge decomposition a Vector calculus: Helmholtz's decomposition ie. vector fields on nice domains may be resolved into irrotational (curl-free and solenoidal(divergence-free) component vector fields F=-Vy+V×A yp scalar potential, A vector potential a Linear algebra: additive orthogonal decomposition of a skew-symmetric matrix into three skew-symmetric matrices W=W1+W2+W3 W,=ve/-ev, W2 clique-consistent, W3 inconsistent Graph theory: orthogonal decomposition of network flows into acyclic and cyclic components

Hodge Decomposition

Visual Image patches Ann Lee, Kim Pedersen, David Mumford(2003)studies statistical properties of 3x3 high contrast image patches of natural images(from Van Heteran's database) Gunnar Carlsson, Vin de Silva, Tigran Ishkhanov, Afra Zomorodian(2004-present) found those image patches concentrate around a 2-dimensional klein bottle imbedded in 7-sphere They build up simplicial complex from point cloud data 1-D Harmonic flows actually focus on densest region 3 major circles

Visual Image Patches • Ann Lee, Kim Pedersen, David Mumford (2003) studies statistical properties of 3x3 high contrast image patches of natural images (from Van Heteran’s database) • Gunnar Carlsson, Vin de Silva, Tigran Ishkhanov, Afra Zomorodian (2004-present) found those image patches concentrate around a 2-dimensional klein bottle imbedded in 7-sphere • They build up simplicial complex from point cloud data • 1-D Harmonic flows actually focus on densest region -- 3 major circles

1-D Harmonic Flows on the space of3×3 Image Patches 左上图: Klein bottle of 3x3 Image Patch Space(Courtesy of Carlsson-shkhanov circles Prescind on NOnin Lotte 2007 左下图: Harmonic flows focus on 3 major circles where most of data concentrate

1-D Harmonic Flows on the space of 3x3 Image Patches • 左上图：Klein Bottle of 3x3 Image Patch Space (Courtesy of Carlsson-Ishkhanov, 2007) • 左下图：Harmonic flows focus on 3 major circles where most of data concentrate

Ranking Psychology: LL. Thurstone(1928)(scaling) Statistics: M. Kendall(1930s, rank corellation), F Mosteller, Bradley-Terry, .. P. Diaconis(group theory), etc Economics: K Arrow, A Sen(voting and social choice theory, Nobel Laureates Computer Science: Google' s PageRank, HITS, etc We shall focus on ranking in the sequel as the construction of abstract simplicial complex is more natural and easier than point cloud data

Ranking Psychology: L. L. Thurstone (1928) (scaling) Statistics: M. Kendall (1930s, rank corellation), F. Mosteller, Bradley-Terry,…, P. Diaconis (group theory), etc. Economics: K. Arrow, A. Sen (voting and social choice theory, Nobel Laureates) Computer Science: Google’s PageRank, HITS, etc. We shall focus on ranking in the sequel as the construction of abstract simplicial complex is more natural and easier than point cloud data

Had William Hodge met Maurice Kendall Hodge Theory Pairwise ranking google talks The bridge of sighs in Cambridge, St John,'s College

Had William Hodge met Maurice Kendall Hodge Theory Pairwise ranking The Bridge of Sighs in Cambridge, St John’s College

Ranking on Networks Multicriteria ranking/decision systems Amazon or NetfliX s recommendation system(user-product) nterest ranking in social networks(person-interest S&P index( time-price Voting(voter-candidate) Peer-review' systems Publication citation systems(paper-paper) Google's webpage ranking( web-Web eBays reputation system(customer-customer

Ranking on Networks • “Multicriteria” ranking/decision systems – Amazon or Netflix’s recommendation system (user-product) – Interest ranking in social networks (person-interest) – S&P index (time-price) – Voting (voter-candidate) • “Peer-review” systems – Publication citation systems (paper-paper) – Google’s webpage ranking (web-web) – eBay’s reputation system (customer-customer)

Ranking on Networks Multicriteria Peer-Review 无法显示该图片 mv1 mv2 mV3 usr1 1 usr2 25 usr 4 Us4325

Ranking on Networks • Multicriteria mv1 mv2 mv3 usr1 1 - - usr2 2 5 - usr3 - - 4 usr4 3 2 5 • Peer-Review

Characteristics Aforementioned ranking data are often Incomplete: typically about 1% Imbalanced: heterogeneously distributed votes Cardinal: given in terms of scores or stochastic choices Pairwise ranking on graphs: implicitly or explicitly, ranking data may be viewed to live on a simple graph G=(V, E),Where V: set of alternatives(webpages, products, etc. to be ranked E: pairs of alternatives to be compared

Characteristics • Aforementioned ranking data are often – Incomplete: typically about 1% – Imbalanced: heterogeneously distributed votes – Cardinal: given in terms of scores or stochastic choices • Pairwise ranking on graphs: implicitly or explicitly, ranking data may be viewed to live on a simple graph G=(V,E), where – V: set of alternatives (webpages, products, etc.) to be ranked – E: pairs of alternatives to be compared

Pagerank Model assumption 无法显示该图片 A Markov chain random walk on networks, subject to the link structure Algorithm [Brin-Page 98 Choose Link matrix L, where L(i,=# links from i to j Markov matrix M=D-1L where d=e L e is the all-one vector Random Surfer model: e is all-one matrix Page Rank mode: P=CM+(1-c)E/n, where c=0.85 chosen by Google Pagerank vector: the primary eigenvector Vo such that PI Vo= Vo Note: SVD decomposition of L gives HITS [Kleinberg 99] algorithm Problem: Can we drop Markov Chain model assumption?

Pagerank • Model assumption: – A Markov chain random walk on networks, subject to the link structure • Algorithm [Brin-Page’98] – Choose Link matrix L, where L(i,j)=# links from i to j. – Markov matrix M=D-1 L, where D = eT L, e is the all-one vector. – Random Surfer model: E is all-one matrix – PageRank model: P = c M + (1-c) E/n, where c = 0.85 chosen by Google. – Pagerank vector: the primary eigenvector v0 such that PT v0 = v0 Note: SVD decomposition of L gives HITS [Kleinberg’99] algorithm. Problem: Can we drop Markov Chain model assumption?