Monday, January 29, 2007

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)

Monday, January 08, 2007

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)

Tuesday, January 03, 2006

Visualizing Folksonomies using Machine Learning Algorithms

This paper, written for my Adv. Machine Learning class, investigates using Semidefinite Embedding (SDE) to visualize data collected from a folksonomy. The del.icio.us social bookmarking service is a perfect example of a folksonomy; a community of users label websites with descriptive tags. Each tag exists in a high-dimensional space corresponding to the frequency of use of that tag among all the users of the system. We are motivated by the following question: can we find a simple low-dimensional structure for these tags that captures the significant relationships inherent in the data? In this paper we explore Semidefinite Embedding, an algorithm for non-linear dimensionality reduction, and its application to visualizing folksonomic systems, focusing on the effects of specifying different levels of connectivity for the data and the heuristics which can be used to find the best parameters for the algorithm. (Full paper found here)

Monday, January 02, 2006

CUtunes Update

CUtunes is looking better after another semester of work. Here is the updated documentation, and some screenshots. Notable new features are user profile pages, flash-based visualizations of your musical neighborhood, and inteligent playlist creation in itunes, allowing the user to say make me a playlist that is like a specified list of musical artists and CUtunes users.

Sunday, January 01, 2006

Utilizing Folksonomy: Similarity Metadata from the Del.icio.us System

Traditionally, metadata is thought of simply as keywords that describe some content, and while the primary aim of folksonomic systems like the Del.icio.us bookmarking tool is to produce these keywords, a richer set of metadata is also produced. Because these keywords are now contributed from many different individuals and aggregated, useful information comes not only from the keyword itself but also from the information about who contributed to labeling the content with that keyword. This idea can be broadened to a general framework for producing a new layer of metadata: similarity between concepts. By analyzing the distributions of how users apply tags, how tags are applied to links, and how users pick content, we should be able to calculate the "distance" between tags, users, and content. This "distance" metric could then be used to construct a more powerful tool for browsing content, allowing the user to specify a query made up of keywords, content, or even other users. Furthermore, this metadata can be condensed into a lower dimensional space and visualized in order to gain better insight into the relationships between the concepts themselves. (Full paper found here)

Building A Better Folksonomy

We live in an age flooded with information. New technologies are making available many large unstructured sets of information. As this information becomes more available, it becomes more difficult to navigate without a guide. Now that a typical user can carry around 10,000 songs in his pocket, the choice of picking which song to listen to becomes increasingly more difficult. Now that a typical user can access 13 billion websites, how does a person know which sites are relevant to him?

The solution to this problem resides in building new web-based technologies that aid in the formation of folksonomies. Folksonomy is commonly defined as a large group of people spontaneously cooperating to organize information into categories [24]. Many websites today are taking advantage of the organizational powers of folksonomies, such as Wikipedia, Flickr, Technorati, Del.icio.us, Yahoo!, and others. All of these sites employ a simple tagging mechanism, where users attribute words or phrases to content. When these tags are aggregated, new metadata for that content is created.

Tagging offers amazing possibilities for information retrieval by using collective social intelligence to organize information instead of relying on one person’s description or categorization. However, tagging only begins to approximate an ideal folksonomy. By simplifying the ways in which we collect metadata from the user, coupling this information collection more strongly with a social framework, and providing more powerful tools for categorization, we should be able to greatly improve systems for retrieving relevant information. (Full paper found here)

Friday, May 13, 2005

Machine Learning Techniques for Visualizing CUtunes Data

Here are some cool images generated using CUtunes data. The first is a map of users, and the second is a map of artists. Distance on the map is a measure of similarity. The third points out some interesting features of the artist map.


Machine Learning Final Project: Locally Linear Embedding for Visualizing High-Dimensional Data