Matrix Tile Analysis
Inmar Givoni, Vincent Cheung, Brendan Frey
Abstract:
Many tasks require finding groups of elements in a matrix of numbers, symbols or class likelihoods. One approach is to use efficient bi or trilinear factorization techniques including PCA, ICA, sparse matrix factorization and plaid analysis. These techniques are not appropriate when addition and multiplication of matrix elements are not sensibly defined. More directly, methods like biclustering can be used to classify matrix elements, but these methods make the overlyrestrictive assumption that the class of each element is a function of a row class and a column class. We introduce a general computational problem, `matrix tile analysis' (MTA), which consists of decomposing a matrix into a set of nonoverlapping tiles, each of which is defined by a subset of usually nonadjacent rows and columns. MTA does not require an algebra for combining tiles, but must search over discrete combinations of tile assignments. Exact MTA is a computationally intractable integer programming problem, but we describe an approximate iterative technique and a computationally efficient sumproduct relaxation of the integer program. We compare the effectiveness of these methods to PCA and plaid on hundreds of randomly generated tasks. Using doublegeneknockout data, we show that MTA finds groups of interacting yeast genes that have biologicallyrelated functions.
Keywords:
Pages: 200207
PS Link:
PDF Link: /papers/06/p200givoni.pdf
BibTex:
@INPROCEEDINGS{Givoni06,
AUTHOR = "Inmar Givoni
and Vincent Cheung and Brendan Frey",
TITLE = "Matrix Tile Analysis",
BOOKTITLE = "Proceedings of the TwentySecond Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI06)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2006",
PAGES = "200207"
}

