Local Search for Balanced Submodular Clusterings

1 Introduction

The clustering of objects/data is a very important problem found in many machine learning applications, often in other guises such as unsupervised learning, vector quantization, dimensionality reduction, image segmentation, etc. The clustering problem can be formalized as follows. Given a finite set S, and a criterion function Jk defined on all partitions of S into k parts, find a partition of S into k parts {S1, S2, . . . , Sk} so that Jk ({S1, S2, . . . , Sk}) is maximized. The number of k-clusters for a size n > k data set is roughly kn/k! [1] so exhaustive search is not an efficient solution. In [9], it was shown that a broad class of criteria are Submodular (defined below), which allows the application of recently discovered polynomial time algorithms for submodular function minimization to find the optimal clusters. Submodularity, a formalization of the notion of diminishing returns, is a powerful way of modeling quality of clusterings that is rich enough to model many important criteria, including Graph Cuts, MDL, Single Linkage, etc. Traditionally, clustering algorithms have relied on computing a distance function between pairs of objects, and hence are not directly capable of incorporating complicated measures of global quality of clusterings where the quality is not just a decomposable function of individual J. Bilmes†

∗Part of this work was done while this author was at the University of Washington and was supported in part by a Microsoft Research Fellowship.

†This work was supported in part by NSF grant IIS-0093430 and an Intel Corporation Grant.

Dept. of Electrical Engg., University of Washington Seattle WA 98195

bilmes@ee.washington.edu

distances. Submodularity allows us to model these decomposable criteria, but also allows to model more complex criteria. However one problemwith all of these criteria is that they can be quite sensitive to outliers. Therefore, algorithms which only optimize these criteria often produce imbalanced partitions in which some parts of the clustering are much smaller than others. We often wish to impose balance constraints, which attempt to tradeoff optimizing Jk with the balance constraints. In this paper we show that the results that Patkar and Narayanan [8] derived for Graph Cuts are broadly applicable to any submodular function, and can lead to efficient implementations for a broad class of functions that are based of bipartite adjacency. We apply this for clustering words in language models.

2 Preliminaries and PriorWork

Let V be a ground set. A function Γ : 2V → R, defined on all subsets of V is said to be increasing if Γ(A) ≤ Γ(B) for all A ⊆ B. It is said to be submodular if Γ(A) + Γ(B) ≥ Γ(A∪B) +Γ(A∩B), symmetric if Γ(A) = Γ(V \A), and normalized if Γ(φ) = 0. For any normalized increasing submodular function Γ : 2V →R+, the function Γc : 2V →R+ defined by Γc(X) = Γ(X)+Γ(V \X)-Γ(V ) is a symmetric submodular function. This function is called the connectivity function of Γ, and is normalized, symmetric and submodular. We can think of Γc(X) = Γc(V \ X) = Γc(X, V \ X) as the cost of "separating" X from V \ X. Because Γc is submodular, there are polynomial time algorithms for finding the non-trivial partition (X, V \ X) that minimizes Γc. Such normalized symmetric submodular functions arise naturally in many applications. One example is the widely used Graph Cut criterion.

Here, the set V to be partitioned is the set of vertices of a graph G = (V,E). The edges have weights we : E → R+ which is proportional to the degree of similarity between the ends of the edge. The graph cut criterion seeks to partition the vertices into two parts so as to minimize the sum of the weights of the edges broken by the partition.

For any X ⊆ V , let

γ(X) = set of edges having at least one endpoint in X

δ(X) = set of edges having exactly one endpoint in X

For example, if X = {1, 2, 5} (the red/darkshaded set in Figure 1-left), then γ(X) = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (5, 4)} (the set of edges which are either dashed/red or solid/black) and δ(X) is the set of solid/black edges {(1, 3), (2, 3), (2, 4), (5, 4)}. It is easy to verify that for any (positive) weights that we assign to the edges wE : E → R+ , the function Γ(X) = wE(γ(X)) = ∑e∈γ(X) wE(e) is a normalized increasing submodular function, and hence the function

