extfieldsofstudy:
Computer Science
Mathematics

text:
Multi-view constrained clustering with an incomplete mapping between views

Multi-view learning algorithms typically assume a complete bipartite mapping between the different views in order to exchange information during the learning process. However, many applications provide only a partial mapping between the views, creating a challenge for current methods. To address this problem, we propose a multi-view algorithm based on constrained clustering that can operate with an incomplete mapping. Given a set of pairwise constraints in each view, our approach propagates these constraints using a local similarity measure to those instances that can be mapped to the other views, allowing the propagated constraints to be transferred across views via the partial mapping. It uses co-EM to iteratively estimate the propagation within each view based on the current clustering model, transfer the constraints across views, and then update the clustering model. By alternating the learning process between views, this approach produces a unified clustering model that is consistent with all views. We show that this approach significantly improves clustering performance over several other methods for transferring constraints and allows multi-view clustering to be reliably applied when given a limited mapping between the views. Our evaluation reveals that the propagated constraints have high precision with respect to the true clusters in the data, explaining their benefit to clustering performance in both single- and multi-view learning scenarios.

Introduction
Using multiple different views often has a synergistic effect on learning, improving the performance of the resulting model beyond learning from a single view. Multi-view learning is especially relevant to applications that simultaneously collect data from different modalities, with each unique modality providing one or more views of the data. For example, a textual field report may have associated image and video content, and an Internet web page may contain both text and audio. Each view contains unique complementary information about an object; only in combination do the views yield a complete representation of the original object. Concepts that are challenging to learn in one view (e.g., identifying images of patrons at an Italian restaurant) may be easier to recognize in another view (e.g., via the associated textual caption), providing an avenue to improve learning. Multi-view learning can share learning progress in a single view to improve learning in the other views via the direct correspondences between views.
Current multi-view algorithms typically assume that there is a complete bipartite mapping between instances in the different views to represent these correspondences, denoting that each object is represented in all views. The predictions of a model in one view are transferred via this mapping to instances in the other views, providing additional labeled data to improve learning. However, what happens if we have only a partial mapping between the views, where only a limited number of objects have multi-view representations?
This problem arises in many industrial and military applications, where data from different modalities are often collected, processed, and stored independently by specialized analysts. Consequently, the mapping between instances in the different views is incomplete. Even in situations where the connections between views are recorded, sensor availability and scheduling may result in many isolated instances in the different views. Although it is feasible to identify a partial mapping between the views, the lack of a complete bipartite mapping presents a challenge to most current multi-view learning methods. Without a complete mapping, these methods will be unable to transfer any information involving an isolated instance to the other views.
To address this problem, we propose a method for multi-view learning with an incomplete mapping in the context of constrained clustering. Constrained clustering (Basu et al., 2008) is a class of semi-supervised learning methods that cluster data, subject to a set of hard or soft constraints that specify the relative cluster membership of pairs of instances. These constraints serve as background information for the clustering by specifying instance pairs that belong in either the same cluster (a must-link constraint) or different clusters (a cannot-link constraint). Given a set of constraints in each view, our approach transfers these constraints to affect learning in the other views. With a complete mapping, each constraint has a direct correspondence in the other views, and therefore can be directly transferred between views using current methods. However, with a partial mapping, these constraints may be between instances that do not have equivalences in the other views, presenting a challenge to multi-view learning, especially when the mapping is very limited.
This article proposes the first multi-view constrained clustering algorithm that considers the use of an incomplete mapping between views. Given an incomplete mapping, our approach propagates the given constraints within each view to pairs of instances that have equivalences in the other views. Since these propagated constraints involve only instances with a mapping to the other views, Fig. 1. An illustration of multi-view constrained clustering between two disjoint data views: text and images. We are given a very limited mapping between the views (solid black lines) and a set of pairwise constraints in the images view: two must-link constraints (thick solid green lines) and one cannot-link constraint (thick dashed red line). Based on the current clustering, each given constraint is propagated to pairs of images that are in close proximity to the given constraint and can be mapped to the text view. These propagated must-link and cannot-link constraints (thin solid green and dashed red lines, respectively) are then directly transferred via the mapping to form constraints between text documents and influence the clustering in the next co-EM iteration. (Best viewed in color.) they can be directly transferred to instances in those other views and affect the clustering. The weight of each propagated constraint is given by its similarity to the original constraint, as measured by a local radial basis weighting function that is based on the current estimate of the clustering. This process is depicted in Figure 1. Our approach uses a variant of co-EM (Nigam and Ghani, 2000) to iteratively estimate the propagation within each view, transfer the constraints across views, and update the clustering model. Our experiments show that using co-EM with constraint propagation provides an effective mechanism for multiview learning under an incomplete mapping between views, yielding significant improvement over several other mechanisms for transferring constraints across views. We also demonstrate that constraint propagation can improve clustering performance even in single-view scenarios, further demonstrating the precision of the inferred constraints and the utility of constraint propagation.
We first survey related work on constrained clustering and multi-view learning in Section 2, and then present details in Section 3 on the specific constrained clustering and co-EM algorithms on which we base our approach. Section 4 describes our problem setting and mathematical notation. We develop our multiview constrained clustering algorithm in Section 5, describing the constraint propagation and clustering processes in Sections 5.1-5.2, its extension to more than two views in Section 5.3, and implementation efficiency in Section 5.4. Section 6 evaluates the performance of our approach in several multi-view scenarios (Section 6.3), and then analyzes the performance of constraint propagation inde-pendently through traditional single-view (Section 6.4) clustering. We conclude with a brief discussion of constraint propagation and future work in Section 7.

Related Work
Our approach combines constrained clustering with multi-view learning. In this section, we briefly review related work on both of these topics.

Constrained clustering
Constrained clustering algorithms (Basu et al., 2008) incorporate side information to influence the resulting clustering model. Most constrained clustering research has focused on using side information given as a set of constraints that specify the relative cluster membership of sets of instances. Typically, these algorithms use both must-link constraints, which specify sets of instances that belong in the same cluster, and cannot-link constraints, which specify instances that belong in different clusters. Depending on the algorithm, this labeled knowledge may be treated as either hard constraints that cannot be violated, or soft constraints that can be violated with some penalty.
These types of constraints have been successfully integrated into a wide variety of clustering methods (Basu et al., 2008), including K-Means, mixturemodels, hierarchical clustering, spectral clustering, and density-based techniques. Although our approach can use most current constrained clustering algorithms, we focus on using K-Means variants and so concentrate our survey on these methods. COP-Kmeans (Wagstaff et al., 2001;Wagstaff, 2002), the first constrained clustering algorithm based on K-Means, performs K-Means clustering while ensuring that all constraints are honored in the cluster assignments. PCK-Means  performs soft constrained clustering by combining the K-Means objective function with penalties for constraint violations. The MPCK-Means algorithm (Bilenko et al., 2004) builds on PCK-Means to learn the distance metrics for each cluster during the clustering process. We use the PCK-Means and MPCK-Means algorithms as the base clustering methods in our experiments, and describe these two algorithms in more detail in Section 3.1. Kulis et al. (2009) explore the connections between several different formulations of constrained clustering, showing that semi-supervised weighted kernel K-Means, graph clustering, and spectral clustering are closely related. Based on these connections, they develop a kernel-based constrained clustering approach that can operate on either vector-or graph-based data, unifying these two areas. Domeniconi et al. (2011) propose an alternative formulation of semi-supervised clustering using composite kernels that is suitable for heterogeneous data fusion.
The models generated by PCK-Means/MPCK-Means are equivalent to particular forms of Gaussian mixtures (Bilenko et al., 2004;Basu et al., 2002), and so our work is also closely related to research in constrained mixture modeling. Shental et al. (2004) incorporate hard constraints into Gaussian mixture models using an equivalence set formulation, and Lu et al. (2005) learn a soft constrained Gaussian mixture model using constraints to influence the prior distribution of instances to clusters. More recent work has focused on incorporating constraints into nonparametric mixture models (Vlachos et al., 2009;Mallapragada, 2010).
Due to the intuitive nature of must-link and cannot-link constraints for user interaction, constrained clustering has been applied to the problem of interactive clustering, where the system and user collaborate to generate the model. Cohn et al. (2009) anddesJardins et al. (2008) present interactive approaches in which a user iteratively provides feedback to improve the quality of a proposed clustering. In both of these cases, the user feedback is incorporated in the form of constraints. This interactive process is a useful extension that could permit user knowledge to be brought into a multi-view clustering algorithm. Additionally, as we discuss in Section 7, a user could specify these constraints in one view of the data where interaction is quick and intuitive (such as images). Our multi-view clustering algorithm could then be used to automatically propagate and transfer these constraints to affect the clustering of other views where interaction may be more difficult (such as text or other data modalities). Interaction could be further improved by the use of active learning to query the users for specific constraints (Wang and Davidson, 2010;Zhao et al., 2012).

