Pre-Grant Publication Number: 20100262568
Please help the USPTO examine the application by evaluating the relevance of the publicly submitted prior art to the patent application.
Peer To Patent forwards the Top 10 most relevant prior art submissions and their annotations to the USPTO.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Prior Art Detail
#699A Generalized Maximum Entropy Approach to Bregman Coclustering and Matrix Approximation
Applies to Claims 1
Summary / Description
| Summary / Description | In this paper, we present a substantially generalized co-clustering framework wherein any Bregman divergence can be used in the objective function, and various conditional expectation based constraints can be considered based on the statistics that need to be preserved. Analysis of the coclustering problem leads to the minimum Bregman information principle, which generalizes the maximum entropy principle, and yields an elegant meta algorithm that is guaranteed to achieve local optimality. Our methodology yields new algorithms and also encompasses several previously known clustering and co-clustering algorithms based on alternate minimization. |
Basic Information
| Type of Prior Art | Online Publication |
| URL | http://portal.acm.org/citation.... |
| Author/Creator | Arindam Banerjee, Inderjit S. Dhillon, Joydeep Ghosh, Srujana Merugu, and Dharmendra S. Modha |
| Title | A Generalized Maximum Entropy Approach to Bregman Co-Clustering with Matrix Approximation |
| Publication Date | August 25, 2004 |
| Publisher | The Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 04), Seattle, Washington, August 22-25, 2004. |
| Directions to Document Location | |
| Additional Information | |
Notes / To Do
| Notes | Prior art provided by Dharmendra S Modha, IBM, and submitted by Diane Willis. |
Excerpt
Excerpt In this paper, we address the following two questions:
(a) what class of distortion functions admit e*cient co-
clustering algorithms based on alternate minimization?, and
(b) what are the di*erent possible matrix reconstruction schemes
for these co-clustering algorithms? We show that alternate
minimization based co-clustering algorithms work for a large
class of distortion measures called Bregman divergences [3],
which include squared Euclidean distance, KL-divergence,
Itakura-Saito distance, etc., as special cases. Further, we
demonstrate that for a given co-clustering, a large variety
of approximation models are possible based on the type of
summary statistics that need to be preserved. Analysis of
this general co-clustering problem leads to the minimum
Bregman information principle that simultaneously generalizes
the maximum entropy and the least squares principles.
Based on this principle, and other related results, we develop
an elegant meta-algorithm for the Bregman co-clustering
problem with a number of desirable properties. Most previously
known parametric clustering and co-clustering algorithms
based on alternate minimization follow as special cases of our methodology. |
Relevance
Claims
1
Relevance
See the Excerpt.
See the Excerpt.
Claim Chart
Some
0 days left
