text:
Learning Unknown Markov Decision Processes: A Thompson Sampling Approach

We consider the problem of learning an unknown Markov Decision Process (MDP) that is weakly communicating in the infinite horizon setting. We propose a Thompson Sampling-based reinforcement learning algorithm with dynamic episodes (TSDE). At the beginning of each episode, the algorithm generates a sample from the posterior distribution over the unknown model parameters. It then follows the optimal stationary policy for the sampled model for the rest of the episode. The duration of each episode is dynamically determined by two stopping criteria. The first stopping criterion controls the growth rate of episode length. The second stopping criterion happens when the number of visits to any state-action pair is doubled. We establish $\tilde O(HS\sqrt{AT})$ bounds on expected regret under a Bayesian setting, where $S$ and $A$ are the sizes of the state and action spaces, $T$ is time, and $H$ is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs. Numerical results show it to perform better than existing algorithms for infinite horizon MDPs.

Introduction
We consider the problem of reinforcement learning by an agent interacting with an environment while trying to minimize the total cost accumulated over time. The environment is modeled by an infinite horizon Markov Decision Process (MDP) with finite state and action spaces. When the environment is perfectly known, the agent can determine optimal actions by solving a dynamic program for the MDP [1]. In reinforcement learning, however, the agent is uncertain about the true dynamics of the MDP. A naive approach to an unknown model is the certainty equivalence principle. The idea is to estimate the unknown MDP parameters from available information and then choose actions as if the estimates are the true parameters. But it is well-known in adaptive control theory that the certainty equivalence principle may lead to suboptimal performance due to the lack of exploration [2]. This issue actually comes from the fundamental exploitation-exploration trade-off: the agent wants to exploit available information to minimize cost, but it also needs to explore the environment to learn system dynamics.
One common way to handle the exploitation-exploration trade-off is to use the optimism in the face of uncertainty (OFU) principle [3]. Under this principle, the agent constructs confidence sets for the system parameters at each time, find the optimistic parameters that are associated with the minimum cost, and then selects an action based on the optimistic parameters. The optimism procedure encourages exploration for rarely visited states and actions. Several optimistic algorithms are proved to possess strong theoretical performance guarantees [4][5][6][7][8][9][10].
An alternative way to incentivize exploration is the Thompson Sampling (TS) or Posterior Sampling method. The idea of TS was first proposed by Thompson in [11] for stochastic bandit problems. It has been applied to MDP environments [12][13][14][15][16][17] where the agent computes the posterior distribution of unknown parameters using observed information and a prior distribution. A TS algorithm generally proceeds in episodes: at the beginning of each episode a set of MDP parameters is randomly sampled from the posterior distribution, then actions are selected based on the sampled model during the episode. TS algorithms have the following advantages over optimistic algorithms. First, TS algorithms can easily incorporate problem structures through the prior distribution. Second, they are more computationally efficient since a TS algorithm only needs to solve the sampled MDP, while an optimistic algorithm requires solving all MDPs that lie within the confident sets. Third, empirical studies suggest that TS algorithms outperform optimistic algorithms in bandit problems [18,19] as well as in MDP environments [13,16,17].
Due to the above advantages, we focus on TS algorithms for the MDP learning problem. The main challenge in the design of a TS algorithm is the lengths of the episodes. For finite horizon MDPs under the episodic setting, the length of each episode can be set as the time horizon [13]. When there exists a recurrent state under any stationary policy, the TS algorithm of [15] starts a new episode whenever the system enters the recurrent state. However, the above methods to end an episode can not be applied to MDPs without the special features. The work of [16] proposed a dynamic episode schedule based on the doubling trick used in [7], but a mistake in their proof of regret bound was pointed out by [20]. In view of the mistake in [16], there is no TS algorithm with strong performance guarantees for general MDPs to the best of our knowledge.
We consider the most general subclass of weakly communicating MDPs in which meaningful finite time regret guarantees can be analyzed. We propose the Thompson Sampling with Dynamic Episodes (TSDE) learning algorithm. In TSDE, there are two stopping criteria for an episode to end. The first stopping criterion controls the growth rate of episode length. The second stopping criterion is the doubling trick similar to the one in [7][8][9][10]16] that stops when the number of visits to any state-action pair is doubled. Under a Bayesian framework, we show that the expected regret of TSDE accumulated up to time T is bounded byÕ(HS √ AT ) whereÕ hides logarithmic factors. Here S and A are the sizes of the state and action spaces, T is time, and H is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs [7], and it matches the theoretical lower bound in order of T except for logarithmic factors. We present numerical results that show that TSDE actually outperforms current algorithms with known regret bounds that have the same order in T for a benchmark MDP problem as well as randomly generated MDPs.

Preliminaries
An infinite horizon Markov Decision Process (MDP) is described by (S, A, c, θ). Here S is the state space, A is the action space, c : S × A → [0, 1] 1 is the cost function, and θ : S 2 × A → [0, 1] represents the transition probabilities such that θ(s ′ |s, a) = P(s t+1 = s ′ |s t = s, a t = a) where s t ∈ S and a t ∈ A are the state and the action at t = 1, 2, 3 . . . . We assume that S and A are finite spaces with sizes S ≥ 2 and A ≥ 2, and the initial state s 1 is a known and fixed state. A stationary policy is a deterministic map π : S → A that maps a state to an action. The average cost per stage of a stationary policy is defined as Here we use J π (θ) to explicitly show the dependency of the average cost on θ. From MDP theory [1], we know that if the MDP is weakly communicating, the optimal average cost per stage J(θ) = min π J π (θ) satisfies the Bellman equation for all s ∈ S. The corresponding optimal stationary policy π * is the minimizer of the above optimization given by a = π * (s, θ).
Since the cost function c(s, a) ∈ [0, 1], J(θ) ∈ [0, 1] for all θ. If v satisfies the Bellman equation, v plus any constant also satisfies the Bellman equation. Without loss of generality, let min s∈S v(s, θ) = 0 and define the span of the MDP as sp(θ) = max s∈S v(s, θ). 2 We define Ω * to be the set of all θ such that the MDP with transition probabilities θ is weakly communicating, and there exists a number H such that sp(θ) ≤ H. We will focus on MDPs with transition probabilities in the set Ω * .

