[Reading] Lecture 07 - Algorithms for Fast Vector Quantization

As in the last paper, this paper studies on finding the closest data point in a high dimensional space. They introduced three searching algorithms and made the experiments based on these methods.

The first two algorithms make refinement on the well-known data structure - kdtree. The first one uses incremental distance calculation to make the complexity of transversing the kdtree reduce to only O(1) (independent of dimension), which is tricky and very useful. The second one uses a priority quene to determine the order of searching. It makes the query terminates earlier.

The third algorithm is based on neighborhood graphs. Any two connected nodes in the neighborhood graphs must satisfy some local criterion, and can be used to accelerate the qurey speed. However, the preprocess

Reference:
S. Arya and D. M. Mount, "Algorithms for fast vector quantization." Proceedings of DCC 93: Data Compression Conference, pp. 381-390, IEEE Press, 1993.

[Reading] Lecture 07 - Similarity Search in High Dimensions via Hashing

Finding the k-nearest neighbors from a database is useful for many applications, especially in a query system. However, if the searching algorithm is not well designed, it becomes a extremely time-consuming process when applied to a large database, and may make the applications impractical to be used.

Although there are some data structures such as k-d trees developed to speed up solving the k-nearest problem, evidence shows that it is no much better than using the brute-force method when the dimensions are high. Researchers use the slang "curse of dimensionality" to describe this annoying phenomenon.

The main idea of this paper is that obtaining the exact answer is not always necessary, an approximate similarity search is usually enough. In other words, the searching speed is usally more important than the accurary of the searching results.

Instead of using space partitioning (e.g. k-d trees), this paper uses locality-sensitive hashing (LSH) to accelerate the searching speed. Specifically, the authors use two levels of hashing - 1. An LSH function maps points to bucket. 2. A standard hash function that maps the contents of buckets into a hash table. The searching methods are primarily composed of two phases, a preprocessing phase and a query phase. The hash tables are built in the preprocessing phases, and later used in the query phase.

The author further analysize the ability of LSH by both mathematical and experimental ways. Of course, they show their method considerable speed-up the query process. An additional advatange of their method is that the running time is determined in advanced.

Comment:
I depreciate the way how they explain their technical thing. The symbols and the equations used in the paper are ambiguous (especially when they explain Locality-Sensitive Hashing). I remember that KT has presented a very similar topic before, she did a much better job than this paper does!

Reference :
Gionis, Indyk, and Motwani, "Similarity Search in High Dimensions via Hashing," VLDB: International Conference on Very Large Data Bases, Morgan Kaufmann Publishers, 1999.

[Reading] Lecture 06 - Algorithms and Applications for the approximate Nonnegative Matrix Factorization

NMF (Nonnegative Matrix Factorization) is another useful algorithm to factorize a matrix A. More specifically, NMF tries to find two matrices W and H, such that WH~A, where ~ means roughly the same here. Very often the data to be processed (A) is nonnegative, to avoid contradicting phsyical meanings, an important constraint imposed to NMF is that all the low rank data (W and H) must be comprised of nonnegative values. In this paper, the cost function is defines as:

0.5 A-WH^2.

In fact, the cost function can be defined by some other ways, too.

The paper introduces three approaches to solve the NMF problem - Multiplicative Update Algorithm, Gradient Descent Algorithm, and Alternating Least Square Algorithm. These algorithms have to face some difficult challenges, such as the existence of local minima and lack of unique soluction. None of these algorithms guarantee the answer is a global minimum in cost function, but in many data mining applications a local minimum is enough to be useful. Each algorithm has its own disadvtanges such as low speed or convergence problem. However, in practice researchers often sacrifices convergence theory to speed up the process. Therefore, ALS is a favored algorithm among the three. After introducing the three algorithms, the paper goes more into detail on how to set the constraints or adding penalty terms.

Then, the paper gives two example applications of NMF, one is text mining and the other is spectral data analysis. In text mining, NMF uses a document-term matrix constructed with the weights of various terms from a set of documents. Then, the matrix is factored into a term-feature and a feature-document matrix similar to LSI. As a matter of fact, NMF is equivalent to PLSA when it is obtained by minimizing the Kullback–Leibler divergence.

Reference:
Michael W. Berry, Murray Browne, Amy Nicole Langville, V. Paul Pauca, and Robert J. Plemmons, "Algorithms and applications for approximate nonnegative matrix factorization," Computational Statistics & Data Analysis, 52(1), pp. 155-173, 2007.

[Reading] Lecture 06 - Probabilistic latent semantic indexing

Before PLSA, some people use LSI to find the relationship between words and documents. An appealing characteristic of LSI is that it automatically find the hidden relevance among two different words (documents) or between a word and a document using the statistical information. Just like PCA, formulating a problem as an optimization problem in linear algebra is theoretical and more convincing than heuristic approaches such as word matching in different documents.

