weekly paper critiques of asriver

Support Vector Learning for Ordinal Regression

2009-06-19T21:51:00.000-07:00

This paper address the formulation of "learning to rank" as a problem of binary classification by using SVM (support vector machine) to learn the binary classifier. This formulation can minimize pair-wise 0-1 loss.

The learned ranking function can be viewed as followed:
(1)Ranking function: given an example, output its ranking score.
(2)Classifier: given a pair of instances, output their relative ranking.

This paper considers the simply concept of SVM, and uses it for ranking. Although inefficiency and not-so-good accuracy, it's still a guide for us to think about ranking problems

The structure and function of complex networks

2009-06-19T21:44:00.000-07:00

This paper gives an overview of networks. Researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of the complex networks, which is inspired by the empirical studies of networked systems such as the Internet(WWW), social networks(Plurk, Facebook, etc), and bio-logical networks. The author review developments in this field, including such concepts as the small-world effects, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

Lazy Snapping

2009-06-19T21:38:00.000-07:00

In this paper, Lazy Snapping, an interactive image cutout tool is presented. Lazy Snapping separates coarse and fine scale processing, making object specification and detailed adjustment easy. Moreover, it provides instant visual feedback, snapping the
cutout contour to the true object boundary efficiently despite the presence of ambiguous or low contrast edges. Instant feedback is made possible by a novel image segmentation algorithm which combines graph cut with pre-computed over-segmentation. A set of intuitive user interface (UI) tools is designed and implemented to provide flexible control and editing for the users, but the setting of energy function would make graph cut process slower if pre-segmentation has not being done at the beginning. Overall, graph cut would become inefficient to solve image cutout problem when image is getting larger, i.e. nodes of graph grows. Without considering efficiency of performance, graph cut is still a good solution for many computer vision problems.

An introduction to graphical models

2009-06-19T21:12:00.000-07:00

Graphical models are a marriage between probability theory and graph theory. Since graphical models have been intuitively illustrated and applied in many algorithms for machine learning intuitively illustrated and designed by using graphical models fields, the importance of graphical models is highly increasing nowadays.
Graphical models provide a natural tool for dealing with
(1) uncertainty
(2) complexity
In particular, graph theory provides the notion of modularity, i.e. a complex system is built by combining simpler parts. Probability theory provides the glue whereby the parts are combined, ensuring that the system as a whole is consistent, and providing ways to interface models to data.

In this topic, the author address following issues in graphical model:
1) Representation: how to represent joint probability by a graphical model?
2) Inference: how to infer hidden states by some observations?
3) Learning: how to estimate parameters of the model?
4) Decision theory
5) Applications

Rapid object detection using a boosted cascade of simple features

2009-06-19T21:05:00.000-07:00

Definition of Boosting:
Boosting refers to the general problem of producing a very accurate prediction rule by combining rough and moderately inaccurate rules-of-thumb.

Adaboost adjusts adaptively the errors of the weak hypotheses by WeakLearn. It's unlike the conventional boosting algorithm, the prior error need not be known ahead of time.

Three key ideas of rapid object detection:
(1) Integral Image
(2) A learning algorithm based on AdaBoostfor critical visual features selection
(3) Attentionalcascade

On Spectral Clustering: Analysis and an algorithm

2009-06-19T21:02:00.000-07:00

What do we concern in applying a clustering method?
• Performance of clustering methods are subjective.
– Is the clustering method persuaded enough?
– Does the theorem make sense?
• What cases?
– Do the results fit our purposes?
• How many clusters?
– Does it automatically decide the number of clusters or not?
– Is the number of clusters meaningful?

Contribution of Ng’s Paper:
• They analyze the algorithm by using tools from matrix perturbation theory.
– Persuade us the theorem is reasonable, kind of proof.
• They design conditions under which it can be expected to do well.
– How many clusters the data will be?
– Make the results more fitted to ideal cases.
• Show surprisingly good experimental results on some challenging clustering problems.

Names and Faces in the News Abstract

2009-06-19T20:53:00.000-07:00

This paper propose a method for face clustering. A dataset is also mentioned which is more realistic than usual face recognition datasets, because it contains faces captured "in the wild" in a variety of configurations with respect to the camera, taking a variety of expressions, and under illumination of widely varying color. Each face image is associated with a set of names, automatically extracted from the associated caption. Many, but not all such sets contain the correct name.

The method is quite intuitive and effective since we do not need to learn or train the unknown data at first, just filter the correct information that we want from given data.

Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary

2009-06-19T20:48:00.000-07:00

This paper describes a new approach to object recognition problem as machine traqnslation. This paper address amd attack three questions with the following answers respectively:
(1) What counts as an object? All words count as objects.
(2) Which objects are easy to recognise? Words that can be reliably attached to image regions are easy to recognise and those that cannot, are not.
(3) Which objects are indistinguishable using our features? Words that are predicted with about the same posterior probability given any image group - such objects are indistinguishable given the current feature set.