Reinforcement Learning for Weakly Communicating MDPs
We consider the reinforcement learning problem of an agent interacting with a random weakly communicating MDP (S, A, c, θ * ). We assume that S, A and the cost function c are completely known to the agent. The actual transition probabilities θ * is randomly generated at the beginning before the MDP interacts with the agent. The value of θ * is then fixed but unknown to the agent. The complete knowledge of the cost is typical as in [7,15]. Algorithms can generally be extended to the unknown costs/rewards case at the expense of some constant factor for the regret bound.
At each time t, the agent selects an action according to is the history of states and actions. The is called a learning algorithm. The functions φ t allow for the possibility of randomization over actions at each time.
We focus on a Bayesian framework for the unknown parameter θ * . Let µ 1 be the prior distribution for θ * , i.e., for any set Θ, P(θ * ∈ Θ) = µ 1 (Θ). We make the following assumptions on µ 1 . Assumption 1. The support of the prior distribution µ 1 is a subset of Ω * . That is, the MDP is weakly communicating and sp(θ * ) ≤ H.
In this Bayesian framework, we define the expected regret (also called Bayesian regret or Bayes risk) of a learning algorithm φ up to time T as where s t , a t , t = 1, . . . , T are generated by φ and J(θ * ) is the optimal per stage cost of the MDP. The above expectation is with respect to the prior distribution µ 1 for θ * , the randomness in state transitions, and the randomized algorithm. The expected regret is an important metric to quantify the performance of a learning algorithm.

Thompson Sampling with Dynamic Episodes
In this section, we propose the Thompson Sampling with Dynamic Episodes (TSDE) learning algorithm. The input of TSDE is the prior distribution µ 1 . At each time t, given the history h t , the agent can compute the posterior distribution µ t given by µ t (Θ) = P(θ * ∈ Θ|h t ) for any set Θ. Upon applying the action a t and observing the new state s t+1 , the posterior distribution at t + 1 can be updated according to Bayes' rule as Let N t (s, a) be the number of visits to any state-action pair (s, a) before time t. That is, N t (s, a) = |{τ < t : (s τ , a τ ) = (s, a)}|.
With these notations, TSDE is described as follows.
Algorithm 1 Thompson Sampling with Dynamic Episodes (TSDE) The TSDE algorithm operates in episodes. Let t k be start time of the kth episode and T k = t k+1 −t k be the length of the episode with the convention T 0 = 1. From the description of the algorithm, t 1 = 1 and t k+1 , k ≥ 1, is given by At the beginning of episode k, a parameter θ k is sampled from the posterior distribution µ t k . During each episode k, actions are generated from the optimal stationary policy π k for the sampled parameter θ k . One important feature of TSDE is that its episode lengths are not fixed. The length T k of each episode is dynamically determined according to two stopping criteria: (i) t > t k + T k−1 , and (ii) N t (s, a) > 2N t k (s, a) for some state-action pair (s, a). The first stopping criterion provides that the episode length grows at a linear rate without triggering the second criterion. The second stopping criterion ensures that the number of visits to any state-action pair (s, a) during an episode should not be more than the number visits to the pair before this episode. Remark 1. Note that TSDE only requires the knowledge of S, A, c, and the prior distribution µ 1 . TSDE can operate without the knowledge of time horizon T , the bound H on span used in [7], and any knowledge about the actual θ * such as the recurrent state needed in [15].

Main Result
Theorem 1. Under Assumption 1, The proof of Theorem 1 appears in Section 4. Remark 2. Note that our regret bound has the same order in H, S, A and T as the optimistic algorithm in [7] which is the best available bound for weakly communicating MDPs. Moreover, the bound does not depend on the prior distribution or other problem-dependent parameters such as the recurrent time of the optimal policy used in the regret bound of [15].

Approximation Error
At the beginning of each episode, TSDE computes the optimal stationary policy π k for the parameter θ k . This step requires the solution to a fixed finite MDP. Policy iteration or value iteration can be used to solve the sampled MDP, but the resulting stationary policy may be only approximately optimal in practice. We call π an ǫ−approximate policy if c(s, π(s)) + When the algorithm returns an ǫ k −approximate policyπ k instead of the optimal stationary policy π k at episode k, we have the following regret bound in the presence of such approximation error. Theorem 2. If TSDE computes an ǫ k −approximate policyπ k instead of the optimal stationary policy π k at each episode k, the expected regret of TSDE satisfies Theorem 2 shows that the approximation error in the computation of optimal stationary policy is only additive to the regret under TSDE. The regret bound would remainÕ(HS √ AT ) if the approximation error is such that ǫ k ≤ 1 k+1 . The proof of Theorem 2 is in the appendix due to the lack of space.

Number of Episodes
To analyze the performance of TSDE over T time steps, define K T = arg max {k : t k ≤ T } be the number of episodes of TSDE until time T . Note that K T is a random variable because the number of visits N t (x, u) depends on the dynamical state trajectory. In the analysis for time T we use the convention that t (KT +1) = T + 1. We provide an upper bound on K T as follows. Lemma 1.
Proof. Define macro episodes with start times t ni , i = 1, 2, . . . where t n1 = t 1 and The idea is that each macro episode starts when the second stopping criterion happens. Let M be the number of macro episodes until time T and define n (M+1) = K T + 1.
T k be the length of the ith macro episode. By the definition of macro episodes, any episode except the last one in a macro episode must be triggered by the first stopping criterion. Therefore, within the ith macro episode, T k = T k−1 + 1 for all k = n i , n i + 1, . . . , n i+1 − 2. Hence, Consequently, n i+1 − n i ≤ 2T i for all i = 1, . . . , M . From this property we obtain Using (7) and the fact that where the second inequality is Cauchy-Schwarz.
From Lemma 6 in the appendix, the number of macro episodes M ≤ SA log(T ). Substituting this bound into (8) we obtain the result of this lemma.
Remark 3. TSDE computes the optimal stationary policy of a finite MDP at each episode. Lemma 1 ensures that such computation only needs to be done at a sublinear rate of 2SAT log(T ).

