Isabelle Tellier
email: isabelle.tellier@univ-lille3.fr

GRAMMATICAL INFERENCE BY SPECIALIZATION AS A STATE SPLITTING STRATEGY

We exhibit connexions beteween two already known learning algorithms developped in different backgrounds. This allows to show that learning classical (or AB) categorial grammars by specialization can be identified with a "state splitting" strategy, in a search space made of extended automata. It also leads to a new interpretation of why it is possible to learn categorial grammars from semantically typed (in Montague's sense) examples.

). In particular, the "state merging" operator used in automata learning was shown to be nothing but a special case of the "unification of variables" operator used in the BP algorithm.

The previous learning algorithms all belung to the family of generalization strategies. A generalization strategy applies as follows: the initial hypothesis is a "least general grammar" representing the available examples. Then, an operator is used to generalize this hypothesis until it belongs to the target class. But in symbolic machine learning in general, and in grammatical inference in particular, there also exists a lesser known family of specialization strategies. In such strategies, the initial hypothesis is the whole target class of grammars. Each example is considered as a constraint which restricts this space, until the space is reduced to a single grammar.

Introduction

The aim of this paper is to show that the translation of CGs into RA, which has helped to better understand the family of generalization strategies, can also help to better understand the family of specialization strategies. As a matter of fact, as it was the case for generalization strategies, specialization approaches have been proposed independantly in two distinct backgrounds: to learn CGs in the one hand, and to learn regular grammars represented by finite state automata in the other hand.

To reach this aim, we first need to briefly recall in section 2. how to transform a CG into a recursive automaton. For sake of simplicity, we restrict ourselves in most of this article to unidirectional CGs, but the definitions can be extended to plain CGs. In section 3., we first present the specialization strategy described in [START_REF] Moreau | Apprentissage partiel de grammaires lexicalises[END_REF], allowing to learn rigid CGs from positive examples. We then explain how it relates to another specialization strategy, which targets regular languages represented by finite state automata [START_REF] Fredouille | Experiences sur l'inference de langage par specialisation[END_REF]. As expected, we show that Moreau's algorithm can be interpreted as a "state splitting" strategy applying on RA. Finaly, the whole picture is completed in section 4. by a new interpretation of yet another already known algorithm allowing to learn CGs from semantically typed (in Montague's sense) examples [START_REF] Dudau-Sofronie | Learning categorial grammars from semantic types[END_REF]). It appears to be an efficiently controled specialization approach.

From categorial grammars to recursive automata

Basic definitions of categorial grammars

Definition 1 (unidirectional classical categorial grammars) Let B be an enumerable set of basic categories containing the axiom S ∈ B. Cat(B) is the smallest set such that B ⊆ Cat(B) and for any A, B ∈ Cat (B), A/B ∈ Cat (B) (for bidirectional CGs, we also have B\A ∈ Cat (B)). For every finite vocabulary Σ, a unidirectional categorial grammar G is a finite relation over Σ × Cat(B). We note w, C ∈ G the assignment of the category C ∈ Cat(B) to the word w ∈ Σ. In classical (or AB) unidirectional categorial grammars (UCGs in the following) the only syntactic rule, called Forward Application and noted FA is:

∀A, B ∈ Cat(B), A/B B → A. The language of G is: L(G)={w = v 1 . . . v n ∈ Σ + | ∀i ∈ {1, . . . , n}, ∃A i ∈ Cat (B) such that v i , A i ∈ G and A 1 . . . A n → * S}
, where → * is the reflexive and transitive closure of the relation →.

Let for example, B = {S, CN, IV } (where CN stands for "common noun" and IV for "intransitive verbs"), Σ = {John, runs, a, man} and G = { John, S/IV , runs, IV , a, (S/IV )/CN , man, CN }. This over-simple UCG only recognizes the sentences "John runs" and "a man runs".

Recursive automata and their language Definition 2 (recursive automaton)

A recursive automaton R is a 5-tuple R = Q, Σ, γ, q 0 , F such that Q is the finite set of states of R, Σ is its finite vocabulary, q 0 ∈ Q its (unique) initial state and F ∈ Q its (unique) final state. γ is the transition function of R, defined from Q × (Σ ∪ Q) to 2 Q .
We restrict ourselves to recursive automata (RA in the following) with unique initial and final states, but it is not a crucial choice The only important difference between this definition and the classical definition of finite state automata is that in a RA, it is possible to label a transition either by an element of Σ or by an element of Q. To use a transition labeled by a state q ∈ Q, you need to generate a string belonging to the language L R (q) of this state q, i.e. a string corresponding to a path starting at the state q and reaching the final state F . The general definition of the set {L R (q)|q ∈ Q} is thus recursive: when it exists, it is a smallest fix-point. In fact, RA are a special case of Recursive Transition Networks [START_REF] Woods | Transition network grammars of natural language analysis[END_REF].

Definition 3 (language of a RA) We define the set of languages L R (q), for every q ∈ Q as the smallest set satisfying: (i) L R (F ) = ; (ii) if there exists a transition labeled by a ∈ Σ between q and q , i.e. q ∈ γ(q, a) then: a.L R (q ) ⊆ L R (q); (iii) if there exists a transition labeled by r ∈ Q between q and q , i.e. q ∈ γ(q, r) then: L R (r).L R (q ) ⊆ L R (q). Finaly, the language of R is:

L(R) = L R (q 0 ).

From unidirectional CGs to RA

Every UCG can be transformed into a strongly equivalent RA, i.e. a RA generating the same structural descriptions [START_REF] Tellier | Learning recursive automata from positive examples[END_REF]. Let G be a UCG over Σ × Cat(B). Build R = Q, Σ, γ, q 0 , F as follows:

• let N be the set of every subcategory of a category assigned to an element of Σ in G (a category is a subcategory of itself). Then Q = N ∪ {F } with F / ∈ N . The initial state q 0 = S, the final one is F .

• For every q ∈ Q, define a transition labeled by q between the state q and F (that is, F ∈ γ(q, q)).

Learning by specialization

Learning rigid UCG from positive examples

A rigid CG G is a CG in which every word w ∈ Σ is assigned at most one category C. Kanazawa has proved [START_REF] Kanazawa | Learnable Classes of Categorial Grammars, The European Association for Logic, Language and Information[END_REF]) that the set of every (bidirectional) CG is learnable "in the limit" (i.e. in the sense of [START_REF] Gold | Language identification in the limit[END_REF] from positive examples, i.e. from sentences. Two distinct learning algorithms are now available for this purpose: Kanazawa's, derived from "BP" [START_REF] Buszkowski | Categorial grammars determined from linguistic data by unification[END_REF], is a generalization strategy; the one proposed in [START_REF] Moreau | Apprentissage partiel de grammaires lexicalises[END_REF]) is a specialization strategy. It is the latter, in its unidirectional version, that we will briefly recall here.

At its start, each member of the vocabulary used at least once in the available example sentences is assigned a distinct variable. For example, for the sentences {"John runs", "a man runs"}, the initial assignment is A = { John, x 1 , runs, x 2 , a, x 3 , man, x 4 }. A specifies a set of grammars: the set of CGs G such that there exists an substitution h satisfying h(A) = { w, h(C) | w, C ∈ A} ⊆ G. It is obvious that the inital set A always specifies the whole set of rigid CGs built on Σ.

Then, each sentence is parsed with the assigments in A. The only possible way to parse "John runs" with only FA is to substitute S/x 2 to x 1 . This substitution is a constraint that the variable x 1 must satisfy: x 1 is thus replaced by S/x 2 in A.

To parse "a man runs", two solutions are possible: either x 3 = (S/x 2 )/x 4 , either x 3 = S/x 5 and x 4 = x 5 /x 2 (with x 5 a new variable). A then becomes a disjunction of distinct possible sets of assignments. A combinatorial explosion can occur.

State merges and state splits

The previous algorithm can now be interpreted in terms of operations applying on RA. As we have seen, A is a disjunction of sets of assignments. Each of these sets can be transformed into a RA, as described in section 2.3.. What is the effect of a constraint on a RA ?

For UCG, the constraints always take the form: x k = x l , with x k and x l already introduced variables, or x k = X m /X n , with X m and X n any category built on the set of every variables union S. The effect of a constraint of the form x k = x l on a RA is a state merge. The effect of a constraint of the form x k = X m /X n can be decomposed in three steps: (i) X m /X n replaces x k everywhere in the RA, (ii) every subcategory of X m and X n (including themselves) becomes a new state, linked to the state F by a transition labeled by its name, and every / inside X m /X n becomes a transition, labeled by the fraction of the names of the linked states (at least, X m and X n are linked by X m /X n ), (iii) the states of the same name are merged.

This operation can be compared to the "state splitting strategy" proposed in (Fredouille and Miclet 2000) to learn finite state automata by specialization. For example, the constraint x 1 = S/x 2 has the effect of splitting the state x 1 into two new states: S and x 2 (then, as a state named x 2 already exists, the new one is merged with the previous one). But our specialization operation is more general, because of the recursive nature of the automata on which it applies. It is also better founded, because it is the formal counterpart of well-defined substitutions.

Learning from typed examples

The idea of learning CGs from typed (in Montague's sense) examples was introduced in (Dudau- [START_REF] Dudau-Sofronie | Learning categorial grammars from semantic types[END_REF]). Montague's types are derived from categories by a morphism, and associated with the vocabulary in the sentences. They can be interpreted as semantic information available in the environment or previously learned. We illustrate the learning strategy and its effects on RA on a simple example. Let: a man runs e, t , e, t , t e, t e, t (tx 1 (tx 2 e))x 3 (tx 4 e) tx 5 e tx 6 e

In this typed sentence, t and e are the usual montagovian basic types. The last line is the result of a simple pre-treatment to reorder the types in a UCG fashion and to introduce distinct variables at every place where an operator / could occur. When we transform this initial assignment into a RA, we obtain three states (plus "F"), each linked to the unique final state F, with their own name and "a", "man" and "runs" as respective labels. The learning algorithm applies as in section 3.1.: it consists in trying to parse the sentence, by defining constraints on the variables.

In a first step, the only way to apply FA between two consecutive types of the example is to define: x 3 = /. This, as already seen, provokes a state split. But the FA rule relying on the introduced operator can apply only if tx 4 e = tx 5 e, that is if x 4 = x 5 , which specifies a state merge. Not every couple of states can be merged at this step: states are also semantically typed in the sense of [START_REF] Coste | Introducing domain and typing bias in automata inference[END_REF]). The result of this step is the set: { a, (tx 1 (tx 2 e))/(tx 4 e) , man, tx 4 e , runs, tx 6 e }, corresponding with the first (simplified) RA of Figure 2.

In a second step, similar to the first one, we have: x 1 = / and x 2 = x 6 . The type t, corresponding with the category S, is now a subcategory of an assigned category, and a new state t playing the role of initial state is thus introduced. The RA obtained, on the right in Figure 2., is isomorph to the one of Figure 1., and recognizes the initial sentence. The types helped to cenverge to the correct solution quicker.

Conclusion

In this paper, we propose a new perspective on already known techniques. First, we see that RA are able to represent the search space of a specialization learning algorithm. In fact, as A is a disjunction of sets, the search space of Moreau's algorithm can be represented by a disjunction of RA. Second, we show that the algorithm to learn CGs from typed examples proposed in [START_REF] Dudau-Sofronie | Learning categorial grammars from semantic types[END_REF]) is a specialization strategy with typed constraints. The initial semantic types associated with the elements of the vocabulary specify some kind of maximal bound on the possible splits to be performed, allowing to limit the combinatorial explosion of solutions.

  Figure 1: RA equivalent with a UCG

Figure 2 :

 2 Figure 2: RA obtained when learning from typed examples


Stevens Le Blond

Arnaud Legout

Fabrice Lefessant

Walid Dabbous

Mohamed Ali Kaafar

Spying the World from your Laptop -Identifying and Profiling Content Providers and Big Downloaders in BitTorrent

This paper presents a set of exploits an adversary can use to continuously spy on most BitTorrent users of the Internet from a single machine and for a long period of time. Using these exploits for a period of 103 days, we collected 148 million IPs downloading 2 billion copies of contents.

We identify the IP address of the content providers for 70% of the BitTorrent contents we spied on. We show that a few content providers inject most contents into BitTorrent and that those content providers are located in foreign data centers. We also show that an adversary can compromise the privacy of any peer in BitTorrent and identify the big downloaders that we define as the peers who subscribe to a large number of contents. This infringement on users' privacy poses a significant impediment to the legal adoption of BitTorrent.

Introduction

BitTorrent is one of the most popular peer-to-peer (P2P) protocols used today for content replication. However, to this day, the privacy threats of the type explored in this paper have been largely overlooked. Specifically, we show that contrary to common wisdom [START_REF] Choffnes | Swarmscreen: Privacy through plausible deniability in p2p systems[END_REF][START_REF] Piatek | Challenges and directions for monitoring p2p file sharing networks or why my printer received a dmca takedown notice[END_REF][START_REF] Zhang | Unraveling the bittorrent ecosystem[END_REF], it is not impractical to monitor large collections of contents and peers over a continuous period of time. The ability to do so has obvious implications for the privacy of BitTorrent users, and so our goal in this work is to raise awareness of how easy it is to identify not only content provider that are peers who are the initial source of the content, but also big downloaders that are peers who subscribe to a large number of contents.

To provide empirical results that underscore our assertion that one can routinely collect the IP-to-content mapping on most BitTorrent users, we report on a study spanning 103 days that was conducted from a single machine. During the course of this study, we collected 148 million IP addresses downloading 2 billions copies of contents. We argue that this is a serious privacy threat for BitTorrent users. Our key contributions are the following.

i) We design an exploit that identify the IP address of the content providers for 70% of the new contents injected in BitTorrent.

