[Paper Review] Improved Boosting Algorithms Using Confidence-rated Predictions

This paper is a complete arrangement of the original AdaBoost algorithm. It discussed the algorithm's behavior in many aspects, gave theoretical bounds and proposed several improvements. The author also validated those new ideas with experiments on real data. The new, improved AdaBoost is more convenient as one can assign real-valued responses in the weak learners.

 

The most attractive feature of AdaBoost should be its simplicity. Given an almost arbitrary configurable classifier, one can enhance its performance considerably by plainly following those simple steps of AdaBoost. The original classifier can be very crude, maybe only slightly better than random guess. In the training progress, AdaBoost will force the weak classifier to "learn" more from the examples it failed before, thus increasing the accuracy of the classifier. The training error of AdaBoost approaches zero at an exponential rate of iterations. The final classifier is a linear combination of all the classifiers used in the progress. This voting structure is a compromise of classifiers, each looks at a small portion of the high dimensional instance space.  For multi-label or multi-class problems, one can map them to the binary case by forming tuples of "instance-label" or "instance-class" and exploring their validity.

 

One obvious weakness of AdaBoost is the neglect of the interaction among individual classifiers. Much likely, it would be the case one could assure a prediction with high confidence if specific two or three classifiers say "yes" at the same time. The linear combination rule of AdaBoost puts the burden on the adaptability of the weak learner, which may not always be a good idea. Another extension of AdaBoost might be to modify it so that inherently different kinds of classifiers can work together.

[Paper Review] Rapid Object Detection using a Boosted Cascade of Simple Features

This paper showed how to apply machine learning techniques in the area of high-speed object detection (or more precisely, template matching). The idea is to choose one kind of coarse features that can be computed very efficiently and to improve their performance by AdaBoost learning and filter cascading. The proposed system can run in real-time in face-detection with comparable accuracy to the state-of-the-art. 

 

Apparently, the most important contribution of this work is in extending AdaBoost so that one can choose from a large pool of available features to form a small, yet equivalently discriminative subset. The extension is not complex, however - you only need to repeat the training in each iteration for all available classifiers (features) instead and select the most promising one. The other two ideas of this work are more straightforward. The integral image is a synonym of one old trick in dynamic programming, and filter cascading is something everyone would possibly do in high-speed application. Nevertheless, the resulting system does demonstrate a great improvement over existing methods (in face detection).

 

One pretty vital problem that was ignored in the paper is the object orientation. The proposed framework seems not to be possible to deal with rotated objects with simple modification. Although one may blindly repeat the same detection algorithm at every possible angle, this would severely slow down the system. I think this should be the cause that I didn't see anyone apply the same idea to objects other than the frontal face.

[Paper Review] Names and Faces in the News

This is an astonishing work. The paper proposed a system framework that can perform face identification and classification on large scale databases from the Internet that may contain ambiguous name labeling, a broad range of individuals and extremely varying photo conditions. Four main parts constitute the system: a simple yet effective data acquisition method, a robust face rectification,  a scalable approximation of PCA and a reliable clustering algorithm.

 

I think the most important contribution of this work shoud be applying the Nystrom approximation to the PCA probem. Although this may not be purely novel ( as seen from the references), it does show that such an approximation is practical and can work well on real data. Many follow-up researches could then base on this result. The rectification, even if not highlighted in the paper, I think, is also vital for the success. The proposed algorithm can run in short time ( important for such a large database) and provide results with enough quality. The clustering algorithm is somehow straight-forward, but is OK for the purpose.

 

One weakness of the work is that it doesn't provide complete retrieval experimental results on the clustered data. The proposed measurement based on information theory appears reasonable, but it does not give an intuitive feeling of the data quality(I didn't understand it either :S). I am currently working on a problem that also deals with Internet photo collection and I believe the former parts of the paper did give me much inspiration.

[Paper Review] Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary

This paper addressed the problem of image annotation by estimating a probability relationship between image segments and text words. The main advantage of this approach is the ability to establish direct correspondence between the two worlds so that one can know which kinds of segments contributes to which words. In this way the user can retrieve images with the conventional text search without manual pre-annotation for the database.

 

The probability table is estimated using EM approach. As usual, we first extract features from image segments and perform vector quantization to represent the high dimensional continous pixel domain information in a discrete space. The EM algorithm then compute the  probability for a word given a blob(the quantized feature) by repeatedly doing assignments from probabilities and estimating probabilities from assignments. After we get this probability table, we can annotate images with the highest probability words of the segments in them.

 

