Andrea G B Tettamanzi
email: andrea.tettamanzi@unice.fr

Catherine Faron-Zucker

Fabien Gandon
email: fabien.gandon@inria.fr

Testing OWL Axioms Against RDF Facts: A possibilistic approach

Keywords: ontology learning, open-world assumption, possibility theory

Automatic knowledge base enrichment methods rely critically on candidate axiom scoring. The most popular scoring heuristics proposed in the literature are based on statistical inference. We argue that such a probability-based framework is not always completely satisfactory and propose a novel, alternative scoring heuristics expressed in terms of possibility theory, whereby a candidate axiom receives a bipolar score consisting of a degree of possibility and a degree of necessity. We evaluate our proposal by applying it to the problem of testing SubClassOf axioms against the DBpedia RDF dataset.

Introduction

A common approach to the semantic Web puts strong emphasis on a principled conceptual analysis of a domain of interest leading to the construction or reuse of ontologies as a prerequisite step for the organization of the Linked Open Data (LOD), much like a database schema must be designed before a database can be populated. However this approach has some limitations: it is aprioristic and dogmatic in the way knowledge should be organized; while it is quite successful when applied to specific domains, it does not scale well to more general settings; it does not lend itself to a collaborative effort; etc. That is why an alternative, bottom-up, grass-roots approach to ontology and knowledge base creation better suits many scenarii: instead of postulating an a priori conceptualization of reality (i.e., an ontology) and requiring that our knowledge about facts complies with it, one can start from RDF facts and learn OWL 2 axioms.

Recent contributions towards the automatic creation of OWL 2 ontologies from large repositories of RDF facts include FOIL-like algorithms for learning concept definitions [START_REF] Fanizzi | DL-FOIL concept learning in description logics[END_REF], statistical schema induction via association rule mining [START_REF] Fleischhacker | Mining RDF data for property axioms[END_REF], and light-weight schema enrichment methods based on the DL-Learner framework [START_REF] Hellmann | Learning of OWL class descriptions on very large knowledge bases[END_REF][START_REF] Bühmann | Universal OWL axiom enrichment for large knowledge bases[END_REF]. All these methods apply and extend techniques developed within inductive logic programming (ILP) [START_REF] Muggleton | ILP turns 20: Biography and future challenges[END_REF].

On a related note, there exists a need for evaluating and validating ontologies, be they the result of an analysis effort or of a semi-automatic learning method. This need is witnessed by general methodological investigations [START_REF] Gangemi | A theoretical framework for ontology evaluation and validation[END_REF][START_REF] Gangemi | Modelling ontology evaluation and validation[END_REF] and surveys [START_REF] Tartir | Ontological evaluation and validation[END_REF] and tools like OOPS! [START_REF] Poveda-Villalón | Validating ontologies with OOPS![END_REF] for detecting pitfalls in ontologies.

Ontology learning and validation rely critically on (candidate) axiom scoring. In this paper, we will tackle the problem of testing a single, isolated axiom, which is anyway the first step to solve the problem of validating an entire ontology. Furthermore, to keep things reasonably simple, we will restrict our attention to subsumption axioms of the form SubClassOf(C D).

The most popular scoring heuristics proposed in the literature are based on statistical inference. We argue that such a probability-based framework is not always completely satisfactory. We will propose an axiom scoring heuristics based on a formalization in possibility theory of the notions of logical content of a theory and of falsification, loosely inspired by Karl Popper's approach to epistemology. Our research question is: "Can we apply a possibilistic approach to the task of testing candidate axioms for ontology learning?". In addition, "Could this be beneficial to ontology and knowledge base validation?".

The paper is organized as follows: Section 2 proposes a heuristics based on possibility theory, alternative to probability-based scoring heuristics. Its implementation is detailed in Section 3 and an evaluation is provided in Section 4. Section 5 draws some conclusions.

A Possibilistic Candidate Axiom Scoring Heuristics

Let φ be a candidate axiom and u φ the support or sample size for φ, i.e., the cardinality of the set of its logical consequences that will be tested in the RDF repository. Notice that every formula which logically follows from an axiom is both a potential falsifier (if it is contradicted by facts) and a potential confirmation (if it is verified by facts) for that axiom.

Let u + φ the number of such consequences which are true (confirmations), and u - φ the number of such consequences which are false (counterexamples). A few interesting properties of these three cardinalities are:

u + φ + u - φ ≤ u φ ; (1)
u + φ = u - ¬φ , u - φ = u + ¬φ , u φ = u ¬φ . (2)
A statistics-based heuristics for the scoring of candidate axioms used in the framework of knowledge base enrichment [START_REF] Bühmann | Universal OWL axiom enrichment for large knowledge bases[END_REF] may be regarded essentially as scoring an axiom by an estimate of the probability that one of its logical consequences is confirmed (or, alternatively, falsified) by the facts stored in the RDF repository. As Bühmann and Lehmann point out [START_REF] Bühmann | Universal OWL axiom enrichment for large knowledge bases[END_REF], estimating the probability of confirmation of axiom φ just by pφ = u + φ /u φ would be too crude and would not take the magnitude of u φ into account. That is why they base their probabilistic score on Agresti and Coull's binomial proportion confidence interval [START_REF] Agresti | Approximate is better than "exact" for interval estimation of binomial proportions[END_REF].

One problem with such approaches is that they only look for confirmations of φ and treat their absence as failures in the calculation of the confidence interval. This is like making an implicit closed-world assumption. An easy fix, in view of the open-world assumption, might be, for example, to use p * = u + φ /(u + φ + u - φ ) as the sample proportion instead of p.

A more serious problem, however, is that these approaches rely on the assumption that it is possible to estimate the probability that an axiom φ is true given some evidence e, where e = "ψ such that φ |= ψ is in the RDF repository", or e = "ψ such that ψ |= ¬φ is in the RDF repository", or e = "ψ such that φ |= ψ is not in the RDF repository", etc., which, by Bayes' formula, may be written as

Therefore, in order to compute (or estimate) such probability, one should be able to estimate the probabilities on the right-hand side of Equation 3. Now, this is possible only under the (strong) assumption that the data at hand are representative.

To capture the basic intuition behind the process of axiom discovery without making unwarranted assumptions, we propose an alternative axiom scoring heuristics based on possibility theory, which is weaker than probability theory.

Possibility Theory

Possibility theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] is a mathematical theory of epistemic uncertainty. Given a finite universe of discourse Ω, whose elements ω ∈ Ω may be regarded as events, values of a variable, possible worlds, or states of affairs, a possibility distribution is a mapping π : Ω → [0, 1], which assigns to each ω a degree of possibility ranging from 0 (impossible, excluded) to 1 (completely possible, normal). A possibility distribution for which there exists a completely possible state of affairs (∃ω * : π(ω * ) = 1) is said to be normalized.

There is a similarity between possibility distribution and probability density. However, it must be stressed that π(ω) = 1 just means that ω is a plausible (normal) situation and therefore should not be excluded. A degree of possibility can then be viewed as an upper bound of a degree of probability. Possibility theory is suitable to represent incomplete knowledge while probability is adapted to represent random and observed phenomena. We invite the reader to see [START_REF] Dubois | Fuzzy sets and probability: Misunderstandings, bridges and gaps[END_REF] for more informations about the relationships between fuzzy sets, possibility, and probability degrees.

A possibility distribution π induces a possibility measure and its dual necessity measure, denoted by Π and N respectively. Both measures apply to a set A ⊆ Ω (or to a formula φ, by way of the set of its models, A = {ω : ω |= φ}), and are defined as follows:

Π(A) = max ω∈A π(ω); (4)
N (A) = 1 -Π( Ā) = min ω∈ Ā{1 -π(ω)}. (5)
A few properties of possibility and necessity measures induced by a normalized possibility distribution on a finite universe of discourse Ω are the following. For all subsets A ⊆ Ω,

1. Π(∅) = N (∅) = 0, Π(Ω) = N (Ω) = 1; 2. Π(A) = 1 -N ( Ā) (duality); 3. N (A) > 0 implies Π(A) = 1, Π(A) < 1 implies N (A) = 0.
In case of complete ignorance on A, Π(A) = Π( Ā) = 1.

Support of an Axiom

At the beginning of this section, we have introduced the notion of support or sample for a candidate axiom φ as the number of its logical consequences that will be tested in the RDF repository. We shall now define that notion more precisely.

Let BS be a finite set of basic statements, i.e., assertions, like the ones contained in an RDF repository, that may be tested by means of a SPARQL ASK query. We define the content of an axiom φ that we wish to evaluate as the set of its logical consequences, but we restrict it to basic statements, to ensure finiteness and testability:

content(φ) = {ψ : φ |= ψ} ∩ BS. (6)
The cardinality of content(φ) is finite, because BS is finite, and every formula ψ ∈ content(φ) may be tested, because it is a basic statement. Now we can define the support of φ as the cardinality of content(φ):

u φ = |content(φ)|. (7)

Possibility and Necessity of an Axiom

The basic principle for establishing the possibility of a formula φ should be that the absence of counterexamples to φ in the RDF repository means Π(φ) = 1, i.e., that φ is completely possible. A hypothesis should be regarded as all the more necessary as it is explicitly supported by facts and not contradicted by any fact; and all the more possible as it is not contradicted by facts. In other words, given hypothesis φ, Π(φ) = 1 if no counterexamples are found; as the number of counterexamples increases, Π(φ) → 0 strictly monotonically; N (φ) = 0 if no confirmations are found; as the number of confirmations increases and no counterexamples are found, N (φ) → 1 strictly monotonically. Notice that a confirmation of φ is a counterexample of ¬φ and that a counterexample of φ is a confirmation of ¬φ. Furthermore, the first counterexamples found to an axiom should determine a sharper decrease of the degree to which we regard the axiom as possible than any further counterexamples, because these latter will only confirm our suspicions and, therefore, will provide less and less information and, similarly, in the absence of counterexamples, the first confirmations found to an axiom should determine a sharper increase of the degree to which we regard the axiom as necessary than any further confirmations, because these latter will only add up to our acceptance and, therefore, will provide less and less information.

A definition of Π and N which captures the above intuitions, but by no means the only possible one, is, for u φ > 0,