Annotated images with corresponding regions and words are really practical in applications. Once annotated images created and mapping regions specified, we can easily use them to identify other unknown objects/images or find similar ones that we want.

Algorithms for fast vector quantization

2009-06-19T20:35:00.000-07:00

Evaluating the nearest neighbor (NN) is an important problem in many applications. Vector quantization is a technique used in the compression of speech and images. In this paper, it presents to relax the requirement of finding the true nearest neighbor, which is possible to achieve significant improvements in running time and a small loss in vector quantizer performance.

This paper present an empirical study of 3 NN algorithms on a number of data distributions, and in dimensions varying from 8 to 16.
(1) Standard k-d tree algorithm: enhanced to use incremental distance calculation.
(2) Priority k-d tree search: a further improvement that orders search by the proximity of the k-d cell to the query point.
(3) A neighborhood graph search algorithm: based on a simple greedy search.

Latent Dirichlet Allocation

2009-06-16T00:57:00.000-07:00

Latent Dirichlet allocation (LDA) is a generative probabilistic model for collections of discrete data. LDA is a three-level hierarchical Bayesian model, in which each item of a collection is modeled as a finite mixture over an underlying set of topics. It models each topic as an infinite mixture over an underlying set of topic robabilities. In the context of text modeling, the topic probabilities provide an explicit representation of a document.

Several simplifying assumptions:
– 1. The dimensionality k of Dirichlet distribution is known and fixed
– 2. The word probabilities β is fixed quantity that is to be estimated
– 3. Document length N is independent of all the other data generating variable θ and z

They present efficient approximate inference techniques based on variational methods and an EM algorithm for empirical Bayes parameter estimation. We report results in document modeling, text classification, and collaborative filtering, comparing to a mixture of unigrams model and the probabilistic LSI model.

Probabilistic Latent Semantic Indexing

2009-06-16T00:30:00.000-07:00

pLSA is a novel approach to automated document indexing and information retrieval.
It is exactly the same as LSA, using a set of latent topics to construct a new relationship between the documents and terms, but with a probabilistic framework.

pLSA is based on the likelihood principle and uses a statistical model called aspect model to define a proper generative model of the data, and directly minimizes word perplexity, so it has a better statistical foundation than LSA. Also, pLSA outperforms LSA in the experiments. pLSA uses EM algorithm to identify latent topics.

Contour and Texture Analysis for Image Segmentation

2009-06-16T00:23:00.000-07:00

The paper provides an algorithm for partitioning grayscale images into disjoint regions of coherent brightness and texture. Natural images contain both textured and untextured regions, so the cues of contour and texture differences are exploited simultaneously. The texture features can be used for segmentation. Contours are treated in the intervening contour framework, while texture is analyzed using textons. Each of these cues has a domain of applicability, so to facilitate cue combination they introduce a gating operator based on the texturedness of the neighborhood at a pixel. Having got a local measure of how likely two nearby pixels are to belong to the same region, they use the spectral graph theoretic framework of normalized cuts to find partitions of the image into regions of coherent texture and brightness.

Scale & Affine Invariant Interest Point Detectors

2009-06-16T00:18:00.000-07:00

In this paper the authors propose a novel approach for detecting interest points invariant to scale and affine transformations. The scale and affine invariant detectors are based on the following recent results :
(1) Interest points extracted with the Harris detector can be adapted to affine transformations and give repeatable results (geometrically stable).
(2) The characteristic scale of a local structure is indicated by a local extremum over scale of normalized derivatives (the Laplacian).
(3) The affine shape of a point neighborhood is estimated based on the second moment
matrix.
The scale invariant detector computes a multi-scale representation for the Harris interest point detector and then selects points at which a local measure (the Laplacian) is maximal over scales. This provides a set of distinctive points which are invariant to scale, rotation and translation as well as robust to illumination changes and limited changes of viewpoint. The characteristic scale determines a scale invariant region for each point. We extend the scale invariant detector to affine invariance by estimating the affine shape of a point neighborhood. An iterative algorithm modifies location, scale and neighborhood of each point and converges to affine invariant points. This method can deal with significant affine transformations including large scale changes. The characteristic scale and the affine shape of neighborhood determine an affine invariant region for each point.

Distinctive Image Features from Scale-Invariant Keypoints

2009-06-16T00:12:00.000-07:00

A method named SIFT for extracting distinctive invariant features from images that providing a basis for object and scene recognition. SIFT is a carefully designed procedure with empirically determined parameters for the invariant and distinctive features.

SIFT four stages:
(1) Scale-space extrema detection (detector)
(2) Keypoint localization (detector)
(3) Orientation assignment (descriptor)
(4) Keypoint descriptor (descriptor)

The keypoint descriptors generated by the above stages are highly distinctive, which is invariant in rotation, scale, and viewpoint.

Image Retrieval