Regret Bound
As discussed in [13,20,21], one key property of Thompson/Posterior Sampling algorithms is that for any function f , if θ t is sampled from the posterior distribution at time t. This property leads to regret bounds for algorithms with fixed sampling episodes since the start time t k of each episode is deterministic. However, our TSDE algorithm has dynamic episodes that requires us to have the stopping-time version of the above property.
Lemma 2. Under TSDE, t k is a stopping time for any episode k. Then for any measurable function f and any σ(h t k )−measurable random variable X, we have Proof. From the definition (6), the start time t k is a stopping-time, i.e. t k is σ(h t k )−measurable.
Note that θ k is randomly sampled from the posterior distribution µ t k . Since t k is a stopping time, t k and µ t k are both measurable with respect to σ(h t k ). From the assumption, X is also measurable with respect to σ(h t k ). Then conditioned on h t k , the only randomness in f (θ k , X) is the random sampling in the algorithm. This gives the following equation: since µ t k is the posterior distribution of θ * given h t k . Now the result follows by taking the expectation of both sides.
For t k ≤ t < t k+1 in episode k, the Bellman equation (1) holds by Assumption 1 for s = s t , θ = θ k and action a t = π k (s t ). Then we obtain Using (10), the expected regret of TSDE is equal to where R 0 , R 1 and R 2 are given by We proceed to derive bounds on R 0 , R 1 and R 2 .
Based on the key property of Lemma 2, we derive an upper bound on R 0 .
Lemma 3. The first term R 0 is bounded as Proof. From monotone convergence theorem we have Note that the first stopping criterion of TSDE ensures that T k ≤ T k−1 + 1 for all k. Because J(θ k ) ≥ 0, each term in the first summation satisfies Note that 1 {t k ≤T } (T k−1 + 1) is measurable with respect to σ(h t k ). Then, Lemma 2 gives Combining the above equations we get Note that the first stopping criterion of TSDE plays a crucial role in the proof of Lemma 3. It allows us to bound the length of an episode using the length of the previous episode which is measurable with respect to the information at the beginning of the episode.
The other two terms R 1 and R 2 of the regret are bounded in the following lemmas. Their proofs follow similar steps to those in [13,16]. The proofs are in the appendix due to the lack of space. Lemma 4. The second term R 1 is bounded as Lemma 5. The third term R 2 is bounded as We are now ready to prove Theorem 1.
Proof of Theorem 1. From (11), where the inequality comes from Lemma 3, Lemma 4. Then the claim of the theorem directly follows from Lemma 1 and Lemma 5.

Simulations
In this section, we compare through simulations the performance of TSDE with three learning algorithms with the same regret order: UCRL2 [8], TSMDP [15], and Lazy PSRL [16]. UCRL2 is an optimistic algorithm with similar regret bounds. TSMDP and Lazy PSRL are TS algorithms for infinite horizon MDPs. TSMDP has the same regret order in T given a recurrent state for resampling. The original regret analysis for Lazy PSRL is incorrect, but the regret bounds are conjectured to be correct [20]. We chose δ = 0.05 for the implementation of UCRL2 and assume an independent Dirichlet prior with parameters [0.1, . . . , 0.1] over the transition probabilities for all TS algorithms.
We consider two environments: randomly generated MDPs and the RiverSwim example [22]. For randomly generated MDPs, we use the independent Dirichlet prior over 6 states and 2 actions but with a fixed cost. We select the resampling state s 0 = 1 for TSMDP here since all states are recurrent under the Dirichlet prior. The RiverSwim example models an agent swimming in a river who can choose to swim either left or right. The MDP consists of six states arranged in a chain with the agent starting in the leftmost state (s = 1). If the agent decides to move left i.e with the river current then he is always successful but if he decides to move right he might fail with some probability. The cost function is given by: c(s, a) = 0.8 if s = 1, a = left; c(s, a) = 0 if s = 6, a = right; and c(s, a) = 1 otherwise. The optimal policy is to swim right to reach the rightmost state which minimizes the cost. For TSMDP in RiverSwim, we consider two versions with s 0 = 1 and with s 0 = 3 for the resampling state. We simulate 500 Monte Carlo runs for both the examples and run for T = 10 5 . From Figure 1(a) we can see that TSDE outperforms all the three algorithms in randomly generated MDPs. In particular, there is a significant gap between the regret of TSDE and that of UCRL2 and TSMDP. The poor performance of UCRL2 assures the motivation to consider TS algorithms. From the specification of TSMDP, its performance heavily hinges on the choice of an appropriate resampling state which is not possible for a general unknown MDP. This is reflected in the randomly generated MDPs experiment.
In the RiverSwim example, Figure 1(b) shows that TSDE significantly outperforms UCRL2, Lazy PSRL, and TSMDP with s 0 = 3. Although TSMDP with s 0 = 1 performs slightly better than TSDE, there is no way to pick this specific s 0 if the MDP is unknown in practice. Since Lazy PSRL is also equipped with the doubling trick criterion, the performance gap between TSDE and Lazy PSRL highlights the importance of the first stopping criterion on the growth rate of episode length. We also like to point out that in this example, the MDP is fixed and is not generated from the Dirichlet prior. Therefore, we conjecture that TSDE also has the same regret bounds under a non-Bayesian setting.

Conclusion
We propose the Thompson Sampling with Dynamic Episodes (TSDE) learning algorithm and es-tablishÕ(HS √ AT ) bounds on expected regret for the general subclass of weakly communicating MDPs. Our result fills a gap in the theoretical analysis of Thompson Sampling for MDPs. Numerical results validate that the TSDE algorithm outperforms other learning algorithms for infinite horizon MDPs.
The TSDE algorithm determines the end of an episode by two stopping criteria. The second criterion comes from the doubling trick used in many reinforcement learning algorithms. But the first criterion on the linear growth rate of episode length seems to be a new idea for episodic learning algorithms. The stopping criterion is crucial in the proof of regret bound (Lemma 3). The simulation results of TSDE versus Lazy PSRL further shows that this criterion is not only a technical constraint for proofs, it indeed helps balance exploitation and exploration. Proof. Since the second stopping criterion is triggered whenever the number of visits to a stateaction pair is doubled, the start times of macro episodes can be expressed as Since the number of visits to (s, a) is doubled at every t k such that k ∈ M (s,a) , the size of M (s,a) should not be larger than O(log(T )). This argument is made rigorous as follows. If where the first inequality is the union bound and the third inequality holds because log is concave.

B Proof of Lemma 4
Proof. We have where the last equality holds because 0 ≤ v(s, θ) ≤ sp(θ) ≤ H for all s, θ from Assumption 1.