Multi-view learning
Multi-view learning was originated by Blum and Mitchell (1998) in the cotraining algorithm for semi-supervised classification. Co-training uses the model for each view to incrementally label the unlabeled data. Labels that are predicted with high confidence are transferred to the corresponding unlabeled instances in the other views to improve learning, and the process iterates until all instances are labeled. Co-training assumes independence between the views, and shows decreased performance when this assumption is violated (Nigam and Ghani, 2000). Dasgupta et al. (2001) provide a PAC generalization analysis of the co-training algorithm that bounds the error of co-training based on the observed disagreement between the partial rules. This analysis relies on the independence of the views, which is often violated in real-world domains.
As an alternative to co-training, Nigam and Ghani (2000) present the co-EM algorithm, an iterative multi-view form of expectation maximization (EM). The co-EM algorithm probabilistically labels all data and transfers those labels to the other view each iteration, repeating this process until convergence. Unlike co-training, it does not require independence between the views in order to perform well. The co-EM algorithm forms the foundation for our approach, and is described in detail in Section 3.2.
Clustering with multiple views was introduced by Bickel and Scheffer (2004), who developed a multi-view EM algorithm that alternates between the views used to learn the model parameters and estimate the cluster assignments. The typical goal of multi-view clustering is to learn models that exhibit agreement across multiple views of the data. Chaudhuri et al. (2009) develop a multi-view approach to support clustering in high-dimensional spaces. They use canonical correlation analysis to construct low-dimensional embeddings from multiple views of the data, then apply co-training to simultaneously cluster the data in these multiple lower-dimensional spaces. de Sa (2005) extends spectral clustering to a multi-view scenario, in which the objective is to minimize the disagreement between views.
In Kumar and Daumé's work, an EM co-training approach is used to perform spectral clustering within one view and use this as a constraint on the similarity graph in another view . In subsequent work, they used a regularization approach to optimize the shared clustering . In effect, these approaches are propagating the entire clustering across views, in contrast to our method, which only propagates the explicit constraints to nearby pairs of instances. Also, unlike our approach, these works assume a complete bipartite mapping between views. Other multi-view clustering variations are based on cross-modal clustering between perceptual channels (Coen, 2005) and information-theoretic frameworks (Sridharan and Kakade, 2008;Gao et al., 2007;Tang et al., 2009).
Recently, several researchers have studied ways to develop mappings between alternative views. Harel and Mannor (2011) describe a method for learning from what they refer to as multiple outlooks. Outlooks are similar to views in that they each have different feature spaces; however, there is no assumption that instances would appear in multiple outlooks. (Harel and Mannor mention the possibility of shared instances but do not present any results.) They learn an affine mapping that scales and rotates a given outlook into another outlook by matching the moments of the empirical distributions within the outlooks. This work assumes that the outlooks can be mapped to each other globally with a single affine mapping, whereas our work assumes only local, potentially nonlinear mappings between the views, based on the learned clustering structure. Quadrianto and Lampert (2011) introduce a technique for projecting multiple views into a common, shared feature space, producing a joint distance function across the views. Their work assumes that each instance appears in every view. They use a neighborhood relationship that defines "similar" instances to optimize a similarity function in the shared feature space that respects the neighborhood relationships. The problem setting in their work is rather different from ours, since they assume a complete bipartite mapping between views, and the provided input consists of neighborhood sets rather than pairwise constraints.
There has been a significant amount of recent research on applying co-training to perform clustering in relational data. These methods generally use the attributes of the objects in a relational network as one view, and the relations as another view (or as multiple views). Greene and Cunningham (2009), for example, combine text similarity (the attribute view) with co-citation data (the relational view) to identify communities in citation data. Banerjee et al. (2007) introduce a general framework for co-clustering of attributes and relations, using an approach that finds the clustering with the minimal information loss. Banerjee et al.'s framework can be applied with any single or combination of Bregman loss functions, permitting it to be applied in a variety of different contexts. Bhattacharya and Getoor (2009) show how the problem of entity resolution (identifying objects in a relational network that refer to the same entity) can be seen as a constrained clustering problem. The way in which information is combined by equating multiple objects in entity resolution can be seen as analogous to multi-view clustering, where each role that the entity plays in the relational network can be thought of as a "view" on that object.

Background
In this section, we present background on the basic methods on which our approach builds: the PCK-Means and MPKC-Means constrained clustering methods, and the co-EM algorithm.

Constrained clustering methods
Constrained clustering algorithms take as input a set of constraints C to inform the clustering process. A pairwise constraint x i , x j , w, type ∈ C denotes the relative clustering of instances x i and x j , where the non-negative weight of the constraint is given by w ∈ R + 0 (the set of non-negative real numbers) and type ∈ {must -link , cannot -link } specifies whether x i and x j belong in either the same cluster (a must-link constraint) or different clusters (a cannot-link constraint). In soft constrained clustering, w can be viewed as the penalty for violating the constraint. Throughout this article, wherever the weight or type of constraint are obvious from context, we will omit them and indicate a pairwise constraint as simply x i , x j or x i , x j , w . For convenience, we refer to the sets of all must-link and cannot-link constraints as, respectively, C ml and C cl .
As mentioned earlier, our approach can be combined with any constrained clustering method. Our current implementation supports the PCK-Means  and MPCK-Means (Bilenko et al., 2004) algorithms; we give results for both methods in Section 6. In the remainder of this section, we provide a brief overview of these methods; further details are available in the original papers.
We first describe the MPCK-Means algorithm, and then show the simplifications that yield PCK-Means. The MPCK-Means algorithm generates a kpartitioning of the data X ⊆ R d by minimizing the following objective function, which combines the K-Means model with penalties for violating must-link and cannot-link constraints: µ xi and M xi are respectively the centroid and metric of the cluster to which x i belongs, x ′ xi and x ′′ xi are the points with the greatest separation according to the M xi metric, the function 1(b) = 1 if predicate b is true and 0 otherwise, and is the Mahalanobis distance between x i and x j using the metric M. The first term of J MPCK attempts to maximize the log-likelihood of the K-Means clustering, while the second and third terms incorporate the costs of violating constraints in C.
Algorithm 1 The co-EM algorithm of Nigam and Ghani (2000) Input: first view X A of the data, second view X B of the data, and an incomplete vector of labels Y over the data. MPCK-Means uses expectation maximization (EM) to locally minimize the objective function J MPCK to generate the clustering. The E-step consists of assigning each point to the cluster that minimizes J MPCK from the perspective of that data point, given the previous assignments of points to clusters. The M-step consists of two parts: re-estimating the cluster centroids given the E-step cluster assignments, and updating the metric matrices {M h } K h=1 to decrease J MPCK . The latter step enables MPCK-Means to learn the metrics for each cluster in combination with learning the constrained clustering model. Learning a Mahalanobis metric has also been considered by Xing et al. (2003) and Bar-Hillel et al. (2005). The PCK-Means algorithm is a simplified form of this approach that minimizes the same objective function as MPCK-Means, but eliminates the metric learning aspect and assumes an identity distance metric, setting

The co-EM algorithm
Co-EM (Nigam and Ghani, 2000) is an iterative algorithm based on expectation maximization that learns a model from multiple views of data. At each iteration, co-EM estimates the model for a view and uses it to probabilistically label all of the data; these labels are then transferred to train another view during the next iteration. Co-EM repeats this process until the models for all views converge. The co-EM algorithm of Nigam and Ghani is given as Algorithm 1; note that this algorithm assumes a complete bipartite mapping between the two views in order to transfer the labels.
Unlike co-training, co-EM does not require the views to be independent in order to perform well. The co-EM algorithm also learns from a large set of data with noisy labels each iteration, in contrast to co-training, which adds few labeled instances to the training set at each iteration. For this reason, Nigam and Ghani (2000) argue that the co-EM algorithm is closer in spirit to the original framework for multi-view learning described by Blum and Mitchell (1998) than the co-training algorithm. The approach we explore in this article uses a vari-ant of co-EM to iteratively infer constraints in each view and to transfer those constraints to affect learning in the other views.

Preliminaries
Our multi-view constrained clustering approach (described in the next section) takes as input multiple views of the data X = {X A , X B , . . .}. Each view V of the data is given by a set of instances The feature set and dimensionality d V may differ between the views. We will initially focus on the case of two views, given by X A and X B , and extend our approach to handle an arbitrary number of views in Section 5.3. Within X , there are pairs of instances that correspond to different views of the same objects. We denote this connection between two instances Most other work on multi-view learning (Nigam and Ghani, 2000;Blum and Mitchell, 1998;Bickel and Scheffer, 2004;Chaudhuri et al., 2009; assumes that R A×B defines a complete bipartite mapping between the two views. We relax this assumption and consider the case in which R A×B provides only a partial mapping between the views. We also consider situations where the partial mapping is extremely limited, with many more data instances than relations between views (i.e., |R A×B | ≪ min(|X A |, |X B |)).
We also have a set of pairwise must-link and cannot-link constraints for each view V , given by cannot -link } denotes the space of all possible pairwise constraints in view V . Depending on the application, these constraints may be either manually specified by the user or extracted automatically from labeled data. Note that the constraints describe relationships between instances within a single view, while the mapping R A×B defines connections between instances in different views.

