The Multi-Feature Information Bottleneck with Application to Unsupervised Image Categorization

1 Introduction

The Information Bottleneck (IB) method [Tishby et al., 1999] is one of the popular and powerful unsupervised data analysis techniques. In the IB framework, the data and its features are treated as the instances of two random variables X and Y , of which the joint distribution p(X, Y ) can be empirically estimated from the "co-occurrence" or "dyadic" data matrix. Then the data analysis problem is viewed as the process of compressing X variable into a "bottleneck" variable T and the compressing results p(t|x) finally reflect the hidden patterns of the data. The IB algorithms have been applied in many fields and the results have demonstrated that the IB method is a promising technique for discovering the underlying patterns resided in the data set [Slonim et al., 2002; Slonim, 2002; Lou et al., 2010].

While compressing X to T , the IB method tries to preserve the information about the relevant variable Y as much as possible. The variable Y specifies what information the compressed representation T should preserve. Consider a simple example where X and Y denote the documents and words respectively. If our task is to compress document variable X, in the IB framework, the compression variable T should preserve the information about word variable Y as high as possible. Since the words carry the semantic information, the final compressing results p(t|x) will reveal the topic patterns of the documents. If a new feature variable Y is available, the IB method will obtain a different compressed representation according to the information provided by Y .

The feature variable Y is of great significance to the IB method. One variable Y , which has the power to perfectly discriminate the classes in the data, will yield a good compressing results for IB algorithms. Therefore, to improve the performance of IB algorithms, one alternative way is to seek a better data representation. There are many works that aim to learn more discriminative features, such as feature weighting [Salton, 1991], feature clustering [Slonim and Tishby, 2000] and feature selection [Dhillon et al., 2004]. We can use some of them to learn a more discriminative feature variable for IB algorithms. However, all these works only consider one type of features. In real applications, there may be several cues to complementally characterize the same object. For example, we can use both words and photos to describe one person. The words can describe the person from the information of age, sex, height and other characters, while the photos can show the appearance of one person directly. Words and photos are two different feature types. Even though we can make use of the words to describe the appearance of one person, and guess the vague age of the person from the photo, such information is not perfectly accurate and direct. So, we would rather adopt both words and photos than adopt only one source of them to describe people complementally. In the IB framework, there is only one feature variable Y to denote one type of features, and the data analysis task can only be performed on one feature variable. While only one feature type can't completely characterize the data, the relevant information provided to IB is limited and the final compressing results will be poor to reveal the hidden patterns. So, can we analyze the data frommultiple feature types simultaneously?

In this paper, we extend the original IB method to the Multi-feature Information Bottleneck (MfIB), which can simultaneously process multiple feature types and analyze the data from multiple cues. In the MfIB framework, each type of features is denoted by one feature variable and there is a corresponding joint distribution between the data variable and feature variable. Instead of only maximally preserving the information of one feature variable, the MfIB tries to simultaneously maintain the information of multiple feature variables while X is compressed to T. Therefore, the compressing results can simultaneously reflect the hidden patterns provided by multiple cues of features, and the multiple complemental variables can help the IB method to extract the patterns of the data that are much closer to the real patterns resided in the data.

In order to verify the effectiveness of the proposed MfIB method, we apply the MfIB algorithm to the field of unsupervised image categorization, of which the task is to discover object or scene categories from a collection of unlabeled images without any supervision [Sivic et al., 2005; Lou et al., 2010; Tuytelaars et al., 2010]. The first step, which is also one of key issues to understand the semantics of the images, is to select one feature extraction technique. In the computer vision field, there are many feature extraction techniques, such as SIFT [Lowe, 2004], SURF [Bay et al., 2008], Color Attention [Khan et al., 2009], TPLBP [Wolf et al., 2008] and so on. Each technique can extract some information from one aspect of the images. For example, SIFT and SURF extract the local shape information, while Color Attention and TPLBP extract the color and texture information respectively. Even though both SIFT and SURF extract the shape information, they don't have the same power to discriminate the image categories because of the differences between the corresponding feature extraction algorithms. Among these feature types, we can't determine which one is better than the others and their powers to discriminate the classes are also different. So, if we categorize the images on multiple complemental feature types, the performance may be improved. [Lou et al., 2010] have demonstrated that the IB method is a powerful technique for unsupervised image categorization. In this paper, we extend the IB to MfIB and apply the proposed MfIB algorithm to unsupervised image categorization. The MfIB algorithm can simultaneously process multiple feature variables, which correspond to multiple feature types extracted from the images. The experiments on 7 benchmark image data sets show that, by combining multiple feature variables, the MfIB clearly outperforms the original IB method. In addition, the performance of MfIB is also superior to the state-of-the-art unsupervised image categorization methods [Sivic et al., 2005; Lou et al., 2010].