Although the approach seems to be promising, it is obvious that the experimental performance is not very good. In the annotation test, almost all the image retrieval queries return with a precision smaller than 0.4, and only a few words can be successfully queried if the threshold is increased. The situation is better in the correspondence test, but the prediction rate are still lower than 0.5 in general. Finally, the two refinements the author proposed( thresholding and merging) do not improve the performance much both. I believe the problem comes from the faulty segmentation and the imperfect features. General image segmentation is so far an active research area where no ideal has be found. On the other hand, some erroneous labelings look to result from bad feature representations(classifying sky with clouds as water). The visual word approach would not suffer from this problem ( or to a less extent) since it requires only two levels of abstraction(feature, clustering), not three(seg, feature, clustering).

....

Windows Live Writer eats one of my posts...@@"

 

Please be careful if you use it too... You have to open a new file before starting up a new post.. or WLW would replace the last one with the new post... xxx

[Paper Review] Similarity Search in High Dimensions via Hashing

This paper talked about the Locality-Sensitive Hashing(LSH) algorithm for the ANN search and improved over the former results to guarantee a sub-linear time complexity. LSH is a popular algorithm in the ANN field because it can provide tight theoretical estimates and upper bounds for many behaviours of the algorithm. This is useful if such assurance is appreciated or critical (e.g. real-time application).

 

The general concept of LSH is simple: if we can somehow design a hash function that could always hash close points into nearby bins, then we need only to look at a few bins when finding the nearest neighbor for one query. For different distance metrics, the design of the hash function would differ. In this paper, the author concentrate on the L1 norm and argued that L2 norm can be approximated through appropriate scaling and rotation on the data. It is interesting for me to here that but I didn't get time to read the original material. Please tell me if you can explain this :).

 

The hashing of L1 norm LSH goes in this way. We first scale the point coordinates so that the smallest seperation of each dimension exceeds one. The coordinates of each point are then discretized, "unarized" and concatnated to form a single binary vector. The LSH function would consists of several sub-functions, each sampling a number of bits from the point binary vector at pre-determined, randomly chosen positions. Each point is put into one hash bins according to the resulting value of each such sub-function. To deal with the huge number of possible bins, the bins are further hashed using standard hashing techniques. When ones need to find the nearest neighbor of a query point, they can go through the whole process and look only at the points in the bins indicated by hash functions. By careful choosing of the number of sub-functions and sampling positions, the LSH can guarantee a high probability of finding true nearest neighbor. In fact, LSH resembles histograms. The sub-functions of LSH are simply a collection of low-dimension histograms with the hope that the true NN would fall in the same cell as the query in at least one of them.

 

The experiments in the paper is proper. Especially, the choice of disk access measurement is brilliant because many large scale problems generates feature pools of millions to tens of billions data points, which is impossible to fill in the main memory. The question is that the error seems to climb up considerably from the first dataset to the second. I am wondering if this is a problem of LSH in dealing with large data. After all an error of 15% on the average does not sounds attractive. Another problem of LSH would be the need to determine the number of sampling position(seeing from the experiments). It is troublesome as this is not required in tree-based ANN search.

[Paper Review] Algorithms and Applications for Approximate Nonnegative Matrix Factorization

This paper is a general survey of recent advances in the NMF area. Given a non-negative matrix A, NMF is to find a pair of also non-negative matrix W and H such that the Frobenius norm of A-WH is minimized. The non-negativity has the advantage that it properly reflects some physical limitations that only non-substractive combinations of features are acceptable(for ex. topics of textual data). In this way, NMF differs from the classical SVD decomposition where no such non-negative restriction is imposed.

 

The benefits of non-negativity does not come without price. In contrary to SVD, NMF is nonconvex in both W and H and requires numerical methods that deals with non-linear optimization. According to the paper, this seems to be the core problem that researchers work on in this area. The original multiplicative update algorithm, although simple, has the problem of converging to saddle points and is very slow. General methods such like gradient descents apply to NMF, but require a good mechanism to determine stepsize. The alternating least square approach seems to be the fast method for now and enjoys the flexibility of "escaping" from zero entries due to the projection step.  Nevertheless, it may still converge to a saddle point. Thus, up to the present, it does not exist an excellent algorithm for NMF in general. Users intend for local minima should initialize the optimization with different start points and check the results for optimality.

 

In general, fundamental mathematic formulations often do not suit a specific problem, and prior knowledges of the problem should be brought in for a good solution to be got. This is even more critical in NMF because the optimal solution is not unique here. The paper addressed several common extensions to the cost function of NMF and validate the value of the most basic one(regularization on magnitudes of H or W) through experiments.  In my personal experience, the regularization(smoothness) terms are usually important factors that may affect the solution quality and require the special care.

 

The two experiments in the paper are the text mining and the spectral data analysis. The results seem quite good, but the author did not put on the comparison with other methods, so I can't judge the power of the NMF approach properly. Indeed, the result on text mining is visually similar to the one in the pLSA paper. It is shown in [1] that NMF with Frobenius norm replaced by KL divergence is essentially the same as pLSA and both kinds of problems are instances of the more general multinomial PCA problem. The connection between those methods and the performance comparison on different problems should be a good research topic.