2009-06-15T23:59:00.000-07:00

Datta, R., Joshi, D., Li, J., and Wang, J. Z. 2008. Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv. 40, 2, Article 5 (April 2008), 60 pages

CBIR technology amounts to 2 problems: (a) signature: the design of image description , and (b) similarity measure: between two image descriptions. In the recent years, the design of features and the signatures constructed by these features have been much progressed. Besides, using machine learning techniques in CBIR has become more popular and also important.

1. Introduction: we sometimes can not express our desire in precise wording. Hence, here comes out CBIR (content-based retrieval system) which can retrieval and index directly according to image content.
2. Real-world image retrieval system: we need to consider aspects, such as query processing (how to search), data scope (where to search), user intent (interaction) and result visualization in different views.
3. Some key approaches for image retrieval.
4. Some problems and applications for CBIR.
5. evaluation of a CBIR system: Evaluation details of evaluation, which include metrics, criteria, datasets and forums, are discussed.

How to Read a Paper

2009-06-15T23:51:00.000-07:00

Three pass methods for reading papers.
(1) The 1st pass (5~10min): Scan the title, abstract, introduction, conclusion,
reference and the headings for each sections.
(2) The 2nd pass (1hr)Read the figures, diagrams, and illustrations carefully to get the key points.
(3) The 3rd pass (4~5hr)Virtually re-implement the paper.
Challenge every assumptions and consider how to solve the problem yourself.

This paper also describe how to use the proposed method to do a survey by 3 steps.
(1) Use search engine and read "RELATED WORK".
(2) Find key citations and key researchers's recent publication.
(3) Quickly scan the top conferences' recent papers

Nonlinear Dimensionality Reduction by Locally Linear Embedding

2009-03-08T00:44:00.000-08:00

ABSTRACT
Analyzing large amounts of multivariate data raises the fundamental problem of dimensionality reduction: how to discover compact representations of high-dimensional data. Here locally linear embedding (LLE) is introduced. LLE is an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs, and also maps its inputs into a single global coordinate system of lower dimensionality, and its optimizations do not involve local minima. LLE is able to learn the global structure of nonlinear manifolds, such as those generated by images of faces or documents of text by exploiting the local symmetries of linear reconstructions.

To compare and classify such observations that lie on or close to a smooth low-dimensional manifold depends crucially on modeling the nonlinear geometry of these low-dimensional manifolds. LLE can eliminate the need to estimate pairwise distances between widely separated data points, and also recover global nonlinear structure from locally linear fits.

METHODOLOGY
The problem: PCA or classical MDS map faraway data points to nearby points in the plane, failing to identify the underlying structure of the manifold. How to map high-dimensional data into a single global coordinate system of lower dimensionality.

They characterize the local geometry of these patches by linear coefficients that reconstruct each data point from its neighbors. Reconstruction errors are measured by the "cost function" which adds up the squared distances between all the data points and their reconstructions.

Minimize the cost function subject to two constraints:
(1) each data point Xi is reconstructed only from its neighbors, enforcing Wij = 0 if Xj does not belong to the set of neighbors of Xi;
(2) the rows of the weight matrix sum to one.

Steps of locally linear embedding:
(1) Assign neighbors to each data point Xi .
(2) Compute the weights Wij that best linearly reconstruct Xi from its neighbors, solving the constrained least-squares problem in the "cost function of Xi".
(3) Compute the low-dimensional embedding vectors Yi best reconstructed by Wij, minimizing the "embedding cost function of Yi" by finding the smallest eigenmodes of the sparse symmetric matrix in Mij .

For implementations of LLE, the algorithm has only one free parameter: the number of neighbors, K.

Eigenfaces for Recognition

2009-02-26T20:44:00.000-08:00

INTRODUCTION
The prupose of the artitle ”Eigenfaces for Recognition” is to implement a system capable of efficient, simple, and accurate face recognition in some specific environment, like a household or an office. The system performs a classification using a linear combination of characteristic features (eigenfaces). However, the traditional 3-D models or intuitive knowledge of the structure of the face (eyes, nose, mouth) are not involved.

Previous works:
1. feature based face recognition,
2. connectionist basedface recognition
3. geometric face recognition

METHODOLOGY
The methodology of eigenfaces seeks to use principal component analysis (PCA) of the images of the faces.This PCA reduces the dimensionality of the training set, leaving only those features that are dominative for face recognition. The PCA procedure can be ignored for we've been familiar with it. The eigenface is bulit by the front M-1 eigenvectors of the covariance matrix of the feature vectors. Then the new image feature is projected into the face space using the linear combination of the eigenvectors. If the euclidean distance distance between the new image and a class of faces k is less then a threshold, the new face is assigned to recognized, and assigned to class k. To determine the validity of the assumption that that new image is a face, they project the image onto the face space, and examine difference between the projected image and the original new image. Afterword, they design four possibilities for classifiying the coming new image.