is a normalized symmetric submodular function 1 . We will refer to this as the Undirected Graph Cut criterion.

In this paper, we will be particularly interested in a slightly different function, which also falls into this framework. V will be the left part of a bipartite graph, and F the right part of the graph. We think of V as objects, and F a set of features that the objects may posses. For example, V might be a vocabulary of words, and F could be features of those words (including possibly the context in which the words occur). Other examples include diseases and their symptoms, species and subsequences of nucleotides that occur in their genome, and people and their preferences.

We construct a bipartite graph B = (V, F, E) with an edge between an object v ∈ V and a feature f ∈ F if the object o has the feature f. We assign positive weights wV : V →R+ and wF : F → R+. The weight wF (f) measures the "importance" of the feature f , while the weight wV (v) is used to determine how balanced the clusterings are. In some applications, such as ours, there is a natural way of assigning weights to V and F (probability of occurrence for example). In this case, for X ⊆ V , we can set

where ne(·) is the graph neighbor function. In other words, if X bi-partitions V into sets of two types (X and V \ X) of objects, then γ(X) is the set of features with neighbors of "type X", and δ(X) is the set of features with neighbors of both types of object. We let Γ(X) = wF (γ(X)) =

1 we use the same notation for the function wE : E → R+ defined on edges and the function wE : 2E → R+, the modular extension defined on all subsets

∑f∈γ(X) wF (f), which can be shown to be a normalized increasing submodular function for any positive weight function wF : V →R+, and Γc(X) = Γ(X)+Γ(V \X)-Γ(V ) measures the weight of the common features. For the example shown in Figure 1-right, if we take X = {1, 2, 5} (the red/dark-shaded set), then γ(X) = {a, b, d, e}, and δ(X) = {b, d, e}. We will refer to this as the Bipartite Adjacency Cut criterion.

Because Γc is symmetric and submodular, we can use Queyranne's algorithm [4] to find the optimal partition in time O(|V |3 ). There are two problems with this approach. First, since the algorithm scales as |V |3 , it becomes impractical when |V | becomes very large. A second problem is that the criterion is quite sensitive to outliers, and therefore tends to produce imbalanced partitions in which one of the parts is substantially smaller than the others. For example, if we have a graph in which one vertex is very weakly connected to the rest of the graph, then the graph cut criterion might produce a partitioning with just this vertex in a partition by itself. For many applications it is quite desirable to produce clusters that are somewhat balanced. There is some inherent tension between the desire for balanced clusters, and the desire to minimize the connectivity between the clusters Γc(X): we would like to minimize the connectivity Γc(X), while making sure that the clustering is balanced. There are two similar criteria that capture this optimization goal

The two criteria are clearly closely related. Unfortunately, minimizing either criterion is NP-complete [11], and so we need to settle for solutions which cannot necessarily be shown to be optimal. The normalized cut is also closely related to spectral clustering methods [6], and so spectral clustering has been used to approximate normalized cut. In this paper, we present a local search approach to approximating normalized cut. The advantage of local search techniques is that they allow us to utilize partial solutions (such as a preexisting clustering of the objects) which is useful in dynamic situations. Further, since local search techniques produce a sequence of solutions, each one better than the last, they serve as anytime algorithms. That is, in time-constrained situations, we can run them only for as much time as available. The local search strategy we employ will allow us to make very strong guarantees about the final solution produced. Such a local search technique was originally proposed by Patkar and Narayanan [8] for producing balanced partitions for the Graph Cut criterion. In this paper, we show that the results in his paper are equally applicable for any submodular criterion. It should be noted that the applicability of these general techniques to any submodular function does not necessarily make it practical. One of the contributions of [8] was to show that it could be done efficiently for the Graph Cut criterion via a reduction to a flow problem. In this problem, we show that the Bipartite Adjacency criteria can also be solved in a similar efficient fashion by reducing to a (different) flow problem.