The main contributions of this paper can be summarized as follows:

• We extend the original Information Bottleneck method to Multi-feature Information Bottleneck, which can fuse multiple aspects of information from multiple cues into the final data analysis results, and thus captures the complementary information residing in multiple features.
• We apply the proposed MfIB algorithm to unsupervised image categorization, which provides a solution to the problem of unsupervised image categorization by combing diverse multiple feature types.

2 The Information BottleneckMethod

The Information Bottleneck [Tishby et al., 1999] is an information-theoretic based data analysis method, which treats the pattern extraction from data as a process of data compression. Assume that we are given a collection of unlabeled data X = {x1 , x2 , · · · , xm} and its co-occurrence features Y = {y1 , y2 , · · · , yn}, where m and n are the total number of samples and the size of features respectively. Let X and Y be two discrete random variables, taking values from X and Y, respectively. Then, for every x ∈ X, we can define the conditional distribution of the features as p(y|x) = n(x,y) ∑y′ n(x,y′ ) , where n(x, y) denotes the number of occurrences of feature y in the sample x. If the prior distribution of p(x) are given, we can obtain the joint distribution between X and Y by p(x, y) = p(y|x)p(x).

Based on the above joint distribution, Tishby et al. [Tishby et al., 1999] formulate the data analysis problem as looking for a compressed representation T of X which maintains the information about the relevant variable Y as high as possible. The compactness of the representation and the preservation of the relevant information are measured by the mutual information I (T ; X) and I (T ; Y ), respectively. The mutual information between variables X and Y are defined as [Cover and Thomas, 1991]:

Formally, Tishby et al. suggest the following IB-functional:

where β is the Lagrange multiplier controlling the trade-off between the compression from X to T and the preserved information of T about Y . The formal solution to the IBfunctional (2) is given by the following equations which must be solved self-consistently,

where DKL[p(y|x)||p(y|t)] = ∑y p(y|x) log p(y|x) p(y|t) is the Kullback-Leibler(KL) divergence [Cover and Thomas, 1991] between the conditional distributions p(y|x) and p(y|t), Z (x, β) is a normalization function. Obviously, the variables p(t) and p(y|t) are determined through p(t|x).

3 The Multi-feature Information Bottleneck

The original IB method processes only one feature variable Y . In this section, we present a new IB framework, Multifeature Information Bottleneck (MfIB), which can simultaneously process multiple feature variables. For clarity, we first define the task of MfIB.

Definition 1 (MfIB). Given a discrete random variable X, taking values from X = {x1 , x2 , · · · , xm}, there are k(k ≥ 1) discrete random variables Y 1 , · · · , Y k and the corresponding joint distributions p(X, Y 1 ), · · · , p(X, Y k ) (1 ≤ i ≤ k). Each variable Y i takes values from one feature source Y i = {yi1 , yi2 , · · · , yini } to characterize the samples of X from one cue. The task of MfIB is to learn a good compressing representation p(t|x) of X to T from multiple feature variables Y 1 , · · · , Y k .

3.1 Objective Function for MfIB

The MfIB aims to simultaneously process multiple feature variables. Figure 1 is the model of MfIB. From this figure, we can see that there are multiple feature variables related to the data variable X, and the compressed variable T should simultaneously preserve the information about feature variables Y 1 , · · · , Y k as much as possible. When k = 1, the MfIB degenerates to the original IB method, which indicates that the MfIB is a general framework for multiple feature variables extension of the IB method. The objective function of MfIB is formulated as

where I (T ; X) measures the compactness of the new representation T, λ1 · I (T ; Y 1 ) + · · · + λk · I (T ; Y k ) measures the preserved relevant information. β ≥ 0 is the balance parameter controlling the trade-off between compression and information preservation. λi ≥ 0(1 ≤ i ≤ k) are trade-off parameters to balance the influence among different feature variables.