Π(φ) = 1 -1 - u φ -u - φ u φ 2 ; (8)
N (φ) = 1 - u φ -u + φ u φ 2 if Π(φ) = 1, 0 otherwise. ( 9
)
Notice that this definition satisfies the duality of possibility and necessity, in that N (φ) = 1 -Π(¬φ) and Π(φ) = 1 -N (¬φ). We combine the possibility and necessity of an axiom to define a single handy acceptance/rejection index (ARI) as follows:

ARI(φ) = N (φ) -N (¬φ) = N (φ) + Π(φ) -1 ∈ [-1, 1]. (10)
A negative ARI(φ) suggests rejection of φ (Π(φ) < 1), whilst a positive ARI(φ) suggests its acceptance (N (φ) > 0), with a strength proportional to its absolute value. A value close to zero reflects ignorance about the status of φ.

A Framework for Candidate Axiom Testing

We refer to the model-theoretic semantics of OWL 2 (as defined in [START_REF] Grau | OWL 2 web ontology language direct semantics[END_REF]), which defines an interpretation I with a valuation function • I mapping OWL 2 expressions into elements and sets of elements of an interpretation domain ∆ I . We take the set of all the resources that occur in a given RDF store as ∆ I and checking an axiom amounts to checking whether I is a model of the axiom. Also, calling linked data search engines like Sindice could virtually extend the interpretation domain to the whole LOD cloud. However, unlike interpretation domains, RDF stores are incomplete and possibly noisy. The open-world hypothesis must be made; therefore, absence of supporting evidence does not necessarily contradict an axiom, and an axiom might hold even in the face of a few counterexamples (exceptions or possible mistakes). For example, out of 541 axioms of the form SubClassOf(C D) in the DBpedia ontology, 143 have an empty content (i.e., class C is empty) and 28 have at least one counterexample in DBpedia 3.9. 3A general algorithm for testing all the possible OWL 2 axioms in a given RDF store is beyond the scope of this paper. Here, we will restrict our attention to atomic class expressions and ObjectComplementOf expressions, needed to test SubClassOf axioms. The model-theoretic semantics of expressions of the form ObjectComplementOf(C) (¬C in description logics syntax), where C denotes a concept expression (called class expression in OWL 2) is ∆ I \ C I . Now, let us define a mapping Q(E, x) from OWL 2 expressions to SPARQL graph patterns, where E is an OWL 2 expression, x is a formal parameter which can be replaced by a SPARQL variable or an RDF term, such that the query SELECT DISTINCT ?x WHERE { Q(E, ?x) } returns all the known instances of class expression E, which we will denote by [Q(E, x)], i.e., the equivalent of E I , and the query ASK { Q(E, a) } checks whether E(a) is in the RDF base.

For an atomic concept A, Q(A, ?x) = ?x a A, where A is a valid IRI. For concept negation, things are slightly more complicated, for RDF does not support negation. The obvious definition

Q(¬C, ?x) = { ?x ?p ?o . FILTER NOT EXISTS Q(C, ?x) }, (11)
has the problem of treating negation as failure, like in databases, where the closed-world assumption is made. Since we want to get as close as possible to an open-world semantics, Q(¬C, x) should be defined differently, as the union of the concepts that are disjoint from C. One might try to express this as the set of individuals x that are instances of a concept C such that no individual z ∈ C I is an instance of C , yielding the query

Q(¬C, ?x) = { ?x a ?dc . FILTER NOT EXISTS { ?z a ?dc . Q(C, ?z) } }, (12)
where ?z is a variable that does not occur anywhere else in the query. This translation is conceptually more satisfactory than the one in Equation 11, but it just pushes the problem one step further, because this way of testing whether two concepts are disjoint is based on negation as failure too. The only way to be certain that two classes are disjoint would be to find an axiom to this effect in the ontology:

Q(¬C, ?x) = { ?x a ?dc . ?dc owl:disjointWith C }, (13)
otherwise, either we find an individual which is an instance of both classes, and thus we know the two classes are not disjoint, or we don't, in which case the two classes may or may not be disjoint. The fact is, very few DisjointClasses axioms are currently found in existing ontologies. For example, in the DBpedia ontology, the query SELECT ?x ?y { ?x owl:disjointWith ?y } executed on November 22, 2013 returned 17 solutions only.

To compare these three alternative definitions of Q(¬C, ?x), we may refer to the diagram in Figure 1. We wish to estimate the actual extent of (¬C) I . Clearly, Q(C, ?x) (in dark grey) underestimates the real extent of C I (in light gray). Therefore, we may say that Equation 11 overestimates the real extent of (¬C) I , in the sense that it will regard as instances of ¬C all individuals a for which "a a C" is not found in the RDF repository. Now, if b is such that "b a C" is not known, but "b a D " is known for some class D and some instances of D are known to be also instances of C, then it might well be that b is an instance of C as well. If, however, a is such that "a a C" is not known and no instance of D is known that is also an instance of C, then we are more likely to believe that a is not an instance of C. Therefore Equation 12 regards as instances of ¬C fewer individuals, those for which it is highly likely that they do not belong in C.

On the other hand, Equation 13certainly underestimates (¬C) I , to the point of considering it empty if "D owl:disjointWith C" is not declared in the RDF repository. Furthermore, an individual may be an instance of ¬C even though it is not an instance of a class disjoint with C! To sum up, Equation 11 is too optimistic, Equation 13 too pessimistic, and Equation 12 somewhere in the middle. Following the old adage "virtue stands in the middle", adopting Equation 12 looks like a sensible choice.

We will end this section by arguing that a suitable definition of confirmation to adopt in this framework is Scheffler and Goodman's selective confirmation [START_REF] Scheffler | Selective confirmation and the ravens: A reply to Foster[END_REF], which characterizes a confirmation as a fact not simply satisfying an axiom, but, further, favoring the axiom rather than its contrary. For instance, the occurence of a black raven selectively confirms the axiom Raven Black because it both confirms it and fails to confirm its negation, namely that there exist ravens that are not black. On the contrary, the observation of a green apple does not contradict Raven Black, but it does not disconfirm Raven Black either; therefore, it does not selectively confirm Raven Black. (

Evaluation on Subsumption Axiom Testing

) 14
In order to compute ARI(C D), we must provide a computational definition of u + C D and u - C D . We start with the following statements:

-confirmations are individuals i such that i ∈ [Q(C, x)] and i ∈ [Q(D, x)]; -counterexamples are individuals i such that i ∈ [Q(C, x)] and i ∈ [Q(¬D, x)].
This may be translated into SPARQL queries to compute u + C D and u - C D :

SELECT (count(DISTINCT ?x) AS ?numConfirmations) WHERE { Q(C, ?x) Q(D, ?x) } (15)
and SELECT (count(DISTINCT ?x) AS ?numCounterexamples

) WHERE { Q(C, ?x) Q(¬D, ?x) } (16) respectively. Notice that an i ∈ [Q(C, x)] such that i / ∈ [Q(D, x)]
does not contradict C D, because it might well be the case that the assertion "i a D" is just missing. Likewise, an i ∈ [Q(¬D, x)] such that i ∈ [Q(¬C, x)] will not be treated as a confirmation, based on our choice to regard as evidence in favor of a hypothesis only selective confirmations.

We evaluated the proposed scoring heuristics by performing tests of subsumption axioms using DBpedia 3.9 in English as the reference RDF fact repository. In particular, on April 27, 2014, we downloaded the DBpedia dumps of English version 3.9, generated in late March/early April 2013, along with the DBpedia ontology, version 3.9. This local dump of DBpedia, consisting of 812,546,748 RDF triples, has been bulk-loaded into Jena TDB and a prototype for performing axiom tests using the proposed method has been coded in Java, using Jena ARQ and TDB to access the RDF repository.

All experiments have been performed on a Fujitsu CELSIUS workstation equipped with twelve six-core Intel Xeon CPU E5-2630 v2 processors at 2.60GHz clock speed, with 15,360 KB cache each, 128 GB RAM, 4 TB of disk space with a 128 GB SSD cache, under the Ubuntu 12.04.4 LTS 64-bit operating system.

We performed two experiments of different type: an explorative test of systematically generated subsumption axioms and an exhaustive test of all subsumption axioms in the DBpedia ontology. 4For the former experiment, we systematically generated and tested subsumption axioms involving atomic classes only according the following protocol: for each of the 442 classes C referred to in the RDF repository, we construct all axioms of the form C D such that C and D share at least one instance. Classes D are obtained with query SELECT DISTINCT ?D WHERE {Q(C, ?x). ?x a ?D}. Due to the sheer number of axioms thus generated, and to the long time it takes to test them,5 this experiment could not complete at the time of writing and is still underway; however, a sufficient number of axioms was tested to allow gathering some statistics. Figure 2a shows the distribution of test time, while the plot of time vs. ARI of axioms in Figure 2b suggests that the time it takes to test an axiom is inversely proportional to its ARI. This is good news, because it suggests that putting a time-out on the test would be an acceptable heuristics to decide whether to accept or reject a candidate axiom, for an axiom which takes too long to test will likely end up having a very negative ARI. By construction, all axioms generated in this experiment have at least one confirmation and, as a consequence, non-zero possibility (thus ARI > -1).

The ARI values of systematically generated axioms tend to cluster around the three values -1, 0, and 1 (see Figure 3a).

To assess the discriminatory ability of the proposed scoring heuristics, we have evaluated these results by sorting the 380 tested axioms by their ARI and by manually tagging each of them as either true or false based on common sense. Three out of the 78 axioms with an ARI of 1 are clearly false: SubClas-sOf(dbo:Eukaryote dbo:Species), SubClassOf(dbo:OrganisationMember dbo:Sports-TeamMember), and SubClassOf(dbo:SportCompetitionResult dbo:OlympicResult). However, no scoring heuristics based on counting would be able to tell these 3 false positives from the true ones. Proceeding by decreasing ARI, the first false axiom encountered was SubClassOf(dbo:TennisLeague skos:Concept), with an ARI of 0.699854, 6 followed by the true axiom SubClassOf(dbo:Road gml: Feature), with an ARI of 0.410399, followed by a large number of false axioms, starting with SubClassOf(schema:Product gml: Feature) with an ARI of 0.326187. This positive ARI means no counterexamples were found; the 2,806 confirmations are all instances of classes dbo:Aircraft and dbo:Ship having, strangely enough, geographical coordinates. A few seemingly true axioms are found with an ARI around zero. They are SubClassOf(schema:School schema:Place), SubClassOf(schema:School dbo:Place), with an ARI of 0.00830433, and SubClassOf(schema:School dbo:EducationalInstitution), SubClassOf(schema:School dbo:Organisation), SubClassOf(schema:School schema:EducationalOrganization), and SubClassOf(schema:School schema:Organization), with an ARI of -0.00830433.