ii) We profile content providers and show that a few of them inject most of the contents in BitTorrent. In particular, the most active injects more than 6 new contents every day and are located in hosting centers.

iii) We design an exploit to continuously retrieve with time the IP-to-content mapping for any peer. iv) We show that a naive exploitation of the large amount of data generated by our exploit would lead to erroneous results. In particular, we design a methodology to filter out false positives when looking for big downloaders that can be due to NATs, HTTP and SOCKS proxies, Tor exit nodes, monitors, and VPNs.

Whereas piracy is the visible part of the lack of privacy in BitTorrent, privacy issues are not limited to piracy. Indeed, BitTorrent is provably a very efficient [START_REF] Legout | Rarest First and Choke Algorithms Are Enough[END_REF][START_REF] Qiu | Modeling and performance analysis of bittorrent-like peer-to-peer networks[END_REF] and widely used P2P content replication protocol. Therefore, it is expected to see an increasing adoption of BitTorrent for legal use. However, a lack of privacy might be a major impediment to the legal adoption of BitTorrent. The goal of this paper is to raise attention on this overlooked issue, and to show how easy it would be for a knowledgeable adversary to compromise the privacy of most BitTorrent users of the Internet.

Exploiting the Sources of Public Information

In this section, we describe the BitTorrent infrastructure and the sources of public information that we exploit to identify and profile BitTorrent content providers and the big downloaders.

Infrastructure

At a high level, the BitTorrent infrastructure is composed of three components: the websites, the trackers, and the peers. The websites distribute the files containing the meta-data of the contents, i.e., .torrent file. The .torrent file contains, for instance, the hostname of the server, called tracker, that should be contacted to obtain a subset of the peers downloading that content.

The trackers are servers that maintain the content-topeers-IP-address mapping for all the contents they are tracking. Once a peer has downloaded the .torrent file from a website, it contacts the tracker to subscribe for that content and the tracker returns a subset of peers that have previously subscribed for that content. Each peer typically requests 200 peers from the tracker every 10 minutes. Essentially all the large BitTorrent trackers run the OpenTracker software so designing an exploit for this software puts the whole BitTorrent community at risk.

Finally, the peers distribute the content, exchange control messages, and maintain the DHT that is a distributed implementation of the trackers.

The Content Providers

BitTorrent content providers are the peers who insert first a content in BitTorrent. They have a central role because without a content provide no distribution is possible. We consider that we identify a content provider when we retrieve its IP address. One approach for identifying a content provider would be to quickly join a newly created torrent and to mark the only one peer with an entire copy of the content as the content provider for this torrent. However, most BitTorrent clients support the superseeding algorithm in which a content provider announces to have only a partial copy of the content. Hence, this naive approach cannot be used. In what follows, we show how we exploit two public sources of information to aide in identifying the content providers.

Newly Injected Contents

The first source of public information that we exploit to identify the IP address of the content providers are the websites that list the content that have just been injected into BitTorrent. Popular websites such as ThePirateBay and IsoHunt have a webpage dedicated to the newly injected contents.

A peculiarity of the content provider in a P2P content distribution network is that he has to be the first one to subscribe to the tracker in order to distribute a first copy of the content. The webpage of the newly injected contents may betray that peculiarity because it signals an adversary that a new content has been injected. An adversary can exploit the newly injected contents to contact the tracker at the very beginning of the content distribution and if he is alone with a peer, conclude that this peer is the content provider.

To exploit this information, every minute, we download the webpage of newly injected contents from TheP-irateBay website, determine the contents that have been added since the last minute, contact the tracker, and monitor the distribution of each content for 24 hours. If there is a single peer when we join the torrent, we conclude that this peer is the content provider. We repeated this procedure for 39, 298 contents for a period of 48 days from July 8 to August 24, 2009.

The Logins

Sometimes, a content is distributed first among a private community of users. Therefore, when the content appears in the public community there will be more than one peer subscribed to the tracker within its first minute of injection on the website. In that case, exploiting the newly injected contents is useless and an adversary needs another source of public information to identify the content provider. The second source that we exploit are the logins of the content providers on the website. Indeed, content providers need to log into web sites using a personal login to announce new contents. Those logins are public information.

Moreover, a content provider will often be the only one peer distributing all the contents uploaded by his login. The login of a content provider betrays which contents have been injected by that peer because it is possible to group all the contents uploaded by the same login on the website. An adversary can exploit the login of a content provider to see whether a given IP address is distributing most of the contents injected by that login.

To exploit this information, every minute, we store the login of the content provider that has uploaded the .torrent file on the webpage of the newly injected contents. We then group the contents per login and keep those logins that have uploaded at least 10 new contents. Finally, we consider the IP address that is distributing the largest number of contents uploaded by a given login as the content provider of those contents. We collected the logins of 6, 210 content providers who have injected 39, 298 contents for a period of 48 days from July 8 to August 24, 2009.

We verified that we did not identify the same IP address for many logins which would indicate that we mistakenly identify an adversary as content provider. In particular, on 2, 206 such IP addresses, we identified only 77 as the content provider for more than 1 login, and only 8 for more than 3 logins. We performed additional checks that we extensively describe in Le Blond et al. [START_REF] Blond | Angling for big fish in bittorrent[END_REF].

We validate the accuracy of those two exploits in Section 3.1.1 and present their efficiency to identify the content providers in Section 3.1.2.

The Big Downloaders

For now, we define the big downloaders as the IP addresses that subscribe to the tracker for the largest number of unique contents. It is believed to be impractical to identify them because it requires to spy on a considerable number of BitTorrent users. We now describe the two sources of public information that we exploit to compromise the privacy of any peer and to identify the big downloaders.

Scrape-all: Give Me All the Content Identifiers

Most trackers support scrape-all requests for which they return the identifiers of all the content they track and for each content, the number of peers that have downloaded a full copy of the content, the number of peers currently subscribed to the tracker with a full copy of the content, i.e., seeds, and with a partial copy of the content, i.e., leechers. A content identifier is a cryptographic hash derived from .torrent file of a content. Whereas they are not strictly necessary to the operation of the BitTorrent protocol, scrape-all requests are used to provide high level statistics on torrents. By exploiting the scrape-all requests, an adversary can learn the identifiers of all the contents for which he can then collect the peers using the announce requests described in Section 2.3.2.

To exploit this information, every 24 hours, we send a scrape-all request to all 8 ThePirateBay trackers and download about 2 million identifiers, which represents 120MB of data per tracker. We then filter out the contents with less than one leecher and one seed which leaves us with between 500 and 750K contents depending on the day. We repeated this procedure for 103 days from May 13 to August 23, 2009. ThePirateBay tracker is by far the largest tracker with an order of magnitude more peers and contents than the second biggest tracker [START_REF] Zhang | Unraveling the bittorrent ecosystem[END_REF], and it runs the OpenTracker software therefore we limited ourselves to that tracker.

Announce: Give Me Some IP Addresses

