[Reading] Lecture 14 - Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

This paper proposed a efficient algorithm for finding frequency item sets. It utilized a data structure called FP tree to do this job. There are two advantages of this algorithm. First, the FP tree can very compactly represent the data without any information loss. That's because it didn't use any approximation. The solution will be exactly as same as the right answer. Second, the query is efficient. You only have to scan the database once, which is better than those apriori-based method. A deficincy of this work is the memory problem.

Reference:
"Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach," Han, Data Mining and Knowledge Discovery, 2004.

[Reading] Lecture 13 - On Spectral Clustering: Analysis and an algorithm

A big problem of spectral clustering is that it is very slow when we solve the eigenvector problem and the Laplacian matrix is big. Therefore, it is a little wasteful to exploit only one (the second) eigenvector and abandon the others to generate only one normalized cuts at a a time. In this paper the methods how to use the 3rd, 4th, ... eigenvectors are presented. According to their algorithm, after the eigenvector is obtained and represented as column in a matrix M, each row of M is normalized and can be clustered by Kmeans. I've tried to understand the physical meaning of the step of normalization in row but in vain. I think maybe it is just a trick operated in the mathematics and not easy to be interpreted by the physical meaning.

Reference:
Lie Lu, and Alan Hanjalic,"Audio Keywords Discovery for Text-Like Audio Content Analysis and Retrieval," to appear IEEE Trans. on Multimedia, 2007-2008.

[Reading] Lecture 13 - Normalized Cuts and Image Segmentation

Spectral clustering is not easy to understand. Although I present this topics, I dare not to say I am familiar with it.

Usually it is easier to understand an algorithm from its physcial meaning. In this paper, feature points clustering is first modeled as a Graph G=(V,E). And the action of clustering is interpreted as grouping the nodes into different groups. A simple method to evaluate the quality of grouping is to calculate the sum of edges that are linked between different groups (Cut(A,B)). Smaller Cut(A,B) is prefered since it means the similarity between the groups is small. However, minimize cut usually causes clustering that has little number of members. To solve this problem, the author proposed a method to evaluate the cut quality, and it is Normlized Cut (NCut(A,B)).

The idea of NCut is that it penalizes a clustering that has few edges connected to the nodes out of its group. However, it makes the problem becomes NP-hard. The author found that the NCut value can be represented by some matrix form consisting of the Laplacian matrix L and the vector f determined by the clustering result. That is, you can minimze NCut by minimize the matrix form. However, it is unreasonable since once we get f, we get the NCut value. In other words, minimizing the matrix form is equivalent to using brute force. In order to solve the matrix form, the author relieves some constraint of f. And then the problem can be solved as an eigenvector problem because of the approximation.

The paper mainly focus on how to cluster the data into two groups and does not put much emphasize on howto cluster the data into several groups simutaneously.

The authors also compared the normalized cut algorithm with other algorithms. There is no suprise that their method performs superior than other methods under some different settings.

Reference:
Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," Trans. PAMI 2000.

[Reading] Lecture 12 - A Comparison of Algorithms for Inference and Learning in Probabilistic Graphical Models

This paper demonstrates several inferences and learning algorithms by a simple computer vision application - occlusion. The graphical models that have been introduced in the paper includes the Bayesian Network, the Markov Random Field, and the Factor Graph. Since the occlusion application is simple, we could easily learn the pros and cons of each graphical model from the examples. Bayesian Network is good at indicating marginal independence while Markov Random Field is good at indicating conditional independence.

The rest of the paper discuss many different algorithms for inference, including exact and approximate inferences. Since the algorithms for exact inference is often intractable, we are interested more on the characteristics of the algorithms for approximate inferences. ICM reaches lower energy more quickly, but converges at a higher energy compared to other algorithms.

Reference :
B. J. Frey and N. Jojic, "A Comparison of Algorithms for Inference and Learning in Probabilistic Graphical Models," IEEE Trans. Pattern Analysis and Machine Intelligence, 27(9), pp. 1392-1416, September 2005.

[Whisper] Humble webpage

My very humble webpage which records my project results in some courses.
http://mpac.ee.ntu.edu.tw/~sutony
or
http://su.sutony.googlepages.com/sutony

[Reading] Lecture 11 - Learning Low-Level Vision

This paper models some computer vision problems by the Markov random field (MRF) model. The target solution depedent to the application is modeled as the hidden states in MRF, and the input image is modeled as the observation in MRF. After the modeling, our goal is to solve the MRF model - to obtain the "most" possible states of the hidden states.

The algorithm used in this paper to solve MRF is belief-propagation. It is easy to understand the physical meaning of the algorihm, and some papers have given the proof of its property such as its ability of convergence.

They give three application examples by using MRF, the first is "super-resolution," the second is "shaing and reflectance estimation", and the last one is "motion estimation." The idea used in super-resolution is quite novel, but it is a little impractical. If the database is not huge, it's unresonable to assume the high-resolution patch can be found from the database.

The second application is smiliar to the first one, so does their weakness in the assumption. They are both ill-posed problem. Their results are very easy to be biasd by database.

I don't think anyone will adopt their method in the third application. It is impractical to sepnd so many time estimating the motion.

Reference:
William T. Freeman and Egon C. Pasztor, "Learning Low-Level Vision," ICCV, pp. 1182-1189, 1999.

[Reading] Lecture 11 - An Introduction to Graphical Models

This paper is easy to read. When I first time hear "graphical model," I surf the internet and found this paper is most suitable for a beginner like me.

The theory supported behind the graphical model is the probability theory, in other words, you can use the mathematical language to describe any graphical model. The paper starts by a example (Fig. 1) to explain how to use a graphical model to represent a simple Bayesian model. After that, many directed graphical models and undirected graphical models are introduced. We can learn from these examples how to translate our probability problem into a graphical problem.

Since how to solve a graphical model is not the main topic in this paper, the paper only introduces a few skills how to simplify the problem. The two skills "variable elimination" and "dynamic programming" is also useful when we do programming other than solve the graphical model. For example, in our homework 2, we can use variable elimination to elliminate some redundent calculations.

I cannot understand well about the rest sections of this paper, especially "Learning." I guess it is a seldom-used technique. The example given in the application is not in vogue, maybe it is because the paper is published in early days. I think using a simplier application example as the end the paper would be better.

I think what I benefit most from this paper is more understanding the relationship between different graphical models. To my surprise, Kalman filter can be translated into a graphical model too. I didn't know that before.

Reference:
Michael I. Jordan, Zoubin Ghahramani, and Tommi S. Jaakkola, "An introduction to variational methods for graphical models," Learning in Graphical Models, Kluwer Academic Publishers, 1999.