3 Local Search and the Principal Partition

In a local search strategy, we generate a sequence of solutions, each solution obtained from the previous one by a (sometimes small) perturbation. For the case of clustering or partitioning, this amounts to starting with a (bi)partition V = V1 ∪ V2, and changing this partition by picking one of a set of moves. This set of moves that we will consider is going from the bipartition {V1, V2} to the bipartition {U1, U2}, where the new partition is obtained by moving some elements from one partition to the other. For example, we could go from {V1, V2} to {V1 \ X, V2 ∪ X}, where X ⊆ V1. This amounts to moving the elements in X from V1 to V2. The key to a local search strategy is have a good way of generating the next move (or to pick a X ⊆ V1 so that moving X to the other side will improve the objective function). In this section, we show that when Γc is a submodular function, then the Principal Partition of the submodular function (to be defined below) can be used to compute the best local move in polynomial time. Moreover, for the specific application we discuss in this paper, we can actually compute this fast even for very large data sets.

So, for Figure 1-left, if we assign a weight of 1 to all edges and all vertices, (so wE ≡ 1 and wV ≡ 1), and let V1 be the set of blue/light nodes and V2 be the set of red/shaded nodes. Then

GGain (X) measures the amount of change in the partition cost Γc (V1) (ignoring the balance constraints). Now, we are really interested in the change in normCut (V1, V2), which incorporates the balance constraint. μ(G, V1) can be seen to be related to the ratio/normalized cut, and so we use solutions to μ(G, V1) to find the set of moves for the local search algorithm. In this section, we present some results which relate changes in normCut (V1, V2) to the principal partition of the submodular function Γc, and for this, μ(G, V1) will play a central role. The principal partition of a submodular function Γc consists of solutions to minX⊆V1 [Γc (X) -λ · wV (X)] for all possible values of λ ≥ 0. It can be shown [7; 8] that the solutions for every possible value of λ can be computed in polynomial time (in much the same way as the entire regularization path of a SVM can be computed [12]). We will give specifics of the computation procedure in Section 4. In this section, we will present results which will relate the solutions of minX⊆V1 [Γc (X) - λ · wV (X)] with solutions to μ(G, V1) = maxφ̸=X⊆V1 averageGain (X).

The following proposition was proven by [Narayanan 2003] for the Graph Cut criterion, but generalizes immediately for an arbitrary increasing submodular function Γc. In particular, this is applicable to the problemwe are interested in which the submodular function is derived from the bipartite graph.

Proposition 1 (Narayanan 2003, Proposition 7). Let (V1, V2) is a bipartition of V (so V = V1 ∪V2, and V1 ∩V2 = φ), and let φ ̸= U ⊂ V1 be a proper subset of V1 satisfying

Then ratioCut (V1 \ U, V2 ∪ U) < ratioCut (V1, V2)

Proof. By assumption,

In particular, for X = V1 we have

Since Γc(V1 \ V1) = 0, we have

Observe that if ab ≤ a-c b-d , then ab - ad ≤ ab - bc and so ab ≥ cd . Therefore, we get

Dividing both sides by wV (V2), we get

We have a similar (but not strict) result for normalized cuts.

Corollary 2. Under the same assumptions of the previous proposition, we have

Proof. Since wV (V1) > wV (V1 \U), and fromEquation 1, it follows that Γc (V1) > Γc (V1 \ U). We consider two cases. First, assume that wV (V1) ≤ wV (V2). In this case, from the normCut definition and Equation 1,

Hence

Hence

For the remaining case, assume that wV (V1) ≥ wV (V2). Again using Equation 1, we have

It follows that

The two previous results show that if we can find a nontrivial solution to maxφ̸=X⊆V1 averageGain (X), then we can find a local move that will improve the normalized cut and the ratio cut. Ideally, we want to show that if it is possible to improve the normalized cut (or the ratio cut), we can in fact find a local move that will improve the current solution. Unfortunately we do not have such a result, but we have one that is slightly weaker which serves as a partial converse.