The announce started/stopped requests are sent when a peer starts/stops distributing a content. Upon receiving an announce started request, the tracker records the peer as distributing the content, returns a subset of peers, and the number of seeds and leechers distributing that content. When a peer stops distributing a content, he sends an announce stopped requests and the tracker decrements a counter telling how many contents that peer is distributing. We have observed that trackers generally blacklist a peer when he distributes around 100 contents. So an adversary should send an announce stopped request after each announce started requests not to get blacklisted. By exploiting announce started/stopped requests for all the identifiers he has collected, an adversary can spy on a considerable number of users.

To exploit this information, every 2 hours, we repeatedly send announce started and stopped requests for all the contents of ThePirateBay trackers so that we collect the IP address for at least 90% of the peers distributing each content. We do this by sending announce started and stopped requests until we have collected a number of unique IP addresses equal to 90% of the number of seeds and leechers returned by the tracker. This procedure takes around 30 minutes for between 500K and 750K contents. By repeating this procedure for 103 days from May 13 to August 23, 2009, we collected 148 million IP addresses downloading 2 billion copies of contents.

We will see in Section 4.1 that once an adversary has collected the IP-to-content mappings for a considerable number of BitTorrent users, it is still complex to identify the big downloaders because it requires to filter out the false positives due to middleboxes such as NATs, IPv6 gateways, proxies, etc. We will also discuss how an adversary could possibly reduce the number of false negatives by identifying the big downloaders with dynamic IP addresses. Finally, we will see that an adversary can also exploit the DHT to collect the IP-to-content mappings in Section 6.

The Torrent Files

Once we have identified the IP address for the content providers and big downloaders, we use the .torrent files to profile them. A .torrent file contains the hostname of the tracker, the content name, its size, the hash of the pieces, etc. Without .torrent file, a content identifier is an opaque hash therefore, an adversary must collect as many .torrent files as possible to profile BitTorrent users. For instance, an adversary can use the .torrent files, to determine if the content is likely to be copyrighted, the volume of unique contents distributed by a content provider, or the type of content he is distributing. Clearly, .torrent files must be public for the peers to distribute contents however, it is surprisingly easy to collect millions of .torrent files within hours and from a single machine. By exploiting the .torrent files, an adversary can focus his spying on specific keywords and profile BitTorrent users.

To exploit this information, we collected all the .torrent files available on Mininova and ThePirateBay websites on May 13, 2009. We discovered 1, 411, 940 unique .torrent files on Mininova and 974, 980 on TheP-irateBay. The overlap between both website was only 227, 620 files. Then, from May 13, to August 24, 2009, we collected the new .torrent files uploaded on the Mininova, ThePirateBay, and Isohunt websites. Those three websites are the most popular and as there is generally a lot of redundancy among the .torrent files hosted by different websites [START_REF] Zhang | Unraveling the bittorrent ecosystem[END_REF], we limit ourselves to those three.

We will discuss the reasons why our measurement was previously thought as impractical by the related work in Section 5.

The Content Providers

In this section, we run the exploits from Section 2.2 in the wild, quantify the content providers that we identify, and present the results of their profiling. Table 1: Cross-validation of the two exploits. This table shows the accuracy of the two exploits to identify the same content provider for the same content. Alone ∩ Login is the number of contents for which both sources identified a content provider. Accuracy is the percentage of such contents for which both sources identified the same content provider.

Identifying the Content Providers

We start by validating the exploits we use to identify the IP address of the content providers.

Validating the Exploits

In Section 2.2, we described two exploits to identify the IP address of a content provider. The first exploit is to connect to the tracker as soon as a new content gets injected and to check whether we are alone with the content provider (Alone). The second exploit is to find the IP address that has injected the largest number of contents uploaded by a single login (Login). Whereas it makes sense to use those exploits to identify content providers, it is necessary to validate how accurate they are. We validate the accuracy of these exploits in Table 1. This table shows that for 9, 243 contents, both exploits identified a content provider. Moreover, for 99.99% of those contents both exploits identified the same IP address as the content provider. Thus, with a high probability the same content providers are identified by two independent exploits.

Quantifying the Identified Content Providers

In Fig. 1, we identify the IP address for 70% of the content providers injecting 39, 298 new contents over a period of 48 days. The fraction of content providers that we identify using Alone only decreases with the number of peers distributing the content. This is because the more popular the content, the lower the chances to be alone with the content provider, i.e., from 60% for contents with 10 peers or less to 17% for contents with more than 1, 000 peers. However, Login compensates for contents with up to 1, 000 peers. In essence, for contents with more than 1, 000 peers, we identify close to half of the content providers.

Profiling the Content Providers

We now use the IP address of the content providers that we have identified for 48 days to profile their contribution in number of contents and their location. On the x-axis, all is for all contents, a-b is for content with between a and b peers distributing the content after 24 hours, and > 1000 for contents with more than 1, 000 peers distributing the content after 24 hours. Others is the fraction of content providers that we do not identify.

Figure 2: Tag cloud of contents injected by the content providers that we have identified. We extract the two most significant keywords from each content name contained in the .torrent files and vary their police size to reflect the number of contents whose name matches those keywords, the largest the keywords, the more frequent those keywords appear in the content names.

Semantic of the Injected Contents

Fig. 2 shows a tag cloud of the names of the contents injected into BitTorrent. This tag cloud suggests that many contents refer to copyrighted material and that BitTorrent closely follow events. Indeed, two weeks before we started to identify the content providers, Michael Jackson died and the latest Happy Potter movie got released one week after.

Contribution of the Content Providers

We see in Fig. 3 (top) that some content providers inject much more contents than others with the most active in- jecting more than 300 contents in 48 days. The most active content providers inject more than 6 contents every day, e.g., eztv [1], the top content provider, daily injects 6.5 TV shows of 430MB in average. Given the time to capture and encode a TV show, it suggests that a small community of users injects contents from the same IP address.

We now look at the contribution of the biggest content providers in comparison to the total number of injected contents. We see in Fig. 3 (bottom), that the top 100 content providers inject 30% of all the contents injected into BitTorrent and the top 1, 000 content providers inject 60% of all the contents. Conclusions These results show that few content providers insert most of the contents. We do not claim that it is easy to stop those content providers from injecting content into BitTorrent however, it is striking that such a small number of content providers triggers billions of downloads. Therefore, it is surprising that the anti-piracy groups try to stop millions of downloaders instead of a handful of content providers.

Location of the Content Providers

Focusing on the top 20 content providers in Table 2, we observe that half of them are using a machine whose IP address is located in a French and a German hosting center, i.e., OVH and Keyweb. Those hosting centers provide cheap offers of dedicated servers with unlimited traffic and a 100MB/s connection.

However, we observed that the users injecting contents from those servers are unlikely to be be French or German. Indeed, on 1, 515 contents injected by the content providers from OVH, only 13 contained the keyword fr (French) in their name whereas 552 contained the keyword spanish. Similarly, on 623 contents injected from Keyweb, we found 228 contents with the keyword spanish in their name and none contained the keywords fr, ge (German), or de (Deutsche). In conclusion, one cannot easily guess the nationality of a content provider based on the geolocalization of the IP address of the machine he is using to inject contents.

The Big Downloaders

In this section, we focus on the identification and the profiling of the big downloaders, i.e., the IP addresses that subscribed in the largest number of contents. Once we have collected the information described in Section 2.3, it is challenging to identify and profile the big downloaders because of the volume of information. Indeed, we collected 148M IP addresses and more than 510M endpoints (IP:port) during a period of 103 days.

Ordering the IP addresses according to the total number of unique contents for which they subscribed, we observe a long tail distribution. In particular, the top 10, 000 IP addresses subscribed for at least 1, 636 contents and the top 100, 000 IP addresses subscribed for at least 309 contents. In the remaining of this section, we focus on the top 10, 000 IP addresses.

In the following, we show that for many IP addresses, there is a linear relation between their number of contents and their number of ports suggesting that those IPs are middleboxes with multiple peers behind them. However, we will also see that some IP addresses significantly deviate from this middlebox behavior and we will identify some of those players with deviant behavior. Finally, we will profile those players.

The Middlebox Behavior

It is sometimes complex to identify a user based on its IP address or its endpoint, because the meaning of this information is different depending on his Internet connectivity. A user can connect through a large variety of middleboxes such as NATs, IPv6 gateways, proxies, etc. In all those cases, many users can use the same IP address and the same user can use a different IP address or endpoints. So an adversary using the IP addresses or endpoints to identify big downloaders may erroneously identify a middlebox as a big downloader. In the following, we aim to filter out those false positives to identify the big downloaders. We do not consider false negatives due, for instance, to a big downloader with a dynamic IP address. It may be possible to identify big downloaders with a dynamic IP address but it would require a complex methodology using the port number as the identifier of a user within an AS; most BitTorrent clients pick a random port number when they are first executed and then use that port number statically. The validation of such a methodology is beyond the scope of this paper and we leave this improvement for future work. However, we will see that we already find a large variety of big downloaders using public IP addresses as identifiers.

We confirm the complexity of using an IP address or endpoint to identify a user in Fig. 4. Indeed, we see that for most of the IP addresses the number of contents increases linearly with the number of ports. Moreover, the slope of this increase corresponds to the slope of the average number of contents per IP over all 148M IP addresses (solid line). Each new port corresponds to between 2 and 3 additional contents per IP address. Therefore, it is likely that those IP addresses correspond to middleboxes with a large number of users behind them. There are also many IP addresses that significantly deviate from this middlebox behavior.

Conclusions A large number of IP addresses that a naive adversary would classify as big downloaders actually corresponds to middleboxes such as NATs, IPv6 gateways, or proxies. However, we also observe many IP addresses whose behavior significantly deviates from a typical middlebox behavior.

Identifying the Big Players

To understand the role of the IP addresses that deviate from middlebox behavior, we identify 6 categories of big players.

HTTP and SOCKS public proxies

The two first categories are HTTP and SOCKS public proxies that can be used by BitTorrent users to hide their IP address from anti-piracy groups. We retrieved a list of IP addresses of such proxies from the sites hidemyass.com and proxy.org. We found 81 HTTP proxies and 62 SOCKS proxies within the top 10, 000 IP addresses.

Tor exit nodes