From the objective function (4), we can see that the multiple feature variables are embedded into the IB framework. Thus, the MfIB can simultaneously process multiple types of features and mine the underlying patterns hidden in the data X from multiple cues. To analyze the data, the number of clusters M is much less than the original data size |X| (i.e. M ≪ |X|, which implies a significant compression. In this paper, we only concentrate on maximally preserving the relevant feature information λ1 · I (T ; Y 1 ) + · · · + λl · I (T ; Y k ), and set β = ∞. Then we rewrite the objective function of MfIB as

Our remaining task is to maximize the value of the objective function Equation (5). However, maximizing Equation (5) is not an easy task, since it is non-convex and there are no good solutions currently to directly optimize this objective function. In this work, we only consider the "hard" clustering, where the value of p(t|x) is either 0 or 1. Thus, the task of MfIB becomes to find an optimal partition of X, which should maximally preserve the information in objective function (5). To realize this, we will adopt a sequential "drawand-merge" optimization procedure [Slonim et al., 2002] to optimize the objective function, which is guaranteed to converge to a local maximum of the information.

3.2 Optimization for MfIB

The sequential "draw-and-merge" procedure starts with a random partition of X into M clusters. At each step, a single x ∈ X is "drawn" from its current cluster told and is represented as a new single cluster. Now, we have M + 1 clusters. To ensure that the number of clusters is M, we must "merge" x into one of the clusters. The goal of the algorithm is to maximize the objective function (5), so each "draw-and-merge" procedure should improve the value of objective function L in (5). Therefore, we must choose the best cluster tnew for x to be merged. In the following, we will give the solution to this problem. First, we have the following proposition.

Proposition 1. : Let x be merged into cluster t and become a new cluster ˜ t, i.e. {{x}, t} ⇒ ˜ t. Then

where 1 ≤ i ≤ k.

The basic question in sequential "draw-and-merge" process is of course which cluster x should be merged into at each step. The value of objective function (5) is changed when x is drawn from its current cluster or merged into one of clusters. Let Lold and Lmid denote the value of objective function (5) before and after the draw step of x. Let Lnew denote the value of (5) after x is merged into some cluster t.

Now, we calculate the difference between the values of Lmid and Lnew , which is also called the merge cost dL({x}, t) in our work.

where

Using Proposition 1, we obtain

ΔI i =

where

is the Jensen-Shannon divergence [Cover and Thomas, 1991],

In this paper, we use JSi to denote JS[p(Y i |x), p(Y i |t)] for simplicity. Similar analysis will yield

Because JSi ≥ 0 [Cover and Thomas, 1991], dL({x}, t) ≥ 0. Therefore, when some x is merged into one of clusters, there must be some information lost. To maximally preserve information, in the merging step, we will choose the cluster that makes the minimal loss of information. That is x will be merged into the cluster tnew such that tnew = argmint∈T dL({x}, t). The details of MfIB algorithm is shown in Algorithm 1.

Algorithm 1 The Multi-feature Information Bottleneck Algorithm: MfIB

• 1: Input: Joint distributions p(X, Y 1 ), · · · , p(X, Y k ), trade-off parameters λ1 , · · · , λk , number of clusters M.
• 2: Output: A partition T of X into M clusters.
• 3: Initialize:
• 4: T ←Random partition of X intoM clusters;
• 5: Procedure:
• 6: repeat
• 7: for For every x ∈ X do
• 8: Remove x from current cluster t(x);
• 9: For data point x, calculate merge costs dL({x}, t) of all possible reassignments of x to different clusters based on Equation (8);
• 10: Merge x into cluster tnew such that tnew = argmint∈T dL({x}, t);
• 11: end for
• 12: until Convergence

In Algorithm 1, each "draw-and-merge" iteration will merge x into the cluster tnew such that tnew = argmint∈T dL({x}, t), so this step will improve the value of object function (5). For each Yi, I (T ; Yi) ≤ I (X; Yi), so the value of objection function (5) is upper bounded. Therefore, MfIB algorithm will converge in a finite number of iterations. Note that, although MfIB algorithm is able to increase the value of (5), it is only able to converge to a local maximum of the information in Equation (5). Finding the global optimal solution is NP-hard.

3.3 Complexity Analysis

We now analyze the computational cost of our proposed MfIB algorithm showed in Algorithm 1. At step 9, we should calculate dL({x}, t) for every t which takes O(M (|Y 1 | + · · · + |Y k |)). The time complexity of our algorithm is O(LM|X |(|Y 1 |+ · · · +|Y k |)), where L is the number of repetitions that should be performed over X until convergence is attained. In the following experiments, we will show that MfIB algorithm will take a few numbers of repetitions to coverage a local optimal value of objective function (5). Usually, the number of clusters M can be considered as constant. So the time complexity of MfIB is O(|X|(|Y 1 | + · · · + |Y k |). Considering space complexity, the MfIB algorithm needs to store all the joint distributions p(X, Y i ). Thus, the space complexity is O(|X||Y 1 | + · · · + |X||Y k |). This indicates that the time complexity and the space complexity of MfIB algorithm are liner on the input.

4 Experiments

In this section, we evaluate our proposed MfIB algorithm on the unsupervised image categorization task, and show the effectiveness of MfIB.

4.1 Image Data Sets

Seven benchmark image data sets, soccer [Weijer and Schmid, 2006], MSRC [Winn et al., 2005], Sports events [Li and Li, 2007], 17flwoers [Nilsback and Zisserman, 2006], dslr, webcam and amazon [Saenko et al., 2010], are employed to validate MfIB algorithm. The corresponding details are described in Table 1. It should be noted that the categories of the data sets used in this paper vary from 7 to 31, and the sizes of the images vary from 240 to 2813. So the tasks of categorizing them without any supervision are very challenging.

4.2 Image Preprocessing

For data preprocessing, we use the "Bag-of-Words" (BoW) model to represent images in our experiments, which is widely used in the field of unsupervised image classification [Sivic et al., 2005; Lou et al., 2010]. The construction of BoW model can be implemented through three steps, (1) Detecting and representing local patches for each image; (2) Building a visual vocabulary by vector quantization; (3) Mapping the descriptors into the vocabulary and representing each image as a histogram.

Finally, each image is transformed to a feature vector, which contains the occurrence number of the individual visual words in the image. At the first step of BoW model, we need extract local features from the images. There are many local feature extraction techniques to extract multiple cues information (such as color, shape and texture information) from images in the field of computer vision. Choosing one appropriate feature extraction method for the data set is not an easy task. While the color information is crucial to discriminate players from two sport teams, the shape is essential to separate oranges from bananas. In general, people want to combine multiple cues to discriminate the categories [Nilsback and Zisserman, 2006; Fernando et al., 2012]. We adopt the MfIB to combine multiple cues of features. In this framework, one feature variable Y i is used to represent one cue of features and multiple aspects' information is combined to discriminate the categories. Thus we can use the MfIB algorithm to categorize the images frommultiple cues. In this paper, we adopt three techniques SURF [Bay et al., 2008], Color Attention [Khan et al., 2009] and TPLBP [Wolf et al., 2008] to extract local features from images in the cues of local shape, color and texture respectively. Each feature type has its own visual vocabulary with the size of 1000 in the second step of BoW.

4.3 Evaluation Criterion

In this paper, we employ the clustering accuracy (AC) [Cai et al., 2009] to evaluate the performance of different methods, which is defined as:

where ti denotes the cluster assignment of xi, li is the ground truth label of xi, and n is size of the data. The delta function δ(x, y) equals 1 if x = y and equals 0 otherwise. The permutation function map(ti) maps each cluster assignment ti to the equivalent label provided by the data corpus.

4.4 Experimental Results and Analysis

To alleviate the influence caused by random partition, we run each algorithm 10 times, each with a different random initialization. We report the average clustering accuracy and standard deviation. The number of categories M is set to be identical with number of real categories on each data set.

Comparison between original IB and MfIB

The original IB method can only process one feature variable. In this paper, we extend the original IB to MfIB, which can simultaneously process multiple feature variables. In this section, we will do the following experiments to compare the performance of MfIB algorithm with original IB algorithm [Slonim et al., 2002].

• We run the IB algorithm on each type of features and get three results. Each result reflects the patterns extracted from one cue.
• We simply concatenate three types of features as one combined type of features with the vocabulary size of 3000 and run the IB algorithm on the combined features.
• We run the proposed MfIB algorithm simultaneously on three types of features.

Note that, the second comparison is a late feature fusion method [Nilsback and Zisserman, 2006] and the combined features are treated as the instances of one discrete variable in the original IBmethod. It is different fromMfIB.

The evaluation results on the data sets are illustrated in Table 2, from which we have the following observations. (1) The performances of the original IB algorithm on the three individual feature variables are different. The shape feature (SURF) attains the best results on webcam and dslr data sets, the color information performs the best results on soccer and 17flowers data sets, while the MSRC and sports data sets gain the best results by texture features. This phenomenon demonstrates that for different tasks of unsupervised image categorization, none of feature types have the consistent power to perfectly discriminate the categories resided in the images. So, for the task of image categorization, it is not a wise choice to use only one type of features. (2) By simply concatenating three types of features, the average performance is improved compared with one type of features. However, for some data sets, such as MSRC, sports and amazon, the performances on the combining features are either equally matched with or inferior to the performances of IB algorithm on TPLBP features. Therefore, simply combining features can't consistently improve the performance compared with only one type of features. (3) By integrating three types of features, the proposed MfIB algorithm can clearly improve the performances on all data sets compared with the original IB algorithm. Even though the performances of MfIB algorithm and IB algorithm on the combined features are comparatively the same on webcam and dslr data sets, the proposed MfIB algorithm can consistently improve the performance compared with the best results on three individual type features.

Comparison with the state-of-the-art unsupervised image categorization methods

The works presented on [Sivic et al., 2005] and [Lou et al., 2010] have demonstrated the effectiveness of PLSA and IB algorithms on the task of unsupervised image categorization. In this section, we compare our MfIB algorithm with the above two state-of-the-art unsupervised image categorization methods. The comparative results are presented in Table 3, additionally with the results of k-means. From the results, we can see that the MfIB can get more promising results than the state-of-the-art image categorization methods PLSA and IB because our method exploits multiple feature variables simultaneously.

Convergence of MfIB algorithm

Figure 2 shows the repetitions of MfIB algorithm on the seven image data sets. Note that, the values of objective function (5) increase monotonically with each repetition. We also observe that 20 iterations are enough for convergence on all our data sets.

5 RelatedWork

This work extends the original IB method [Tishby et al., 1999] to MfIB, which can simultaneously deal with multiple feature variables and analyze the data from multiple feature variables. Multivariate Information Bottleneck [Slonim et al., 2006] is a general principled framework for multivariate extensions of the IB method. However, it merely works on a single modality setting and thus is not adequate for multi-feature clustering task. In our work, we extend the original work on Multivariate IB framework into a multi-feature scenario, which fully takes advantages of the properties of IB method while providing a novel solution to multiple feature clustering task. Besides, the work presented in [Gao et al., 2007] concentrates on multi-view clustering, where each clustering result, generated by one type of features, is treated as one view and the final clustering result is an ensemble results from these views. Differently, our MfIB framework directly takes multiple features as input and tries to fully leverage the correlative information across features.

There are many works in the field of machine learning [Cui et al., 2010] and computer vision [Nilsback and Zisserman, 2006; Fernando et al., 2012] to cope with the problem of multiple feature types. But most of them need the supervision, i.e. the class label information, to help the corresponding algorithms cope with the multiple sources of features. Note that, MfIB is an unsupervised learning method.

6 Conclusions

We have extended the original IB to the MfIB, which aims to extract the data patterns from multiple feature variables. Instead of maximally preserving the information of only one feature variable, the MfIB tries to maintain the information of all the feature variables while X is compressed to T. Therefore, the compressing results can simultaneously reflect the hidden patterns provided by multiple types of features, and the multiple feature variables can complementally help each other to find the patterns which are much closer to the real patterns resided in the data. The experiments on seven challenging benchmark image data sets have confirmed the effectiveness of the proposed MfIB algorithm.

Acknowledgements

This work is supported by the National Natural Science Foundation of China under grant No. 61170223, Joint Funds of the National Natural Science Foundation of China under grant No. U1204610.