Multi-View Constrained Clustering
Our multi-view constrained clustering approach takes as input multiple views of the data X = {X A , X B , . . .}, their associated sets of pairwise constraints C A , C B , . . ., and a (potentially incomplete) mapping R U×V between each pair of different views U and V . Although we focus primarily on the case of two views A and B, we also generalize our approach to multiple views, as described in Section 5.3. The objective of our approach is to determine a k-partitioning of the data for each view that respects both the constraints within each view and the mapping between the views.
Our approach, given as Algorithm 2, iteratively clusters each view, infers new constraints within each view, and transfers those inferred constraints across views via the mapping. Through this process, progress in learning the model for one view will be rapidly transmitted to other views, making this approach particularly suited for problems where different aspects of the model are easy to learn in one view but difficult to learn in others.
The base constrained clustering algorithm is given by the CKmeans subfunction, which computes the clustering that maximizes the log-likelihood of the data

Algorithm 2 Multi-view Constrained Clustering with Constraint Propagation
Input: first view X A and constraints C A , second view X B and constraints C B , thresholds t A ∈ (0, 1] and t B ∈ (0, 1], the set of cross-view relations R A×B , and the number of clusters k. 1: Compute the transitive closure of C A C B R A×B . 2: Augment C A , C B , and R A×B with additional constraints from the transitive closure involving only instances from, respectively, Define the unified set of constraints, mapped with respect to view V : 10: Update the clustering using constrained K-Means: Estimate the set of propagated constraints: end for 13: until P A and P B have both internally converged Output: the clustering P A and P B . Subfunction: (P, M) = CKmeans(X, C, k) Function prototype for constrained K-Means. Input: data X, must-link and cannot-link constraints C, and the number of clusters k. X given the set of must-and cannot-link constraints C. Our implementation uses either the PCK-Means or MPCK-Means algorithms as the CKmeans subfunction due to their native support for soft constraints and, for MPCK-Means, metric learning. However, our approach can utilize other constrained K-Means clustering algorithms, provided that they meet the criteria for the CKmeans function listed above.
We fit the clustering model across both views using a variant of the co-EM algorithm (Nigam and Ghani, 2000), described in Section 3.2. In the Estep, we propagate the set of given constraints based on the current clustering models to those instances (X A andX B ) with direct mappings to the other views (Step 11, further described in Section 5.1). These propagated constraints can then be directly transferred to the other views via the mapping R A×B (Steps 4-9, further described in Section 5.2) to influence clustering during the M-step (Step 10). Note that instead of taking the direct union of all of the constraints, we keep only the maximally weighted constraint of each type (must-link and cannot-link) for every pair of instances; this operation is notated by the max operator in Step 9.
Following previous work on co-EM and multi-view clustering (Nigam and Ghani, 2000;Bickel and Scheffer, 2004), we iterate the E-step in one view to propagate the constraints followed by the M-step in the other view to transfer those constraints and update the clustering. Each iteration of the co-EM loop (Steps 6-13) contains two iterations of both the E-step and the M-step, one for each view. The relationship between these steps is illustrated in Figure 2. The co-EM process continues until each view has internally converged. We assume that convergence has occurred when the PCK-Means/MPCK-Means objective function's value differs by less than ǫ = 10 −6 between successive iterations. Like Nigam and Ghani (2000), we observed that our co-EM variant converged in very few iterations in practice. The iterative exchange of constraints between the views ensures a consistent clustering that respects both the constraints within and the mapping between views. The next two sections describe each step of the co-EM process in detail.

E-step: Constraint propagation
In our model, the sets of pairwise constraints are the sole mechanisms for guiding the resulting clustering. We can directly map a constraint x u , x v between views only if the mapping is defined in R A×B for both endpoints x u and x v of the constraint. When R A×B is incomplete, the number of constraints with such a direct mapping for both endpoints is likely to be small. Consequently, we will be unable to directly map many of the constraints between views; each constraint that we cannot map represents lost information that may have improved the clustering.
LetX V ⊆ X V be the set of instances for view V that are mapped to another view. Given the initial constraints in C V , we infer new constraints between pairs of instances inX V based on their local similarity to constraints in C V . We define this local similarity metric based on the current clustering model for view V , and propagate a constraint the pair is sufficiently similar to the original constraint. This process essentially considers these as spatial constraints (Klein et al., 2002) that affect not only the endpoints, but local neighborhoods of the instance space around those endpoints. Any effect on a pair of points in the neighborhood can be realized as a weighted constraint between those instances. Our constraint propagation method infers these constraints between instances inX V with respect to the current clustering model. Since this set of new constraints (which we refer to as propagated constraints) is between instances with a direct mapping to other views, these constraints can be directly transferred to those other views via the mapping R A×B . This approach can also be interpreted as inferring two weighted must-link constraints The propagation process occurs with respect to the current clustering model for view V . Since we use K-Means variants as the base learning algorithm, the learned model is essentially equivalent to a Gaussian mixture model, under particular assumptions of uniform mixture priors and conditional distributions based on the set of constraints (Bilenko et al., 2004;Basu et al., 2002). Therefore, we can consider that each cluster h is generated by a Gaussian with a covariance matrix Σ h . For base clustering algorithms that support metric learning (e.g., MPCK-Means), the cluster covariance is related to the inverse of the cluster metric M h learned as part of the clustering process. Bar-Hillel et al. (2005) note that, in practice, metric learning typically constructs the metric modulo a scale factor α h . Although this scale factor does not affect clustering, since only relative distances are required, constraint propagation requires absolute distances. Therefore, we must rescale the learned covariance matrix M −1 h by α h to match the data.
We compute α h based on the empirical covarianceΣ h of the data P h ⊂ X V assigned to cluster h, given bỹ adding a small amount of regularization γI to ensure thatΣ h is non-singular for small data samples. Given M −1 h andΣ h , we compute α h as the scale such that the variances of the first principal component of each matrix are identical. We take the eigendecomposition of each matrix to yield diagonal matrices of eigenvalues in Λ M −1 h and ΛΣ h . To derive the scale factor α h , we ensure that both first principal components have equal variances, which occurs when yielding Σ h = α h M −1 h as the covariance matrix for cluster h. When the base learning algorithm does not support metric learning, as with PCK-Means, we can instead use Σ h =Σ h as cluster h's covariance matrix. The model for cluster h is then given by where is the squared Mahalanobis distance between x V and µ V h according to the cluster's rescaled metric Σ h −1 . We assume that each constraint should be propagated with respect to the current clustering model, with the shape (i.e., covariance) of the propagation being equivalent to the shape of the respective clusters (as given by their covariance matrices). Additionally, we assume that the propagation distance should be proportional to the constraint's location in the cluster. Intuitively, a constraint located near the center of a cluster can be propagated a far distance, up to the cluster's edges, since being located near the center of the cluster implies that the model has high confidence in the relationship depicted by the constraint. Similarly, a constraint located near the edges of a cluster should only be propagated a short distance, since the relative cluster membership of these points is less certain at the cluster's fringe.
We propagate a given constraint x V u , x V v ∈ C V to two other points x V i , x V j ∈ X V according to a Gaussian radial basis function (RBF) of the distance as Under this construction, the weight of the propagated constraint decreases according to the RBF centered in 2d Vdimensional space at the original constraint's endpoints x V u x V v ∈ R 2dV with a covariance matrix Σ V uv based on the respective clusters' covariance matrices. To form the propagation covariance matrices for each endpoint, we scale the covariance matrix associated with endpoint x V u by the weight assigned to that endpoint according to the clustering model (Equation 7). This ensures that the amount of propagation falls off with increasing distance from the centroid, in direct relation to the model's confidence in the cluster membership of x V u . The covariance matrix for the constraint propagation function is then given by where c u denotes the cluster of x u and 0 denotes the d V × d V zero matrix. This construction assumes independence between x V u and x V v . While this assumption is likely to be violated in practice, we empirically show that it yields good results. For convenience, we represent the covariance matrices associated with each endpoint by Σ Figure 3 illustrates the results of this process on an example cluster.
3. Constraint propagation applied to a single example cluster h, showing the learned covariance matrix Σ h (dashed blue ellipse) rescaled to fit the data, two constraints (solid black lines), and the weighting functions centered at each endpoint (dotted green ellipses), which decrease in variance as they move farther from the centroid µ h .
Given a constraint x V u , x V v , w, type ∈ C V and two candidate points x V i ∈ X V and x V j ∈ X V , we can now estimate the weight of the propagated constraint Since the ordering of the instances matters in the propagation, we compute both possible pairings of constraint endpoints (x V u and x V v ) to target endpoints (x V i and x V j ), taking the maximum value of the propagation in Equation 10 to determine the best match. Under this propagation scheme, a constraint propagated to its own endpoints is given a weight of w (since the second term of the RHS of Equation 10 will be 1); the weight of the propagated constraint decreases as the endpoints x V i and x V j move farther from x V u and x V v . Section 5.4 describes mechanisms for implementing constraint propagation efficiently, taking advantage of the independence assumption between the two endpoints of a constraint and memoization of repeated computations.
The E-step of Algorithm 2 (Step 11) uses Equation 10 to propagate all given constraints within each view to those instancesX V with cross-view mappings, thereby inferring the expected value of constraints between those instances given the current clustering. Using this set of expected constraints P V , we then update the current clustering model in the M-step, as described in the next section.