The third category is composed of Tor exit nodes that are the outgoing public interfaces of the Tor anonymity network. To find, the IP address of the Tor exit nodes, we performed a reverse DNS lookup for the top 10, 000 IP addresses and extracted all names containing the tor keyword and manually filtered the results to make sure they are indeed Tor exit nodes. We also retrieved a list of nodes on the Web site proxy.org. We found 174 Tor exit nodes within the top 10, 000 IP addresses.

Monitors

The fourth category is composed of monitors that are peers spying on a large number of contents without participating in the content distribution. We identified two ASes, corresponding to hosting centers located in the US and UK, containing a large number of IP addresses within the top 10, 000 with the same behavior. Indeed, these IP addresses always used a single port and we were never able to download content from them. Therefore, they look like a dedicated monitoring infrastructure instead of regular peers. We found 1, 052 such IP addresses within only two ASes in the top 10, 000 IP addresses VPNs The fifth category is composed of VPNs that are SOCKS proxies requiring authentication and whose communication with BitTorrent users is encrypted. To find VPNs, we performed a reverse DNS lookup for the top 10, 000 IP addresses and extracted all names containing the itshidden, cyberghostvpn, peer2me, ipredate, mullvad, and perfect-privacy keywords and manually filtered the results to make sure they are indeed the corresponding VPNs. Those keywords correspond to wellknown VPN services. We found 30 VPNs within the top 10, 000 IP addresses.

Big downloaders

The last category is composed of big downloaders that we redefine as the IP addresses that distribute the largest number of contents and that are used by a few users. We selected the IP addresses we could download content from and that used fewer than 10 ports. Hence, those IP addresses cannot be a monitors as we downloaded content from them and they cannot be large middleboxes due to the small number of ports. We found 77 such big downloaders.

Conclusions

We have identified 6 categories of big players including the big downloaders. We do not claim that we have identified all categories of players nor found all the IP addresses that belong to one of those 6 categories. Instead, we have identified few IP addresses in each category within the top 10, 000 peers that we use in the following to profile the big players.

Profiling the Big Players

We see in Fig. 5 that for HTTP and SOCKS proxies the number of contents per IP address is much larger than for middleboxes (solid line). Considering the huge number of contents these IP addresses subscribed to, it is likely that the proxies are used by anti-piracy groups. Indeed, we see in Fig. 6 that our measurement system suddenly stops seeing the IP addresses of monitors after day 50. In fact, by that date, ThePirateBay tracker changed its blacklisting strategy to reject IP addresses that are subscribed to a large number of contents. Whereas it was not a problem for our measurement system because it uses announce stopped requests as described in Section 2.3.2, monitors got blacklisted. However, we observe on day 80 that the number of HTTP and SOCKS proxies suddenly increased, probably corresponding to anti-piracy groups migrating their monitoring infrastructure from dedicated hosting centers to proxies. Considering, the synchronization we observe in Fig. 6 in the activity of the HTTP and SOCKS proxies, it is likely that those proxies were used in a coordinated effort. The correlation for monitors and big downloaders in Fig. 5 does not show any striking result, therefore we do not discuss it further. However, we observe in Fig. 5 that for Tor exit nodes and VPNs the number of contents per IP address is close to the IP addresses of the middleboxes (solid line). For large number of ports, Tor exit nodes deviate from the standard middlebox behavior. In fact, we found that just a few IP addresses are responsible of this deviation, all other Tor exit nodes following the trend of the solid line. We believe that those few IP addresses responsible for the deviation are used by either big downloaders or anti-piracy groups.

Conclusions

We have shown that many peers do not correspond to a BitTorrent user but to monitors or to middleboxes with multiple users behind them. These peers introduce a lot of noise for an adversary who would like to spy on BitTorrent users and in particular on the big downloaders. However, we have shown that it is possible to filter out that noise to identify the IP address and profile the big downloaders.

Related Work

As far as we know, no related work has explored the identification of the content providers in BitTorrent so both the data and the results concerning these players are entirely new. Some related work has measured BitTorrent at a moderate scale but none at a large-enough scale to identify the big downloaders. This is because most of the measurements inherited two problems from using existing BitTorrent clients [START_REF] Piatek | One hop reputations for peer to peer file sharing workloads[END_REF][START_REF] Piatek | Challenges and directions for monitoring p2p file sharing networks or why my printer received a dmca takedown notice[END_REF][START_REF] Siganos | Monitoring the bittorrent monitors: A bird's eye view[END_REF]. The first problem is that existing clients introduce a huge computational overhead on the measurement. For instance, each announce started request takes one fork and one exec. Therefore, the measurement is hard to efficiently parallelize.

The second problem is that regular BitTorrent clients do not exploit all the public sources of information that we have presented in Section 2.3 and 2.4. A content identifier is essentially the hash of a .torrent file. So not exploiting scrape-all requests limits the number of spied contents to the number of .torrent files an adversary has collected. In addition, clients may not be stopped properly and so not send the announce stopped request, making the measurement prone to blacklisting.

In the following, we describe how the scale of previous measurements differs from ours according to the sources of public information that they exploit.

No Exploitation of Scrape-all Requests

We split the related work not exploiting scrape-all requests into two families: A first family spying on few contents and a second one using a large infrastructure to spy on more contents. Siganos et al. measured the top 600 contents from The ThePirateBay [START_REF] Siganos | Monitoring the bittorrent monitors: A bird's eye view[END_REF] Web site during 45 days collecting 37 million IP addresses. Using only the top 600 contents does not allow an adversary to identify the big downloaders. The same remark holds for Choffnes et al. [START_REF] Choffnes | Swarmscreen: Privacy through plausible deniability in p2p systems[END_REF] who monitored 10, 000 peers and did not record information identifying contents therefore they cannot either identify the big downloaders.

The second family spied on more contents but using a large infrastructure. Piatek et al. used a cluster of workstations to collect 12 million IP addresses distributing 55, 523 contents in total [START_REF] Piatek | One hop reputations for peer to peer file sharing workloads[END_REF][START_REF] Piatek | Challenges and directions for monitoring p2p file sharing networks or why my printer received a dmca takedown notice[END_REF]. It is unclear how many simultaneous contents they spied as they reported being blacklisted when being too aggressive, suggesting that they did not properly send announce stopped requests.

Finally, Zhang et al. [START_REF] Zhang | Unraveling the bittorrent ecosystem[END_REF] is the work that is the closest to ours in scale however, they used an infrastructure of 35 machines to collect 5 million IP addresses within a 12 hours window. In comparison, our customized measurement system used 1 machine to collect around 7 million IP addresses within the same time window, making it about 50 times more efficient. In addition, that we performed our measurement from a single machine demonstrates that virtually anyone can spy on BitTorrent users, which is a serious privacy issue.

No Exploitation of Announce Requests

Dan et al. measured 2.4 million torrents with 37 million peers, but used a different terminology [START_REF] Dán | Dynamic swarm management for improved bittorrent performance[END_REF]. Indeed, they performed only scrape-all requests so they knew the number of peers per torrent but not the IP addresses of those peers. This data is much easier to get and completely different in focus.

Discussion and Conclusions

We have shown that enough information is available publicly in BitTorrent for an adversary to spy on most BitTorrent users of the Internet from a single machine. At any moment in time for 103 days, we were spying on the distribution of between 500 and 750K contents. In total, we collected 148M of IP addresses distributing 1.2M contents, which represents 2 billion copies of content.

Leveraging on this measurement, we were able to identify the IP address of the content providers for 70% of the new contents injected into BitTorrent and to profile them. In particular, we have shown that a few content providers inject most of the contents into BitTorrent making us wonder why anti-piracy groups targeted random users instead. We also showed that an adversary can compromise the privacy of any peer in BitTorrent and identify the IP address of the big downloaders. We have seen that it was complex to filter out false positives of big downloaders such as monitors and middleboxes and proposed a methodology to do so.

We argue that this privacy threat is a fundamental problem of open P2P infrastructures. Even though we did not present it in this paper, we have also exploited the DHT to collect IP-to-content mappings using a similar methodology as for the trackers. That we were also able to collect the IP-to-content mappings on a completely different infrastructure reinforces our claim that the problem of privacy is inherent to open P2P infrastructures.

A solution to protect the privacy of BitTorrent users might be to use proxies or anonymity networks such as Tor, however a recent work shows that it is even possible to collect the IP-to-content mappings of BitTorrent users on Tor [START_REF] Blond | De-anonymizing bittorrent users on tor[END_REF]. Therefore, the degree to which it is possible to protect the IP-to-content mappings of P2P filesharing users remains an open question.

Figure 1 :

 1 Figure1: Fraction of content providers that we identify. On the x-axis, all is for all contents, a-b is for content with between a and b peers distributing the content after 24 hours, and > 1000 for contents with more than 1, 000 peers distributing the content after 24 hours. Others is the fraction of content providers that we do not identify.

Figure 4 :

 4 Figure 4: Correlation of the number of ports per IP address and of the number of contents for the top 10, 000 IP addresses. Each dot represents an IP address. The solid line is the average number of contents on the 148M IP addresses computed per interval of 2, 000 ports.

Figure 5 :

 5 Figure 5: Correlation of the number of ports per IP address and of the number of contents of the big players. Each dot represents an IP address. The solid line represents the middlebox behavior.

Table 2 :

 2 Figure 3: Distribution of the number of contents injected by each content provider. The top plot shows the number of contents per content provider and the bottom plot shows the CDF of contents.

		Distribution of Contents Injected per Content Provider
	Number of contents	0 50 100 150 200 250 300 350
		1	10	100		1000	10000
		IP address rank (sorted by decreasing number of contents, log scale)
	CDF of contents	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 1 0.9
		1	10	100		1000	10000
		IP address rank (sorted by decreasing number of contents, log scale)
		Rank	# contents	Volume	CC	AS name
		1	313	136	NZ	Vodafone
		2	304	79	FR	OVH
		3	266	152	DE	Keyweb
		4	246	34	FR	OVH
		5	219	186	FR	OVH
		6	212	247	DE	Keyweb
		7	201	535	FR	OVH
		8	181	73	US	HV
		9	181	17	CA	Wightman
		10	180	7	SK	Energotel
		11	172	161	FR	OVH
		12	167	23	RU	Corgina
		13	145	197	DE	Keyweb
		14	140	11	FR	OVH
		15	138	109	US	Aaron
		16	132	12	US	Charter
		17	117	119	FR	OVH
		18	116	109	FR	OVH
		19	114	79	NL	Telfort
		20	107	225	RU	Matrix