Proposition 3. Suppose that φ ̸= U ⊂ V1 satisfies α2 · normCut (V1, V2) ≥ normCut (V1 \ U, V2 ∪ U) where α = wV (V2) wV (V2∪U) . Then Γc(V1\U) wV (V1\U) ≤ Γc(V1) wV (V1) .

Now, the previous result shows the existence of a set which can be moved to the other side which will let us improve the current value of the normalized cut. However, an existence result is not enough. We need to be able to compute this set. The following theorem gives a connection between this set and the Principal Partition of the Bipartite Adjacency function. Since we can compute the principal partition, we can explicitly compute a local move which will improve the normalized cut.

Proposition 4 (Narayanan, 2003, Proposition 6). λ = μ(G, V1) iff there is a proper subset Z ⊂ V1 such that

Proof. Suppose that λ = μ(G, V1), Then there is a φ ̸=W ⊆ V1 so that

with equality holding for X = W. It follows that

because wV is always positive. Hence

Because the left hand side is a constant, it follows that

Note that equality holds for X = W. In particular, for Z = V1 \ W, we get

Therefore, by taking Z = V1 \ W, the forward direction follows. For the reverse direction, suppose that for some λ > 0, we have

Then by taking W = V1 \ X, we get

Therefore,

because W ̸= 0 and wV > 0, we have

Therefore, if we can compute solutions to minX⊆V1 [Γc (X) -λ · wV (X)], then we can find a local move that will let us improve the normalized cut. In the next section, we show how we can compute these solutions efficiently for our application.

4 Computing the Principal Partition

Proposition 1 tells us if we have a partition (V1, V2), then if we can find a set φ ̸= U ⊆ V1 satisfying μ(G, V1) = Γc(V1)-Γc(V1\U) wV (U) , then we can improve the current partition by moving U from V1 to the other part of the partition. Proposition 4 tells us that we can find such a subset by finding λ so thatmin

While this can be done in polynomial time for any submodular function [7; 8], in this section, we show that it can be done especially efficiently in our case by reducing it to a parametric flow problem. For parametric flow problems, we can use the results of [2], to solve the flow problem for all values of the parameter in the same time required to solve a single flow problem. Now, for a fixed parameter λ, we can compute minX⊆V1 [Γc (X) - λ · wV (X)] by solving a max flow problem on the network which is created as follows. Add a

source node S, and connect S to all the nodes in v ∈ V with edge capacity λ · wV (v). Add a sink node T , and connect all the nodes in f ∈ F to T , with capacity wF (f) as shown in Figure 2. The remaining edges (from the original graph) have infinite capacity. By the max-flow/min-cut theorem, every flow corresponds to a cut, and so we just examine the cuts in the network. It is clear that the min cut must be finite (since there is at least one finite cut), and hence the only edges that are part of the cut are the newly added edges (which are adjacent to either S or T). Hence if a vertex v ∈ V is on one side of the cut, all its neighbors must be as well. Therefore, every cut value is of the form wv(V \ X) + wF (γ(X)) = λ · wV (V ) - λ · wV (X) + wF (X). Minimizing this function is equivalent to minimizing wF (γ(X)) - λ · wV (X). We can compute this for every value of λ by using the parametric flow algorithmof [2]. In [2], it is also shown that there are distinct solutions corresponding to at most |V | values of λ, and further, the complexity of finding the solutions for all values of λ is the same as the complexity of finding the solution for a single value of λ (namely that of a flow computation in this network). This algorithm returns the values of λ corresponding to the distinct solutions along with the solutions. Since there are at most |V | distinct solutions, each one of them can be examined to find the one which results in the maximum improvement of the current partition (i.e., the local move that improves the normalized cut value by the most). Since the complexity of the flow computation is O(|V |2 |E|), the final search through all the distinct solutions does not add to the complexity, and hence the total time required for computing a local improvement is O(|V |2 |E|).