A dubious case is SubClassOf(schema:Museum dbo:Building), with an ARI of -0.031754, 3,957 confirmations and two counterexamples :Saint Peter's Basilica and :US 90. We tagged it as false, because one could imagine a museum hosted on a ship or an open-air museum, but we admit to our choice being debatable.

This distribution of true and false axioms suggests ARI(φ) > 1/3 as the optimal acceptance criterion for a candidate axiom φ. This would yield 4 false positives and 6 false negatives (corresponding to a 97.37% accuracy). However, it appears that the misclassification of the above axioms is to blame on mistakes in DBpedia. This highlights the potential for the proposed heuristics as a tool for RDF data validation: confirmations and counterexamples of axioms with ARI around zero is where the search for bugs should focus.

It is interesting to compare these results with those one would obtain by using a probability-based score. Figure 3b provides a comparison by plotting each axiom according to its ARI (X-axis) and its score computed as in [START_REF] Bühmann | Universal OWL axiom enrichment for large knowledge bases[END_REF] (Y-axis). First of all it is clear that both scores tend to agree in the extremes, with some notable exceptions, but behave quite differently in all other cases. The probabilistic score with the 0.7 threshold suggested by [START_REF] Bühmann | Universal OWL axiom enrichment for large knowledge bases[END_REF] gives 13 false negatives (7 more than the ARI) and 4 false positives (the three false axioms with ARI of 1, plus SubClassOf(schema:Museum dbo:Building), which we tagged as false). Among the false negatives, there are five axioms with an ARI of 1 which are rejected by the probabilistic score: they are all of the form SubClas-sOf(dbo:TennisLeague D). Then we find SubClassOf(schema:School schema:Place) and SubClassOf(schema:School dbo:Place), which were also rejected by the ARI, and six axioms of the form SubClassOf(C gml: Feature), which have ARIs comprised between 0.41 and 0.997. Finally, most false axiom candidates get an ARI close to -1, whilst their probabilistic scores are almost evenly distributed between 0 and 0.5. We might say that, besides being more accurate, ARI gives clearer indications than the probabilistic score.

For the second, more validation-oriented experiment, we extracted an exhaustive list of SubClassOf axioms in the DBpedia ontology, in functional syntax, with the query SELECT DISTINCT concat("SubClassOf(<",str(?x),"> <",str(?y),">)") WHERE { ?x a owl:Class . ?x rdfs:subClassOf ?y } thus obtaining 541 axioms. Testing them took "only" 1 h 23 min 31 s, due to the fact that most of these axioms have a positive ARI and can thus be tested relatively rapidly.

A large number of these axioms (143) turned out to have u φ = 0 (empty content) thus their ARI is 0. For 28 axioms, a negative ARI signals the presence of seemingly erroneous facts: the following table gives :New People's Army, :Syrian

Conclusion

We have proposed a candidate axiom scoring heuristics, based on possibility theory, to be used for automatic axiom induction from RDF data and, ultimately, to provide a solid basis for ontology learning. In addition, we have developed a framework based on the proposed heuristics, which uses the model-theoretic semantics of OWL 2 and SPARQL queries to test candidate axioms.

The results of experimental evaluation on the DBpedia dataset clearly indicate that the proposed heuristics is suitable for tasks such axiom induction and ontology learning and, furthermore, may be beneficial as a tool for ontology and knowledge-base validation.

One may object that, being based on possibility theory, our scoring heuristics is less objective than a probability-based scoring method. However, we have argued in Section 2 that scoring heuristics based on probability are doomed to be arbitrary and subjective or, in other words, qualitative and, therefore, hardly more rigorous or objective than the proposed approach. The experimental results corroborate this claim.

Future work includes extending the experimental evaluation to more general sets of candidate axioms and enlarging the test base by including additional RDF datasets from the LOD. We also plan on improving the implementation of the framework by setting a time-out on query evaluation to reduce the computational overhead of axiom testing.

  Pr(φ | e) = Pr(e | φ) Pr(e) Pr(e | φ) Pr(e) + Pr(e | ¬φ) Pr(¬e).

Fig. 1 .

 1 Fig. 1. A schematic illustration of the heuristics used to capture negation under the open world assumption. D is a concept which is declared to be disjoint with C in the RDF repository.

  The semantics of subsumption axioms of the form SubClassOf(C D) (C D in description logic syntax) is C I ⊆ D I , which may also be written x ∈ C I ⇒ x ∈ D I . Therefore, content(C D) = {D(a) : C(a) in the RDF store}, because, if C(a) holds, C(a) ⇒ D(a) = ¬C(a) ∨ D(a) = ∨ D(a) = D(a). The support u C D of the axiom can thus be computed with the following SPARQL query: SELECT (count(DISTINCT ?x) AS ?u) WHERE {Q(C, ?x)}.

Fig. 2 .

 2 Fig. 2. A histogram showing the distribution of test time of systematically generated SubClassOf axioms (a), and a plot of the time taken for testing as a function of ARI.

Fig. 3 .

 3 Fig. 3. A histogram showing the distribution of the acceptance/rejection index of systematically generated SubClassOf axioms (a), and the relationship between the acceptance/rejection index and the probability-based score used in [2] (b).

  a few examples of axioms C D with their conterexamples (instances of the subclass that also belong to a class disjoint with the superclass, i.e., a such that C(a) and E(a) with E I ∩ D I = ∅: in this case, either C(a) is wrong or E(a) is). Axiom Counterexamples SubClassOf(dbo:LaunchPad dbo:Infrastructure) :USA SubClassOf(dbo:Brain dbo:AnatomicalStructure) :Brain [sic] SubClassOf(dbo:Train dbo:MeanOfTransportation) :New Jersey Transit rail operations, :ALWEG SubClassOf(dbo:ProgrammingLanguage dbo:Software) :Ajax SubClassOf(dbo:PoliticalParty dbo:Organisation) :Guelphs and Ghibellines, :-, 7

And one, namely SubClassOf(dbo:Person dbo:Agent), even has 76 counterexamples!

Results available at URL http://www.i3s.unice.fr/ ~tettaman/RDFMining/.

Up to 27 hours for axiom SubClassOf(dbo:Eukaryote dbo:Artist)!

The confirmations of this and several other axioms of the form SubclassOf(C skos:Concept) with a much lower ARI are obvious mistakes: no individual should be a skos:Concept. This seems now to have been fixed in the live version of DBpedia.

That is <http://dbpedia.org/resource/->. This IRI is dereferenced to the "hyphen-minus" resource.


Quentin Pradet

Laurence Danlos

Gaël De Chalendar

Adapting VerbNet to French using existing resources

VerbNet is an English lexical resource for verbs that has proven useful for English NLP due to its high coverage and coherent classification. Such a resource doesn't exist for other languages, despite some (mostly automatic and unsupervised) attempts. We show how to semi-automatically adapt VerbNet using existing resources designed for different purposes. This study focuses on French and uses two French resources: a semantic lexicon (Les Verbes Français) and a syntactic lexicon (Lexique-Grammaire).

Introduction

Natural Language Processing needs lexicons and a large amount of data to efficiently analyze opendomain text. Getting this amount of data is a problem in itself, and is known as the knowledge acquisition bottleneck in the word sense disambiguation literature [START_REF] Gale | Using bilingual materials to develop word sense disambiguation methods[END_REF]. While annotating more and more data will reduce the bottlenecks for some domains, encoding lexicons in a cost-effective way can lead to better improvements by explicitly stating similarities and differences between words. The two main issues faced by sense lexicon creators are sense granularity and sense distinction, both of which are addressed by Levin classes [START_REF] Levin | English verb classes and alternations: a preliminary investigation[END_REF]. In those classes, verbs are classified according to their semantics and to their syntactic alternations. VerbNet (Kipper-Schuler 2005) is an electronic lexicon which is inspired by Levin classes. It encodes thematic roles and semantic decomposition (Section 3). New constructions, new classes and new corrections have been added to VerbNet over the years. With VerbNet, one can use a syntactic alternation to map syntactic chunks of a sentence to thematic roles [START_REF] Swier | Exploiting a Verb Lexicon in Automatic Semantic Role Labelling[END_REF][START_REF] Pradet | Revisiting knowledge-based Semantic Role Labeling[END_REF]. This task, semantic role labeling, has grown steadily in importance: it helps information extraction (Surdeanu et al. 2003), question-answering (Shen andLapata 2007), event extraction [START_REF] Exner | Using semantic role labeling to extract events from Wikipedia[END_REF], plagiarism detection [START_REF] Osman | An improved plagiarism detection scheme based on semantic role labeling[END_REF], machine translation [START_REF] Bazrafshan | Semantic Roles for String to Tree Machine Translation[END_REF], or even stock prediction [START_REF] Xie | Semantic Frames to Predict Stock Price Movement[END_REF]. Thanks to its high coverage (more than four thousand distinct verbs) and useful verb separation, VerbNet is well-suited for semantic role labeling. However, a high-quality version of VerbNet is currently only available for the English language. Such a resource would be even more useful for less-resourced languages where role-labeled corpora are missing. VerbNet has cross-linguistic potential, as shown with the Portuguese language (Kipper-Schuler 2005, section 2.2.2). Adapting VerbNet to a new language would make it possible to reuse its structure, keep most semantic information, and produce a useful lexicon without years of manual work.

With the goal of developing a French version of Verb-Net (called Verb∋net) in mind, we first have translated top-level VerbNet members in French and used French linguistic resources that encode the syntactic and semantic behavior of verbs (Section 3) to keep only the right translations (Section 4.1). The second step in building Verb∋net, which is still underway, is to adapt VerbNet syntactic alternations for French, which gives rise to various problems that we will discuss in Section 4.2.

Related work