C Proof of Lemma 5
Proof. For notational simplicity, we use z = (s, a) ∈ S × A and z t = (s t , a t ) to denote the corresponding state-action pair. Then Since 0 ≤ v(s ′ , θ t ) ≤ H from Assumption 1, each term in the inner summation is bounded by Nt k (zt) is the empirical mean for the transition probability at the beginning of episode k where N t k (s t , a t , s ′ ) = |{τ < t k : (s τ , a τ , s τ +1 ) = (s t , a t , s ′ )}|.

Define confidence set
where β k (z) = 14S log(2At k T ) max(1,Nt k (z)) . Note that β k (z) is the confidence set used in [8] with δ = 1/T . Then we have For the first term in (14) we have .
for all t in the kth episodes from the second criterion. So we get 28S log(2AT 2 ) max(1, N t (z t )) ≤ 56S log(AT ) T t=1 1 max(1, N t (z t )) .
Since N t (z t ) is the count of visits to z t , we have Since z N T +1 (z) = T , we have Combining (15)- (16) we get Let's now work on the second term in (14). Since T k ≤ T for all k, we have Since B k is measurable with respect to σ(h t k ), using Lemma 2 we get By the definition of B k in (13), [8, Lemma 17, setting δ = 1/T ] implies that Combining (18), (19) and (20) we obtain The statement of the lemma then follows by substituting (17) and (21) into (14).
Since R 0 + R 1 + R 2 =Õ(HS √ AT ) from the proof of Theorem 1, we obtain the first part of the result.
where the last inequality follows from Lemma 1.


extfieldsofstudy:
Computer Science
Mathematics

text:
Constraint-Based Clustering Selection

Semi-supervised clustering methods incorporate a limited amount of supervision into the clustering process. Typically, this supervision is provided by the user in the form of pairwise constraints. Existing methods use such constraints in one of the following ways: they adapt their clustering procedure, their similarity metric, or both. All of these approaches operate within the scope of individual clustering algorithms. In contrast, we propose to use constraints to choose between clusterings generated by very different unsupervised clustering algorithms, run with different parameter settings. We empirically show that this simple approach often outperforms existing semi-supervised clustering methods.

I. INTRODUCTION
Clustering is one of the core tasks in data analysis [19]. It is inherently subjective, as users may prefer very different clusterings of the same data [10], [34]. Semi-supervised clustering [35], [37] aims to deal with this subjectivity by allowing the user to specify background knowledge, often in the form of pairwise constraints that indicate whether two instances should be in the same cluster or not.
Traditional approaches to semi-supervised (or constraintbased) clustering use constraints in one of the following three ways. First, one can modify an existing clustering algorithm to take them into account. This approach is taken in COP-KMeans [35], one of the first clustering algorithms able to deal with pairwise constraints. Second, one can learn a distance metric based on the constraints [37], after which the metric is used within a traditional clustering algorithm. Third, one can combine the above two approaches and develop so-called hybrid methods [7].
Our approach to constraint-based clustering is quite different from existing methods, and does not fit in any of these three categories. It is motivated by the well-known fact that different algorithms may produce very different clusterings of the same data [14], and even within one algorithm, different parameter settings may yield different clusterings. This implies that selecting a clustering algorithm and tuning its parameter settings is crucial to obtain a good clustering.
We propose to use constraints to solve these tasks: to find an appropriate clustering, we first generate a set of clusterings using several unsupervised algorithms, with different hyperparameter settings, and afterwards select from this set the clustering that satisfies the largest number of constraints. Our experiments show that, surprisingly, this simple constraintbased selection approach often yields better clusterings than existing semi-supervised algorithms. This shows that it is more important to use an algorithm of which the inherent bias matches a particular problem, than to modify the optimization criterion of any individual algorithm to take the constraints into account. We also present a method for selecting the most informative constraints first, which further increases the usefulness of our approach.
The remainder of this paper is structured as follows. In Section II we give some background on semi-supervised clustering, and algorithm and hyperparameter selection for clustering. Section III presents our approach to using pairwise constraints in clustering, which we call COBS (for Constraint-Based Selection). In Section 4 we describe how COBS can be extended to actively select informative constraints. We conclude in Section V.

II. BACKGROUND
We first describe related work on semi-supervised clustering. As our approach consists of using constraints to choose an algorithm and tune its parameters, we also discuss related work on meta-learning for clustering, as well as on algorithm and hyperparameter selection.
Semi-supervised clustering algorithms allow the user to incorporate a limited amount of supervision into the clustering procedure. Several kinds of supervision have been proposed, one of the most popular ones being pairwise constraints. Must-link (ML) constraints indicate that two instances should be in the same cluster, cannot-link (CL) constraints that they should be in different clusters. Most existing semi-supervised approaches use such constraints within the scope of an individual clustering algorithm. COP-KMeans [35], for example, modifies the clustering assignment step of K-means: instances are assigned to the closest cluster for which the assignment does not violate any constraints. Similarly, the clustering procedures of DBSCAN [9], [21], [28], EM [29] and spectral clustering [26], [36] have been extended to incorporate pairwise constraints. Another approach to semisupervised clustering is to learn a distance metric based on the constraints [3], [11], [37]. Xing et al. [37], for example, propose to learn a Mahalanobis distance by solving a convex optimization problem in which the distance between instances with a must-link constraint between them is minimized, while simultaneously separating instances connected by a cannotlink constraint. Hybrid algorithms, such as MPCKMeans [7], combine metric learning with an adapted clustering procedure.
Meta-learning and algorithm selection have been studied extensively in supervised learning [8], [30], but much less clustering. There is some work on building meta-learning systems that recommend clustering algorithms [12], [15]. However, these systems do not take hyperparameter selection into account, or any form of supervision. More related to ours is the work of Caruana et al. [10]. They generate a large number of clusterings using K-means and spectral clustering, and cluster these clusterings. This meta-clustering is presented to the user as a dendrogram. Here, we also generate a set of clusterings, but afterwards we select from that set the most suitable clustering based on pairwise constraints. The only other work, to our knowledge, that has explored the use of pairwise constraints for algorithm selection is that by Adam and Blockeel [1]. They define a meta-feature based on constraints, and use this feature to predict whether EM or spectral clustering will perform better for a dataset. While their meta-feature attempts to capture one specific property of the desired clusters, i.e. whether they overlap, our approach is more general and allows selection between any clustering algorithms.
Whereas algorithm selection has received little attention in clustering, several methods have been proposed for hyperparameter selection.
One strategy is to run the algorithm with several parameter settings, and select the clustering that scores highest on an internal quality measure [2], [31]. Such measures try to capture the idea of a "good" clustering. A first limitation is that they are not able to deal with the inherent subjectivity of clustering, as they do not take any external information into account. Furthermore, internal measures are only applicable within the scope of individual clustering algorithms, as each of them comes with its own bias [34]. For example, the vast majority of them has a preference for spherical clusters, making them suitable for K-means, but not for e.g. spectral clustering and DBSCAN.
Another strategy for parameter selection in clustering is based on stability analysis [5], [6], [33]. A parameter setting is considered to be stable if similar clusterings are produced with that setting when it is applied to several datasets from the same underlying model. These datasets can for example be obtained by taking subsamples of the original dataset [6], [20]. In contrast to internal quality measures, stability analysis does not require an explicit definition of what it means for a clustering to be good. Most studies on stability focus on selecting parameter settings in the scope of individual algorithms (in particular, often the number of clusters).
Additionally, one can also avoid the need for explicit parameter selection. In self-tuning spectral clustering [39], for example, the affinity matrix is constructed based on local statistics and the number of clusters is estimated using the structure of the eigenvectors of the Laplacian.
A key distinction with COBS is that none of the above methods takes the subjective preferences of the user into account. We will compare our constraint-based selection strategy to some of them in the next section.