M-step: Updating the clustering model
Given the expected constraints P U between instances inX U , we transfer those constraints to the other views and then update the clustering model to reflect these new constraints. These steps together constitute the M-step of Algorithm 2.
Any propagated constraint where both endpoints are inX U can be transferred to another view V via the bipartite mapping R U×V . We define a mapping function f U →V : C U → C V that takes a given constraint x U i , x U j , w, type ∈ P U and maps it to constrain instances in X V by: Using this construction, we can define the mapping functions f B →A and f A →B in Algorithm 2. We then use these functions f A →B and f B →A to map propagated constraints between views in Step 9, transferring constraints inferred in one view to the other related views. These transferred constraints (from view U ) can then be combined with the original constraints in each view V to inform the clustering. Instead of taking the direct union of these constraints, we keep only the maximally weighted constraint between each pair of instances to form the set since each inferred constraint represents an estimate of the minimal strength of the pairwise relationship. The partitioning for view V can then be computed by clustering the data X V subject to the constraints inC V (Step 10). The CKmeans subfunction computes the clustering that maximizes the log-likelihood of the data subject to the set of constraints, thereby completing the M-step of Algorithm 2.

Extension to multiple views
Algorithm 2 can be easily extended to support more than two views. Each view X V independently maintains its own sets of given constraints C V , threshold t V , dataX V ⊆ X V involved in any cross-view relations, current partitioning P V , current cluster metrics M V , and propagated constraints P V . To handle more than two views, we maintain separate mappings R U×V for each pair of views X U and X V and use each mapping to define pairwise mapping functions f U →V and f V →U between views. For D views, X (1) , . . . , X (D) , this approach will yield D 2 − D mapping functions.
To generalize our approach to more than two views, we hold each set of propagated constraints fixed, and iteratively update the clustering (M-step), then recompute the set of propagated constraints (E-step) for one view. The unified sets of constraints for each view V becomes (Step 9): under the convention that f U →U (P U ) = ∅. Each iteration of co-EM loops over the E-steps and M-steps for all views, and proceeds until the clustering for each view converges. The order of the views may either be fixed or chosen randomly at each iteration.

Implementation efficiency
The overall computational complexity of Algorithm 2 is determined by the maximum number of EM iterations and by the complexity of the CKMeans function, which depends on the chosen clustering algorithm. Besides these aspects, the constraint propagation step (Step 11) incurs the greatest computational cost.
To make this step computationally efficient, our implementation relies on the independence assumption inherent in Equation 11 between the two endpoints of the constraint. To efficiently compute the weight of all propagated constraints, we memoize the value of each endpoint's propagation Through memoization, we reduce the constraint propagation step to |X V |×|X V | Gaussian evaluations. Memoization applies similarly to all other views. Each constraint propagation is inherently independent from the others, making this approach suitable for parallel implementation using Hadoop/MapReduce (Dean and Ghemawat, 2008).
When the covariance matrix Σ x V u is diagonal, we can further reduce the computational cost through early stopping of the Gaussian evaluation once we are certain that the endpoint's propagation weight will be below the given threshold t V . When Σ x V u is diagonal, given by Σ x V u = diag (σ 2 1 , σ 2 2 , . . . , σ 2 dV ), Since a constraint is only propagated when the weight exceeds t V > 0 and the maximum propagation for each Gaussian weight G( Since all terms in the RHS summation are positive, we can compute them incrementally and stop early once the sum exceeds −2 ln t V , since we will never need to evaluate any propagation weight W ′ (·) involving G(x V i , x V u ). In our implementation, we set G(x V i , x V u ) = 0 in any cases where we can guarantee that

Evaluation
We evaluated multi-view constrained clustering on a variety of data sets, both synthetic and real, showing that our approach improves multi-view learning under an incomplete mapping as compared to several other methods. Our results reveal that the constraints inferred by propagation have high precision with respect to the true clusters in the data. We also examined the performance of Constraint Propagation in the individual views, revealing that Constraint Propagation can also improve performance in single-view clustering scenarios.

Data sets
In order to examine the performance of our approach under various data distributions, we use a combination of synthetic and real data in our experiments. We follow the methodology of Nigam and Ghani (2000) to create these multi-view data sets by pairing classes together to create "super-instances" consisting of one instance from each class in the pair. The two original instances then represent two different views of the super-instance, and their connection forms a mapping between the views. This methodology can be trivially extended to an arbitrary number of views. These data sets are described below and summarized in Table 1.
Four Quadrants is a synthetic data set composed of 200 instances drawn from four Gaussians in R 2 space with identity covariance. The Gaussians are centered at the coordinates (±3, ±3), one in each of the four quadrants. Quadrants I and IV belong to the same cluster and quadrants II and III belong to the same cluster. The challenge in this simple data set is to identify these clusters automatically, which requires the use of constraints to improve performance beyond random chance. To form the two views, we drew 50 instances from each of the four Gaussians, divided them evenly between views, and created mappings between nearest neighbors that were in the same quadrant but different views.
To create multiple views of this data set, we partition it into two views containing respectively instances from classes {c 1 , c 2 , c 3 } and {c 4 , c 5 , c 6 }. We connect instances between the following pairs of classes to create the two views: c 1 & c 4 , c 2 & c 5 , and c 3 & c 6 . Through this construction, a model learned for clustering {c 1 , c 2 , c 3 } in one view can be used to inform the clustering of {c 4 , c 5 , c 6 } in the other view. Since the clusters do not contain the same numbers of instances, some instances within each view are isolated in the mapping. Letters/Digits uses the letters-IJL and digits-389 data sets previously used by Bilenko et al. (2004). These are subsets of the letters and digits data sets from the UCI machine learning repository (Asuncion and Newman, 2007) containing only the letters {I, J, L} and the digits {3, 8, 9}, respectively. We map instances between views according to the following pairings: I & 3, J & 8, and L & 9, leaving those instances without a correspondence in the other view isolated in the mapping. Rec/Talk is a subset of the 20 Newsgroups data set (Rennie, 2003), containing 5% of the instances from the newsgroups {rec.autos, rec.motorcycles} in the rec view, and 5% of the instances from the newsgroups {talk.politics.guns, talk.politics.mideast } in the talk view. We process each view independently, removing stop words and representing the data as a binary vector of the 50 most discriminatory words as determined by Weka's string-to-wordvector filter (Witten and Frank, 2005). As in the previous data sets, we form the mapping between views by pairing clusters in order.
We create a low-dimensional embedding of each data set using the spectral features (Ng et al., 2001) in order to improve clustering, with the exception of Four Quadrants, for which we use the original features because the dimensionality is already low. For each view V , we compute the pairwise affinity matrix A between the instances x i and x j using a radial basis function of their distance, given by A i,j = exp(−||x i − x j || 2 /2σ 2 ). We use σ = 1 as the rate at which the affinity falls off with increasing distance. From A, we form the normalized Laplacian matrix (Chung, 1994) for the data set, given by L = I − D − 1 2 AD − 1 2 , where D is the diagonal degree matrix D i,i = nV j=1 A i,j and I is the identity matrix. The eigendecomposition of the normalized Laplacian matrix L = QΛQ T yields the spectral features for the data set in the columns of the eigenvector matrix Q. We keep the 2 nd through d + 1 th eigenvectors (corresponding to the 2 nd through d + 1 th lowest eigenvalues in Λ) as the features for clustering; we discard the first eigenvector since it is constant and therefore does not discriminate between the instances. In this article, we use d = √ d V for Protein and Letters/Digits, and d = 5 for the Rec/Talk data set. Additionally, we standardize all features to have zero mean and unit variance. These spectral features are computed independently between the different views, further emphasizing that the mapping is the only connection between views.

Methodology
Within each view, we use the true cluster labels on the instances to sample a set of pairwise constraints, ensuring equal proportions of must-link and cannot-link constraints. The weight of all sampled constraints w is set to 1. We also sample a portion of the mapping to use for transferring constraints between views. Both the sets of constraints and the mapping between views are resampled each trial.
We compare Constraint Propagation against several other potential methods for transferring constraints: Direct Mapping transfers only those constraints that already exist between instances inX V . This approach is equivalent to other methods for multiview learning that are only capable of transferring labeled information if there is a direct mapping between views. Cluster Membership can be used to infer constraints between instances in X V . This approach simply considers the relative cluster membership for each pair of instances inX V and infers the appropriate type of constraint with a weight of 1. It represents the direct application of co-EM to infer and transfer constraints between views via the partial mapping. Single View performs constrained clustering on each of the individual views in isolation and serves as a lower baseline for the experiments.
For the base constrained clustering algorithms, we use the PCK-Means and MPCK-Means implementations provided in the WekaUT extension 1 to the Weka machine learning toolkit (Witten and Frank, 2005) with their default values. For PCK-Means, Constraint Propagation uses the full empirical covariance for each cluster; for MPCK-Means, it uses the diagonal weighted Euclidean metrics that are learned on a per-cluster basis by MPCK-Means. We measure performance using the pairwise F-measure -a version of the information-theoretic F-measure adapted to measure the number of same-cluster pairs for clustering (Basu, 2005). The pairwise F-measure is the harmonic mean of precision and recall, given by where P pred is the set of entity pairs predicted to be in the same community, P same is the set of entity pairs actually in the same community, and P correct = P pred P same is the set of correct predictions. We take the mean of the Fmeasure performance for all views, yielding a single performance measure for each experiment.
In each trial, we consider performance as we vary the number of constraints used for learning and the percentage of instances in each view that are mapped to the other views. Our results are shown in Figure 4, averaged over 100 trials.