Translating Levin classes and more recently VerbNet is recognized as a useful task in the literature. First, automatic methods have led to improvements in Verb-Net itself: new classes have been incorporated (Korhonen and Briscoe 2004) and new verbs have been added from the LCS database [START_REF] Dorr | LCS verb database[END_REF] or using the Sketch Engine tool [START_REF] Bonial | Expanding VerbNet with Sketch Engine[END_REF]. In other languages, [START_REF] Merlo | A Multilingual Paradigm for Automatic Verb Classification[END_REF] have used crosslinguistic similarities to convert 20 Levin classes to Italian. Automatic acquisitions have also been led in Japanese [START_REF] Suzuki | Classifying Japanese Polysemous Verbs based on Fuzzy C-means Clustering[END_REF], German (Im Walde 2006), and Spanish [START_REF] Ferrer | Towards a Semantic Classification of Spanish Verbs Based on Subcategorisation Information[END_REF]). The only direct translations we are aware of are the Estonian Verb-Net [START_REF] Jentson | VerbNet Workbench[END_REF]) and the Brazilian Portuguese Verb-Net [START_REF] Scarton | Towards a cross-linguistic VerbNet-style lexicon for Brazilian Portuguese[END_REF], which uses the mappings between VerbNet and WordNet, and between WordNet.Br and WordNet. In French, [START_REF] Saint-Dizier | Constructing Verb Semantic Classes for French: Methods and Evaluation[END_REF] first produced a VerbNet-like resource. To the best of our knowledge, effort on this resource has stopped and the result is not available. Later work has focused on automatic acquisition of subcategorization frames which were clustered according to their syntactic and semantic similarity. [START_REF] Sun | Investigating the crosslinguistic potential of VerbNet: style classification[END_REF] used a large subcategorization frame lexicon [START_REF] Messiant | Acquisition de connaissances lexicales à partir de corpus: la sous-catégorisation verbale en français[END_REF] to cluster verbs according to two types of features: syntactic (subcategorization frames) and semantic (collocations and lexical preferences of verbs). Evaluation against a manually created gold standard led to an F-measure of 55.1%. [START_REF] Falk | Classifying French Verbs Using French and English Lexical Resources[END_REF] apply a different clustering algorithm, and use different features, improving the F-measure to 70% on a similar but easier dataset. While those resources highlight new ways to separate French verbs, the errors they contain are only one source of errors in applications: it is important to correct them if possible. While the results can still be improved, we believe that there is also a need for a manually validated French VerbNet. Our translation will be linked to the English VerbNet and the two linguistic resources we use, Les Verbes Français and the Lexique-Grammaire. It will also be open: we want to foster external contributions with our web-based tool and make the resource easy to use by using the same file formats than VerbNet.

Presentation of VerbNet and French Lexical resources

The top hierarchy in VerbNet is made up of 270 classes. Any class can be further divided into sub-classes organized in a tree structure. For each (sub-)class, this electronic lexicon gives: the list of verbs belonging to it, the relevant thematic roles which are possibly associated with selection restrictions, and the list of frames.

A frame includes an illustrating example, a syntactic formula explicating the relation between syntactic arguments and thematic roles, and a semantic formula based on predicates that denote relations between participants and events. Starting in the 70's two main lexical resources for French verbs, LVF and LG, were manually developed:

• LVF (Les Verbes Français, Dubois and Dubois-Charlier (1997)) includes around 25000 entries classified into 14 semantic classes with 54 syntactico-semantic subclasses and 248 subsubclasses.

• LG (Lexique-Grammaire, [START_REF] Gross | Méthodes en syntaxe[END_REF] and [START_REF] Boons | La structure des phrases simples en français : constructions intransitives[END_REF]) includes around 14000 entries classified into 67 "tables", each table grouping verbs with the same frames and possibly with similar semantics. Each column of the table encodes additional restrictions that will apply to some of the verbs of that table.

Both LVF's classes and LG's tables can be compared to VerbNet's classes. However, these (old) French resources record neither thematic roles nor semantic formulae1 . This is why we want to build a new French resource, Verb∋net. It will take advantage, on the one hand, of the existing French resources with a rich encoding of syntactic information, and on the other hand, of the semantic information in VerbNet built for English, a language relatively close to French.

Building Verb∋net

Our basic principle is that the top hierarchy in Verb∋net should be as close as possible to that in VerbNet with 270 classes. Nevertheless, some classes may disappear. This can be simply due to morphological reasons. Any VerbNet class made up only of

First step

The first step in building Verb∋net was to determine which French verbs belong to one of VerbNet's 270 classes. This was done in three stages:

1 , the results are precise and syntactically and semantically coherent. For example, the scribble-25.2 class contains 18 verbs in English; it is associated with LVF R3a.1 and LG 32A, which leads to a list of 16 French verbs: composer,couper,donner,exécuter,fabriquer,faire,forger,former,imprimer,lever,produire,reproduire,sculpter,tailler,tirer and tracer. All these verbs are valid for this class. This method results in a lexicon with 4058 verbs (2128 distinct verbs).

Second step

The second step in building Verb∋net has proven much more difficult than the first. For each of the 270 C f sub-classes, we determine whenever possible:

• the possible subclasses in order to assign the verbs found in the first step to one of these sub-classes (if possible)

• the frames that are valid for French with possible adjustments for thematic roles and selection restrictions.

This step has first required to develop an editing tool (Section 4.2.1) to help and maintain the lexicographers' work. Next, it has required to set up basic principles on French frames, when they differ from English ones (Section 4.2.2). Finally, a fine grained case-by-case study reveals some tough differences between French and English, which are illustrated in (Section 4.2.3).

Verb∋net editing tool

This step required us to develop a web-based tool which makes it possible to collaboratively edit Verb-Net classes and frames by manipulating their representation on the website. This online interface developed with Django (a Python web framework) hides a Post-greSQL database that stores all this information and tracks all changes to the data. The tool was first filled with VerbNet frames and verb translations found in the first step. It allows us to edit a frame and to suppress or add a (sub-)class or a frame. For example, all the frames involving a conative, dative or benefactive alternation can be systematically suppressed because these alternations don't exist in French.

With the help of this tool (illustrated in Figure 1), the work for the second step can be very easy. For example, the four sub-classes of image-creation-25 have direct equivalent classes in French, so the only thing to do is to provide French examples with the right preposition(s), e.g. with in 25.3 has to be replaced in French with de or avec.

Principles on frames

So far, we have found two general differences between the coding of French and English frames in Verb∋net and VerbNet respectively. The first one concerns "sub-frames", i.e. frames with missing complements such as NP V in 25.1 illustrated by Smith was inscribing which could be a sub-frame of e.g. NP V NP.destination (Smith was inscribing the rings). The coding of such sub-frames is dubious when based on introspection so it requires some corpus study. We don't know how this coding has been made in VerbNet and we don't have at our disposal enough French corpus data. So we decided for the time being to remove sub-frames from Verb∋net. For example in class remove-10.1, VerbNet encodes not only NP V NP PP.Source PP.Destination (Doug removed the smudges from the tabletop) but also NP V NP (Doug removed the smudges). Verb∋net only includes the first one; it is understood that the second one can be automatically inferred from the first one, without being (manually) validated 3 . The second one concerns the order of the complements. VerbNet sometimes encodes two frames which differ only by the order of the complements, e.g. in bring 11-3 the frames NP V NP PP.destination (Nora brought the book to the meeting) and NP V PP.destination NP (Nora brought to lunch the book). In French, the order of complements depends on a number of syntactic and semantic factors [START_REF] Thuilier | Contraintes préférentielles et ordre des mots en français[END_REF]), but it doesn't seem that it depends on a lexical factor, i.e. what is the lexical verb governing the complements. As a consequence, Verb∋net only records one frame in such cases, e.g. it only records NP V NP PP.destination (Nora a apporté le livre au meeting) with the direct object before the PP; it is understood that the other frame, NP V PP.destination NP (Nora a apporté au meeting le livre) can be automatically inferred from the first one.

Case by case work