III. CONSTRAINT-BASED CLUSTERING SELECTION
Algorithm and hyperparameter selection are difficult tasks in an entirely unsupervised setting, mainly due to the lack of a well-defined way to estimate the quality of clustering results [14]. We propose to use constraints for this purpose, and estimate the quality of a clustering as the number of constraints that it satisfies. This quality estimate allows us to do a search over unsupervised algorithms and their parameter settings, as described in Algorithm 1. We use a basic grid search, but in principle also more advanced optimization strategies could be used [18], [30]. We assume that we are given a set of must-link constraints ML, where (i, j) ∈ ML indicates that instances x i and x j should be in the same cluster. Similarly, we are given a set of cannot-link constraints CL, where (i, j) ∈ CL indicates that x i and x j should be in different clusters. A clustering maps instances (through their index) to their cluster label, i.e. c[i] = k indicates that in clustering c, x i is an element of cluster k. The indicator function I has value one if the enclosed expression is true, zero otherwise. We select the "best" solution from a set of clusterings as the one satisfying the largest number of constraints (in case of a tie, we select randomly from the involved clusterings).

Algorithm 1 Constraint-based selection (COBS)
Input: D: a dataset ML: set of must-link constraints CL: set of cannot-link constraints Output: a clustering of D 1: Generate a set of clusterings C by varying the hyperparameters of several unsupervised clustering algorithms 2: return arg max COBS is motivated by the following two observations. First, it is commonly accepted that no single algorithm performs best on all clustering problems: each algorithm comes with its own bias, which may match a particular problem to a greater or lesser degree [14]. Traditional semisupervised approaches use constraints within the scope of an individual algorithm. By doing so, they can change the bias of the algorithm, but only to a certain extent. For instance, using constraints to learn a Mahalanobis distance allows Kmeans to find ellipsoidal clusters, rather than spherical ones, but still does not make it possible to find non-convex clusters. In contrast, by using constraints to choose between clusterings generated by very different algorithms, COBS aims to select the most suitable one from a diverse range of biases.
Second, it is also widely known that within a single clustering algorithm the choice of the hyperparameters can strongly influence the clustering result. Consequently, choosing a good parameter setting is crucial. Currently, a user can either do this manually, or use one of the selection strategies discussed in section II. Both options come with significant drawbacks. Doing parameter tuning manually is time-consuming, given the often large number of combinations one might try. Existing automated selection strategies avoid this manual labor, but can easily fail to select a good setting as they do not take the user's preferences into account. For COBS, parameters are an asset rather than a burden. They allow generating a large and diverse set of clusterings, from which we can select the most suitable solution with a limited number of pairwise constraints.
Although our approach is very simple, it does not appear to have been studied before, neither as a way to incorporate constraints into clustering, nor as a way to select clustering algorithms and their parameter settings (despite the substantial body of research on both constraint-based clustering and hyperparameter selection).

Research questions
In the remainder of this section, we aim to answer the following questions: Q1 How does COBS, for hyperparameter selection only, compare to unsupervised hyperparameter selection methods? Q2 How does COBS, for hyperparameter selection only, compare to existing semi-supervised clustering algorithms? Q3 How does COBS, for both algorithm and hyperparameter selection, compare to existing semi-supervised algorithms? Q4 Can we improve COBS by using semi-supervised algorithms to generate clusterings, instead of unsupervised ones? Although our selection strategy is also related to metaclustering [10], an experimental comparison would be difficult as meta-clustering produces a dendrogram of clusterings for the user to explore. The user can traverse this dendrogram to obtain a single clustering, but the outcome of this process is highly subjective. COBS works with pairwise constraints, therefore we compare to other methods that do the same.