Rank, number of contents, volume of contents (GB), country code, and AS name for the top 20 content providers.

  Activity of the big players in time. For each category, the dashed line represents the fraction of the top 10, 000 IP addresses of a given snapshot that belongs to the top 10, 000 IP addresses on all snapshots. The solid line represents, for each category, the fraction of the top 10, 000 IP addresses on all previous snapshots that belongs to the top 10, 000 IP addresses on all snapshots.

		HTTP proxies	SOCKS		Tor
	CDF	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
		0 20 40 60 80 100	0 20 40 60 80 100	0 20 40 60 80 100
		Time (days)	Time (days)		Time (days)
		Monitors	VPNs		Big downloaders
	CDF	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
		0 20 40 60 80 100	0 20 40 60 80 100	0 20 40 60 80 100
		Time (days)	Time (days)		Time (days)
	Figure 6:

Acknowledgments

We would like to thank Thierry Parmentelat and T. Barıs ¸Metin for their system support and the anonymous reviewers for their useful comments.


Laurent Candillier
email: candillier@grappa.univ-lille3.fr

Isabelle Tellier

Fabien Torre

Olivier Bousquet
email: olivier.bousquet@pertinence.com

Cascade evaluation of clustering algorithms

This paper is about the evaluation of the results of clustering algorithms, and the comparison of such algorithms. We propose a new method based on the enrichment of a set of independent labeled datasets by the results of clustering, and the use of a supervised method to evaluate the interest of adding such new information to the datasets. We thus adapt the cascade generalization [1] paradigm in the case where we combine an unsupervised and a supervised learner. We also consider the case where independent supervised learnings are performed on the different groups of data objects created by the clustering [2]. We then conduct experiments using different supervised algorithms to compare various clustering algorithms. And we thus show that our proposed method exhibits a coherent behavior, pointing out, for example, that the algorithms based on the use of complex probabilistic models outperform algorithms based on the use of simpler models.

Introduction

In both supervised and unsupervised learning, the evaluation of the results of a given method, as well as the comparison of various methods, is an important issue. But if cross-validation is a widely accepted method to evaluate supervised learning algorithms, the problem of evaluating unsupervised learning algorithms remains an open issue. The main problem is that the evaluation of clustering results is subjective by nature. Indeed, there are often many different and relevant ways of grouping together some given data objects.

In practice, four main techniques are used to measure the quality of clustering algorithms. But each of these techniques has its own limitations.

1. Use artificial datasets where the desired grouping is known. But the given algorithms are thus evaluated only on the corresponding generated distribution, and results on artificial data can not be generalized to real data. 2. Use labeled datasets and check if the clustering algorithm retrieves the initial classes. But the classes of a supervised problem are not necessarily the classes that have to be found by a clustering algorithm because other groupings can also be meaningful. 3. Work with an expert who evaluates the meaning of the clustering in a particular field. However, if it is possible for an expert to tell if a given clustering has some meaning, it is much harder to quantify its interest, or to tell if a given result is better than another one. Besides, the relevance of the method can not be generalized to various types of data. 4. Or use some internal criterion, like the intra-cluster inertia and/or the interclusters separation. But such pre-defined criteria are also subjective by nature because they use some pre-defined notion of what is a good clustering. For example, inter-clusters separation is not always the best criterion to use : clusters that overlap may sometimes be more relevant.

The main risk in evaluating a clustering method is to consider it as a goal in itself. In fact, what we want to evaluate is how well a given clustering method is able to capture new meaningful and useful information, that is some new knowledge interesting to use for some purpose. We also expect the method to be able to capture such interesting information on various types of problems.

So the main idea of our approach is to consider the clustering as a preprocessing step for another task that we are able to evaluate : supervised learning for instance. Thus the new evaluation method we propose in this paper consists in comparing the results of a supervised algorithm when it is (or not) provided with information coming from a clustering algorithm. If the results of the supervised learning algorithm are improved when some extra-knowledge coming from a clustering process is added, then we conjecture that it means that the clustering process managed to capture some new meaningful and useful information.

This method thus allows us to objectively evaluate the interest of the information captured by a given clustering algorithm. Moreover, the decrease of the error rate of the supervised algorithm when it is helped with the information coming from the clustering algorithm also allows us to quantify this interest. Our evaluation method thus depends on the chosen task, but it allows us to evaluate the contribution of the clustering in the achievement of this objective and real task. Besides, such a bias is less important than when a direct mapping between the clusters and the classes is evaluated.

So our method lies in the framework of classifier combination, in our case the combination of an unsupervised and a supervised method. Many ways of combining classifiers by votes can be found in [START_REF] Ali | Error reduction through learning multiple descriptions[END_REF], the two mostly used methods being bagging [START_REF] Breiman | Bagging predictors[END_REF] and boosting [START_REF] Freund | Experiments with a new boosting algorithm[END_REF]. Some theoretical generalization of these techniques have also been studied, leading to arcing classifiers [START_REF] Breiman | Bias, variance, and arcing classifiers[END_REF], ensemble methods [START_REF] Dietterich | Ensemble methods in machine learning[END_REF] and leveraging methods [START_REF] Meir | An introduction to boosting and leveraging[END_REF].

We focus here on techniques that use different learners in a sequential way. In such methods, the output of a learner is an enrichment of the example description, that is then used by the next learner. In that field, stacked generalization [START_REF] Wolpert | Stacked generalization[END_REF] is a very general framework in which different treatments are stacked : each treatment modifies the example description, and this new dataset is used by the next level. Cascade generalization [START_REF] Gama | Cascade generalization[END_REF] is a special case of stacked generalization. At each level, a classifier is applied on each example x providing probabilities p(c|x) that x belongs to class c. These probabilities are then added to the example description and used by the next level classifier. Cascade generalization allows to combine several classifiers but in practice, only two learners are used.

Finally, we also consider the case where we combine an unsupervised and a supervised learner as is done in [START_REF] Apte | A probabilistic estimaton framework for predictive model analytics[END_REF]. In that case, many clusterings are run with different input parameters, leading to different partitions of the set of data objects. For each partition, many independent supervised learnings are executed on the different created groups of data objects and the global error rate is computed. Finally, the partition that leads to the lower error rate is kept.

Based on this principle of sequentially combining an unsupervised and a supervised learner, and then computing the decrease of the error rate of the supervised learner when it is helped by the unsupervised learner, the new evaluation method of clustering algorithms we propose is called cascade evaluation. We first describe this new method in section 2. Then section 3 presents some experiments conducted with this new method. Finally, section 4 concludes the paper and suggests topics for future research.

Cascade evaluation methodology

Being given an initial dataset with classes information, the general steps of our proposed methodology are as follows :

1. learning 1 :

perform a supervised learning on the initial dataset; 2. learning 2 :

perform a clustering on the dataset without using the classes information; -enrich the dataset from the clustering results; -and perform a supervised learning on the enriched dataset; 3. compare the results of both learned classifiers.

As we already stated, we consider two different ways of enriching datasets from the results of a given clustering. The first one consists in creating new attributes that represent the information captured by the clustering process, and then adding these new attributes to the initial dataset before running the supervised learning on the enriched dataset. The second way is to consider the new sub-datasets created by the clustering and to run many supervised learnings independently on each sub-dataset.

Concerning the new attributes created from the clustering results in the case of the first combination method, different types of information can be added.

1. As many clustering algorithms provide as output a partition of the initial dataset, we can use the membership of the data objects to the clusters to create new attributes. This information would be represented by a new categorical attribute, each data object being associated with an identifier of the cluster it belongs to. 2. We can also associate to each data object a set of attributes that represent the center of the cluster it belongs to. We would thus double the number of attributes in the dataset.

3. Recently, many subspace clustering algorithms [START_REF] Parsons | Evaluating subspace clustering algorithms[END_REF] emerged that are able to associate to each dimension of each cluster a weight specifying its relevance in determining the membership of the data objects to the cluster. So in such cases, we could add to each data object one new continuous attribute per initial dimension corresponding to the weight, on that dimension, of the cluster it belongs to. Such new attribute would thus allow to differentiate data objects for which a given dimension is relevant from those for which it is not relevant (according to the subspace clustering results).

Besides, as most clustering algorithms need some parameters to tune, we can run these algorithms many times with different input parameter values and enrich the dataset for each clustering results. For example, many clustering methods need as input the number of clusters to be found. In such cases, we could run them many times, varying this parameter from 2 to 10 for example. The supervised algorithm used afterwards would then be able to choose which attribute(s) to use among them.

In the case of the second combination method proposed, we first generate many partitions with different input parameters. We then compute the crossvalidation error of independent supervised learners executed on the different groups of data objects created by the clustering. And finally, we select the partition that led to the lowest error rate.

To evaluate the improvement in the results of the supervised learning algorithm with or without the new information coming from the clustering process, we test both methods on various independent datasets. On each dataset, we perform five 2-fold cross-validations, as proposed in [START_REF] Dietterich | Approximate statistical test for comparing supervised classification learning algorithms[END_REF]. For each 2-fold crossvalidation, we compute the balanced error rates of both methods. And we then use four measures to compare them :

nb wins: the number of wins of each method; -sign wins: the number of significant wins, using the 5×2cv F-test [START_REF] Alpaydin | Combined 5x2cv F-test for comparing supervised classification learning algorithms[END_REF] to check if the results are significantly different;

wilcoxon: the wilcoxon signed rank test, that indicates if a method is significantly better than another one on a set of independent problems (if its value is higher than 1.96);

and av perf : the mean balanced error rate.

Experiments

We present in this section the results of the comparisons of various clustering algorithms :

-Rand, an algorithm that generates random partitions, being given the number of expected clusters (used as a reference);

-K-means, the well-known full-space clustering algorithm based on the evolution of K centroids that represent the K clusters to be found;

-LAC [START_REF] Domeniconi | Subspace clustering of high dimensional data[END_REF], a subspace clustering algorithm based on K-means that associates with each centroid a vector of weights on each dimension, inversely proportional to the dispersion of the members of the clusters on the dimension;

-SSC [START_REF] Candillier | SSC : Statistical Subspace Clustering[END_REF], that is based on the use of a probabilistic model and the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] under the assumption that the data follow independent gaussian distributions on each dimension;

and SuSE [START_REF] Candillier | SuSE : Subspace Selection embedded in an EM algorithm[END_REF], an adaptation of SSC that performs hard feature selection during the learning process, by selecting for each cluster a subset of the dimensions on which the standard deviation is minimized.