Discussion of multi-view clustering results
As shown in Figure 4, Constraint Propagation clearly performs better than the baseline of Single View clustering, and better than Cluster Membership for inferring constraints in all cases, except for when learning with few constraints on Letters/Digits. Constraint Propagation also yields an improvement over Direct Mapping for each percentage of instances mapped between views, as shown in Figure 5. Unlike Direct Mapping, Constraint Propagation is able to transfer those constraints that would otherwise be discarded, increasing the performance of multi-view clustering.   Figure 4, averaged over the learning curve. The peak whiskers depict the maximum percentage improvement. 2 views, with Constraint Propagation still retaining an advantage over Direct Mapping even with a complete mapping, as shown in all data sets. We hypothesize that in the case of a complete mapping, Constraint Propagation behaves similarly to spatial constraints (Klein et al., 2002), warping the underlying space with the inference of new constraints that improve performance. On these data sets, the number of constraints inferred by Constraint Propagation is approximately linear in the number of original constraints, as shown in Figure 6. Clearly, as the mapping between views becomes more complete, Constraint Propagation is able to infer a larger number of constraints between those instances inX V .
The improvement in clustering performance is due to the high precision of the propagated constraints. Figure 7 shows the average weighted precision of the propagated constraints for the 100% mapping case, measured against the complete set of pairwise constraints that can be inferred from the true cluster labels. The proportion that each propagated constraint contributed to the weighted precision is given by the constraint's inferred weight w. We also measured the precision of propagated constraints for various partial mappings, and the results were comparable to those for the complete mapping. The constraints inferred through propagation show a high average precision of 98-100% for all data sets, signifying that the propagation method infers very few incorrect constraints.
Interestingly, the constraint propagation method works slightly better for cannot-link constraints than for must-link constraints. This phenomenon can be explained by a counting argument that there are many more chances for a cannotlink constraint to be correctly propagated than a must-link constraint. For example, with k clusters where each cluster contains n/k instances, each given mustlink constraint can be correctly propagated to numMLprop = n/k 2 − 1 other pairs of instances in the same cluster. However, each given cannot-link constraint can be correctly propagated to numCLprop = n 2 − k n/k 2 − 1 other pairs of instances that belong in different clusters. The number of propagated cannotlink constraints is computed by taking the number of possible different constraints, n 2 − 1, and subtracting off the total number of possible must-link constraints, k n/k 2 . Note that numCLprop is much greater than numMLprop (e.g., for n = 1, 000 and k = 10, numCLprop = 449, 999 ≫ 4, 949 = numMLprop), implying that a must-link constraint has much less chance of being propagated correctly than a cannot-link constraint.
We found that for high-dimensional data, the curse of dimensionality causes instances to be so far separated that Constraint Propagation is only able to infer constraints with a very low weight. Consequently, it works best with a low-dimensional embedding of the data, motivating our use of spectral feature reduction. Other approaches could also be used for creating the low-dimensional embedding, such as principal components analysis or manifold learning.
Additionally, like other multi-view algorithms, we found Constraint Propagation to be somewhat sensitive to the cutoff thresholds t V , but this problem can be remedied by using cross-validation to choose t V . Too high a threshold yields performance identical to Direct Mapping (since no constraints would be inferred), while too low a threshold yields the same decreased performance as exhibited by other co-training algorithms. For this reason, we recommend setting t V to optimize cross-validated performance over the set of constrained instances.
We ran several additional experiments on multi-view data sets with poor mappings and distributions that violated the mixture-of-Gaussians assumption of K-Means clustering. On these data sets, Constraint Propagation decreased performance in some cases, due to inferring constraints that were not justified by the data. This would occur, for example, in clusters with a nested half-moon shape or concentric rings, where Constraint Propagation would incorrectly infer constraints between instances in the opposing cluster. In these cases, clustering using only the directly mapped constraints yielded the best performance.

Constraint propagation within single views
To dissect the benefits of Constraint Propagation independently from multiview learning, we evaluated the use of Constraint Propagation in traditional single-view clustering scenarios. We found that using the constraints inferred by propagation can also improve performance in single-view clustering, further explaining its performance in multi-view scenarios and also demonstrating the high quality of the inferred constraints.
Instead of propagating constraints across views, we used Constraint Propagation to infer additional constraints within a single view A, employed those constraints to inform the clustering for that view, and then used the resulting clusters to guide the propagation for the next iteration of clustering. This process was repeated until the clustering model for view A converged. To implement this approach, we modified Algorithm 2 to use only a single view by eliminating all steps involving view B, altering step 3 to setX A = X A , and altering step 9 to compute the unified set of constraints asC V = C V max ∪ P V . With these modifications, the algorithm alternates the M-step clustering and E-step Constraint Propagation to learn a model for the single view A. We then evaluated the performance of this single-view clustering method on individual data sets. Figure 8 depicts the performance of single-view clustering with Constraint Propagation on a sample of the data sets, averaged over 100 trials. All parameters were specified as described in Table 1, with the exceptions of using t V = 0.7 for protein and t V = 0.98 for digits, since we now set t V for each individual view. We compare single-view clustering with Constraint Propagation against standard constrained clustering. Our analysis omits the other two methods tested in the multi-view experiments, since Direct Mapping has no analogous case for singleview scenarios, and constraints inferred by Cluster Membership in a single view will not alter the resulting model.
These results show that the constraints inferred by propagation within a single view can also be used to improve clustering performance in that view. Both MPCK-Means and PCK-Means show improved performance using the constraints inferred by propagation to augment the original constraints. The maximum improvement from Constraint Propagation occurs with a moderate number of constraints; as we would expect, Constraint Propagation provides little benefit when the number of original constraints is either very small or very large. Even in the single-view case, the number of constraints inferred by propagation is roughly linear in the number of original constraints (Figure 9). We also found that the inferred constraints have very high precision with the true cluster assignments in all single-view scenarios ( Figure 10). As in the multi-view experiments, the inferred cannot-link constraints have slightly higher precision than the inferred must-link constraints.
As mentioned in the previous section, we found that Constraint Propagation can decrease performance when applied to data sets that violate the assumptions of K-Means clustering. The two conditions assumed by K-Means that are most necessary for successful Constraint Propagation are that: (1) the clusters are globular under the cluster metrics, and (2) the clusters are separable (i.e., have little overlap). However, it may be difficult to determine a priori whether a particular data set meets these conditions, and is therefore an appropriate candidate for Constraint Propagation. For this reason, it is important to determine whether the data set satisfies these conditions during the clustering process; we next discuss two potential methods for making this determination.
In cases where the data set does violate these conditions, we have observed that the clustering is primarily driven by the provided constraints rather than the K-Means component. One of the strengths of the MPCK-Means and PCK-Means algorithms is that in situations where K-Means does poorly on the data, large numbers of constraints can overcome the K-Means component and ensure the proper clustering. In terms of the PCK-Means/MPCK-Means objective function (Equation 1), the second and third terms of the equation (those involving the must-and cannot-link constraints) dominate the first term (K-Means) in these situations. When the data set does not meet these conditions, the cluster distributions specified by the learned centroids and metrics have little in common with the resulting partitions. During the clustering process, we can examine the learned cluster distributions for disagreement with the resulting partitions; the presence of a large disagreement is one indication that the data set may be inappropriate for Constraint Propagation.
To determine whether the data set meets the second condition, we can also directly examine the resulting clusters for overlap. Since constraints are propagated based on RBF distance from the given constraint and the relative cluster membership of the endpoints, Constraint Propagation may not infer constraints correctly between points belonging to overlapping clusters. We can detect overlap in the clusters by measuring the KL divergence (Kullback and Leibler, 1951) between their learned distributions; the presence of significant overlap is another indication that the data set may violate the conditions necessary for successful Constraint Propagation. Currently, we simply alert the user if the data set may be inappropriate for Constraint Propagation based on either indicator; we leave the robust determination of whether Constraint Propagation is guaranteed to improve performance to future work.

Conclusion
Constraint Propagation has the ability to improve multi-view constrained clustering when the mapping between views is incomplete. Besides improving performance, Constraint Propagation also enables information supplied in one view to be propagated and transferred to improve learning in other views. This is especially beneficial for applications in which it is more natural for users to interact with particular views of the data. For example, users may be able to rapidly and intuitively supply constraints between images, but may require a lengthy examination of other views (e.g., text or audio) in order to infer constraints. In other cases, users may not have access to particular views (or even data within a view) due to privacy restrictions. In these scenarios, our approach would be able to propagate user-supplied constraints both within and across views to maximize clustering performance.
Beyond our approach, there are a variety of other methods that could be adapted for learning with a partial mapping between views, such as manifold alignment and transfer learning. Further work on this problem will improve the ability to use isolated instances that do not have a corresponding multi-view representation to improve learning, and enable multi-view learning to be used for a wider variety of applications.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Probabilistic Monads, Domains and Classical Information