However, LSI lacks a statistical foundation and hence harder to be used by combining it with other model. To overcome this deficit, this paper introduce an aspect model to analysize the problem based on the probabilistic principle. Latent class (similar to the hidden state in HMM) is used to model the implicit relationship among documents and words. The author says that the class-conditional multinomial distribution over the vocabulary in the aspect model which can be represented as points of all possible multinomials. That is, PLSA can be thought of in terms of dimensionality reduction to a probabilistic latent semantic space.

With strong probabilistic foundation, PLSA take advantage of statistical standard methods for model fitting, overfitting control, and model combination. Experiments proofs that it achieves significant gains in precision over both standard term matching and LSI.

Reference:
T. Hoffman, "Probabilistic latent semantic indexing," Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 50-57, ACM Press, 1999.

[Reading] Lecture 05 - Shape matching and object recognition using shape contexts

This paper provides an approach to measure the similarity (distance) between two shapes. They uses several points sampled from the contours to represent the shape. Each sample point has a descriptor to describe the coarse distribution of the rest parts of the shape by using histogram of the angle and distance of other sample points. From the point descriptors, the problem of finding the correspondence between two shapes becomes the problem of finding for each sample point on another shape that has the most similar shape context.

After obtaining the correspondences between points on two shapes, an aligning transformation (warping) from one shape to the other is estimated. The magnitude of the aligning transform is viewed as a measure of shape similarity. The overall similarity between the two shapes is computed as the sum of the matching errors between corresponding points and the magnitude of the aligning transform.

K-medoids (a variant version of K-means) is adopted to select the prototypes that should be stored, and a K-NN classifier is used in the recognition job. By making experiments on 3D object database, they have shown that their algorithm is invariant to several image transformations.

This paper provides a method to evaluate the distance between two shapes in a very dissimilar way compared with previous works. By using shape context descriptor, they do not require any key-point (e.g., maxima of curvature or inflection points) or the grayscale values inside the silhouette to describe the shape.

Reference:
S. Belongie, J. Malik and J. Puzicha, "Shape Matching and Object Recognition Using Shape Contexts." IEEE Trans. Pattern Anal. Mach. Intell, 24(4), pp. 509-522, 2002.

[Reading] Lecture 05 - A Boundary-Fragment-Model for Object Detection

There are many different features that can be used to detect the objects, such as texture, shape, and color. Sicne they can be used altogether to get superior performance, we cannot say any of them is the best one. In this paper, the authors introduce a system which uses boundary fragment as the feature to enhance the capability of shape information. The reason that they don't use the entire object boundary as the feature is because of the limitation in edge detection. It's really hard to obtain a complete ojbect boundary from a noisy image (or because of the occlusion).

Like most of the object detectors, the BFM (Boundary-Fragment-Model) system needs a traning phase beforehand. The BFM system first detect edges by Canny detector from the training images. After finding the edges, several fragments are chosen accoding to the scores tested on the validation images. Since each fragment has the information of the object centroid, the system can estimate the object position from the matched fragments in the detection phase. The fragment candidates are used alone or combined together to form weak classifiers. From the weak classifiers, A strong classifier is obtained by the classic AdaBoost algorithm.

In the detection phase, the strong classifer is used to decide the existence of an object. If the object exists, Mean Shift is applied on the Hough voting space to get the centroid of the object. And then, the silhouette of this object is obtained by backprojection of each weak classifer.

In their experiment, they prove that their performance is competitive to other state-of-the-art detectors'. They also show their detector's ability to distingush between different objects with similar contours.

At the end of the paper, they discuss about the invariance to scale, rotation, and viewpoint. However, I think this part is explained ambiguously, and thus I have no more comments about this section.

Reference:
A. Opelt and A. Pinz and A. Zisserman, "A Boundary-Fragment-Model for Object Detection ." European Conference on Computer Vision, p. II: 575-588, 2006.

[Reading] Lecture 04 - Nonlinear Dimensionality Reduction by Locally Linear Embedding

The idea used in this paper is very simple. Imagine that the feature points are scattered on the manifolds (locally linear patch), that is, a feature point can be described (linear combination) by its neiborhoods. Under this assumption, the low-dimensional description (weights) of each feature point is firstly obtained by searching its kNN and minimizing an error function. Given those weights, choose y (less than d) d-dimensional coordinates to minimize the sum of the reconstruction cost for every feature point.

My idea:
I think a major trick used in LLE is that the (rough) low-dimensional descriptions are found first. By this way, some information (local relationship in LLE) are preserved when the embedding coordinates are computed. My point is: If we obtain the weights by other methods (e.g., choose the neighbors that belong to the same class instead of using kNN), something other than local relationship (e.g., in-class relationship) can be preserved after the dimension reduction.

Reference:
S. T. Roweis and L. K. Saul, "Nonlinear Dimensionality Reduction by Locally Linear Embedding." Science, Vol. 290, pp. 2323-2326, 2000.