So the algorithms compared here use different models with different complexity levels. K-means uses only one centroid to represent a cluster. LAC adds to each centroid a vector of weights on each dimension. SSC defines a membership probability of each data object to each cluster, in addition to use a gaussian model. And SuSE also considers a subset of relevant dimensions associated to each cluster. All these algorithms need as input parameter the number K of clusters to be found. So as we discussed earlier, we will run them many times with K varying from 2 to 10.

In order to check if the results depend on the supervised algorithm used, we conduct these experiments with various supervised learning algorithms :

-C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF], the well-known supervised method based on the iterative construction of a decision tree;

-C5 [START_REF] Quinlan | Data mining tools see5 and c5[END_REF] boosted 10 times, that uses the boosting of decision trees, in order to observe if the information added by clustering algorithms also help supervised methods that already combine many classifiers;

-DLG [START_REF] Webb | Inducing diagnostic rules for glomerular disease with the DLG machine learning algorithm[END_REF], a supervised method that uses least general generalizations instead of decision trees, so that many attributes are considered at a time to construct decision surfaces;

and multi-class Support Vector Machines (SVM) [START_REF] Tsochantaridis | Large margin methods for structured and interdependent output variables[END_REF], that construct large margin classifiers, in order to check if the information added by clustering algorithms also help supervised methods that use linear combinations of the initial features.

Finally, the datasets used are those of the UCI Machine Learning Repository [START_REF] Blake | UCI repository of machine learning databases[END_REF] that contain only numerical attributes.

Table 1 presents the balanced error rates of C4.5 run on the initial dataset, and then run on datasets enriched by the results of the corresponding clustering algorithms. Each measure corresponds to an average over five 2-fold crossvalidations. At each time, all the methods are run on the same training set and evaluated on the same test set.

From this table, we can observe that most of the time, the results of C4.5 are improved when some information coming from real clustering algorithms are added, whereas adding information from a random clustering degrades the results. Besides, we can note that the results of SSC and SuSE are often better than those of K-means and LAC. Then table 2 presents a summary of the comparison between C4.5 and C4.5 enriched by the clustering algorithms. SuSE is the only clustering algorithm that significantly helps C4.5 improve its results, according to the wilcoxon signed rank test. It is significantly better on 3 datasets according to the 5×2cv F-test. But as SuSE, SSC improves the results of C4.5 nine times over ten, contrary to K-means and LAC. All algorithms improve the results of C4.5 on average, except the random clustering. And when C4.5 is combined with clustering algorithms based on more complex models, then the error rate is lower and the improvements are more significant than when it is combined with clustering algorithms based on simpler models.

Such experiments were also conducted using different supervised algorithms, namely C5 boosted, DLG and SVM, and using the second method for combining unsupervised and supervised algorithms. It is then very interesting to note that, in spite of the use of different supervised and combination methods, the clustering algorithms that best help supervised learners to minimize the cross-validation error rate on the different datasets remain mostly the same. In particular, SSC and SuSE still outperform K-means and LAC in many cases. Moreover, the order in which the clustering methods are ranked remains the same no matter which supervised and combination methods are used.

Finally, as a comparison, we computed the F-measure and the Entropy between the clusters obtained by the various clustering methods and the initial classes of the various problems in order to measure the mapping between them. We thus first observed that the two measures do not agree on which clustering method leads to the best mapping between the clusters and the classes on each dataset. Then we noted that there is no direct relation between the methods that optimize these values and the methods that better help the supervised learners to improve their results. Besides, such measures do not provide objective information about the interest of the clustering methods, contrary to our proposed evaluation method that shows if the results are significantly better with the help of the given clustering methods.

Conclusion

We have presented in this paper a new objective and quantitative evaluation method of clustering algorithms that consists in comparing the results of a supervised algorithm when it is (or not) provided with information coming from a clustering algorithm. We have considered different supervised algorithms to be used in our evaluation method. We have also considered two different ways of combining unsupervised and supervised learning algorithms.

The experiments pointed out that the order in which the clustering methods are ranked remains the same no matter which supervised algorithm and which combination method are used. So it shows the robustness of our proposed evaluation method. The experiments also pointed out that clustering methods based on the use of more complex models outperform methods based on the use of simpler models. This result is not surprising, but rather exhibits coherent results of our new evaluation method.

Although it was not the aim of our investigations, we have also shown that the results of supervised learning algorithms are improved when they use some extra-knowledge coming from non random clustering algorithms. We conjecture supervised learners can benefit from the information added by clustering methods because these new information are of very different nature. In particular, clustering algorithms can help supervised learners to specialize their treatments according to different specific areas in the input space. They can also help supervised learners fit more complex decision surfaces. It thus seems interesting to continue our investigations in the more general framework of classifier combination when one learner is unsupervised.

Our experiments seem to show that using the clustering to partition the object space, and then executing independent supervised learnings on each created group of data objects gives better results than enriching the datasets with new attributes and then executing a supervised learning on the enriched dataset, since the improvements are more important when the second method for combining unsupervised and supervised algorithms is used. But this may be a consequence of the method we have used to create new attributes, that significantly increases the size of the dataset. It would thus be interesting to examine this point in detail in future research.

Finally, in future works, it would also be interesting to find other tasks as objective as supervised learning, and for which clustering would be an interesting pre-processing, in order to conduct other experiments with our proposed evaluation method in such another framework. One possible way would be for example to compute the reduction in the execution time of various requests on OLAP databases that use (or not) a clustering algorithm to create their index.

Table 1 .

 1 Balanced error rates (in %) of C4.5 enriched by clustering algorithms. The bold values correspond to the minimum error rates obtained on each dataset.

	C4.5 C4.5	C4.5	C4.5	C4.5	C4.5
	alone + Rand + K-means + LAC + SSC + SuSE
	ecoli 48.5	48.3	42.8	40.3	42	43.1
	glass 32.6 40.8	35.7	37	40.4	34.9
	image 4.8	6	4.8	4.6	4.6	4.6
	iono 14.1	15.8	14.2	13.1	9.8	11.2
	iris	7.3	7.9	6.7	3.7	5.1	4.7
	pima 31	35	32.1	32.1	30.8	30
	sonar 31	35.2	30	28.8	28.8	27.2
	vowel 29.5	38.5	25	26.4	24.1	22.2
	wdbc 5.9	6.8	4.6	3.9	5.1	3.1
	wine 8.7	8.8	10.4	9.6	2.7	3.6
		C4.5 C4.5	C4.5	C4.5	C4.5	C4.5
		alone + Rand + K-means + LAC + SSC + SuSE
	nb wins	-	1/9	5/4	7/3	9/1	9/1
	sign wins	-	0/1	0/0	1/0	2/0	3/0
	wilcoxon	-	-2.67	-0.05	1.31	1.83	2.56
	av perf 21.3	24.3	20.6	20	19.3	18.5

Table 2 .

 2 Comparison of C4.5 alone with C4.5 enriched by clustering algorithms.


Maurice Robert Kibler

Bases for qudits from a nonstandard approach to SU(2)

Keywords: numbers: 03.65.Fd, 03.65.Ta, 03.65.Ud, 03.67.-a, 02.20.Qs I. PROLEGOMENA

Bases of finite-dimensional Hilbert spaces (in dimension d) of relevance for quantum information and quantum computation are constructed from angular momentum theory and su(2) Lie algebraic methods. We report on a formula for deriving in one step the (1 + p)p qupits (i.e., qudits with d = p a prime integer) of a complete set of 1 + p mutually unbiased bases in C p . Repeated application of the formula can be used for generating mutually unbiased bases in C d with d = p e (e ≥ 2) a power of a prime integer. A connection between mutually unbiased bases and the unitary group SU (d) is briefly discussed in the case d = p e .

The use of symmetry adapted functions (or state vectors) is of paramount importance in molecular physics and condensed matter physics as well as in the clustering phenomenon of nuclei. For instance, wavefunctions adapted to a finite subgroup of SU(2) turn out to be very useful in crystal-and ligand-field theory [1]- [START_REF] Kibler | Symmetry adaptation and two-photon spectroscopy of ions in molecular or solid-state finite symmetry[END_REF].

It is the purpose of the present work to report on state vectors adapted to the cyclic subgroup C d of SO(3) ∼ SU(2)/Z 2 . Such vectors give rise to bases of SU(2), the so-called mutually unbiased bases (MUBs), to be defined in Section V. They play a fundamental role in quantum information and quantum computation in view of the fact that these bases describe 1 From a talk presented at the 13th International Conference on Symmetry Methods in Physics (Dubna, Russia, 6-9 July 2009) organized in memory of Prof. Yurii Fedorovich Smirnov by the Bogoliubov Laboratory of Theoretical Physics of the JINR (Russia) and the ICAS at Yerevan State University (Armenia).

qudits (the analogs of qubits in dimension d).

A single formula for MUBs is obtained in this paper from a polar decomposition of SU [START_REF] Vonsovski | Crystal-Field Theory and Optical Spectra of Partly Filled d Shell Transition Ions[END_REF] and analysed in terms of quantum quadratic discrete Fourier transforms, Hadamard matrices, generalized quadratic Gauss sums, and special unitary groups SU(d).

Before dealing with the main body of this work, we continue this introduction with a brief survey for nonspecialists of some particular aspects of quantum computation and quantum information for which the concept of MUBs is useful.

According to the law by Moore, the size of electronic and spintronic devices for a classical computer should approach 10 nm in 2018-2020, i.e., the scale where quantum effects are visible, a fact in favor of a quantum computer. This explains the growing interest for a new field, viz., the field of quantum information and quantum computation. Such a field, which started in the 1980's, is at the crossroads of quantum mechanics, discrete mathematics and informatics with the aim of building a quantum computer. We note in passing that, even in the case where the aim would not be reached, physics, mathematics, informatics and engineering will greatly benefit from the enormous amount of works along this line.

In a quantum computer, classical bits (0 and 1) are replaced by quantum bits or qubits (that interpolate in some sense between 0 and 1). A qubit is a vector |φ in the twodimensional Hilbert space C 2 :