Experimental methodology
To answer our research questions we perform experiments with 10 UCI classification datasets, listed in Table I. These have also been used in several other studies on semi-supervised clustering [7], [38]. The optdigits389 dataset is a subset of the UCI handwritten digits dataset, containing only digits 3, 8 and 9 [7], [22]. The classes are assumed to represent the clusters of interest. We evaluate how well the returned clusters coincide with them by computing the Adjusted Rand Index (ARI) [17], which is a commonly used measure for this; 0 means that the clustering is not better than random, 1 is a perfect match. In our experiments with semi-supervised clustering, we always repeat the following steps 25 times and report average results:  wine  178  13  3  dermatology  358  33  6  iris  147  4  3  ionosphere  350  34  2  breast-cancer-wisconsin  449  32  2  ecoli  336  7  8  optdigits389  1151  64  3  segmentation  2100  19  7  glass  214  10  7  hepatitis 112 19 2  self-tuning spectral clustering 1) Randomly partition the full dataset into 70% ("potential supervision set") and 30% ("left-out set"). 2) Generate c pairwise constraints (c is a parameter) by repeatedly selecting two random instances from the supervision set, and adding a must-link constraint if they belong to the same class, and a cannot-link otherwise. 3) Apply COBS to the full dataset to obtain a clustering. 4) Evaluate the clustering by calculating the ARI on all objects that were not involved in any constraints.
We avoid including pairs in the evaluation that were among the given constraints, as this would be the equivalent of testing on the training set.
We use K-means, DBSCAN and spectral clustering to generate clusterings in step one of Algorithm 1, as they are common representatives of different types of algorithms (we use implementations from scikit-learn [24]). The hyperparameters are varied in the ranges specified in Table II. In particular, for each dataset we generate 180 clusterings using K-means (for each number of clusters we store the clusterings obtained with 20 random initializations), 351 using spectral clustering and 400 using DBSCAN, yielding a total of 931 clusterings. For discrete parameters, clusterings are generated for the complete range. For continuous parameters, clusterings are generated using 20 evenly spaced values in the specified intervals. For the parameter used in DBSCAN, the lower and upper bounds are the minimum and maximum pairwise distances between instances (referred to as min(d) and max(d) in Table II).
All datasets are normalized by rescaling each feature to the range [0, 1]. We use the Euclidean distance for all unsupervised algorithms.

Q1: COBS vs. unsupervised hyperparameter tuning
To evaluate hyperparameter selection for individual algorithms, we use Algorithm 1 with C a set of clusterings generated using one particular algorithm (K-means, DBSCAN or spectral). We compare COBS to state of the art unsupervised selection strategies. As there is no single method that can be used for all three algorithms, we use three different approaches, which are briefly described next.
K-means has one hyperparameter: the number of clusters K. A popular method to select K in K-means is by using internal clustering quality measures [2], [31]. K-means is ran for different values of K (and in this case also for different random seeds), and afterwards the clustering that scores highest on such an internal measure is chosen. In our setup, we generate 20 clusterings for each K by using different random seeds. We select the clustering that scores highest on the silhouette index [27], which was identified as one of the best internal criteria by Arbelaitz et al. [2].
DBSCAN has two parameters: , which specifies how close points should be to be in the same neighborhood, and minP ts, which specifies the number of points that are required in the neighborhood to be a core point. Most internal criteria are not suited for DBSCAN, as they assume spherical clusters, and one of the key characteristics of DBSCAN is that it can find clusters with arbitrary shape. One exception is the Density-Based Cluster Validation (DBCV) score [23], which we use in our experiments.
Spectral clustering requires the construction of a similarity graph, which can be done in several ways [32]. If a k-nearest neighbor graph is used, k has to be set. For graphs based on a Gaussian similarity function, σ has to be set to specify the width of the neighborhoods. Also the number of clusters K should be specified. Self-tuning spectral clustering [39] avoids having to specify any of these parameters, by relying on local statistics to compute different σ values for each instance, and by exploiting structure in the eigenvectors to determine the number of clusters. This approach is different from the one used for K-means and DBSCAN, as here we do not generate a set of clusterings first, but instead hyperparameters are estimated directly from the data.
Results and conclusion: The columns of Table III marked with Q1 compare the ARIs obtained with the unsupervised approaches to those obtained with COBS. The best of these two is underlined for each algorithm and dataset combination. Most of the times the constraint-based selection strategy performs better, and often by a large margin. Note for example the large difference for ionosphere: DBSCAN is able to produce a good clustering, but it is only selected using the constraintbased approach. When the unsupervised selection method performs better, the difference is usually small. We conclude that often the internal measures do not match the actually desired clusters. Constraints provide useful information that can help select a good parameter setting.

Q2: COBS vs. semi-supervised algorithms
It is not too surprising that COBS outperforms unsupervised hyperparameter selection, since it has access to more information. We now compare to semi-supervised algorithms, which have access to the same information.
Existing semi-supervised algorithms: We compare to the following algorithms, as they are semi-supervised variants of the unsupervised algorithms used in our experiments: • MPCKMeans [7] is a hybrid semi-supervised extension of K-means. It minimizes an objective that combines the within-cluster sum of squares with the cost of violating constraints. This objective is greedily minimized using a procedure based on K-means. Besides a modified cluster assignment step and the usual cluster center re-estimation step, this procedure also adapts an individual metric associated with each cluster in each iteration. We use the implementation available in the WekaUT package 1 .
• FOSC-OpticsDend [9] is a semi-supervised extension of OPTICS, which is in turn based on ideas similar to DBSCAN. The first step of this algorithm is to run the unsupervised OPTICS algorithm, and to construct a dendrogram using its output. The FOSC framework is then used to extract a flat clustering from this dendrogram that is optimal w.r.t. the given constraints.
• COSC [26] is based on spectral clustering, but optimizes for an objective that combines the normalized cut with a penalty for constraint violation. We use the implementation available on the authors' web page 2 . In our experiments, the only kind of supervision that is given to the algorithms is in the form of pairwise constraints. In particular, the number of clusters K is assumed to be unknown. In COBS, K is treated as any other hyperparameter. MPCKMeans and COSC, however, require specifying the number of clusters. The following strategies are used to select K based on the constraints: • NumSat: We run the algorithms for multiple K, and select the clustering that violates the smallest number of constraints. In case of a tie, we choose the solution with the lowest number of clusters. • CVCP: Cross-Validation for finding Clustering Parameters [25] is a cross-validation procedure for semisupervised clustering. The set of constraints is divided into n independent folds. To evaluate a parameter setting, the algorithm is repeatedly run on the entire dataset given the constraints in n − 1 folds, keeping aside the nth fold as a test set. The clustering that is produced given the constraints in the n−1 folds, is then considered as a classifier that distinguishes between must-link and cannotlink constraints in the nth fold. The F-measure is used to evaluate the score of this classifier. The performance of the parameter setting is then estimated as the average F-measure over all test folds. This process is repeated for all parameter settings, and the one resulting in the highest average F-measure is retained. The algorithm is then run with this parameter setting using all constraints to produce the final clustering. We use 5-fold crossvalidation. We also compare to unsupervised hyperparameter selection strategies for the semi-supervised algorithms. In particular, we use the silhouette index for MPCKMeans, and the eigengap heuristic for COSC [32]. The affinity matrix for COSC is constructed using local scaling as in [26]. Table III marked with Q2 show the ARIs obtained with the semi-supervised algorithms. The best result for each type of algorithm (unsupervised or semi-supervised) is indicated in bold. The table shows that in several cases it is more advantageous to use the constraints to optimize the hyperparameters of the unsupervised algorithm (as COBS does). In other cases, it is better to use the constraints within the algorithm itself, to perform a more informed search (as the semi-supervised variants do). Within the scope of a single clustering algorithm, neither strategy consistently outperforms the other. For example, if we use spectral clustering on the dermatology data, it is better to use the constraints for tuning the hyperparameters of unsupervised spectral clustering (also varying k and σ for constructing the signature matrix) than within COSC, its semi-supervised variant (which uses local scaling for this). In contrast, if we use density-based clustering on the same data, it is better to use constraints in FOSC-OpticsDend (which does not have an parameter, and for which minP ts is set to 4, a value commonly used in the literature [9], [13]) than to use them to tune the hyperparameters of DBSCAN (varying both and minP ts).

