Yevgeny Seldin, Naftali Tishby. Pac-bayesian Analysis of Co-clustering and Beyond
Natural Sciences / Computer Science / Analysis of algorithms
Submitted on: Aug 24, 2012, 19:11:55
Description: The analysis of co-clustering is extended to tree-shaped graphical models, which can be used to analyze high dimensional tensors. According to the bounds, the generalization abilities of tree-shaped graphical models depend on a trade-off between their empirical data fit and the mutual information that is propagated up the tree levels. We also formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. The analysis of co-clustering easily extends to this problem and suggests that graph clustering should optimize the trade-off between empirical data fit and the mutual information that clusters preserve on graph nodes.