|φ = x|0 + y|1 , x ∈ C, y ∈ C, |x| 2 + |y| 2 = 1, (1)
where |0 and |1 are the elements of an orthonormal basis in this space. The result of a measurement of |φ is not deterministic since it gives |0 or |1 with the probability |x| 2 or |y| 2 , respectively. The consideration of N qubits leads to work in the 2 N -dimensional Hilbert space C 2 N . Note that the notion of qubit, corresponding to C 2 , is a particular case of the one of qudit, corresponding to C d (d not necessarily in the form 2 N ). A system of N qudits is associated with the Hilbert space C d N . In this connection, the techniques developed for finite-dimensional Hilbert spaces are of paramount importance in quantum computation and quantum calculation.

From a formal point of view, a quantum computer can be considered as a set of qubits, the state of which can be (controlled and) manipulated via unitary transformations. These transformations correspond to the product of elementary unitary operators called quantum gates acting on one or two qubits. Measurement of the qubits outcoming from a circuit of quantum gates yields the result of a (quantum) computation. In other words, a realization of quantum information processing can be performed by preparing a quantum system in a quantum state, then submitting this state to a unitary transformation and, finally, reading the outcome from a measurement.

Unitary operator bases in C d are of pivotal importance for quantum information and quantum computation as well as for quantum mechanics in general. The interest for unitary operator bases started with the seminal work by Schwinger [START_REF] Schwinger | Proc. Nat. Acad. Sci. USA[END_REF]. Among such bases, MUBs play a key role in quantum information and quantum computation [START_REF] Ivanović | [END_REF]- [17]. The various irreducible representation classes of the group SU(2) are characterized by a label j with 2j ∈ N. The standard irreducible matrix representation associated with j is spanned by the irreducible tensorial set

B 2j+1 = {|j, m : m = j, j -1, . . . , -j}, (2)
where the vector |j, m is a common eigenvector of the Casimir operator j 2 and of the Cartan operator j z of the Lie algebra su(2) of SU(2). More precisely, we have the relations

j 2 |j, m = j(j + 1)|j, m , j z |j, m = m|j, m , (3)
which are familiar in angular momentum theory. (We use lower case letters for operators and capital letters for matrices so that j 2 in (3) stands for the square of a generalized angular momentum.)

Following the works in [18,19], let us define the linear operators v ra and h by

v ra = e i2πjr |j, -j j, j| + j-1 m=-j q (j-m)a |j, m + 1 j, m| (4)
and

h = j m=-j (j + m)(j -m + 1)|j, m j, m|, (5)
where

r ∈ R, q = e 2πi/(2j+1) , a ∈ R. (6)
It can be checked that the three operators

j + = hv ra , j -= (v ra ) † h, j z = 1 2 h 2 -(v ra ) † h 2 v ra , (7)
where (v ra ) † stands for the adjoint of v ra , satisfy the commutation relations

[j z , j + ] = +j + , [j z , j -] = -j -, [j + , j -] = 2j z (8)
of the algebra su(2). (In angular momentum theory, the operators j + and j -are connected to j 2 via j 2 = j ± j ∓ + j z (j z ∓ 1).)

The operator v ra is unitary while the operator h is Hermitian. Thus, Eq. ( 7) corresponds to a polar decomposition of su(2) with the help of the operators v ra and h. It should be noted that v ra can be derived in terms of operators acting on the tensor product of two commuting quon algebras associated with two truncated harmonic oscillators. The latter oscillators play a central role in the intoduction of k-fermions which are supersymmetric objects interpolating between fermions and bosons [START_REF] Daoud | The k-fermions as objects interpolating between fermions and bosons[END_REF][START_REF] Daoud | [END_REF].

It is evident that v ra and j 2 commute. Therefore, the {j 2 , v ra } scheme constitutes an alternative to the {j 2 , j z } scheme. This yields the following result.

Result 1. For fixed j, r and a, the 2j + 1 vectors

|jα; ra = 1 √ 2j + 1 j m=-j q (j+m)(j-m+1)a/2-jmr+(j+m)α |j, m , (9)
with α = 0, 1, . . . , 2j, are common eigenvectors of v ra and j 2 . The eigenvalues of v ra are given by v ra |jα; ra = q j(a+r)-α |jα; ra , [START_REF] Kibler | Finite symmetry adaptation in spectroscopy[END_REF] so that the spectrum of v ra is nondegenerate.

For fixed j, r and a, the inner product

jα; ra|jβ; ra = δ α,β (11)
shows that {|jα; ra : α = 0, 1, . . . , 2j} is an orthonormal set which provides a nonstandard basis for the irreducible matrix representation of SU(2) associated with j.

III. QUANTUM QUADRATIC DISCRETE FOURIER TRANSFORM

In view of the interest of the bases {|jα; 0a : α = 0, 1, . . . , 2j} for quantum information and quantum computation, we shall continue with the case r = 0. From now on, we shall also assume that a = 0, 1, . . . , 2j. Furthermore, by making the following change of notation

n ≡ j + m, |n ≡ |j, m , d ≡ 2j + 1, (12)
Eq. ( 9) gives

|jα; 0a = 1 √ d d-1 n=0 q n(d-n)a/2+nα |n . (13)
Alternatively, the change of notation

k ≡ j -m, |k ≡ |j, m , d ≡ 2j + 1 (14) leads to |jα; 0a = 1 √ d d-1 k=0 q (k+1)(d-k-1)a/2-(k+1)α |k . (15)
Equations ( 13) and ( 15) were used in [22] and [23,24]. They are equivalent as far as quadratic discrete Fourier transforms and mutually unbiased bases (MUBs) are concerned.

Both Eqs. ( 13) and ( 15) correspond to quantum quadratic discrete Fourier transforms which can be inverted to give

|n = 1 √ d q -n(d-n)a/2 d-1 α=0 q -αn |jα; 0a (16)
and

|k = 1 √ d q -(k+1)(d-k-1)a/2 d-1 α=0 q α(k+1) |jα; 0a . (17)
Note that the word quantum in quantum quadratic discrete Fourier transform refers to the fact that the vectors |n or |k (corresponding to |j, m ) are used in the quantum theory of generalized angular momentum.

In the following we shall adopt the change of notation ( 12) and shall re-define |jα; 0a as |aα . In other words

|aα = 1 √ d d-1 n=0 q n(d-n)a/2+nα |n (18)
or, in an equivalent way,

|n = 1 √ d q -n(d-n)a/2 d-1 α=0 q -αn |aα . ( 19
)
Note that the action of the operator v 0a on the vector |n reads

v 0a |n = q -(n+1)a |n + 1 (20) modulo d. It is clear that the basis B 0a = {|aα : α = 0, 1, . . . , d -1} (21)
is an alternative to the basis B d ≡ B 2j+1 . There are d = 2j + 1 bases of this type for a in the ring Z/dZ. Each basis B 0a spans the regular representation of the cyclic group C d .

IV. QUADRATIC DISCRETE FOURIER TRANSFORM

The expression

(H 0a ) nα = 1 √ d q n(d-n)a/2+nα , (22)
occurring in (18), defines the nα th matrix element of a quadratic discrete Fourier transform.

To be more precise, for fixed d and a, let us consider the transformation

x = {x(n) ∈ C : n = 0, 1, . . . , d -1} ↔ y = {y(α) ∈ C : α = 0, 1, . . . , d -1} (23)
defined by

y(α) = d-1 n=0 (H 0a ) nα x(n) ⇔ x(n) = d-1 α=0 (H 0a ) nα y(α). (24)
The particular case a = 0 corresponds to the ordinary discrete Fourier transform which satisfies

(H 00 ) 4 = I d , (25)
where I d is the identity d × d matrix. For a = 0, the bijective transformation x ↔ y can be thought of as a quadratic discrete Fourier transform. The analog of the Parseval-Plancherel theorem for the usual Fourier transform can be expressed in the following way.

Result 2. The quadratic discrete Fourier transforms x ↔ y and x ′ ↔ y ′ associated with the same matrix H 0a , a ∈ Z/dZ, satisfy the conservation rule

d-1 α=0 y(α)y ′ (α) = d-1 n=0 x(n)x ′ (n), ( 26
)
where the common value is independent of a.

It is to be observed that the matrix H 0a is a generalized Hadamard matrix in the sense that the modulus of each of its matrix element is equal to 1/ √ d. Such a matrix reduces the endomorphism associated with the operator v 0a . As a matter of fact, we have

(H 0a ) † V 0a H 0a = q (d-1)a/2         q 1 0 . . . 0 0 q 2 . . . 0 . . . . . . . . . . . . 0 0 . . . q d         , ( 27
)
where the matrix

V 0a =             0 q a 0 . . . 0 0 0 q 2a . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . q (d-1)a 1 0 0 . . . 0             ( 28
)
represents the linear operator v 0a on the basis

B d = {|n : n = d -1, d -2, . . . , 0}, (29)
known as the computational basis in quantum information and quantum computation.

The Hadamard matrices H 0a and H 0b (a, b ∈ Z/dZ) are connected to the inner product aα|bβ . In fact, we have

(H 0a ) † H 0b αβ = aα|bβ = 1 d d-1 n=0 q n(d-n)(b-a)/2+n(β-α) . (30)
Thus, each matrix element of (H 0a ) † H 0b can be written in the form of a generalized quadratic Gauss sum S(u, v, w) defined by [START_REF] Berndt | Gauss and Jacobi Sums[END_REF] S(u, v, w)

= |w|-1 n=0 e iπ(un 2 +vn)/w , (31)
where u, v, and w are integers such that u and w are mutually prime, uw = 0, and uw + v is even. In detail, we obtain

aα|bβ = (H 0a ) † H 0b αβ = 1 d S(u, v, w), (32)
with the parameters

u = a -b, v = -(a -b)d -2(α -β), w = d, (33)
which ensure that uw + v is even.

The matrix V 0a can be decomposed as

V 0a = X 0 Z a , (34)
where

X 0 =             0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1 1 0 0 . . . 0             (35)
and

Z =             1 0 0 . . . 0 0 q 0 . . . 0 0 0 q 2 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . q d-1             . (36)
The unitary matrices X 0 and Z q-commute in the sense that

X 0 Z -qZX 0 = 0. (37)
In addition, they satisfy

(X 0 ) d = Z d = I d . (38)
Equations ( 37) and (38) show that X 0 (to be noted as X in what follows in order to conform to the notations used for Pauli matrices) and Z constitute a Weyl pair. Weyl pairs were introduced at the beginning of quantum mechanics [START_REF] Weyl | The Theory of Groups and Quantum Mechanics[END_REF] and used for building operator unitary bases [START_REF] Schwinger | Proc. Nat. Acad. Sci. USA[END_REF]. The Weyl pair (X, Z) turns out to be an integrity basis for generating a set {X a Z b : a, b ∈ Z/dZ} of d 2 generalized Pauli matrices in d dimensions (see for instance [23,24] and references therein). In this respect, note that for d = 2 we have