Shannon's classical information theory uses probability theory to analyze channels as mechanisms for information flow. In this paper, we generalize results of Martin, Allwein and Moskowitz for binary channels to show how some more modern tools - probabilistic monads and domain theory in particular - can be used to model classical channels. As initiated Martin, et al., the point of departure is to consider the family of channels with fixed inputs and outputs, rather than trying to analyze channels one at a time. The results show that domain theory has a role to play in the capacity of channels; in particular, the (n x n)-stochastic matrices, which are the classical channels having the same sized input as output, admit a quotient compact ordered space which is a domain, and the capacity map factors through this quotient via a Scott-continuous map that measures the quotient domain. We also comment on how some of our results relate to recent discoveries about quantum channels and free affine monoids.

Introduction
Classical information theory has its foundations in the seminal work of Claude Shannon [18], who first conceived of analyzing the behavior of channels using entropy and deriving a formula for channel capacity based on mutual information (cf. [6] for a modern presentation of the basic results). Recent work of Martin, et al. [14] reveals that the theory of compact, affine monoids and domain theory can be used to analyze the family of binary channels. In this paper, our goal is to generalize the results in [14] to the case of n × n-channels -channels that have n input ports and n output ports. Our approach also uses the monadic properties of probability distributions to give an abstract presentation of how channels arise, and that clarifies the role of the doubly stochastic matrices, which are special channels. While our work focuses on the classical case, the situation around quantum information and quantum channels is also a concern, and we point out how our results relate to some recent work [7,15] on quantum qubit channels and free affine monoids. While most of the ingredients we piece together are not new, we believe the approach we present does represent a new way in which to understand families of channels and some of their important features.
The rest of the paper is structured as follows. In the next section, we describe three monads based on the probability measures over compact spaces, compact monoids and compact groups. Each of these is used to present some aspect of the classical channels. We then introduce topology, and show how the capacity of a channel can be viewed from a topological perspective. The main result here is that capacity is the maximum distance from the surface determined by the entropy function and the underlying polytope generated by the rows of a channel matrix, viewed as vectors in R n for appropriate n. This leads to a generalization of Jensen's Lemma that characterizes strictly concave functions. Domain theory is then introduced, as applied to the finitely-generated polytopes residing in a compact convex set, ordered by reverse inclusion. Here we characterize when proper maps measure a domain, in the sense of Martin [13]; a closely related result can be found in [16]. Finally, we return to the compact monoid of n × n-stochastic matrices and show that it has a natural, algebraically-defined pre-order relative to which capacity measures the quotient partial order, which is a compact ordered space. The capacity mapping is also shown to be strictly monotone with respect to this pre-order, which means that strictly smaller channel matrices have strictly smaller capacity. We close with a summary and comments about future work.

Three probabilistic monads
The categorical presentation of classical information relies on three monads, each of which has the family Prob(X ) of probability distributions over a set X as the object-level of the left adjoint. The first of these starts with compact Hausdorff spaces, and uses several results from functional analysis: standard references for this material are [4,17]. We present these monads in turn:

A spatial monad
We begin with the probability measure monad over topological spaces. If X is a compact Hausdorff space, then C(X , R), the family of continuous, real-valued functions defined on X , is a Banach space (complete, normed linear space) in the sup-norm. The Banach space dual of C(X , R), denoted C(X , R) * consists of all continuous linear functionals from C(X , R) into R. C(X , R) * is another Banach space, and the Riesz Representation Theorem implies this is the Banach space of Radon measures on X (those that are both inner-and outer regular). The unit sphere of C(X , R) * is the family Prob(X ) of probability measures over X . If we endow Prob(X ) with the weak * topology (the weakest topology making all continuous linear functionals into R continuous), then Prob(X ) becomes a compact, Hausdorff space, by the Banach-Alaoglu Theorem. Prob extends to a functor Prob S : Comp → CompConv LC from the category of compact Hausdorff spaces and continuous maps, to the category of compact, convex, locally convex spaces and continuous affine maps, via Prob S (X ) = Prob(X ) and f : X → Y maps to Moreover, if the mapping x → δ x : X → C(X , R) * sending a point to the Dirac measure it defines, is a continuous mapping into the weak * topology. Since X is compact Hausdorff, Urysohn's Lemma implies C(X , R) separates the points of X , and so x → δ x is a homeomorphism onto its image. Another application of Urysohn's Lemma shows each Dirac measure is an extreme point Prob(X ) and in fact the Dirac measures form the set of extreme points of Prob(X ).
A simple measure is a finite, convex combination of Dirac measures, i.e., one of the form ∑ i≤n r i δ x i , where r i ≥ 0, ∑ i r i = 1, and x i ∈ X for each i. We let Prob sim (X ) denote this family. The Krein-Milman Theorem implies that Prob sim (X ) is weak * dense among the probability measures. So, if f : X → C is a continuous function from X into a compact subset of a locally convex vector space, then the function f (δ x ) = f (x) extends uniquely to continuous function f (∑ i≤n r i δ x i ) = ∑ i≤n r i f (x i ), and then to all of Prob(X ), by the density of the simple measures.
We conclude that the functor Prob S is left adjoint to the forgetful functor. In fact, Prob S defines a monad, where the unit of the adjunction is the mapping η X (x) = δ x and the multiplication µ : Prob(Prob(X )) → Prob(X ) is integration. Theorem 1. The functor Prob S sending a compact space to its family of probability measure in the weak * topology defines a monad on the category Comp. The unit of the monad sends a point x ∈ X to the Dirac measure δ x , and the image of the unit is the set of extreme points in Prob(X ). Definition 1. Let X and Y be compact Hausdorff spaces. A (lossless) noisy channel from X to Y is a mapping f : X → Prob(Y ).
Since Prob S is a monad, each channel f : X → Prob(Y ) corresponds uniquely to a continuous, affine mapping Prob S ( f ) : Prob(X ) → Prob(Y ) in the Kleisli category K Prob S of Prob S . Example 1. Let n ≥ 1 and let n = {0, . . . , n − 1} be the discrete, compact space. Then Prob(n) is the family of probability distributions on n points, and given m ≥ 1, a channel f : m → Prob(n) is an m × n-stochastic matrix. The family ST(m, n) of m × n-stochastic matrices is then the family of lossless, noisy channels from m to n. Moreover, from our comment about the Kleisli category K Prob S , we conclude that the family of morphisms K Prob S (m, Prob(n)) is ST(m, n) ֒→ Aff(Prob(m), Prob(n)), where Aff(Prob(m), Prob(n)) is the family of continuous affine maps from Prob(m) to Prob(n).
This first probabilistic monad shows that classical channels correspond to mappings in the Kleisli category of the "spatial" monad Prob S on the category Comp. If we let m = n, then ST(n) def = ST(n, n) is also a monoid using composition in the Kleisli category: if f , g ∈ ST(n), and g : Prob(n) → Prob(n) is the extension of g, then g • f ::= g • f ∈ ST(n). We next present a second monad that gives another account of this special case.

A monad on monoids
The second monad we define is based on the category CMon of compact monoids and compact monoid homomorphisms. More precisely, a compact monoid is a monoid S -a non-empty set endowed with an associative binary operation (x, y) → xy : S × S → S that also has an identity element, 1 S -that also is a compact Hausdorff space for which the multiplication is continuous. We can apply the probability functor to such an S to obtain the compact convex (Hausdorff) space Prob(S) of probability measures on S. If we denote multiplication on S by ·, then Prob(·) : Prob(S × S) → Prob(S), and since ι S : Prob(S) × Prob(S) ֒→ Prob(S × S) is an embedding, we have a continuous affine map Prob(·) • ι S : Prob(S) × Prob(S) → Prob(S). This map is called convolution, and we denote (Prob(·) • ι S )(µ, ν) = µ * S ν. It is routine to show convolution is associative, so Prob(S) is a compact affine monoid.
If φ : S → T is a morphism of compact semigroups, then Prob(φ ) : Prob(S) → Prob(T ) is defined by Prob(φ )(µ)( f ) = f • φ dµ for any f : T → R. If µ, ν ∈ Prob(S) and f ∈ C(T, R), then where m S : S × S → S, m T : T × T → T are the semigroup operations, * S , * T denote convolution, and where 1 = follows from the fact that φ is a homomorphism. Thus Prob S : (Prob(S), * S ) → (Prob(T ), * T ) is a semigroup homomorphism. Finally, the fact that Prob(φ ) preserves the identity follows from the observation that δ x * S δ y = δ xy , which implies that δ 1 is an identity for the simple measures, and consequently for all measures since the simple measures are dense.
It follows that restricting Prob S to the subcategory CMon of Comp yields a functor Prob M : CMon → CAM into the category of locally convex compact affine monoids and continuous affine monoid maps. Theorem 2. The restriction of Prob S to Mon induces a monad Prob M whose target is CAM, the category of locally convex compact affine monoids and continuous, affine monoid homomorphisms. The unit of the monad is again the Dirac map, and its image is again the set of extreme points of Prob(S).
Applying the same reasoning as for Prob S , we see that each continuous monoid homomorphism φ : S → Prob(T ) corresponds to a unique morphism of compact affine monoids, φ : Prob(S) → Prob(T ) in the Kleisli category K Prob M . However, in relation to classical channels, our interest is in the object level of Prob M : Example 2. We return to the example ST(n) of stochastic n × n-matrices. These arise as channels on a discrete, n-element set. For such a set n, the selfmaps of n form a finite -hence compact -monoid. If we denote this monoid by [n → n], then applying Prob M we obtain a compact affine monoid is a compact affine monoid, this mapping extends to a morphism of compact affine monoids Since

