iccv2019论文全集9664-flattening-a-hierarchical-clustering-through-active-learning

1、Flattening a Hierarchical Clustering through Active Learning Fabio Vitale Department of Computer Science INRIA Lille, France we call them the nodes abovec and the nodes belowc. Cutcalso univocally induces a clustering overL, made up of the clusters L(i1),L(i2),.,L(iK), wherei1,i2,.,iKare the nodes b

2、elowcthat the edges ofcare incident to. We denote this clustering byC(c), and call the nodesi1,i2,.,iKthe lower boundary ofc. We say that clusteringC0is realized byTif there exists a cutcofTsuch thatC(c) = C0. See Figure 1 (left) for a pictorial illustration. Clearly enough, for a givenL, and a give

3、n treeTwith set of leavesL, not all possible clusterings overLare realized byT, as the number and shape of the clusterings realized byTare strongly infl uenced byTs structure. LetN(T)be the number of clusterings realized byT(notice that this is also equal to the number of distinct cuts admitted byT)

4、. ThenN(T)can be computed through a simple recursive formula. If we letN(i)be the number of cuts realized byT(i), one can easily verify thatN(i) = 1 + N(left(i) N(right(i), withN(xi) = 1for allxi L. With this notation, we then haveN(T) = N(r(T). IfThasnleaves,N(T)ranges fromn, whenTis a degenerate l

5、ine tree, to the exponentialbnc, whenTis the full binary tree, where 1.502(e.g., /A003095). See again Figure 1 (left) for a simple example. 1 In fact, the trees we can handle are more general than binary: we are making the binary assumption throughout for presentational convenience onl

6、y. 2 A strongly binary tree is a rooted binary tree for which the root is adjacent to either zero or two nodes, and all non-root nodes are adjacent to either one or three nodes. 3 2x3x4x5x6x7x8x1x 5x4x7 x 2 x 8 x 1x 3x r T 2x3x4x5x6x7x8x1x 5x 4x7x 2 x 8 x 1x 3x r T 6x 6x 2x3x4x5x6x7x8x1x 5x4x 7 x 2

7、x 8 x 1x 3x r T 6x 2x3x4x5x6x7x8x1x 5x 4x 7 x 2 x 8 x 1x 3x r T 6x 12 34 Figure 2:Cuts and corresponding values ofdH(,bC)in four input treesforthesameground-truth determinedbythecluster- ingx1,x2,x3,x4,x5,x6, x7,x8.Underneath each tree is the clustering b Cinduced by the depicted cut. The color of a

8、 cluster is green if it corresponds to a cluster in the clustering of, and is red other- wise. InT1we havedH(,bC) = 0 (realizable case). The other 3 trees illustrate the non-realizable case with the cut minimizingdH(,bC)on the corresponding tree.Recalling that dH(,bC)counts ordered pairs, inT2 we ha

9、vedH(,bC) = 10, because x6 now belongs to the fi rst cluster according to clustering b C. InT3we havedH(,bC) = 2. Finally, inT4it is easy to verify that dH(,bC) = 10. A ground-truth matrixis annnand1-valued symmetric matrix = (xi,xj)nn i,j=1encoding a pairwise similarity relation overL . Specifi cal

10、ly, if(xi,xj) = 1we say thatxiandxjare similar, while if(xi,xj) = 1we say they are dissimilar. Moreover, we always have(xi,xi) = 1for all xi L. Notice thatneed not be consistent with a given clustering overL, i.e., the binary relation defi ned by over L need not be transitive. GivenTand its leavesL,

11、 an active learning algorithmAproceeds in a sequence of rounds. In a purely active setting, at roundt, the algorithm queries a pair of items(xit,xjt), and observes the associated label(xit,xjt). In a selective sampling setting, at roundt, the algorithm is presented with(xit,xjt) drawn from some dist

12、ribution overL L, and has to decide whether or not to query the associated label(xit,xjt). In both cases, the algorithm is stopped at some point, and is compelled to commit to a specifi c cut ofT (inducing a fl at clustering overL). Coarsely speaking, the goal ofAis to come up with a good cut of T,

13、by making as few queries as possible on the entries of . Noise Models.The simplest possible setting, called noiseless realizable setting, is whenitself is consistent with a given clustering realized byT, i.e., when there exists a cutcofTsuch that C(c) = L(i1),.,L(iK), for some nodesi1,.,iK V , that

14、satisfi es the following: For all r = 1,.,K, and for all pairs(xi,xj) L(ir) L(ir)we have(xi,xj) = 1, while for all other pairs we have(xi,xj) = 1. We call (persistent) noisy realizable setting one whereis generated as follows. Start off from the noiseless ground-truth matrix, and call it. Then, in o

15、rder to obtainfrom, consider the set of all ?n 2 ? pairs(xi,xj)withi 0), while bounding the expected number of queries(xit,xjt)made to the ground-truth matrix, the expectation being over the noise, and possibly overP(c). In particular, if b Cis the clustering produced by the algorithm after it stops

16、, we would like to prove upper bounds onEdH(,bC), as related to the number of active learning rounds, as well as to the properties of the prior distribution. The second setting (Section 4) is a selective sampling setting where the pairs(xit,xjt)are drawn i.i.d. according to an arbitrary and unknown

17、distributionDover then2entries of, and the algorithm at every round can choose whether or not to query the label. After a given number of rounds the algorithm is stopped, and the goal is the typical goal of agnostic learning: no prior distribution over cuts is available anymore, and we would like to

18、 bound with high probability over the sample(xi1,xj1),(xi2,xj2),. the so-called excess risk of the clustering b C produced by A, i.e., the difference P(xi,xj)D ?(x i,xj) 6= b C(xi,xj) ? min c P(xi,xj)D ?(x i,xj) 6= C(c)(xi,xj) ? ,(2) the minimum being over all possible cutscrealized byT. Notice that

19、 whenDis uniform the excess risk reduces to 1 n2 ? dH(,bC) mincdH(,C(c) ? .At the same time, we would like to bound with high probability the total number of labels the algorithm has queried. 3Active learning in the realizable case As a warm up, we start by considering the case where = 0(no noise).

20、The underlying cutccan be conveniently described by assigning to each nodeiofTa binary valuey(i) = 0ifiis abovec, andy(i) = 1ifiis below. Then we can think of an active learning algorithm as querying nodes, instead of querying pairs of leaves. A query to nodei Vcan be implemented by querying any pai

21、r(xi,xir) L(left(i) L(right(i). When doing so, we actually receivey(i), since for any such(xi,xir), we clearly havey(i) = (xi,xir). An obvious baseline is then to perform a kind of breadth-fi rst search in the tree: We start by querying the root r, and observe y(r); if y(r) = 1 we stop and output cl

22、ustering b C = L; otherwise, we go down by querying bothleft(r)andright(r), and then proceed recursively. It is not hard to show that this simple algorithm will make at most 2K 1queries, with an overall running time ofO(K), whereKis the number of clusters ofC(c). See Figure 3 for an illustration. If

23、 we know beforehand thatKis very small, then this baseline is a tough competitor. Yet, this is not the best we can do in general. Consider, for instance, the line graph in Figure 3 (right), where chas K = n. 5 Ideally, for a given priorP(), we would like to obtain a query complexity of the formlog(1

24、/P(c), holding in the worst-case for all underlyingc. As we shall see momentarily, this is easily obtained whenP() is uniform. We fi rst describe a version space algorithm (One Third Splitting,OTS) that admits a fast implementation, and whose number of queries in the worst-case isO(logN(T). This wil

25、l in turn pave the way for our second algorithm, Weighted Dichotomic Path (WDP).WDPleverages P(), but its theoretical guarantees only hold in expectation overP(c).WDPwill then be extended to the persistent noisy setting through its variant Noisy Weighted Dichotomic Path (N-WDP). We need a few ancill

26、ary defi nitions. First of all note that, in the noiseless setting, we have a clear hierarchical structure on the labelsy(i)of the internal nodes ofT: Whenever a query reveals a label y(i) = 0, we know that allis ancestors will have label0. On the other hand, if we observey(i) = 1 we know that all i

27、nternal nodes of subtreeT(i)have label1. Hence, disclosing the label of some node indirectly entails disclosing the labels of either its ancestors or its descendants. GivenT, a bottom-up path is any path connecting a node with one of its ancestors inT. In particular, we call a backbone path any bott

28、om up path having maximal length. Giveni V, we denote bySt(i)the version space at timetassociated withT(i), i.e., the set of all cuts ofT(i)that are consistent with the labels revealed so far. For any nodej 6= i,St(i)splits intoSy(j)=0 t (i)andSy(j)=1 t (i), the subsets of St(i) obtained by imposing

29、 a further constraint on y(j). OTS(One Third Splitting):For alli V,OTSmaintains over time the value|St(i)|, i.e., the size ofSt(i), along with the forestFmade up of all maximal subtreesT0ofTsuch that|V (T0)| 1and for which none of their node labels have been revealed so far.OTSinitializesFto contain

30、Tonly, and maintainsFupdated over time, by picking any backbone of any subtreeT0 F, and visiting it in a bottom-up manner. See the details in Appendix B.1. The following theorem (proof in Appendix B.1) crucially relies on the fact that is a backbone path of T0, rather than an arbitrary path. Theorem

31、 1On a treeTwithnleaves, heighth, and number of cutsN,OTS fi ndscby making O(logN)queries. Moreover, an ad hoc data-structure exists that makes the overall running time O(n + hlogN) and the space complexity O(n). Hence, Theorem 1 ensures that, for allc , a time-effi cient active learning algorithm e

32、xists whose number of queries is of the formlog(1/P(c), providedP(c) = 1/N(T)for allc. This query bound is fully in line with well-known results on splittable version spaces 12,25,24, so we cannot make claims of originality. Yet, what is relevant here is that this splitting can be done very effi cie

33、ntly. We complement the above result with a lower bound holding in expectation over prior distributions onc. This lower bound depends in a detailed way on the structure ofT. Given treeT, with set of leavesL, and cutc , recall the defi nitions ofAB(c)andLB(c)we gave in Section 2. LetT0 cbe the subtre

34、e ofTwhose nodes are(AB(c) LB(c) L, and then let e K(T,c) = |L(T0 c)| be the number of its leaves. For instance, in Figure 3 (left),T0 cis made up of the six nodesi1,.,i6, so that e K(T,c) = 3, while in Figure 3 (right),T0 c has nodesi1,.,in1, hence e K(T,c) = 1. Notice that we always have e K(T,c)

35、K, but for many treesT, e K(T,c)may be much smaller thanK. A striking example is again provided by the cut in Figure 3 (right), where e K(T,c) = 1, but K = n. It is also helpful to introduce Ls(T), the set of all pairs of sibling leaves in T. For instance, in the tree of Figure 3, we have |Ls(T)| =

36、3. One can easily verify that, for all T we have max c e K(T,c) = |Ls(T)| log2N(T) . We now show that there always exist families of prior distributionsP()such that the expected number of queries needed to fi ndcis(EeK(T,c). The quantityEeK(T,c)is our notion of average (query) complexity. Since the

37、lower bound holds in expectation, it also holds in the worst case. The proof can be found in Appendix B.2. Theorem 2In the noiseless realizable setting, for any treeT, any positive integerB |Ls(T)|, and any (possibly randomized) active learning algorithmA, there exists a prior distributionP()over cs

38、uch that the expected (overP()andAs internal randomization) number of queriesAhas to make in order to recovercis lower bounded byB/2, whileB EeK(T,c) 2B, the latter expectation being over P(). Next, we describe an algorithm that, unlikeOTS, is indeed able to take advantage of the prior distribution,

39、 but it does so at the price of bounding the number of queries only in expectation. WDP(Weighted Dichotomic Path): Recall prior distibution (1), collectively encoded through the valuesp(i),i V . As forOTS, we denote byFthe forest made up of all maximal subtreesT0 6 0.5 0.9 11 0.3 11 0.25 0.1 11 (1-0

40、.25)*0.5=0.375 (1-0.25)*(1-0.5)*0.9=0.3375 (1-0.25)*(1-0.5)* (1-0.9)*1=0.0375 0.0375 0.1125 0.075 0.675 0.675 0.2625 0.2625 0 0.25 0.0375*log_2(1/0.0375)+ 0.3375*log_2(1/0.3375)+ 0.375*log_2(1/0.375)+ 0.25*log_2(1/0.25)=1.737 1.7371.8911.891 1.163 1.163 0 0.9 11 1 11 0 0.1 11 0 0.9 (1-0.9)*1=0.1 0.1

41、 1 0.1 0.9 0.9 00 0 0 0.1*log_2(1/0.1)+ 0.9*log_2(1/0.9)=0.468 0.468 0.4680.468 Figure 4:An example of input treeT before (left) and after (right) the fi rst binary search ofWDP. The green node is a dummy super-root. The nodes in yellow are the roots of the subtrees cur- rently included in forestF.

42、The num- bers in red within each nodeiindicate the probabilitiesp(i), while theq(i) values are in blue, and viewed here as associated with edges (par(i),i). The magenta numbers at each leafgive the entropyH(,r(T0), wherer(T0)is the root of the subtree inF that contains bothandr(T0).Left:The input tr

43、eeTat timet = 0. No labels are revealed, and no clusters of C(c)are found.Right:TreeTafter a full binary search has been performed on the depicted light blue path. Before this binary search, that path connected a leaf of a subtree inFto its root (in this case,Fcontains only T). The selected path is

44、the one maximazing entropy within the forest/tree on the left. The dashed line indicates the edge ofcfound by the binary search. The red, blue and magenta numbers are updated accordingly to the result of the binary search. The leaves enclosed in the grey ellipse are now known to form a cluster of C(

45、c). ofTsuch that|V (T0)| 1and for which none of their node labels have so far been revealed.Fis updated over time, and initially contains onlyT. We denote by(u,v)a bottom-up path inThaving as terminal nodesuandv(hencevis an ancestor ofuinT). For a given cutc, and associated labels y(i),i V , any tre

46、e T0 F, and any node i V (T0 ), we defi ne3 q(i) = P(y(i) = 1 y(par(i) = 0) = p(i) Y j(par(i),r(T0) (1 p(j) .(3) We then associate with any backbone path of the form(,r(T0), where L(T0), an en- tropyH(,r(T0) = P i(,r(T0)q(i) log2q(i). Notice that at the beginning we have P i(,r(T)q(i) = 1 for all L.

47、 This invariant will be maintained on all subtreesT0. The prior probabilitiesp(i)will evolve during the algorithms functioning into posterior probabilities based on the information revealed by the labels. Accordingly, also the related valuesq(i)w.r.t. which the entropy H() is calculated will change

48、over time. Due to space limitations,WDPs pseudocode is given in Appendix B.3, but we have included an example of its execution in Figure 4. At each round,WDP fi nds the path whose entropy is maximized over all bottom-up paths(,r0), with Landr0= r(T0), whereT0is the subtree inFcontaining .WDPperforms

49、 a binary search on such(,r0) to fi nd the edge ofT0which is cut byc, taking into account the current values ofq(i)over that path. Once a binary search terminates,WDPupdates Fand the probabilitiesp(i)at all nodesiin the subtrees ofF. See Figure 4 for an example. Notice that thep(i)on the selected pa

50、th become either0(if above the edge cut byc) or1(if below). In turn, this causes updates on all probabilitiesq(i).WDPcontinues with the next binary search on the next path with maximum entropy at the current stage, discovering another edge cut byc, and so on, untilFbecomes empty. Denote byP0the set

51、of all priorsP()such that for all cutscofTwe have P(c) 0. The proof of the following theorem is given in Appendix B.3. Theorem 3In the noiseless realizable setting, for any treeTof heighth, any prior distribution P()overc, such thatP() P0, the expected number of queries made byWDP to fi ndcis O ? E

52、h e K(T,c) i logh ? , the expectations being over P(). For instance, in the line graph of Figure 3 (right), the expected number of queries isO(logn)for any priorP(), while ifTis a complete binary tree withnleaves, and we know thatC(c)hasO(K) clusters, we can setp(i)in (1) asp(i) = 1/logK, which woul

53、d guaranteeEeK(T,c) = O(K), and a bound on the expected number of queries of the formO(K loglogn). By comparison, observe that the results in 12,15,27 would give a query complexity which is at bestO(K log2n), while those in 25,24 yield at bestO(K logn). In addition, we show below (Remark 1) that our

54、 algorithm has very compelling running time guarantees. It is often the case that a linkage function generatingTalso tags each internal nodeiwith a coherence leveliofT(i), which is typically increasing as we move downwards from root to leaves. A common 3 For defi niteness, we sety(par(r) = 0, that i

55、s, we are treating the parent ofr(T)as a “dummy superroot” with labeled 0 since time t = 0. Thus, according to this defi nition, q(r) = p(r). 7 situation in hierarchical clustering is then to fi gure out the “right” level of granularity of the fl at clustering we search for by defi ning parallel ban

56、ds of nodes of similar coherence wherecis possibly located. For such cases, a slightly more involved guarantee forWDPis contained in Theorem 6 in Appendix B.3, where the query complexity depends in a more detailed way on the interplay between Tand the priorP(). In the above example, if we haveb-many

57、 edge-disjoint bands, Theorem 6 replaces factor logh of Theorem 3 by logb. N-WDP(Noisy Weighted Dichotomic Path): This is a robust variant ofWDPthat copes with persistent noise. Whenever a labely(i)is requested,N-WDPdetermines its value by a majority vote over randomly selected pairs fromL(left(i) L

58、(right(i). Due to space limitations, all details are contained in Appendix B.4. The next theorem quantifi esN-WDPs performance in terms of a tradeoff between the expected number of queries and the distance to the noiseless ground-truth matrix . Theorem 4In the noisy realizable setting, given any input treeTof heighth, any cutc P() P0, and any (0,1/2),N-WDPoutputs with probability 1 (over the noise in the labels) a clustering b Csuch that 1 n2 dH(,bC) = O ? 1 n (log(n/)3/2 (12)3 ? by askingO ? log(n/) (12)2 EeK(T,c)