In some cases, the second step in building Verb∋net is hard. There are two main reasons for that. First, there exist semantic differences which are taken into 3 However, this principle concerning sub-frames is not applied for verbs which accept a single double-locative complement "from here to there (a single complement PP.source PP.destination)" without accepting a single source complement (PP.source), while accepting a single destination complement (PP.destination) : Fred a transferré le vin de la cruche en pierre vers la cruche en terre cuite (Fred transferred the wine from the stone jar to the terra-cotta jar), *Fred a transferré le vin de la cruche en pierre (*Fred transferred the wine from the stone jar), Fred a transferré le vin vers la cruche en terre cuite (Fred transferred the wine to the terra-cotta jar.

account in VerbNet but not in LVF or in LG. For example, among the verbs of Sending and Carrying (Verb-Net super-class 11), the verbs in classes 11.3, 11.4 and 11.5 describe an accompanied motion (both the Agent and the Theme change location as in Pamela drove packages to NY ), while those in classes 11.1 and 11.2 describe an unaccompanied motion (only the Theme changes location as in Pamela sent packages to NY ). In the French resources, classes do exist for verbs with a change of location for a Theme caused by an Agent, but nothing is said about the Agent being or not being in motion. In the face of this difficulty, two solutions are possible: either make a study of French verbs of sending and carrying to distinguish accompanied and unaccompanied motions, or simply ignore this semantic difference. We opted for the second solution since this semantic difference does not appear to be relevant for a task such as semantic role labeling. 4 Ignoring this semantic difference leads us to adopt in Verb∋net a hierarchy for verbs of Sending and Carrying different from that in VerbNet: there is no equivalent in Verb∋net of class 11.4, the verbs belonging to this class being added to 11.1 or 11.2. Let us add that there is no French equivalent of class 11.3 made up of the two verbs bring and take with a deictically-specified direction (Levin 1993, page 135) since the French locative deictic ici and là don't work as here and there 5 . The second main source of difficulty comes from crucial differences between French and English. There exist translation problems between these two languages which are very well-known and documented, for example translation of motion verbs as illustrated in John swam across the river → Jean a traversé la rivière à la nage (lit. John crossed the river with the swim). We put aside those well-known cases here to discuss more subtle difficulties as illustrated with the verbs of change of possession. In VerbNet, there exist ten classes dedicated to these verbs. It seems that such a hierarchy cannot be adopted for French. Without going into all the details, let us underline the following points:

• The absence of dative and benefactive alternations in French means that the difference between Verb-Net's classes 13.1 and 13.2 should probably not be kept.

• The semantic difference between 13.1 and 13.3 (namely HAS-POSSESSION versus FUTURE-POSSESSION) is perhaps too subtle and could be ignored.

• The preposition with in the frame corresponding to Agent V Recipient with Theme used in 13.4-1 and 13.4-2 has to be replaced with en and/or de according to the verb (e.g. Luc livre Max en/*de 4 Moreover, it seems that, for some English verbs, the Agent can be moving or not as reflected by the difference between VerbNet's classes 11.4 and 11.4-1.

5 Je suis là (lit. I am there) can mean Je suis ici (lit I am here).

lait, Luc équipe Max en/de téléviseurs, Luc dote Max *en/de téléviseurs), which requires a reorganization into (sub-)classes.

All in all, it turns out that entering into the frame details has led us to revise the hierarchy of Verb∋net though we are trying to minimize the amount of revision in order to keep as much semantic information from VerbNet as possible.

Conclusion

We have presented a method for adapting the English syntactic and semantic resource VerbNet to a new language. This method combines the automation of structures transfer, automatic translation of the lexicon and linguistic expertise. We have applied this method to French and have reached a state where it is validated and the systematic work on each class is currently being realized. We are not able to give an evaluation of this resource since it is not yet completed. When it will be completed, we will make it freely available along with the web-based tool which makes it possible to collaboratively edit it. In this work, we acknowledge the structural differences existing between languages: the class structure of Verb∋net does not follow exactly VerbNet. We keep track of such changes so that the differences between the two resources are explicit and well-documented. Thus they will be available for interacting with other resources through mappings, making our resource useful for multilingual applications. This work is part of the ASFALDA6 project which goals include the creation of a French FrameNet and mappings between it and other semantic resources, like LVF, LG and Verb∋net.

Figure 1 :

 1 Figure 1: Web interface to analyze and edit Verb∋net. Every frame can be modified and the structure can be reorganized. The translations in purple belong to the intersection of C lvf and C lg ; the translations in red (resp. green) belong only to C lvf (resp. C lg ).

  . For a given VerbNet class C e , we manually assigned the LVF class(es) C lvf and the LG's table(s) C lg that fit its semantic definition (e.g.

	put-9.1 L3b 38LD or body_internal_motion-49 M1a 32CL or 32R3 or 32C),
	2. we used two bilingual dictionaries (SCI-FRAN-EURADIC and the French Wiktionary) which give the list L

trad of the French translations of the English verbs belonging to C e or a subclass of C e , 3. we computed the verbs of the French class C f which are a priori the simple verbs of L trad which belong to the intersection of C lvf and C lg (e.g. mettre, poser or installer in put-9.1). This step was performed quickly and gave accurate results: by keeping only verbs at the intersection of L trad , C lvf and C lg 2

The uses of thematic role and event were not much widespread in the 70's.verbs that are zero-related to nominals doesn't have a French equivalent, eg. class pit-10.7 with verbs such as bark and bone or week-end-56 with verbs such as week-end and december. On the other hand, class 10.8 with verbs formed by the prefix dé-plus a nominal (debark, debone) does have a French equivalent with verbs formed by the prefix dé-or é-(déveiner, équeuter). Given this basic principle, building Verb∋net goes in two steps.

When the intersection is empty, the non-empty list (C lvf or C lg ) was chosen.

https://sites.google.com/site/anrasfalda/

Acknowledgements

This work has been funded by the French national research agency (Agence Nationale de la Recherche, ANR) ASFALDA project under reference ANR-12-CORD-0023.


G Varank

A Demir

E Sekman

A Akkaya

M.S. Bilgili K Nathalie Yetilezsoy

Touze

Nathalie Touze-Foltz Irstea
email: nathalie.touze@irstea.fr

Discussion on paper entitled "Migration behaviour, of landfill leachate contaminants through

Keywords: composite liners, advective transfers, geomembranes, diffusion

come   L'archive ouverte pluridisciplinaire

One can be surprised that metals like copper and zinc cross the geomembrane of reactors R2 to R4 (see Figure 2). Indeed it is well know that cationic and anionic species do not diffuse through geomembranes [START_REF] Rowe | Diffusion of chloride and dichloromethane through an HDPE geomembrane HDPE geomembrane[END_REF]Rowe, 2011). This means that the geomembranes of reactors R2 to R4 exhibit hole (s). No mention of this important point in made through the paper, leading to the potential interpretation by the readers that metals can diffuse through HDPE geomembranes which is erroneous. Metals can only cross geomembrane by advection.

I could get confirmation by the authors during the review process of a "companion paper" (WM_18_868 accepted for publication in Waste Management) entitled "Estimation of transport parameters of phenolic compounds and inorganic contaminants through composite landfill liners using one-dimensional mass transport model", that the geomembranes from reactors R2 to R4 exhibit hole(s). The authors did not however clarify the number of holes drilled in each geomembrane specimen, but a reasonable minimum is one hole. The hole size given by the authors during the review process was equal to 10 -4 m 2 .

Assuming a single 10 -4 m² hole in the geomembrane, the authors should have calculated the radius of the corresponding wetted area. The wetted area is the area on which a flow will occur between the geomembrane and the underlying mineral liner, in a space called interface. This phenomenon has been evidenced experimentally by various authors [START_REF] Brown | Quantification of leakage rates through holes in landfill liners[END_REF][START_REF] Touze-Foltz | The influence of non-uniform transmissivity vis-à-vis hole location[END_REF][START_REF] Barroso | Laboratory investigation of flow rate through composite liners consisting of a geomembrane, a GCL and a soil liner[END_REF].

Had the authors performed the calculation of the radius of the wetted area assuming good contact conditions for the sake of consistency with the fact that they performed the experiment in the laboratory (flat surface of the soil, no wrinkles in the geomembrane), the result obtained would have been as follows using Equation 1 previously proposed by [START_REF] Giroud | Leakage through liners constructed with geomembranes. Part II -Composite liners[END_REF] assuming a hydraulic gradient equal to 1:

13 . 0 45 . 0 w 05 . 0 f k h a C R - π = (1)
Where: R is the radius of the wetted area (m), C f a contract factor depending on contact conditions, h w the hydraulic head (m), and k the soil liner hydraulic conductivity.

The value of R obtained assuming a hydraulic head to 0.3m, a hole diameter as given in the paper (10 -4 m²) and a soil liner hydraulic conductivity equal to 10 -8 m/s with the contact factor C f equal to 0.21 (good contact conditions as defined by [START_REF] Giroud | Leakage through liners constructed with geomembranes. Part II -Composite liners[END_REF]) is 1m. In case the hydraulic head considered is only 0.1 m then the radius of the wetted area is 0.65 m.

This means that with only a single hole in the geomembrane, the liquid flowing through this hole assuming good contact conditions has the ability to flow in the whole interface and to wet the whole area of the mineral liner, as the radius of the reactors is only 0.2m. Things are just as if there was no geomembrane at all in this particular case, which is not representative of field conditions. The authors should have clearly stated this point in the paper.

The title of the paper is thus in this case erroneous and inappropriate as the authors did not compare the behaviour of composite liners but of mineral liners as the geomembrane is of no use from a hydraulic point of view due to the presence of this hole(s): there were some edge effects in all reactors including a geomembrane specimen.

It is well know for years [START_REF] Giroud | Leakage through liners constructed with geomembranes. Part II -Composite liners[END_REF][START_REF] Bonaparte | LDCRS flow from double-lined landfills and surface impoundments[END_REF]Rowe, 1998[START_REF] Bonaparte | Assesment an recommendations for improving the performance of waste containment systems[END_REF] that composite liners perform significantly better than single mineral liners, this being again recently evidenced by Pr. Kerry Rowe 2011). The small scale of the tests performed by the authors leads to different results due to the presence of a hole(s) in the geomembrane and the small size of the reactors. It is important that the readers can understand this huge limitation of the study.

Conclusions obtained cannot at all be extended to field cases as the experiments were not performed in conditions representative of in situ conditions.

The only comparison that the authors can give here is for the mineral liners as everything is as if there was no geomembrane present in the system.

What the authors studied, despite the presence of a geomembrane is advective-diffusive transfers through mineral liners.

Very different results would have been obtained at a larger scale and/or without a hole in the geomembrane. Conclusions should have been restricted to the scale tests and no attempt made to give conclusions for in situ conditions as they can lead to the interpretation that composite liners do not perform significantly better than single mineral liners, which is totally erroneous and could lead to unfortunate regressions as far as the design of liner systems for landfills is concerned.

Touze-foltz, N. (2012): Discussion on paper entitled Migration behaviour, of landfill leachate contaminants through alternative composite liners by G. Varank, A. Demir, E. Sekman, A. Akkaya, K. Yetilezsoy, M.S. Bilgili. Science of the Total Environment.


Ratnesh Kumar

Guillaume Charpiat

Monique Thonnat

Multiple Object Tracking by Efficient Graph Partitioning

In this paper, we view multiple object tracking as a graph partitioning problem. Given any object detector, we build the graph of all detections and aim to partition it into trajectories. To quantify the similarity of any two detections, we consider local cues such as point tracks and speed, global cues such as appearance, as well as intermediate ones such as trajectory straightness. These different clues are dealt jointly to make the approach robust to detection mistakes (missing or extra detections). We thus define a Conditional Random Field and optimize it using an efficient combination of message passing and move-making algorithms. Our approach is fast on video batch sizes of hundreds of frames. Competitive and stable results on varied videos demonstrate the robustness and efficiency of our approach.

Introduction

The tracking of objects, persons or animals is required for high-level vision inference systems, from action recognition to animal behavior analysis. Other applications of tracking include video editing, e.g. inpainting, wherein a good tracking system can help in reducing the manual effort to annotate the parts of the video to keep or to remove.

In this paper, we address the problem of multiple person tracking in videos obtained from a single camera. We suppose that we are already given person detections in each frame, from any pre-trained detector. This detector is not assumed to be perfect, but may produce false negatives (persons missed) and false positives (extraneous detections). Our objective is to group detections into consistent trajectories, as well as to eliminate false negatives and false positives.

Tracking algorithms can be broadly divided into two categories: online and batch-based. Online methods infer the object state using the current frame and the previous ones; this can be achieved for instance with particle filtering [START_REF] Breitenstein | Robust tracking-by-detection using a detector confidence particle filter[END_REF]. On the opposite, batch-based tracking considers the entire temporal sequence at once, or at least a significant part of it (hundreds of frames). Such methods are also referred to as global tracking. Our approach belongs to the latter class, hence we focus on related work in the realm of batch-based tracking.

Global tracking should be in principle less prone to identity switches (confusion of several different persons) than online approaches, and provide better occlusion management as they have both present and future frames available to determine the state of objects. This extra information brought by the 2D+T volume has led to the development of many different approaches utilizing all kinds of color and motion clues, as well as many different optimization methods. We discuss below some of the recent notable ones [START_REF] Andriyenko | Discrete-continuous optimization for multi-target tracking[END_REF][START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF][START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF][START_REF] Brendel | Multiobject tracking as maximum weight independent set[END_REF][START_REF] Zhang | Global data association for multi-object tracking using network flows[END_REF][START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF][START_REF] Berclaz | Multiple Object Tracking using K-Shortest Paths Optimization[END_REF][START_REF] Pirsiavash | Globally-optimal greedy algorithms for tracking a variable number of objects[END_REF][START_REF] Russell | Efficient Second Order Multi-Target Tracking with Exclusion Constraints[END_REF][START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF].

[4] computes cliques on a graph of detection responses to find object trajectories. False negatives and occlusions are handled using hypothetical nodes by assuming linear motion of the object. [START_REF] Brendel | Multiobject tracking as maximum weight independent set[END_REF] presents another data association approach, based on maximum weight independent sets, to merge tracklets of length 2 to compute full trajectories. [START_REF] Zhang | Global data association for multi-object tracking using network flows[END_REF] uses a network flow based approach to obtain person trajectories and incorporates an explicit occlusion handling mechanism to provide information such as object i is occluded by object j. The work by [START_REF] Pirsiavash | Globally-optimal greedy algorithms for tracking a variable number of objects[END_REF] also uses a network flow based model similar to [START_REF] Zhang | Global data association for multi-object tracking using network flows[END_REF]. By greedily computing shortest path problems, they reach near-linear time complexity in computing the global minimum of successive sub-problems, which however doesn't guarantee a global optimum on the real global problem.

Most network flow models suffer from the disadvantage that possible occlusions or false negatives are not handled from the start, but in a post-processing step by introducing iteratively new nodes in the graph, which asks for re-iterating the optimization process until convergence. Importantly all network flow approaches and [START_REF] Brendel | Multiobject tracking as maximum weight independent set[END_REF] do not incorporate acceleration information for computing trajectories. Acceleration knowledge is vital for ensuring smooth velocity in trajectories, and at least three nodes (i.e. detections) located at different time frames are required to compute acceleration. Recently a proof-of-concept work by [START_REF] Collins | Multitarget data association with higher-order motion models[END_REF] have shown that a network flow model can only deal with pairwise factors and hence cannot incorporate a third (or higher order) factor. [START_REF] Butt | Multi-target tracking by Lagrangian relaxation to min-cost network flow[END_REF] extends a typical network flow model by adding higher order connections. However in doing so they have to resort to a relaxation (discrete to continuous) based optimization scheme, as the model can no longer be minimized by efficient network flow approaches. For time critical vision applications such as tracking, a discrete to continuous relaxation approach should be avoided, as these do not provide a usable solution at all instants during their run times, and stopping the optimizer to meet time requirements might return a non usable solution.

Works by [START_REF] Andriyenko | Discrete-continuous optimization for multi-target tracking[END_REF][START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] use a discrete-continuous optimization model to optimize detections and trajectories. They incorporate statistical data analysis to compute the parameters of the energy along with adding exclusion constraints at both trajectory and detection levels. However for this they use an already-performed tracking (from [START_REF] Pirsiavash | Globally-optimal greedy algorithms for tracking a variable number of objects[END_REF]) as input to their approach. Hence these works should rather be seen as trajectory-refinement process.

All of the above approaches including our proposed approach is categorized as tracking using detections in the literature. Instead of using detections, [START_REF] Berclaz | Multiple Object Tracking using K-Shortest Paths Optimization[END_REF] uses probabilistic occupancy maps obtained from a background subtraction process. Subsequently the scene space is discretized into grid cells, and targets are forced to move along the grid. A global optimum for this model is computed using K-Shortest Paths. This scene discretization is possible only for situations wherein the camera calibration parameters are known, and hence cannot be applied to moving camera scenarios. This approach is computationally fast but is prone to identity switches. Global appearance constraints are added by [START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] to provide robustness to identity switches.

Another relevant aspect of tracking algorithms is their computational cost in practice. Most approaches performing well [START_REF] Andriyenko | Discrete-continuous optimization for multi-target tracking[END_REF][START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF][START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF][START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] mention speeds of several seconds per frame. In contrast we will show an appreciable gain of speed (factor 10), with near real time performance in complicated videos. Also, [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF][START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] require a lot of memory and consequently cannot handle batches of many frames (typically 50), while we do not suffer from memory consumption and will consider blocks of several hundreds of frames.

With respect to the literature, our approach has the following advantages :

-A principled way of unifying natural constraints that arise in tracking.

-Thanks to an apt combination of optimizers (section 3.1), a novel triplet search for trajectory-curvature penalization (section 2.5), and graph reduction (section 3.2), the proposed approach is computationally efficient (in terms of both memory and time), and can operate on hundreds of frames of HD videos on a simple machine. -Last, but not least, the proposed tracker is self contained and unlike [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF][START_REF] Andriyenko | Discrete-continuous optimization for multi-target tracking[END_REF],

we do not require beforehand trajectories from an external tracker.

Following sections introduce our proposed model and the optimizers used. Subsequently section 4 elaborates on experimental results and processing times.

Model

A reliable tracking model should have the following criteria: (C 1 ) Uniqueness : An object label (identity) should never appear more than once inside any frame over the whole sequence (cf. section 2.2). (C 2 ) Smooth Trajectories : The trajectory of each object should be as smooth as possible in time. In particular, there should not be jumps in an object location in consecutive frames (cf. sections 2.2 & 2.5). (C 3 ) Robustness to Occlusions and False Negatives : The trajectories should not be lost or confused during occlusions or when several detections are missed (cf. sections 2.3 & 2.4). (C 4 ) No Ghost Objects : False Positives from the detector should be removed and not form output trajectories (cf. section 3.4).

The incorporation of these traits into our model will be discussed in the following sections.

Approach and Formalization

A person detector is used to obtain detection responses for all frames of a batch. We then build a graph G = (V, E) whose nodes correspond to detection responses. Our aim is to find an optimal partition of G such that each part corresponds to the trajectory of one person. The notations used in the paper are presented below: L : Number of possible labels (i.e. of graph parts). X : Set of all possible partitions ⊂ L |V | .

i : A node of the graph, i.e. a person detection.

x i : Label of the node i, to be found. w ij : Edge weight between nodes i and j (benefit for them to have same label).

For a set of L labels, each of the |V | nodes can then take any of L states. A labeling x = (x i ) i∈V ∈ X then defines a partition of V into subsets T l assigned to each class l ∈ L. The quality of such a labeling, to be maximized, is the sum of weighted edges connecting vertices with the same label:

argmax x∈X ij w ij δ xi=xj = argmin x∈X ij w ij δ xi =xj
In the following sections, we will define the quantities relevant to the problem of tracking, and show how to set the interaction terms w ij to express them.

Repulsive Constraints

Adhering to the criterion C 1 , it is imperative to have repulsive constraints in the model. The goal of these constraints is to prevent nodes in a same frame from being allocated the same label. To this end we set repulsive constraints by assigning huge negative weights w ij between all pairs of detections (i, j) from the same frames. We refer to this as intra-frame repulsive constraint. In regard to C 2 , the tracker should also prevent objects from jumping from one location in a frame to a complete different location in the next frame. Otherwisely said, two nodes far apart in consecutive frames should not have the same label. To this end, we define a maximum object speed (4m/s) and set highly negative weights w ij between detections (i, j) in consecutive frames if the speed required for such a displacement is higher. The speed between two such detections is converted from pixels/frame into m/s by multiplying them with the factor 2f / min(H i , H j ), where f is the frame rate and where H i is the height (in pixels) of the bounding box of detection i. Indeed, H i /2 is a simple yet practical and sufficient approximation of the number of pixels per meter, and it has the advantage of adapting automatically to the depth in the video. We denote these no-jump constraints as inter-frame constraints (cf. Middle Inset in Fig 1).

Temporal Neighborhoods and Point Tracks

Motion estimates for each detection provide vital information regarding its possible temporal neighbors. Without such estimates, temporal neighborhoods could become significantly big, which in turn would restrict the amount of frames processed in one batch due to a larger number of variables. Moreover, detections may be infrequent (false negatives) and may contain false positives, which prevents obtaining good motion estimates.

Owing to these reasons we do not rely only on the location of the detections, but instead we use point tracks, which provide motion estimates on a pixel t t+1 r t-1 r t i k t+δt j t-δt Fig. 1. Left: Point Tracks and detections. Middle: High repulsive exclusion constraints, shown for the central green bounding box in frame t, with red edges. Intraframe repulsive constraints prevent this detection from having the same label as any other detection in the same frame t, while inter-frame repulsive constraints prevent it from having the same label as detections in previous and next frames t -1, t + 1 that are too far. The maximum radius r is detection-dependent, in that it corresponds to the maximum physically-plausible displacement within a duration of one frame, and that speed estimation depends on object depth. Right: Computing the trajectory straightness for a triplet of detections j, i, k at the temporal scale δt (cf. sec 2.5).

(or sub-pixellic) level. The proportion F (i, j) of common point tracks between two nodes i and j, i.e. of points tracks which go through two given bounding boxes B i and B j from different times, defines a first similarity measure between these nodes. This similarity measure has the advantage of being robust to false detections (positive as negative) that occur between the two nodes. Also, in the case of partial occlusions, point tracks on the non-occluded part will still manage to follow the object and define a meaningful similarity, while overlapping detections make appearance-based affinities noisy in such partial occlusion cases.

Appearance Connections

In the previous sections, apart from defining repulsive constraints, we have added connections between the nodes which share common point tracks, as an incentive for them to choose the same label and consequently be part of the trajectory of the same object. But point tracks most often do not cover the full temporal span of the video and tracks may get lost or confused (aperture problem) after some time due to occlusion or pose changes. This calls for the need of long temporal range connections in the graph. To define such a similarity between detections from any frames, possibly far apart in time, we consider the appearance of objects. To cater this, we compute an appearance feature for each bounding box, and cluster these appearances into L groups using K-means. The appearance cluster of node i is denoted by A i . The appearance similarity between any nodes belonging to a same cluster is then defined as a constant weight β > 0, while the one between nodes from different cluster is 0, which will lead to the quantity β δ Ai=Aj in Equation [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF]. For appearance clustering we do not need to know the exact number of objects in the scene, as over-clustering is not an issue with our approach. In our experiments we set L to twice the maximum number of detections observed in a single frame of the current video batch.

The appearance feature for a detection is based on the histogram of colors inside the detection The distance between two appearances is computed by the L 2 norm between features.

Favoring Smooth Trajectories

When the trajectories of people with a similar appearance cross each other, and that, in plus, full occlusion or detection mistakes (false positives or negatives) occur at this crossing, then the tracking based on the previous quantities may fail and induce small jumps in location or identity switches. This can be mitigated by penalizing high curvature of the trajectories. To this end we define an energy term which favors smooth trajectories, involving three detections j, i, k from different frames regularly spaced in time (t -δt, t, t + δt), as shown in Right-most inset of Fig 1 . Given such detections, we compute a triplet factor R(i, j, k) expressing the regularity of the associated trajectory. It is based on the Laplacian of the centroids p i of the three bounding boxes:

∆ ijk = f H i δt p j + p k -2p i (1)
and is expressed as:

R(i, j, k) = 1 √ δt max(τ -∆ ijk , 0) (2)
Note that the Laplacian was normalized in order to be invariant to the video resolution and to the time interval, using the frame rate f , the frame interval δt and the bounding box height H i used as previously as a depth/resolution indicator. R denotes the benefit for the triplet j, i, k to belong to a same trajectory. The threshold τ indicates the maximum speed difference, or curvature, above which there is no gain. Note that τ = 1m/s 2 is video-invariant.

Considering all triplets in the graph is computationally prohibitive as there are |V | 3 possible triplets (|V | 2 symmetrical triplets). Furthermore searching only temporally successive triplets (δt = 1) would be sensitive to missed detections. Thus we compute R(i, j, k) on various temporal scales, with δt ∈ {1, 2, 3, 4, 5, 10}. As object trajectory is more predictable at shorter temporal ranges, we decrease the importance of the smoothness assumption for longer time spans with the factor 1/ √ δt. Unlike [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF], which requires the knowledge of trajectory proposals for curvature penalization, we model curvature penalization using an apt triplet search, thus making our model as unified and self contained as possible.

Optimization

Summing up all quantities defined in the previous section, we obtain the following similarity criterion to maximize over possible labellings x:

S(x) = α ij F (i, j) δ xi=xj + β ij δ Ai=Aj δ xi=xj +γ ijk R(i, j, k) δ T xi,xj ,x k -Ω (i,j)∈C δ xi=xj (3)
where δ true = 1 and δ false = 0, where

δ T xi,xj ,x k = 1 3 δ xi=xj + δ xi=x k + δ xj =x k is a good 2nd-order approximation of δ xi=xj =x k .
C denotes the set of all pairwise inter-frame or intra-frame constraints, and Ω > 0 is sufficiently high to be dissuasive. Maximizing S(x) in ( 3) is equivalent to minimizing E(x) = -S(x). Note that if one denotes by X the set of feasible labellings, i.e. satisfying all constraints, then solving argmin x∈L V E(x) with high Ω is equivalent to solving argmin x∈X E(x) with Ω = 0, and that E(x) in this latter formulation is submodular on X , but to our knowledge there is no optimizer dedicated to the minimization of submodular functions over arbitrary sets.

Optimizers

The criterion (3) is a non-submodular Conditional Random Field, and a host of available optimization techniques can be employed. This section aims at providing a concise overview on selecting optimizers for E(x).

Heuristic approaches such as Tabu Search (used by [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF]) or Simulated Annealing can be used to optimize [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF]. However these suffer from at least two notable problems to applied to a tracking model. Firstly, they do not provide any indication certifying the vicinity of a solution from optimal. Secondly, in time critical applications it is often desirable to use techniques which can provide a usable solution (i.e. a solution satisfying all constraints) whenever required. These heuristic approaches along with relaxation techniques (e.g. Lagrangian relaxation), Polyhedral methods, do not provide a usable solution at all time instants of their operation. In a recent work by [START_REF] Kappes | Towards Efficient and Exact MAP-Inference for Large Scale Discrete Computer Vision Problems via Combinatorial Optimization[END_REF], the authors show that combinatorial methods (such as Integer Linear Programming, Max Cut using Reweighted Perfect Matching) based on branch-and-bound and cutting plane techniques do not scale well with the problem size.

Therefore we employ a fast message passing variant: Tree Re-Weighted Message Passing (TRW-S) [START_REF] Kolmogorov | Convergent tree-reweighted message passing for energy minimization[END_REF]. TRW-S considers the full graph for labeling and provides good optima (along with the optimality bound). To make further improvements, we design local moves based on an Iterated Conditional Modes (ICM) that will satisfy the constraints and are likely to be useful.

ICM [START_REF] Besag | On the Statistical Analysis of Dirty Pictures Julian Besag[END_REF] is an iterative procedure, wherein an optimum labeling for a variable is chosen conditioned on all other variables. The process is repeated for all variables until convergence. Owing to this local nature of moves it is practically difficult for ICM to find a usable solution from scratch. However with a good initialization, ICM can find more meaningful solutions quickly. [START_REF] Andres | The Lazy Flipper : MAP Inference in[END_REF] proposed a variant of ICM: Lazy Flipper (LF). As opposed to ICM, a LF takes into account a large connected subset of variables up to a prescribed size. Upon convergence, the LF's labeling is guaranteed to be optimal within a Hamming distance equal to the subgraph size.

Inspired from LF, we search for flips of variables which reduce the energy, by considering a single variable or a subset of variables at a time. For a given subset size we repeat the above process until the energy cannot be reduced further. We also limit our search to only those subsets of variables which have a joint temporal distance of less than 20 frames, i.e. the maximum time scale in triplets. This structural information incorporation brings significant computational speed up on this part of the optimization process.

Notice that this flipper is different from the Block-ICM proposed by [START_REF] Collins | Multitarget data association with higher-order motion models[END_REF]. The authors in [START_REF] Collins | Multitarget data association with higher-order motion models[END_REF] sweep in a temporally forward manner, and check for flips locally in two frames. The flipper in our approach is more general as the nodes considered for flips have no time ordering restrictions. Furthermore as an ICM is susceptible to initialization ( [START_REF] Collins | Multitarget data association with higher-order motion models[END_REF]), we provide a good usable solution satisfying all constraints to our flipper, obtained from TRW-S.

We experimented with recently proposed optimizers based on dual decomposition [START_REF] Martins | An augmented Lagrangian approach to constrained MAP inference[END_REF] and linear programming relaxations [START_REF] Sontag | Efficiently searching for frustrated cycles in MAP inference[END_REF]. Both these techniques were excruciatingly slow on finding one usable solution.

Graph Reduction

Point tracks can be used to reduce the initial graph, and consequently speed up the optimization, by fusing nodes for which there is no tracking ambiguity. More The ratio of the fused graph size to the original size translates directly to the optimization speed, as we observe a reduction in the computational cost by the same ratio.

Parameter Setting

We have three constant factors in CRF, namely α, β and γ (cf. equation ( 3)). These have to be set considering the relative importance of each term, and this setting should be as invariant to videos as possible. We set Ω = 1000000, sufficiently high to enforce repulsive constraints. The rationale in setting these parameters is outlined below.

-The main contribution of point tracks is to obtain motion estimates which help in fusing the graph. On the fused graph, the nodes are either close to occlusion vicinity or false negatives. In both these situations, we need to look at appearance and trajectory curvature in time to decide about the labeling.

Hence we set more weight on triplets and appearance clusters. -Near occlusion vicinity, it is important to consider both motion difference and appearance. However trajectory curvature in short temporal scale should have higher weight than appearance due to following reasons: Firstly, trajectories are not supposed to change their path substantially in course of a few frames, and secondly, the appearance of persons can be similar either due to the presence of noise or persons having the same appearance. Hence β = 0.5 is set lower than γ = 50, with α = 0.01. A small perturbation of these values while respecting the relative order does not change the results.

Graph Cleaning

After solving the optimization on a batch, any temporal gap along a trajectory due to false negatives is filled by assuming linear motion between the closest detected bounding boxes on either side of the temporal axis. False positives from detections usually form short trajectories and with long temporal gaps, and these tracks are removed.

Streaming Trajectory Computation is performed using a sliding window approach, with an overlap of 15 frames from the previous batch.

Experimental Results and Evaluation

Comparative quantitative evaluation is challenging due to the lack of benchmark datasets, such as [START_REF] Butler | A naturalistic open source movie for optical flow evaluation[END_REF] for optical flow evaluation purpose. For our evaluation purposes, we use the metrics proposed by [START_REF] Zhang | Global data association for multi-object tracking using network flows[END_REF] 1 . Recently, [START_REF] Milan | Challenges of Ground Truth Evaluation of Multi-Target Tracking[END_REF] has thrown light on the ambiguities in evaluation due to dissimilarities in groundtruth annotations and evaluation codes used by different tracking approaches. Taking these ambiguities into account we provide other relevant information, e.g. type of detector, groundtruth and the code used for computing the metrics. Other widely adopted metrics are Multiple Object Tracking Accuracy/Precision (MOTA and MOTP) [START_REF] Bernardin | Evaluating Multiple Object Tracking Performance: The CLEAR MOT Metrics[END_REF]. MOTA takes into account the number of false positives, false negatives and IDS. MOTP quantifies the average distance between the groundtruth and the estimated target locations. MOTA is the preferred metric for us as we do not change the locations of input detections.

Results and Discussion

We consider videos from public datasets for evaluation. TRW-S is run for a fixed number of iterations (50), and the output is then optimized by the flipper. All our results are obtained with the same unique set of parameters.

PETS dataset: We use the S2L1 view. This video is challenging due to non linear motion, and persons of similar appearances occluding each other 2 . With global appearance features, we are able to keep the same ID for persons exiting and re-entering the scene (cf. Fig 5).

Method

Rec Prec FAF GT MT ML IDS MOTA(3D) MOTA(2D) Milan et al. [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] 96.9 94.1 0.36 [START_REF] Martins | An augmented Lagrangian approach to constrained MAP inference[END_REF] 1. Comparison with the recent proposed approaches on PETS S2L1 Video. The metrics on the first and last row are obtained using the same code, while middle ones are taken from the respective papers as their result files are unavailable.

We observe (Table 1) that our approach performs well and is on par or better with the best in the metrics. At the same time our approach is much faster (cf. section 4.3) and do not rely on external tracker as [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] or camera calibration as [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF][START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF][START_REF] Berclaz | Multiple Object Tracking using K-Shortest Paths Optimization[END_REF]. Also the model of [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] has 11 parameters and requires an explicit parameter estimation step for a video. [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF] uses Tabu Search on their model and hence guarantees of a stable output on multiple runs are minimal. Moreover [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF] do not cater to a proper video streaming, as merging trajectories from batches is based on solving a clique problem by considering multiple batches. Typically better cliques can be found if more batches are considered for merging, which in turn adds to the latency time.

Usefulness of Triplets: Triplets are necessary to maintain consistent identities in time. Indeed without using triplets, our results for MOTA (3D) would decrease to 84.4 and the identity switches would increase to 35.

Towncenter dataset: For the evaluation on HD videos with higher person density, we consider Towncenter video [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF]. The groundtruth, result and detection files can be obtained from the webpage of [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF]. We achieve competitive MOTA3 (cf. Table 3,Fig 7). [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF] uses a head detector along with motion estimates to make precise the location of body and head bounding boxes, hence achieves higher MOTP. Also [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF] requires camera calibration and a parameter estimation step which takes several hours.

Although [START_REF] Zhang | Online multi-person tracking by tracker hierarchy[END_REF] is a frame-by-frame method, we compare to this approach as the output files are available, and as it outperforms other previous approaches. While being competitive, we are 6 times faster on a single core implementation than the dual core implementation of [START_REF] Zhang | Online multi-person tracking by tracker hierarchy[END_REF].

Optimizer Scaling w.r.t. problem size: With this proposed combination of optimizers on a batch of 400 frames (with a high density of 15 persons/frame), we achieve competitive MOTA as shown in Table 2. The maximum memory consumed by our algorithm is under 6 GB, demonstrating the memory efficiency.

Stable output on multiple runs: We performed 5 trials on 50 frame batches for the first 1000 frames, and obtain a stable MOTA with a standard deviation of 0.7. In these trials we stop the optimizer to meet a requirement of 5-10 fps (by stopping the flipper). Such stability guarantees can not be provided by heuristic (or stochastic) optimization approaches e.g. Tabu Search. Usefulness of Point Tracks: Point tracks are an integral part of many vision systems. For our tracking system, point tracks help in reducing the graph and in-turn aid in swift convergence of our optimizer. On standard GPUs, optical flow based point-tracker such as [START_REF] Senst | Robust local optical flow for feature tracking[END_REF] and the KLT based point-tracker from [START_REF] Zach | Fast gain-adaptive KLT tracking on the GPU[END_REF] provide dense point tracks at 25 fps and 200 fps, respectively for high resolution videos. Moreover as ours is a batch based tracker, a simple dual-threaded implementation with a dedicated thread for computation of point tracks for the successive batch can remove any probable latency. In order to demonstrate the advantage of graph reduction, we consider the complete batch of 794 frames of the PETS S2L1 video, with or without the graph reduction step (cf. Table 4). We observe a 4x increase in efficiency with the graph reduction step. Similar comparative details on Towncenter video can be seen in Fig 6. 4. Usefulness of graph reduction: PETS S2L1 computation times (in seconds) for the cases when the graph reduction step is either chosen (Row 1 ) or discarded (Row 2 ). The column App+k-means, shows cumulative times for both appearance feature computation and clustering. The quantitative results for both rows are similar.

Processing Time

Computational times are one of the major factors in choosing a tracking algorithm. Comparing exact running times is challenging, as peers often do not provide them (nor the code) or quote only average times over a set of varied videos. Our optimizer takes 0.01 s/frame on average for 50 frames batches (8 persons/frame, PETS S2L1) on a single 2.4 GHz core, which is 100x faster than the best case of [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] in 2013. The run time of optimizer from [START_REF] Milan | Detection-and Trajectory-Level Exclusion in Multiple Object Tracking[END_REF] is 1-2 s/frame. The average run time for [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF] optimizer is 4.4 s/frame on four 2.4 GHz cores. On videos similar to PETS S2L1, [START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] takes 4s/frame on 3 GHz CPU. Table 5 shows computational efficiency of our approach w.r.t. recent approaches.

We perform optimization at a speed of 5-11 fps (on 50 frames batches the Towncenter with 10-17 persons/frame), which is 20x-40x faster than the 4-core implementation of [START_REF] Zamir | GMCP-Tracker: Global Multi-Object Tracking Using Generalized Minimum Clique Graphs[END_REF], and 6x-10x faster than the 2-core implementation of [START_REF] Zhang | Online multi-person tracking by tracker hierarchy[END_REF]. [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF] achieves a real time performance on Towncenter using parallel CPU implementation, however the tracking accuracy is significantly lower than us. Computational Times vs. MOTA TIME (Seconds) [7] [3] [4] Ours MOTA α-Expansion, TRW-S × [START_REF] Benfold | Stable multi-target tracking in real-time surveillance video[END_REF] Markov Monte-Carlo × × [START_REF] Shitrit | Tracking multiple people under global appearance constraints[END_REF] Integer Programming × [START_REF] Butt | Multi-target tracking by Lagrangian relaxation to min-cost network flow[END_REF] Lagrange Relaxation × Ours TRW-S, Flipper Table 6. State-of-the-art approaches and their incorporation of local and global clues. TOF stands for 3rd order factor (triplet). GAF denotes global appearance factor.

Conclusion

We proposed a novel tracking algorithm which exploits local and global cues in the most unified manner as compared to the state-of-the-art (cf. Table 6). Furthermore an apt combination of optimizers and suitable graph reduction lends robustness, stability and efficiency (5-10 fps on HD video of busy town street, on a single core CPU) to the model. The results obtained are competitive or better than the state-of-the-art at this speed. The proposed model has two degrees of freedom, and hence would be highly amenable to parameter learning using scene context and other relevant inputs. Also the algorithm is easy to implement and reproduce. Future prospects include tracking object parts and providing feedback to the point-trackers about incorrect tracks. Supplementary materials can be found at the project webpage.

Fig. 2 .

 2 Fig. 2. Sample appearance clusters for PETS09 S2L1: Each box encloses a few samples belonging to the same cluster. Notice that the clustering is robust to scale changes.

  Fig 2 shows a few clusters from a PETS09 [14] video.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Graph reduction by fusing nodes u,v and w,x.

  Fig 4 shows a simple illustration for the speed gain due to this graph reduction step (cf. Fig 4 caption for details).

4. 1

 1 Evaluation Metrics -Recall: % of correct detections w.r.t. total detections in groundtruth. -Precision: % of correct detections w.r.t. total detections in tracking. -FAF: False alarms per frame. GT : Number of trajectories in groundtruth. -MT: Number of trajectories successfully tracked for > 80% of their groundtruth time span. ML : Number of trajectories successfully tracked for < 20% of their groundtruth time span. -IDS: Number of times a tracked trajectory changes its matched id.

Fig. 5 .

 5 Fig. 5. Consistent tracks before and after occlusion: Frame numbers are shown on Top-Left of each image. The dotted points show the trajectories of bounding boxes in previous and successive frames. To reduce clutter in display, we show 3 trajectories and their few previous and future locations. Owing to the global appearance incorporation, ID 4 is kept intact for the person as he leaves and comes back in the view. This immaculate consistency in identities during crossing is obtained due to triplet factors.

Batch

  Size (Number of Frames) App+k-means TRW-S Flipper Total Memory 794

Fig. 7 .

 7 Fig. 7. Consistent people crossing over a span of 134 frames. The above images are cropped to show the crossing.

4

 4 Acknowledgements: This work has received funding from the European Community's FP7/2007-2013 -under grant agreement n o 248907-VANAHEIM.

4

  http://www-sop.inria.fr/stars/Documents/tracking/

Table 2 .

 2 Results on a crowded batch of 400 frames. There are 6000 detections in this batch starting at the 450th frame.

	Towncenter MOTA MOTP Detector Benfold et al. [11] 55.8 Method 84.4 [11] Zhang et al. [24] 66.4 75.2 [11] Ours 66.5 75.8 [11]	Towncenter Method MOTA MOTP Detector [11] 55.9 84.7 [11] [24] 64.9 76.4 [11] Ours 64.6 75.0 [11]
	.

Table 3 .

 3 Results for first 1000 frames (50 frame batches). Competitive accuracy is obtained at 6x faster speed.

  Processing time improvement using graph reduction (similar MOTA in both cases), for the first 15 batches. High processing times from batch 8 to 12 are due to high detection rate/frame. In the above cases we let the optimizer run until convergence.

				Processing Times for Optimizer Convergence
		300
	(seconds)	150 200 250		Without Graph Reduction
	Time	50 100									With Graph Reduction
		0
		1	2	3	4	5	6	7	8	9	10	11 12	13	14	15
			Batch Number (50 frames size) of Towncenter Video
	Fig. 6.

Table 5 .

 5 Approximate comparison of computation times for PETS S2L1,showing a significant positive gap between ours and state-of-the-art approaches in terms of speed vs. accuracy.

	Method	Optimization	TOF GAF
	[9]	K-Shortest Paths	×	×
	[4]	Tabu Search	×
	[3]

We use the code provided by[START_REF] Andriyenko | Discrete-continuous optimization for multi-target tracking[END_REF] to compute these metrics.

Detections from http://iris.usc.edu/people/yangbo/downloads.html

MOTA code from https://github.com/glisanti/CLEAR-MOT