A monad over compact groups
Our final use of Prob to define a monad starts with CGrp, the category of compact groups and continuous group homomorphisms. Since CGrp is a subcategory of CMon, we know that applying Prob M to a compact group yields a compact affine monoid. However, Prob M (G) is not a group in general, so the forgetful functor from CMon does not take Prob M (G) to a group, but instead yields a compact monoid.
But, when applied to a compact group G qua compact monoid, the unit of the monad Prob M sends each g ∈ G to δ g ∈ Prob(G), and this is a monoid -hence group -homomorphism. So  Example 3. We again consider the case of classical channels. Here, given n ≥ 1, ST(n) has for its group of units the permutation group S(n). Applying Prob G , we find that Prob G (S(n)) is the free compact affine monoid over the group S(n). But this is just the family DT(n) of doubly stochastic n × n-matrices.
We can use information about Prob G (S(n)) to conclude information about DT(n). Wendel's Theorem [20] states that, for a compact group G, the compact monoid Prob(G) has {δ g | g ∈ G} as its group of units, and the minimal ideal (every compact monoid has one -cf. [10]) is a zero, which in fact is Haar measure on G. In the case of S(n), this reaffirms that the units of DT(n) are the permutations of n, and that DT(n) has a zero, which is the equidistribution ∑ i≤n 1 n δ i . Corollary 1. If G is a finite group, then Prob G (G) is the free affine monoid over G, as well as the being the free compact affine monoid over G.
consists of simple measures. If S is an affine monoid and φ : G → S is a monoid homomorphism, then φ (G) ⊆ H(1 S ), and so φ : is easily seen to be a morphism of affine monoids that satisfies φ (δ g ) = φ (g) for each g ∈ G, and φ is the unique such since Prob G (G) consists of simple measures. This shows Prob G (G) is the free affine monoid over G, and the Theorem implies it also is the free compact affine monoid over G since G is finite, and hence compact.
Remark 1. In [7,15], the free affine monoid over a finite group is employed to deduce properties of quantum channels. The Corollary shows that the free affine monoid over G is nothing other than Prob G (G), which implies it is compact, as well as telling us that it has a zero -the uniform distribution on G. We believe other useful properties about quantum channels over finite groups can be deduced from this observation.

Capacity as a topological concept
In this section we develop a new approach to understanding the capacity of a classical channel. Our idea is to analyze capacity from a topological perspective, rather from the usual perspective of inequalities prevalent in information theory. We begin with a brief reprise of the basics of Shannon information; the standard reference for this material is [6].
If X : X → R is a random variable on a finite probability space (X , p), then the entropy 2 of X is defined as and the mutual information in X and Y is If C : X → Y is a channel from inputs X to outputs Y , then C is an X × Y -matrix whose (x, y)-entry is the conditional probability of output y occurring, given that the input was x. Each distribution p on the inputs X then produces a corresponding distribution p ·C on Y . The capacity of a channel is given by i.e., Cap(C) is the supremum of the possible mutual information values I (p ·C | p) as p ranges over the distributions on X , the set of inputs. If we let X = Y = n and C : n → Prob(n) is a channel, then This formula requires some interpretation.
1. First, the term to which H is first applied -(∑ j≤n r j C( j, 1), . . . , ∑ j≤n r j C( j, n)) -represents a distribution on Y = n obtained from pC, where p = ∑ i r i δ i is a distribution on X = n. This is the p-convex combination of the n vectors (C (1, 1), . . . ,C(1, n)), . . . , (C(n, 1), . . . ,C(n, n)) ∈ [0, 1] n comprising the rows of the channel C, where C(i, j) denotes the i, j-entry of C, interpreted as a conditional probability. Since C is a channel, each of these rows is a probability distribution on n. (As a sanity check, we see that applying H to the convex combination (∑ j≤n r j C( j, 1), . . . , ∑ j≤n r j C( j, n)) thus makes sense, since a convex combination of probability distributions is another such, and H applies to probability distributions.) 2. Now, the convex combination pC = (∑ j≤n r j C( j, 1), . . . , ∑ j≤n r j C( j, n)) is a point on the polytope K ⊆ [0, 1] n the rows of C generate, so  , 1), . . . ,C(i, n)) ∈ R n+1 , and hence the p-convex combination of these points lies on the polytope these points generate.
4. Finally, the difference H(∑ j≤n r j C( j|1), . . . , ∑ j≤n r j C( j|n)) − ∑ i≤n r i H (C(i|1), . . . ,C(i|n)) is the difference in the n + 1-coordinates described under 2. and 3., so it is height of the vertical line between the point pC in 3. and the corresponding point  , 1), . . . ,C(n, n)))) on the surface H generates over K.
Thus, Cap(C) as presented by Equation 2 takes the supremum of the differences between the value of H at a convex combination of the rows of C and the same convex combination of H applied to the rows of C. It is well-known that entropy H is a strictly concave function, and we now take advantage of this to formulate a result about Cap.
for all r ∈ (0, 1) and all We next recall Jensen's Inequality: Theorem 4 (Jensen (cf. [9])). If f : K → R is a convex function defined on a convex subset K of a vector space V , then E f (X ) ≥ f (E(X )) for a finite random variable X : X → K, where E denotes expectation.
Moreover, if f is strictly convex, then E( f (X )) = f (E(X )) implies X is constant.
Jensen's Inequality is a fundamental result of information theory; for example, it is crucial for proving mutual information is non-negative, that the mutual information in a pair of random variables is 0 iff the random variables are independent, and that entropy itself is strictly concave (cf. [6], Chapter 2). Since f is (strictly) concave iff − f is (strictly) convex, the following generalizes Jensen's Inequality by strengthening the result in case f is strictly convex.
Proof. (ii) ⇒ (i) is obvious. For the reverse direction, we proceed by induction on m. The base case, m = 2, is just the definition of strict concavity. So suppose (ii) holds for some m, and consider a family r 1 , . . . , r m+1 ∈ [0, 1] and and so . . , y m })).

Domains
In this section, we introduce domains, which are the next ingredient in our analysis of classical channels. For details about these structures, a standard reference is [1] or [8]. A partial order is a non-empty set P endowed with a reflexive, antisymmetric and transitive relation. A subset D ⊆ P is directed is every finite subset of D has an upper bound in D; P is directed complete if every directed subset of P has a least upper bound in P. We denote directed complete partial orders as dcpos.
If P and Q are dcpos, then f : P → Q is Scott continuous if f is monotone and preserves suprema of directed sets. An equivalent definition is available using topology: a subset U ⊆ P is Scott open if U = ↑U = {x ∈ P | (∃u ∈ U ) u ≤ x} is an upper set, and for any directed subset D ⊆ P, if sup D ∈ U , then D ∩U = / 0. The Scott-open sets form a topology on P, called the Scott topology, and the functions f : P → Q that are continuous with respect to this topology are exactly those that are Scott continuous, as defined above.