X = σ x , Z = σ z , XZ = -iσ y , X 0 Z 0 = σ 0 , (39)
in terms of the ordinary Pauli matrices σ 0 = I 2 , σ x , σ y , and σ z . Equations ( 37) and ( 38) can be generalized through

V 0a Z -qZV 0a = 0, (V 0a ) d = e iπ(d-1)a I d , Z d = I d , (40)
so that other pairs of Weyl can be obtained from V 0a and Z.

| aα|bβ | = δ a,b δ α,β + (1 -δ a,b ) 1 √ d . (41)
From Eq. ( 41), note that if two MUBs undergo the same unitary or antiunitary transformation, they remain mutually unbiased. It is well-known that the maximum number N of MUBs in C d is N = 1 + d and that this number is attained when d is a prime number p or a power p e (e ≥ 2) of a prime number p [13]- [15]. In the other cases (d = p e , p prime and e integer with e ≥ 1), the number N is not known although it can be shown that 3 ≤ N ≤ 1 + d (see for example [16]). In the general composite case d = i p e i i , we know that 1 + min(p e i i ) ≤ N ≤ 1 + d (see for example [17]). i.e.

su(p) ≃ v 0 ⊎ v 1 ⊎ . . . ⊎ v p (61)
where the 1 + p subalgebras v 0 , v 1 , . . . , v p are Cartan subalgebras generated respectively by the sets V 0 , V 1 , . . . , V p containing each p -1 commuting matrices.

Result 4 can be extended when d = p e with p a prime integer and e an integer (e ≥ 2):

there exists a decomposition of su(p e ) into 1 + p e abelian subalgebras of dimension p e -1

[27]- [33] (see also [23,24]).

VII. CLOSING REMARKS

MUBs prove to be useful in classical information theory (network communication protocols), in quantum information theory (quantum state tomography and quantum cryptography), and in the theory of quantum mechanics as for the solution of the Mean King problem and the understanding of the Feynman path integral formalism (see [23,24] for an extensive list of references).

There exist numerous ways of constructing sets of MUBs. Most of them are based on discrete Fourier transform over Galois fields and Galois rings, discrete Wigner distribution, generalized Pauli operators, mutually orthogonal Latin squares, discrete geometry methods, angular momentum theory and Lie-like approaches. In many of the papers dealing with the construction of MUBs for d a prime integer or a power of a prime integer, the explicit derivation of the bases requires the diagonalisation of a set of matrices.

In the present paper, the generic formula (18) arises from the diagonalisation of a single matrix (the matrix V 0a ), for the N = 1 + p MUBs corresponding to d = p with p a prime integer. Repeated application (e times) of this formula can be used in the case where d = p e is the power of a prime integer. Results 1 and 3 of this paper concern the closed form formula (18). Its derivation is based on the master matrix V 0a . From V 0a we can deduce the Weyl pair (X, Z) through

X = V 00 , Z = (V 00 ) † V 01 . (62)
The operators X and Z are known as the flip or shift and clock operators, respectively. For d arbitrary, they are at the root of the Pauli group, a finite subgroup of order d 3 of the group SU(d), of considerable importance in quantum information and quantum computation (e.g., see [34]- [36] and references therein for recent geometrical approaches to the Pauli group).

The Pauli group is relevant for describing quantum errors and quantum fault tolerance in quantum computation.

  From a very general point of view, MUBs are closely connected to the principle of complementarity introduced by Bohr in the early days of quantum mechanics. This principle, quite familiar in terms of observables like position and momentum, tells that for two noncommuting observables, if we have a complete knowledge of one observable, then we have a total uncertainty of the other. Equation (41) in Section V for a = b indicates that the development in the basis B a of any vector of the basis B b is such that each vector of B a appears in the development with the probability 1/d. This is especially interesting when translated in terms of measurements, the bases B a and B b corresponding to the (nondegenerate) eigenvectors of two noncommuting observables. II. A NONSTANDARD BASIS FOR SU (2)

V

  . MUTUALLY UNBIASED BASES From a very general point of view, let us recall that two orthonormal bases B a = {|aα : α = 0, 1, . . . , d -1} and B b = {|bβ : β = 0, 1, . . . , d -1} of the Hilbert space C d are said to be mutually unbiased if and only if the inner product aα|bβ has a modulus independent of α and β. In other words ∀α ∈ Z/dZ, ∀β ∈ Z/dZ :

Result 4 .

 4 For d = p, with p a prime integer, the Lie algebra su(p) of the group SU(p) can be decomposed into a direct sum of 1 + p abelian subalgebras each of dimension p -1,

Acknowledgments This paper is dedicated to the memory of Yurii Fedorovich Smirnov. It was presented at the 13th International Conference on Symmetry Methods in Physics (SYMPHYS-XIII) organized in memory of Prof. Yurii Fedorovich Smirnov by the Bogoliubov Laboratory of Theoretical Physics of the Joint Institute for Nuclear Research and the International Center for Advanced Studies at Yerevan State University (the conference was held in Dubna, Russia, 6-9 July 2009). The author acknowledges the Organizing Committee of SYMPHYS-XIII, especially George S. Pogosyan, for their kind invitation to participate to this interesting conference.

A. Mutually unbiased bases for d prime

For d = 2, it can be checked that the bases B 00 , B 01 , and B 2 are 1 + d = 3 MUBs. A similar result follows for d = 3: the bases B 00 , B 01 , B 02 , and B 3 are 1 + d = 4 MUBs. This can be generalized by the following result.

Result 3. For d = p, with p a prime number, the bases B 00 , B 01 , . . . , B 0p-1 , B p form a complete set of 1 + p MUBs. The p 2 vectors |aα , with a, α = 0, 1, . . . , p -1, of the bases B 00 , B 01 , . . . , B 0p-1 are given by a single formula (namely Eq. ( 18)).

The proof of Result 3 is as follows. First, Eq. ( 18) yields

a relation that holds for all k, a, and α in Z/pZ so that each basis B 0a is unbiased with B p .

Second, the generalized quadratic Gauss sum S(u, v, w) in (32), with d = p prime, can be calculated to give

for all a, b, α, and β in Z/pZ. This completes the proof.

We note in passing that, in the case where d = p is a prime integer, the product (H 0a ) † H 0b is another generalized Hadamard matrix.

To close this subsection, we may ask what becomes Result 3 when the prime integer p is replaced by an arbitrary (not prime) integer d. In this case, the formula (18) does not provide a complete set of 1 + d MUBs. However, it is possible to show [23,24] that the bases B 0a , B 0a⊕1 , and B d are three MUBs in C d (the addition ⊕ is understood modulo d). This result is in agreement with the well-known result according to which the maximum number of MUBs in C d , with d arbitrary, is greater or equal to 3 ([16]). Moreover, it can be proved [23,24] that the bases B 0a and B 0a⊕2 are unbiased for d odd with d ≥ 3 (d prime or nor prime).

B. Mutually unbiased bases for d power of a prime

Equation ( 18) can be used for deriving a complete set of 1 + p e MUBs in the case where d = p e is a power (e ≥ 2) of a prime integer p. The general case is very much involved.

Hence, we shall proceed with the example p = e = 2 corresponding to two qubits.

For d = 2 2 = 4, the application of ( 18) and ( 21) yields four bases B 0a (a = 0, 1, 2, 3). As a point of fact, the bases B 00 , B 01 , B 02 , B 03 , and B 4 do not form a complete set of 1 + d = 5

MUBs. However, it is possible to construct a set of five MUBs from repeated application of (18).

Four of the five MUBs for d = 4 can be constructed from the direct products |aα ⊗ |bβ which are eigenvectors of the operators v 0a ⊗ v 0b . Obviously, the set

is an orthonormal basis in C 4 . It is evident that B 0000 and B 0101 are two unbiased bases since the modulus of the inner product of

A similar result holds for the two bases B 0001 and B 0100 . However, the four bases B 0000 , B 0101 , B 0001 , and B 0100 are not mutually unbiased. A possible way to overcome this no-go result is to keep the bases B 0000 and B 0101 intact and to re-organize the vectors inside the bases B 0001 and B 0100 in order to obtain four MUBs. We are thus left with four bases

which together with the computational basis B 4 give five MUBs. In detail, we have

where

and the vectors of type |aα are given by the master formula (18). As a résumé, only two formulas are necessary for obtaining the d 2 = 16 vectors |ab; αβ for the bases W ab , namely

for all a, α, and β in Z/2Z.

It is to be noted that the vectors of the W 00 and W 11 bases are not intricated (i.e., each vector is the direct product of two vectors) while the vectors of the W 01 and W 10 bases are intricated (i.e., each vector is not the direct product of two vectors).

Generalization of ( 52) and ( 53) can be obtained in more complicated situations (two qupits, three qubits, . . . ). The generalization of (52) is immediate. The generalization of (53) can be achieved by taking linear combinations of vectors such that each linear combination is made of vectors corresponding to the same eigenvalue of the relevant tensor product of operators of type v 0a .

VI. MUTUALLY UNBIASED BASES AND UNITARY GROUPS

In the case where d is a prime integer or a power of a prime integer, it is known that the set {X a Z b : a, b = 0, 1, . . . , d -1} of cardinality d 2 can be partitioned into 1 + d subsets containing each d -1 commuting matrices (cf. [15]). By way of illustration, for d = p with p prime, the 1 + p sets of p -1 commuting matrices are easily seen to be

V 3 = {X a Z 2a : a = 1, 2, . . . , p -1}, (57) . . .

V p = {X a Z (p-1)a : a = 1, 2, . . . , p -1}.

Each of the 1 + p sets V 0 , V 1 , . . . , V p can be put in a one-to-one correspondance with one basis of the complete set of 1 + p MUBs. In fact, V 0 is associated with the computational basis while V 1 , V 2 , . . . , V p are associated with the p remaining MUBs in view of V 0a ∈ V a⊕1 , a = 0, 1, . . . , p -1.

(60)

Keeping into account the fact that the set {X a Z b : a, b = 0, 1, . . . , p -1} \ {X 0 Z 0 } spans the Lie algebra of SU(p), we get the following result.