Q3: COBS with multiple unsupervised algorithms
In the previous two subsections, we showed that constraints can be useful to tune the hyperparameters of individual algorithms. Table III also shows, however, that no single algorithm (unsupervised or semi-supervised) performs well on all datasets. This motivates the use of COBS to not only select hyperparameters, but also the clustering algorithm. In this subsection we again use Algorithm 1, but set C in step 1 now includes clusterings produced by any of the three unsupervised algorithms.
Results: We compare COBS with existing semi-supervised algorithms in Figure 1 3 . COBS is able to find relatively good clusterings for the first 8 datasets. While some other approaches also do well on some of these datasets, none of them do so consistently. Compared to each competitor individually, COBS is clearly superior. For example, COSC-EigenGap outperforms COBS on the iris dataset, but performs much worse on several others. COBS performs poorly on glass and hepatitis, as do the other semi-supervised algorithms, although for hepatitis other approaches are able to find better solutions after a larger number of constraints. The overall poor performance on these last two datasets suggests that the class labels do not indicate a natural grouping.
Table IV allows us to assess the quality of the clusterings that are selected by COBS, relative to the quality of the best clustering in the set of generated clusterings. Column 2 shows the highest ARI of all generated clusterings for each dataset. Note that we can only compute this value in an experimental setting, in which we have labels for all elements. In a real clustering application, we cannot simply select the result with the highest ARI. Column 3, then, shows the ARI of the clustering that is actually selected using COBS when it is given 50 constraints. It shows that there still is room for improvement, i.e. a more advanced strategy might get closer to the maxima. Nevertheless, even our simple strategy gets close enough to outperform most other semi-supervised methods. The last column of Table IV shows how often and spectral clustering ('S'). It illustrates that the selected algorithm strongly depends on the dataset. For example, for ionosphere COBS selects clusterings generated by DBSCAN, as it is the only algorithm able to produce good clusterings of this dataset. For most other datasets, spectral clustering is preferred.
Conclusion: If any of the unsupervised algorithms is able to produce good clusterings, COBS can select them using a limited number of constraints. If not, COBS performs poorly, but in our experiments none of the algorithms did well in this case. We conclude that it is often better to use constraints to select and tune an unsupervised algorithm, than within a randomly chosen semi-supervised algorithm.

Q4: Using COBS with semi-supervised algorithms
In the previous section we have shown that we can use constraints to do algorithm and hyperparameter selection for unsupervised algorithms. On the other hand, constraints can also be useful when used within an adapted clustering IV: The ARI of the best clustering that is generated by any of the unsupervised algorithms, the ARI of the clustering that is selected after 50 constraints (averaged over 25 runs), and the algorithms that produced the selected clusterings. procedure, as traditional semi-supervised algorithms do. This raises the question: can we combine both approaches?
In this section, we use the constraints to select and tune a semi-supervised clustering algorithm. In particular, we vary the hyperparameters of the semi-supervised algorithms to generate the set of clusterings from which we select. The varied hyperparameters are the same as those for their unsupervised variants, except for two. First, is not varied for FOSC-OpticsDend, as it is not a hyperparameter for that algorithm. Second, in this section we only use k-nearest neighbors graphs for (semi-supervised) spectral clustering, as full similarity graphs lead to long execution times for COSC.
Results and conclusions: Column 3 of Table V shows that this strategy does not produce better results. This is caused by using the same constraints twice: once within the semisupervised algorithms, and once to evaluate the algorithms and select the best-performing one. Obviously, algorithms that overfit the given constraints will get selected in this manner. The problem could be alleviated by using separate constraints inside the algorithm and for evaluation, but this decreases the number of constraints that can effectively be used for either purpose. Column 4 of Table V shows the average ARIs that are obtained if we use half of the constraints within the semisupervised algorithms, and half to select one of the generated clusterings afterwards. This works better, but still often not as good as COBS with unsupervised algorithms. Results are only improved for segmentation, hepatitis and glass, the datasets with less clear clustering structure (as indicated by the ARIs). We conclude that using semi-supervised algorithms within COBS can only be beneficial if the semi-supervised algorithms use different constraints from those used for selection. Even then, when a limited number of constraints is available, using all of them for selection is often the best choice.