5 Word Clustering in Language Models

Statistical language models are used in many applications, including speech recognition and machine translation, and are often based on estimating the probabilities of n-grams of words: Pr(w1:k) = ∏ki=1 Pr(wi|w1:i-1) ≈ ∏n-1 i=1 Pr(wi|w1:i-1) · ∏ki=n Pr(wi|wi-n+1:i-1) The problem is that the number of n-grams grows as |W|n, where W is the set of words in the vocabulary. As this grows exponentially with n, we cannot obtain high-confidence statistical estimates using naive methods, so alternatives are needed in order to learn reliable estimates with only finite size training corpora. Brown et al. [3] suggested clustering words, and then constructing predictive models based only on word classes: If c(w) is the class of word w, then we approximate the probability of the word sequence w1:k by Pr(w1:k) ≈ ∏n-1 i=1 Pr(wi|c(wi-1), . . . , c(w1)) · ∏ki=n Pr(wi|c(wi-1), . . . , c(wi-n+1)). In this case, the number of probabilities needing to be estimated grows only as |C|n-1 · |W|. Factored language models [10] generalize this further, where we use Pr(wi|wi-1, c(wi-1), . . . ,wi-n+1, c(wi-n+1)) - note that conditioning on both wi-1 and c(wi-1) is not redundant, as backoff-based smoothing methods are such that if, say, an instance of wi,wi-1 was not encountered in training data, an instance of wi, c(wi-1) might have been encountered via some other word w′ ̸= wi-1 such that wi,w′ was encountered, and with c(w′ ) = c(wi-1). Often, we can construct such models in a data-dependent way.

The quality of these models depends crucially on the quality of the clustering. In this section, we construct a bipartite adjacency graph, and use the algorithm described above for generating the clusters. While the algorithm described in this paper only generates a partition with two clusters, we can apply it recursively (in the form of a binary tree) to the generated clusters to generate more clusters (stopping only when the number of elements in a cluster goes below a prescribed value, or if the height of the tree exceeds a pre-specified limit). The bipartite graph we use is constructed as follows: V and F are copies of the words in the language model. We connect a node v ∈ V to a node f ∈ F if the word f follows the word v in some sentence. Ideally, we want to put words which have the same set of neighbors into one cluster. The model as described ignores the number of occurrences of a bigram pair. However, we can easily account for numbers by replicating each word f ∈ F to form f1, f2, . . . , fk, where a word v ∈ V is connected to f1, f2, . . . , fr if the bigram vf occurs r times in the text. It is very simple to modify the network-flow algorithm to solve networks of this type in the same complexity as the original network. The goal is to partition the words into clusters so that words from different clusters share as few neighbors as possible (and words from the same cluster share as many neighbors as possible). Observe that this criterion does not require us to compute "distances" between words as is done in the clustering method proposed by Brown et al. [3]. The advantage of our scheme over a distance based approach is that it more naturally captures transitive relationships.

To test this procedure, we generated a clustering with 497 clusters on Wall Street Journal (WSJ) data from the Penn Treebank 2 tagged (88-89) WSJ collection. Word and (human generated) part-of-speech (POS) tag information was extracted from the treebank. The sentence order was randomized to produce 5-fold cross validation results using (4/5)/(1/5) training/testing sizes. We compared our submodular clustering with both the manual POS clusters, and also the clustering procedure described in Brown et al. [3], as shown in Table 1. We note that this particular bipartite model is designed specifically for bigram n = 2 models, and not surprisingly, we get a significant improvement in perplexity for such models. We find a non-significant improvement in the trigram case, but the non-significance is expected as it shows the importance of a correct model - it would be straight-forward, however, when clustering wt-1 to use a different bipartite graph, where F contains not only wt but also wt-2, to cluster wt-1 as a predictor for wt relative to the context in which it will be used in the trigram. In this fashion, a separate clustering could also be done for wt-2. This shows the generality of our technique.