Minimum Volume Embedding

Here is a pre-final-version of my first published paper in Machine Learning. The following paper is written with Prof. Jebara at Columbia, and will be published at the AI and Statistics 2007 conference. How exciting!

Abstract:
Minimum Volume Embedding (MVE) is an algorithm for non-linear dimensionality reduction that uses semidefinite programming (SDP) and matrix factorization to find a low-dimensional embedding that preserves local distances between points while representing the dataset in many fewer dimensions. MVE follows an approach similar to algorithms such as Semidefinite Embedding (SDE), in that it learns a kernel matrix using an SDP before applying Kernel Principal Component Analysis. However, the objective function for MVE directly optimizes the eigenspectrum of the data to preserve as much of its energy as possible within the few dimensions available to the embedding. Simultaneously, remaining eigenspectrum energy is minimized in directions orthogonal to the embedding thereby keeping data in a so-called minimum volume manifold. We show how MVE improves upon SDE in terms of the volume of the preserved embedding and the resulting eigenspectrum, producing better visualizations for a variety of synthetic and real-world datasets, including simple toy examples, face images, handwritten digits, phylogenetic trees, and social networks.

Minimum Volume Embedding (not final version)

Learning from a Visual Folksonomy: Automatically Annotating Images from Flickr

Recently, a large visual dataset has emerged from a web-based photo service called Flickr which utilizes the organizational power of folksonomy to label a tremendous amount of visual data. Flickr users upload snapshots from their digital cameras to the web, and if marked as public, the community annotates these images with descriptive tags. Can this large collective labeling effort be used to train a computer to annotate images? What concepts are we able to train a computer to visually identify?

This project uses a simple crawler to download photos from Flickr labeled with a certain tag, and then extracts color and texture features from these images so that they can be used to train a classifier, such as a Support Vector Machine (SVM). By automating this process of downloading images, extracting features, training, and testing, we are able to apply our system to many different tags and see which tags correspond to identifiable visual features. We have found that the system performs relatively well annotating images with one label, selected from a small vocabulary, for images belonging to concepts with distinct color and texture features. (Full paper found here)