Example 4. Let K be a compact convex subset of a topological vector space, and let Con(K) denote the compact convex subsets of K. We can order these by reverse inclusion: C ⊑ C ′ ⇔ C ′ ⊆ C. A directed family D ⊆ Con(K) is simply a filterbasis, and since K is compact and each set in D is convex, the set D ∈ Con(K). Thus Con(K) is a dcpo.
We can say more. If C,C ′ ∈ Con(K) and C ′ ⊆ C • , the interior of C, then given any directed set D with D ⊆ C ′ , there is some E ∈ D with E ⊆ C • , and hence E ⊆ C. In this case we say C is way-below C ′ , and we write C ≪ C ′ . In fact, if the ambient topological vector space is locally convex, then each C ′ ∈ Con(K) is the filtered intersection of those C satisfying C ≪ C ′ : this follows from the fact that in any compact Hausdorff space, each compact subset is the filtered intersection of its compact neighborhoods, and the same applies to compact, convex sets in a locally convex topological vector space.
A domain is a dcpo satisfying {y ∈ P | y ≪ x} is directed and x = sup{y ∈ P | y ≪ x} for each x ∈ P. The original motivation for domains was to provide semantic models for high-level programming languages, where the fact that any Scott-continuous selfmap on a domain with least element has a least fixed point gives a canonical model for recursion.
Motivated by examples of selfmaps that are not Scott continuous, Martin [13] devised another approach to guaranteeing fixed points, using the concept of a measurement: A Scott-continuous function m : P → [0, ∞) op is said to measure the content at x ∈ P if, given U ⊆ P Scott open, We say that m measures P if m measures the content at x for each x ∈ P.
For our next result, we need some notions from topology. Recall that s subset A ⊆ X of a topological space is saturated if A = {U | A ⊆ U open}. The saturation of a subset A is {U | A ⊆ U open}, so a set is saturated iff it is equal to its saturation. Moreover, a subset is compact iff its saturation is compact.
A Scott-continuous map m : P → Q between continuous posets is proper iff m −1 (↑ y) is Scott compact for each y ∈ Q. We say that a Scott-continuous mapping m : P → Q between posets is proper at Proof. The discussion in Example 4 applies to K = P n to show that Con(P n ) is a domain, and Con n (P n ) is closed in Con(P n ) under filtered intersections. Since R n is locally convex, it's easy to show that each conv(F) is the intersection of sets conv(G), where conv(F) ⊆ conv(G) • and |G| ≤ n if |F| ≤ n. Hence (Con n (P n ), ⊇) is a domain.
A compact, saturated subset of [0, ∞) op has the form A = [0, r] for some r, and then cap −1 ([0, r]) = {conv(F) | cap(conv(F) ≤ r} is closed, and hence compact, since cap is continuous and Con(P n ) -and hence also Con n (P n ) -are compact in the Lawson topology (cf. [1,8]). But cap −1 ([0, r]) also is an upper set, so it is Scott compact. Thus cap is proper, and so it measures Con n (P n ) iff it is strictly monotone. But the latter follows from Proposition 1, since entropy is strictly concave.
Remark: As we will see in a moment, the real import of this last result is not so much that cap measures Con n (P n ), per se, but rather that this implies the mapping cap is strictly monotone. This will tell us that under an appropriate (pre-)order, having one channel strictly below another implies that the capacity of the lower channel is strictly less than that of the larger one.
We also note that Martin and Panangaden have obtained results in [16] that can be used to derive the Proposition 2 and Corollary 2.

A domain-like structure of ST(n)
We have seen that ST(n) is a compact affine monoid, and we already commented that every compact semigroup has a unique smallest ideal: i.e., a non-empty subset I ⊆ S satisfying IS ∪ SI ⊆ I. This minimal ideal is denoted M (S), and it is closed, hence compact. For example, we noted that M (DT(n)) is a point, which is the equidistribution on n. A reference for much of the material in this section is [10], where basic results about compact affine monoids are laid out. A good reference for results about transformation semigroups can be found in [5].
Proof. If C ∈ ST(n), then C : Prob(n) → Prob(n) is an affine mapping, so it preserves the convex structure of Prob(n). It follows that C(Prob(n)) = conv({δ i C | i ≤ n}), where δ i ∈ Prob(n) is the Dirac measure on i ∈ n. Thus, C(Prob(n)) is a convex polytope in Prob(n).
As a result of the Proposition, we can define a relation on ST(n) by This is clearly a closed equivalence relation, and because channels are affine maps.
Now, C(δ i ) = δ i C = C(i), the i th row of C, so C ≡ C ′ iff C and C ′ have the same set of rows vectors. Hence, where M π is the stochastic matrix representing the permutation π ∈ S(n).
We also can obtain an algebraic representation of the relation ≡ using the monoid structure of ST(n).

Definition 4.
If X is a set, then the full transformation semigroup T (X ) on X is the family of all selfmaps of X under composition. A transformation semigroup is a subsemigroup of T (X ) for some set X .
Notation: If S ⊆ T (X ) is a transformation semigroup, then for s, s ′ ∈ T (X ) and x ∈ X , the element ss ′ ∈ S denotes the function ss ′ (x) = s ′ (s(x)) -i.e., we use the "algebraic notation" for function application, which agrees with our representation matrix multiplication as composition of functions.
Here are some simple observations about T (X ); the proofs are all straightforward: It is routine to show that ≡ M and ≤ M are both (topologically) closed relations on any compact monoid S.
Proof. For 1., it is clear from Equation Because ≡ M is a closed relation and ST(n) is compact, the quotient space is compact and the quotient map is closed and continuous. The definition of the pre-order ≤ M and the quotient order ≤ M /≡ M implies the quotient map is monotone.
So we see that ST(n)) has a natural pre-order ≤ M defined by its algebraic structure as a compact monoid, and if C ≤ M C ′ then Cap(C) ≤ Cap(C ′ ). Moreover, this pre-order turns into a partial order on ST(n)/ ≡ M , and here capacity is the mapping cap. Importantly, cap -and hence Cap on ST(n) -is strictly monotone with respect to this partial (pre-) order. Moreover, C ≡ M C ′ iff S(n)C = S(n)C ′ , so each is a permutation of the rows of the other.

Example 5. Here's an example of what our results tell us about ST(n). Recall that a Z-channel is a binary channel of the form
showing that each lies on a one-parameter semigroup ψ : ([0, 1], ·) → ST(2) by ψ(p) = Z p . Now, ψ is a homomorphism, so p < p ′ ⇒ Z p = Z p p ′ Z p ′ , while obviously, p = p ′ ⇒ S(2)Z p ∩ S(2)Z p ′ = / 0. It follows that p < p ′ ⇒ π(Z p ) < π(Z p ′ ) ⇒ Cap(Z p ) = cap(π(Z p )) < cap(π(Z p ′ )) = Cap(Z p ′ ), so the Z-channels Similarly, the matrices form a one parameter semigroup from I 2 to M (ST (2)), along which Cap is strictly decreasing. Now where O i is the matrix both of whose rows are (δ 1i δ 2i ), for i = 1, 2. For each fixed r ∈ [0, 1], there is a one-parameter semigroup p → p · I 2 + (1 − p) · (r · Z p + (1 − r) · Z ′ p ), and combining the earlier results, we conclude that along this one-parameter semigroup, Cap is strictly decreasing. Note as well that conv({I 2 } ∪ M (ST (2))) is equal to the union of these one-parameter semigroups.
We can generalize this verbatim to ST(n): define a Z-channel in ST(n) to be one of the form Z p = p · I n + (1 − p) · O k , where p ∈ [0, 1] and O k is the channel in M (ST(n)) all of whose rows are (0, . . . , 0, 1, 0, . . .), where the unique 1 appears in the k th entry. As in the binary case, p ≤ p ′ ⇒ Z p = Z p p ′ Z p ′ , and p = p ′ ⇒ S(n)Z p ∩ S(n)Z p ′ = / 0. So we can again conclude that Cap is strictly decreasing along this one-parameter semigroup. As in the case of n = 2, M (ST(n)) = {∑ i≤n r k O k | ∑ k r k = 1}, so the result extends verbatim to these one-parameter semigroups.

Summary and future work
We have used an array of tools to analyze the capacity map on the set of classical channels. In Section 3, we gave a topological interpretation of capacity of a channel: it is the maximum distance between the surface generated by the entropy function applied to the rows of the channel, and the polytope generated by the entropy function applied to each individual row. This suggests an method for computing capacity: the Generalized Mean Value Theorem implies the capacity is achieved at the unique place where gradient of the capacity function is 0 -this point is unique because entropy is strongly concave. Moreover, this produces the input distribution where capacity is achieved -the celebrated Arimoto-Blahut Algorithm [2,3] commonly used to compute the capacity of a discrete memoryless channel is an iterative procedure that approximates the capacity, not the input distribution where its value is assumed. An algorithm more closely related to our results can be found in [19], where the iteration scheme follows the concavity of the capacity function using Newton's Method. We also applied our topological result to derive a domain-theoretic interpretation of capacity, again using the strong concavity of entropy: the family Con n (P n ) of polytopes with at most n vertices is a domain, and capacity measures this domain. The important point is that this implies capacity is strictly monotone with respect to the partial order. We found that ST(n) has a natural, algebraically-defined preorder whose associated equivalence ≡ M defines a closed congruence on ST(n), and modulo which we obtain a copy of Conv n (P n ). This implies that capacity is strictly monotone with respect to the pre-order on ST(n).
In addition, we used the probabilistic measures on compact spaces to define three monads, each of which tells us something about classical channels. The first realizes ST(m, n) as the morphisms on the Kleisli category of the monad Prob S . The second shows that ST(n) is the free compact, affine monoid Prob M [n → n], while the third shows that DT(n) is the free compact monoid over S(n), the group of permutations on n letters. This last also implies DT(n) has a zero, which is Haar measure on S(n).
The work discussed here concerns classical channels, but we believe that much of it could be generalized to the quantum setting. We pointed out one connection to existing work on the roll of free affine monoids in analyzing quantum qubit channels. In any case, we have shown that the basic results of [14] generalize from the binary case, where the capacity function of a binary channel was studied in terms of the subinterval of [0, 1] it determines. The analog here is the polytope the rows of an n × n-stochastic channel determine.