Making Archetypal Analysis Practical

The paper is by Christian Bauckhage and Christian Thurau

Summary: Archetypes are a convex combination of data, and data points are a convex combination of archetypes. Archetypal Analysis (AA) can be applied to various computer science and real-world applications. Some applications include clustering, dimensionality reduction, and text summarization. However, AA suffers a setback when computational complexity is taken into account. In this paper, the authors present methods for effectively reducing dimensionality.

The paper is provided in Google Scholar via ResearchGate.

You can have a look at the video explanation of the paper step by step here on the following my YouTube channel: 

Paper: Making Archetypal Analysis Practical

 (https://www.youtube.com/watch?v=bJfOK9PqHyk)

Key points in the paper are given here.

— Archetypal Analysis (AA) was introduced by Cutler and Breiman.

— Example as in the following image taken from the reference paper [1] Bauckhage, C., & Thurau, C. (2009)

— Each data point can be expressed as a convex combination of archetypes.

— Each archetype is a convex combination of data points.

— Data points, X = {x1, x2,…., xn}

— Archetypes, Z = {z1, z2,..zp}

— In matrix form, Z= XB, B is n x p matrix

— In matrix form, X=ZA, a is p x n matrix

— AA minimizes Residual Sum of Squares (RSS)

— RSS is [1]

— In matrix form, RSS is,

RSS(p)= ||X-ZA||2 = ||X-XBA||2

— The algorithm by Cutler and Breiman to solve this problem, to determine archetypes and coefficients, is as follows:

Making AA Practical, by the authors, Bauckhage, C., & Thurau, C.

The problem is that AA depends on the size of the data samples; therefore, the authors [1] have provided the following suggestions, which effectively reduce the problem’s time complexity. These are as follows:

— The algorithm by the authors is the same as the algorithm by Cutler and Breiman, except they use X+ and XH instead of X. The algorithm is described in [1].

The improvements in time complexity are remarkable and are presented in the paper [1], in the last but one section.

Furthermore, the authors have experimented with Flickr data and have shown what archetypes actually look like in images of the archetypes.

It would be interesting to watch what archetypes look like in the paper.

Subscribe for updates.

Reference

[1] Bauckhage, C., & Thurau, C. (2009, September). Making archetypal analysis practical. In Joint Pattern Recognition Symposium (pp. 272–281). Berlin, Heidelberg: Springer Berlin Heidelberg.