Note on computational complexity
One might expect COBS to be prohibitively expensive, given the large number of clusterings it needs to generate. This is not the case, for multiple reasons. First, the runtimes of individual clustering algorithms vary greatly, and in addition to that, some semi-supervised algorithms are much slower than their unsupervised counterpart. As a result, constructing many clusterings with unsupervised algorithms is only slightly more expensive than running the slowest semi-supervised algorithm just once. In our experiments, for the largest dataset we used (segmentation), generating 931 unsupervised clusterings took 560s on a single core, using scikit-learn implementations. A single run of COSC, the semi-supervised variant of spectral clustering, took 200s (using the Matlab implementation available on the authors' web page). If COSC is run multiple times, for instance with different numbers of clusters (as is done in COSC-NumSat and COSC-CVCP), its runtime quickly exceeds that of COBS.
Second, the runtime of COBS can be reduced in several ways. The cluster generation step can easily be parallelized. For larger datasets, one might consider doing the algorithm and hyperparameter selection on a sample of the data, and afterwards cluster the complete dataset only once with the selected configuration.
Finally, note that the added cost of doing algorithm and parameter selection is no different from its comparable, and commonly accepted, cost in (semi-)supervised learning. The focus is on maximally exploiting the limited amount of supervision, as obtaining labels or constraints is often expensive, whereas computation is cheap.

IV. ACTIVE COBS
Obtaining constraints can be costly, as they are often specified by human experts. Consequently, several methods have been proposed to actively select the most informative constraints [4], [22], [38]. We first briefly discuss some of these methods, and subsequently present a constraint selection strategy for COBS.

A. Related work
Basu et al. [4] were the first to propose an active constraint selection method for semi-supervised clustering. Their strategy is based on the construction of neighborhoods, which are points that are known to belong to the same cluster because must-link constraints are defined between them. These neighborhoods are initialized in the exploration phase: K (the number of clusters) instances with cannot-link constraints between them are sought, by iteratively querying the relation between the existing neighborhoods and the point farthest from these neighborhoods. In the subsequent consolidation phase these neighborhoods are expanded by iteratively querying a random point against the known neighborhoods until a mustlink occurs and the right neighborhood is found. Mallapragada et al. [22] extend this strategy by selecting the most uncertain points to query in the consolidation phase, instead of random ones. Note that in these approaches all constraints are queried before the actual clustering is performed. More recently, Xiong et al. [38] proposed the normalized point-based uncertainty (NPU) framework. Like the approach introduced by Mallapragada et al. [22], NPU incrementally expands neighborhoods and uses an uncertainty-based principle to determine which pairs to query. In the NPU framework, however, data is re-clustered several times, and at each iteration the current clustering is used to determine the next set of pairs to query. NPU can be used with any semi-supervised clustering algorithm, and Xiong et al. [38] use it with MPCKMeans to experimentally demonstrate its superiority to the method of Mallapragada et al. [22].

B. Active constraint selection in COBS
Like the approaches in [22] and [38], our constraint selection strategy for COBS is based on uncertainty sampling. Defining this uncertainty is straightforward within COBS, because of the availability of a set of clusterings: a pair is more uncertain if more clusterings disagree on whether it should be in the same cluster or not. Algorithm 2 presents a selection strategy based on this idea. We associate with each clustering c a weight w c that depends on the number of constraints c was right or wrong about. In each iteration we query the pair with the lowest weighted agreement. The agreement of a pair (line 5 of the algorithm) is defined as the absolute value of the difference between the sum of weights of clusterings in which the instances in the pair belong to the same cluster, and the sum of weights of clusterings in which they belong to a different cluster. The weights of clusterings that correctly "predict" the relation between pairs are increased by multiplying with an update factor m, weights of other clusterings are decreased by dividing by m. As the total number of pairwise constraints is quite large ( n 2 with n the number of instances), we only consider constraints in a small random sample P of all possible constraints.

C. Experiments
We first demonstrate the influence of the weight update factor and sample size, and then compare our approach to active constraint selection with NPU [38].
Effect of weight update factor and sample size: Our constraint selection strategy requires specifying a weight update factor m and a sample size s. Figure 2 shows the ∀c∈C: multiply w c with m if c correctly predicted the relation between i and j, divide by m if not 8: u←u + 1 9: end while 10: return the clustering with the highest weight results for wine and dermatology for various values of m. First, the figure shows that the active strategy can significantly improve performance over random selection. Second, it shows that the selection process is not very sensitive to the choice of the update factor. Figure 3 shows the results for various sample sizes. It shows that the sample size has a limited effect on performance for a small number of constraints, but that this effect increases as more constraints are given. In the remainder of this section we use a sample of 1000 constraints (i.e. we try to choose the most useful constraints to ask from 1000 possible queries), and set the weight update factor to 2.
Comparison to active selection with NPU: NPU [38] can be used in combination with any semi-supervised clustering algorithm, we use the same ones as in the previous section. We do not include CVCP hyperparameter selection in these experiments, because of its high computational complexity (for these experiments we cannot cluster for several fixed numbers of constraints, as the choice of the next constraints depends on the current clustering). For the same reason we only include the EigenGap parameter selection method for   Figure 4. For the first 8 datasets, the conclusions are similar to those for the random setting: COBS consistently performs relatively well. Also in the active setting, none of the approaches produces a clustering with a high ARI for glass. For hepatitis, however, MPCKMeans is able to find good clusterings while COBS is not, albeit only after a relatively large number of constraints (hepatitis contains 112 instances). This implies that, although the labels might not represent a natural grouping, the class structure does match the bias of MPCKMeans, and given many constraints the algorithm finds this structure.
Time complexity: We distinguish between the offline and online stages of COBS. In the offline stage, the set of clusterings is generated. As mentioned before, this took 560s on a single core for the largest dataset (segmentation, with 2100 instances). In the online stage, we select the most informative pairs and ask the user about their relation. Execution time is particularly important here, as this stage requires user interaction. In active COBS, selecting the next pair to query is O(|C||P |), as we have to loop through all clusterings (|C|) for each constraint in the sample (|P |). For the setup used in our experiments (|C|=931, |P |=1000), this was always less than 0.02s. Note that this time does not depend on the size of the dataset (as all clusterings are generated beforehand). In contrast, NPU requires re-clustering the data several times during the constraint selection process, which is usually significantly more computationally expensive.

Conclusion:
The COBS approach allows for a straightforward definition of uncertainty: pairs of instances are more uncertain if more clusterings disagree on them. Selecting the most uncertain pairs first can significantly increase performance.

V. CONCLUSION
Exploiting constraints has been the subject of substantial research, but all existing methods use them within the clustering process of individual algorithms. In contrast, we propose to use them to choose between clusterings generated by different unsupervised algorithms, ran with different parameter settings. We experimentally show that this strategy is superior to all the semi-supervised algorithms compared to, which themselves are state of the art and representative for a wide range of algorithms. For the majority of the datasets, it works as well as the best among them, and on average it performs much better. The generated clusterings can also be used to select more informative constraints first, which further improves performance.
In future work, we would like to study several strategies that have been used in supervised learning in the context of semi-supervised clustering. In particular, we want to consider more advanced algorithm and hyperparameter optimization strategies (as in [30]), meta-learning approaches (as in [8]), and combinations of these two (as in [16]).