Duy Dinh
email: duy.dinh@tudor.lu

Julio Cesar

Dos Reis

Cédric Pruski
email: cedric.pruski@tudor.lu

Marcos Da Silveira
email: marcos.dasilveira@tudor.lu

Chantal Reynaud-Delaître

Identifying change patterns of concept attributes in ontology evolution

Keywords: ontology evolution, ontology changes, change patterns, ontology versioning, biomedical ontologies

Ontology versions are periodically released to ensure their usefulness and reliability over time. This potentially impacts dependent artefacts such as mappings and annotations. To deal with this issue requires to finely characterize ontology entities' changes between ontology versions. This article proposes to identify change patterns at attribute values when an ontology evolves, to track textual statements describing concepts. We empirically evaluate our approach by using biomedical ontologies, for which new ontology versions are frequently released. Our achieved results suggest the feasibility of the proposed techniques.

Introduction

The dynamic aspect of knowledge in various domains requires that knowledge engineers apply changes to different ontology entities by adding, removing and revising them. This periodically leads to new ontology versions, which ensures that software applications use the most up-to-date representation of the domain knowledge. Ontology changes potentially impact mappings, annotations and queries which rely on these ontologies [START_REF] Groß | Semi-automatic adaptation of mappings between life science ontologies[END_REF][START_REF] Reis | Mapping adaptation actions for the automatic reconciliation of dynamic ontologies[END_REF].

Changes applied to generate new ontology versions are not always fully documented, which impedes the minimization and handling of their impact. To this end, we need methods to automatically identify ontology change operations (OCOs) in an explicit way, given two versions of the same ontology [START_REF] Hartung | Conto-diff -generation of complex evolution mappings for life science ontologies[END_REF]. Our previous studies have underlined the need of precisely characterizing the evolution of attributes describing concepts for maintaining mappings valid over time [START_REF] Reis | Understanding semantic mapping evolution by observing changes in biomedical ontologies[END_REF][START_REF] Reis | Characterizing semantic mappings adaptation via biomedical kos evolution: A case study investigating snomed ct and icd[END_REF].

When analyzing two consecutive versions of the same ontology, for instance, we found cases where textual statements which are values of attributes describing concepts are completly transferred from one concept to its siblings. This had affected the associated mappings since their definition relies on such textual information. For example, we observed this case with the concept "560.39" of the ICD-9-CM3 (ICD) biomedical ontology. Such concept contains three attributes and one of them has as value "Fecal impaction" (release 2009). Five mappings are defined with this concept as domain, and one of these mappings has a range called "Fecal impaction (disorder)", from SNOMED CT4 (SCT). After evolution (i.e., ICD release 2010), the attribute value "Fecal impaction" is no longer associated with the ICD concept and the previously mentioned mapping has been removed. Moreover, the concept "Fecal impaction" has been newly created in ICD (release 2010) and is reconnected to "Fecal impaction (disorder)" of SCT.

Literature has highlighted challenges related to ontology changes' management and has proposed change patterns to improve the ontology evolution process [START_REF] Noy | Ontology evolution: Not the same as schema evolution[END_REF][START_REF] Javed | Ontology change management and identification of change patterns[END_REF]. Although useful tools exist to identify the most traditional and frequent OCOs between two ontology versions [START_REF] Hartung | Conto-diff -generation of complex evolution mappings for life science ontologies[END_REF][START_REF] Noy | PROMPTDIFF: A Fixed-Point Algorithm for Comparing Ontology Versions[END_REF][START_REF] Kremen | Owldiff: A practical tool for comparison and merge of owl ontologies[END_REF], taking into account the nature of changes (e.g., atomic or complex) and the type of changes (e.g., addition, removal, splitting, merging of entities), these tools fail to automatically identify ontology modifications at a finer level of detail, required for supporting tasks dependent on ontology changes (e.g., mapping adaptation). This remains an open issue that requires further research.

To cope with this issue, our proposal underscores a nontrivial solution to recognize the diffusion of attribute values between concepts from one version of the ontology to another. We inquire whether techniques based on linguistic characteristics of textual values, combined with similarity measure, play a role in supporting automatic change patterns identification at the level of concept attributes. In summary, we make the following contributions:

• We formally define a set of ontology change patterns to express different behaviours of the evolution of attributes. • We introduce a novel linguistic-based approach implementing methods to automatically identify instances of the proposed change patterns by comparing successive ontology versions. We investigate different techniques to rank candidate attributes in the identification method. Our systematic study provides useful tools to precisely characterize ontology evolution. • We experimentally assess our approach by using real-world biomedical ontologies as a case study. We investigate the influence of different aspects in the performance of the proposed methods and our obtained results show innovative findings.

We structure the remainder of this article as follows: Section 2 discusses related work; Section 3 reports on our approach to change patterns; Section 4 describes the techniques for identifying change patterns; Section 5 presents the evaluation while Section 6 draws conclusions and future work.

Ontology change patterns

Noy & Klein [START_REF] Noy | Ontology evolution: Not the same as schema evolution[END_REF] have originally evoked the notion of change patterns (CPs) through a first simple classification of changes that may affect entities of on-tologies at evolution time. This classification, under basic and complex changes, paved the way for new approaches addressing ontology evolution. These approaches explore CPs to characterize complex changes and evolution scenarios, simplifying the management of ontologies to control the impact of the evolution and to ensure consistency in ontology [START_REF] Shaban-Nejad | Bio-medical ontologies maintenance and change management[END_REF].

Change patterns may allow to identify complex changes between versions of the same ontology. Groner et al. [START_REF] Gröner | Semantic Recognition of Ontology Refactoring[END_REF] addressed the problem of refactoring recognition using reasoning to semantically compare different versions of an OWL DL ontology. They proposed a high-level categorization of ontology changes like the refactoring patterns in software engineering, and applied it to OWL ontology. Some approaches define CPs at the level of RDF data model. Auer & Herre [START_REF] Auer | A Versioning and Evolution Framework for RDF Knowledge Bases[END_REF] proposed to support ontology evolution by using basic changes and aggregate them into more complex changes in RDF. Their approach consists in annotating the derived compound changes with meta-information and classifying them as ontology evolution patterns. Differently, Rieß et al. [START_REF] Rieß | EvoPat -Pattern-based Evolution and Refactoring of RDF Knowledge Bases[END_REF] proposed a pattern-based approach to evolving data and refactoring RDF knowledge bases. They defined basic evolution patterns that can be combined into compound ones. Their work formally specifies modular evolution patterns in a declarative manner, capturing simple evolution and refactoring operations on both data and schema levels.

Djedidi & Aufaure defined an ontology evolution methodology driven by a pattern-oriented modelling. They proposed the Change Management Patterns to guide the ontology evolution process by driving and controlling change application while maintaining consistency of the evolving ontology [START_REF] Djedidi | ONTO-EVOAL an Ontology Evolution Approach Guided by Pattern Modeling and Quality Evaluation[END_REF]. They considered four kinds of consistency concerning the OWL DL language: structural, logical, conceptual and domain modeling consistency [START_REF] Djedidi | ONTO-EVOAL an Ontology Evolution Approach Guided by Pattern Modeling and Quality Evaluation[END_REF]. The solution looks for invariances in change management that repeatedly appear when ontologies evolve. They proposed three types of patterns: change patterns classifying types of changes, inconsistency patterns classifying types of logical inconsistencies, and alternative patterns classifying types of inconsistency resolution alternatives.

Javed et al. suggested an approach to dealing with ontology evolution through a framework of compositional operators where they represent domain changes as CPs [START_REF] Javed | Ontology change management and identification of change patterns[END_REF]. They composed this framework with different levels of change operators, and empirically studied ontology evolution to investigate the relationships between generic and domain-specific changes to determine common CPs.

This literature review clearly highlights that existing approaches exploit CPs to deal with ontology evolution, and frequently their definition relies on ontology meta-models and languages (e.g., OWL or RDF). While existing change patterns seem sufficient to identify a set of inconsistencies, they remain inefficient for dealing with the impact of ontology evolution on dependent artifacts because their design fails to consider requirements for adapting mappings. We address CPs at the level of attribute values using linguistic-based features for identifying the diffusion of textual values between concepts over time. Complementary to other approaches, we refine meta-model patterns on model level to further support the ontology evolution impact, which influences the way we design the required CPs and the recognition methods.

Change patterns in attribute values

Preliminaries and problem definition

We adopt a traditional definition of ontology [START_REF] Gruber | Toward principles for the design of ontologies used for knowledge sharing?[END_REF]. We define a set of concepts of an ontology O x at time j as C(O x j ) = {c j 1 , c j 2 , ..., c j n }. Each concept c j i ∈ C, described by a set of attributes, has a unique identifier. We consider the set of attributes characterizing a concept c as A(c) = {a 1 , a 2 , ..., a n } (e.g., name, definition, synonym, etc.). For instance, an attribute a i , of type name, contains the value "cardio vascular diseases". We use a i .value to denote the value of an attribute a i . A relationship r ∈ R interconnects two concepts and has a specific type, e.g., "subsumption", "part-of ", etc.

The context of a concept c i in the ontology stands for a set of super concepts (sup(c i )), sub concepts (sub(c i )) and sibling concepts of c i (sib(c i )), as following:

CT (c i ) = sup(c i ) ∪ sub(c i ) ∪ sib(c i ) (1)
where

sup(c i ) = {c k |c k ∈ C(O x ), c i c k ∧ c i ̸ = c k } sub(c i ) = {c k |c k ∈ C(O x ), c k c i ∧ c i ̸ = c k } sib(c i ) = {c k |c k ∈ C(O x ), sup(c k ) = sup(c i ) ∧ c i / ∈ sup(c k )} (2)
where c i c k means that c i is related to c k through a subsumption relationship.

Figure 1 depicts the investigated scenario. Given an attribute a i from a concept c at time t 0 , we investigate a way to characterize how such attribute evolves by considering the context of the concept c 1 at time t 1 (i.e., in the new version of ontology O A ). Evolution of ontology entities usually remains restricted in an ontology space like the context [START_REF] Reis | Understanding semantic mapping evolution by observing changes in biomedical ontologies[END_REF]. We focus on a i .value to identify useful behaviours of evolution concerning the attributes and search for describing these behaviours as well-delineated change patterns. We face issues to determine which attribute at time t 1 represents the most adequate candidate in the recognition process to identify CPs occurrences. We apply syntactic analysis techniques to recognize textual values of attributes in different versions of the same ontology.

Proposed change patterns

Considering change patterns (CPs) as means to deal with ontology entity changes, we focus on changes related to concept's attribute values. Therefore, our defined change patterns relate to the linguistic characteristics of the attributes' value before and after their evolution. We denote O j 0 an ontology O 0 at time

t 0 and c 1 k ∈ C(O 1
x ) a concept belonging to this ontology at time t 1 . A change pattern between an attribute a 0 p of concept c 0 k ∈ C(O 0 x ) and another attribute a 1 q of concept c 1 cand ∈ CT (c 1 k ) occurs when changes in the value of the attribute a 0 p which shares some similarity with the attribute a 1 q are observed. In addition, we suppose that the attribute a 1 q is new or its value differs at time t 1 from the one at time t 0 . Therefore, any change pattern must satisfy the following constraint : We define the CP classes as "total copy" (TC), "total transfer" (TT), "partial copy" (PC), and "partial transfer" (PT). Table 1 illustrates the proposed change patterns and presents examples borrowed from the biomedical domain. We justify our definition of CPs through the specific needs to understand ontology changes to support mapping adaptation [START_REF] Reis | Characterizing semantic mappings adaptation via biomedical kos evolution: A case study investigating snomed ct and icd[END_REF]. We assume that correctly identifying the defined CPs will support addressing the adaptation of ontology mappings [START_REF] Reis | Mapping adaptation actions for the automatic reconciliation of dynamic ontologies[END_REF]. In what follows, we define W (a j i ) as a set of words/tokens from a i .value of an attribute a i , and w j ki as a single word/token from an attribute value at time t j . The sim(a 0 p , a 1 q ) function refers to the similarity between the value of the attributes a 0 p ∈ A(c 0 k ) and a 1 q ∈ A(c 1 cand ). The used similarity measure indicates the degree of relatedness between two given textual values. We use the γ param-eter to control the overlap in terms of words between two attribute values. Since the performance of the similarity measure is not the focus of this paper, we keep it generic in our definition of CPs so that we can choose it as a parameter in our experiments. We formalize each type of CP between a p and a q , if any, as follows:

a 0 q / ∈ A(c 0 cand ) ∨ a 0 q ̸ = a 1 q (3)
• Total copy. A total copy of content occurs between attribute a 0 p in concept c k and a 1 q in concept c cand if and only if a minimal degree γ of words in a p appears in a q and a minimal similarity value τ exists between them. Formally:

T C(a 0 p , a 1 q ) ⇔                a 0 p ∈ A(c 0 k ) c 1 k ∈ C(O 1 x ) a 1 p ∈ A(c 1 k ) sim(a 0 p , a 1 q ) ≥ τ ∥W (a 0 p ) ∩ W (a 1 q )∥/∥W (a 0 p )∥ ≥ γ (4)
• Total transfer. A total transfer of content occurs between attribute a 0 p in concept c k and a 1 q in concept c cand if and only if a minimal degree γ of words in a p appears in a q and a minimal similarity value τ exists between them while the original attribute a 0 p is removed from

c 1 k ∈ O 1
x . Note that in total copy (cf. Equation 4) a 1 p ∈ A(c 1 k ) while in total transfer (cf. Equation 5)

a 1 p / ∈ A(c 1 k
) which states the main difference between them. Formally:

T T (a 0 p , a 1 q ) ⇔          a 0 p ∈ A(c 0 k ) a 1 p / ∈ A(c 1 k ) sim(a 0 p , a 1 q ) ≥ τ ∥W (a 0 p ) ∩ W (a 1 q )∥/∥W (a 0 p )∥ ≥ γ (5)
• Partial copy. A partial copy of content occurs between attribute a 0 p in concept c k and a 1 q in concept c cand if and only if there exists a partial overlap between words constituting attributes a 0 p and a 1 q , while respecting a minimal similarity value τ and a degree of overlap between 0 and γ. Formally:

P C(a 0 p , a 1 q ) ⇔                        a 0 p ∈ A(c 0 k ) c 1 k ∈ C(O 1 x ) a 1 p ∈ A(c 1 k ) ∃w 0 ip ∈ W (a 0 p ), w 0 ip ∈ W (a 1 q ) ∃w 0 jp ∈ W (a 0 p ), w 0 jp / ∈ W (a 1 q ) sim(a 0 p , a 1 q ) ≥ τ 0 ≤ ∥W (a 0 p ) ∩ W (a 1 q )∥/∥W (a 0 p )∥ ≤ γ (6)
• Partial transfer. A partial transfer of content occurs between attribute a 0 p in concept c k and a 1 q in concept c cand if and only if there exists a partial overlap between words constituting attributes a 0 p and a 1 q while respecting a minimal similarity value τ , a degree of overlap between 0 and γ, and the original attribute a 0 p is removed from c 0 k ∈ O 0 x . Formally:

P T (a 0 p , a 1 q ) ⇔                    a 0 p ∈ A(c 0 k ) a 1 p / ∈ A(c 1 k ) ∃w p i ∈ W (a 0 p ), w p i ∈ W (a 1 q ) ∃w p j ∈ W (a 0 p ), w p j / ∈ W (a 1 q ) sim(a 0 p , a 1 q ) ≥ τ 0 ≤ ∥W (a 0 p ) ∩ W (a 1 q )∥/∥W (a 0 p )∥ ≤ γ (7)

Recognizing change patterns related to attributes

In our approach to recognize change pattern, we first determine a candidate attribute a 1 q in the context of a concept c 1 k (Section 4.1). This candidate refers to a changed attribute at time t 1 related to the attribute a 0 p in concept c 0 k that we used to identify occurences of CPs (Section 4.2).

Candidate attribute in the context

We designed Algorithm that explores textual attributes from a given concept at time t 0 . In particular, given an attribute a 0 p ∈ A(c 0 k ) from O 0 A , the algorithm courses the whole set of changed attributes of the context of c k at time t 1 by calculating the similarity to retrieve candidate attributes. It aims to find the most adequate attribute in the context of the given one from A(c k ), which we will use in Algorithm 2 to identify change patterns. We consider the types of comparable textual attributes as a parameter in our approach. For example, we can take only attributes of type "name" and "synonym" into consideration when comparing the attribute values (i.e., strings denoting concepts). Our methods exclude all types of attributes out of the comparable set of attributes defined beforehand. The function sim(a 0 i , a 1 j ) computes the similarity between two given attribute values. It returns a value ranging from 0 to 1. The higher the result is, the more similar these attributes are. We explore traditional string-based similarity metrics (the bi-gram measure), when calculating the similarity between attribute values in Algorithm 1. We selected this metric as the default similarity because it performs well on ontology matching [START_REF] Cheatham | String similarity metrics for ontology alignment[END_REF].

Algorithm 1 generates a list of candidate attributes which is denoted as S cand (a 0 p ) = {(a q1 , sim pq1 ), (a q2 , sim pq2 ), ..., (a qm , sim pqm )}, where a qi ∈ A(CT (c 1 k )) and sim pqi = sim(a 0 p , a 1 qi ). In fact, S cand (a 0 p ) stores the candidate attributes along with their similarity with the attribute a 0 p ∈ A(c 0 k ). This algorithm uses a ranking function to determine the best candidate attribute as a result.

We distinguish two ranking approaches to find the best candidate attribute: global and local. The candidate attribute may have a strong influence on the CP identification method which motivates us to investigate both rankings.

• Global ranking (GR). In this ranking the best a 1 q candidate attribute (found at time t 1 ) refers to the one that has the highest similarity with a Algorithm 1: Find candidate attribute in the context

Require: a 0 p ∈ A(c 0 k ); CT (c 1 k ) ⊂ C(O 1 A ) sim ← ∅; a 1 q ← ∅; S cand ← ∅; for all c 1 i ∈ CT (c 1 k ) do for all a 1 i ∈ A(c 1 i ) do if a 0 i / ∈ A(c 0 i ) ∨ a 0 i ̸ = a 1 i then sim ← sim(a 0 p , a 1 i ); S cand ← S cand ∪ {(a 1 i , c 1 i , sim)}; end if end for end for return S cand ← rank(S cand ).f irst;
given attribute a 0 p ∈ A(c 0 k ). We denote this as the global candidate because selection relies on the optimum similarity value considering the whole context. Formally:

candidate GR (S cand (a 0 p )) ← arg max a 1 q i ∈A(CT (c 1 k )) {sim(a 0 p , a 1 qi )} (8)
• Local ranking (LR). Unlike the GR, this approach assumes that the best candidate attribute locates in a part of the evolving ontology where we observe most changes in attributes. LR executes two steps: (1) it analyzes which elements of the context of concept c (i.e., sup(c), sub(c), sib(c)) has the highest number of changed attributes; (2) based on this result, it selects the most similar attribute. We refer to this as the local candidate because the selection relies on the optimum similarity value considering part of the context. We compute the distribution of the different relationship types from the context in the list of changed attributes S cand (a 0 p ) as follows:

dist(S cand (a 0 p ), Γ ) = ∑ f (a 1 qi ) ∥S cand (a 0 p )∥ (9)
• Γ is among the three types of relationships we consider in CT (c) interconnecting super, sub and sibling concepts. • f (a 1 qi ) stands for the function counting the frequency of a particular relationship type, defined as follows:

f (a 1 qi ) = { 1 if rel(a 1 qi ) = Γ 0 otherwise
where rel(a 1 qi ) refers to the type of relationship between concepts c 0 k denoted by attribute a 0 p and c 1 cand denoted by attribute a 1 qi . We define the local candidate as follows:

candidate LR (S cand (a 0 p )) ←        best dist(Γ ) ← arg max a 1 q i ∈A(CT (c 1 k )) dist(S cand (a 0 p ), Γ ) arg max a 1 q i ∈best dist(Γ )∧rel(a 1 q i )=Γ sim(a 0 p , a 1 qi ) (10)

Identification method

Algorithm 2 describes the designed procedure to identify CPs. The best candidate c 1 cand refers to the concept denoted by attribute a 1 q , retrieved with algorithm 1. For each candidate a 1 q , the algorithm checks whether its similarity value with attribute a 0 p is greater or equal to a threshold τ , and the conditions for applying each type of change pattern on the couple of attributes a 0 p and a 1 q . To this end, it calculates the number of common words between a 0 p and a 1 q by removing stop words from the original attributes. The algorithm also explores whether attributes a 0 p ∈ A(c 0 k ) and a 1 q ∈ A(c 1 cand ) remain at time t 1 (i.e., it is not removed). According to the definitions, the algorithm assigns the adequate CP. Given two versions of the same ontology, we can apply Algorithm 2 to all concepts placed in ontology regions affected by traditional change operations.

Algorithm 2: Change pattern identification

Require:

a 0 p ∈ A(c 0 k ); c 0 k ∈ C(O 0 A ); CT (c 1 k ) ⊂ C(O 1 A ) CP ← ∅; sim ← 0; nbEqW ords ← 0 a 1 q ; sim ← Algorithm 1(a 0 p ; CT (c 1 k )); if a 1 q ̸ = ∅ then if 0 < sim > τ then nbEqW ords ← ∥W (a 0 p ) ∩ W (a 1 q )∥ if nbEqW ords/∥W (a 0 p )∥ ≤ γ ∧ nbEqW ords > 0 ∧ nbEqW ords < ∥W (a 0 p )∥ then if a 1 p ∈ A(c 1 k ) then CP ← P C(a 0 p , a 1 q ); else CP ← P T (a 0 p , a 1 q ); end if else if nbEqW ords/∥W (a 0 p )∥ ≥ γ then if a 1 p ∈ A(c 1 k ) then CP ← T C(a 0 p , a 1 q ); else CP ← T T (a 0 p , a 1 q ); end if end if end if end if end if return (a 0 p , a 1 q , CP );

Experimental evaluation

We present the used materials followed by the experimental procedure conducted to achieve the following objectives:

• We evaluate the effectiveness of the proposed methods for identifying change patterns based on exploiting lexical features of attributes. • We assess the proposed ranking functions by comparing their performance.

Materials

In the conducted experiments we used various versions of three large biomedical ontologies: SNOMED-CT (SCT), MeSH and ICD-9-CM (ICD9). Table 2 presents statistics regarding the number of concepts, attributes and the number of direct subsumption relationships between concepts, since this study focused on exploiting the hierarchical structure of ontologies. SCT contains a much higher number of concepts than MeSH and ICD9. Table 2 also depicts the evolution of concepts and attributes for the three studied biomedical ontologies in a combined way over the last years. This dynamic evolution motivates us to use biomedical ontologies as a case study in this research. Reference change patterns. To evaluate the effectiveness of our approach, we defined a set of reference change patterns as our standards. We needed to build our own set of reference since no available gold standard exists for the investigated context. To this end, we conducted the following steps:

• We combined the ontologies and we randomly selected a set of 1.000 couples of attributes. We defined the size of our sample in accordance with the involved experts taking into account their availability and scientific consistencies for our experiments. One attribute of a couple comes from a concept at time t j and the other one in the same couple comes from a concept in the context of the former concept in the same ontology at time t j+1 . We chose these couples based on the similarity between attribute values, excluding attributes with very low similarity and unchanged attributes at time t j+1 . • We invited three ontology engineering experts to evaluate all selected couples of attributes to assign their answer regarding CPs. For this purpose, we supported them with a software tool suited to present additional information regarding each attribute. This tool presents the couple of attributes along with concepts in the context, the attributes denoting concepts as well as the changes affecting them, etc. We gave instructions on the purpose of the different patterns, and recorded the answers for each evaluator separately.

• The evaluators performed one round of evaluation, and we merged the agreement answers. The domain experts collaborated and re-evaluated a second round only with the disagreement part of couples. We merged the final agreement couples with the respective correct answers according to the evaluators.

We achieved an average agreement rate of 86%. Finally, we retained 675 pairs of attributes that had the consent from all evaluators for our experiments.

Experimental procedure

For evaluating the effectiveness of our CP identification algorithm, we computed the standard metrics of Precision, Recall and F-measure based on the reference CPs as input. Specifically, we computed the precision as the number of CPs correctly identified by the algorithm over the total number of identified CPs. Recall was computed as the number of correctly identified CPs over the total number of relevant/expected CPs in the set of reference. F-measure was computed as the harmonic mean of precision and recall. We investigated the influence of the similarity threshold in the CP identification algorithm. For this purpose, we analyzed the CP identification performance by varying the similarity threshold from 0 to 1 to observe the performance of our algorithm, and we set τ = γ. Additionally, we examined the quality of the outcomes by comparing both GR and LR ranking functions proposed.

Results

Figure 2 presents the effectiveness of the CP identification algorithm in terms of precision, recall and F-measure by varying the similarity thresholds (denoted as τ ). We achieved these results using the global ranking in Algorithm 1.

The performance of this algorithm varies according to the value of τ . Overall, the F-measure is greater than 0.60 for all types of CP. We observe that the similarity threshold plays a relevant role in CP identification because its performance dramatically changes when the threshold is set very low (e.g., τ < 0.5). Our CP identification algorithm reaches the best performance with thresholds ranging from 0.7 to 0.9, which points out the necessity of having a minimal similarity between attributes to boost the identification results.

By observing the results for each type of CP, we found that the identification of partial copy CP reaches the highest F-measure of 0.68 (precision=0.61, recall=0.77) at τ = 0.75. This remains similar to the case of total copy CP, where the highest F-measure is 0.66 (precision=0.66, recall=0.66) at τ = 0.85. Moreover, the recall for total copy CP tends to be higher than the precision for τ < 0.85, but we observed the contrary phenomenon for partial copy CP. We potentially explain this by the fact that for correctly identifying total copy CPs require higher similarity between attributes, while for partial copy, the higher the similarity value, the lower the number of partial copy CPs correctly identified.

Regarding total transfer CP, Algorithm 2 reaches the best F-measure at 0.78 (precision=0.90, recall=0.69) for τ = 0.80. The algorithm performs better on identifying total transfer than on partial transfer. Partial transfer CP seems a To analyze the results comparing the proposed rankings, we retain the maximum value of the similarity threshold, i.e., τ = 0.85, that optimizes the performance of the GR (denoted as baseline M AX ). Tables 3 and4 present the achieved results for transfer and copy CPs by running our method using the local ranking function. We chose the similarity thresholds among the values in the set {0.2, 0.4, 0.6, 0.75, 0.8} to analyze the performance, and compare the difference in terms of precision, recall and F-measure between LR and GR.

Results in Table 3 reveal that the LR improves the performance in terms of recall for total transfer with a maximum improvement rate of +4.69%, while the performance dramatically decreases for precision and F-measure. For partial transfer CP, the LR method outperforms the baseline for values of τ in the interval [0.6, 0.75]. The performance of the latter is zero for either precision, recall and F-measure, probably because the similarity threshold was very high (τ = 0.85). This suggests that CP identification for either partial or total transfer must use a flexible or approximate string matching with an appropriate similarity threshold that should not be very low (e.g., < 0.5) nor very high (e.g., > 0.8).

Regarding the performance of the local ranking for identifying copy CPs (cf. Table 4), we observe that for total copy CP, the precision is proportional to the similarity threshold while the recall is not. For partial copy CP, the local ranking shows a significant improvement rate of +29.41 % for precision, +378% for recall and +204% for F-measure by using τ = 0.75.

Discussion

We found that the suggested types of CPs at the level of attributes can be observed in real cases of ontology evolution. These CPs refine the traditional ones at a finer level of granularity to characterize ontology evolution. Overall results pointed out the effectiveness of the proposed method underlaid by similarity measure and intersection of words between attribute values to recognize CPs between ontology versions. We demonstrated that the similarity threshold plays an important role in the quality of the outcomes. We explain this by the fact that our method selects the candidate attribute based on the similarity that is proportional to the degree of relatedness between the analyzed attributes.

When comparing the overall performance of CP identification under the GR and LR methods, our findings demonstrated that considering both the types of context relationships as well as their distribution affect the identification results. The LR method performs better, in particular for partial copy with a significant improvement compared to the GR. However, for total copy and transfer the performance under LR remains low, probably because the nature of these CPs requires a relatively high similarity threshold. We conclude that CPs of partial type should base on the local ranking for selecting the candidate attribute in CP recognition, while for CPs of total type we recommend using the global ranking.

Our scholarly obtained findings have revealed evidences of the quality of the results that were yielded by the proposed method, relying on standard evaluation metrics. In addition, we conducted experiments using real biomedical ontologies which strengthens our results.

Conclusion

Ontology evolution requires further means to describe specific changes at different entities. This plays a relevant role in controlling the impact of changes on dependent artefacts. In this article, we defined change patterns of concept attributes to characterize the evolution of their textual values. We designed a novel method to recognize the change patterns between ontology versions and empirically evaluated our proposition by observing the evolution of biomedical ontologies. We studied the influence of different aspects in the change pattern identification on the quality of the outcomes. The achieved results showed evidences of the performance of the proposed method.

In addition to existing and traditional ontology change operations, our contribution in this article originally allows to characterize ontology evolution by means of change patterns at attribute level. This stands for fine-grained changes that may facilitate tasks related to the impact of ontology evolution such as mapping and annotation maintenance. As future work, we aim to study techniques to recognize the way attribute values become more or less semantically specific in ontology evolution, and to investigate to which extent the different types of change patterns may influence the way ontology mappings evolve.

Fig. 1 .

 1 Fig. 1. Problem definition

Fig. 2 .

 2 Fig. 2. Effectiveness of the CP identification method (using GR ranking) in terms of precision, recall and f-measure for the different types of change patterns.

Table 1 .

 1 Description and examples of the proposed change patterns from attribute a 0

	attribute	t0	CP t1	CP type	t0	example t1
	ap	ABC ABC	total copy (TC)	'portal encephalopathy' systemic	'portal encephalopathy' systemic
	aq	ABC ABC(D)		∅		'portal	systemic
							encephalopathy'
	ap aq	ABC ABC ABC ABC(D)	total transfer (TT)	'fecal impaction' ∅	∅ 'fecal impaction'
	ap	ABC ABC	partial copy (PC)	'familial hyperchy-lomicronemia'	'familial hyperchy-lomicronemia'
	aq	ABC AB(D)		∅		'familial chylomi-
							cronemia'
	ap aq	ABC ABC ABC AB(D)	partial transfer (PT)	'eye swelling' ∅		∅ 'head swelling'

p to attribute a 1 q . The symbol ∅ means that the corresponding attribute does not exist.

Table 2 .

 2 Evolution of biomedical ontologies. The numbers between parentheses represent the change rate between two releases of the same ontology.

	ontology	year	#concepts	#attributes	#subsumptions
	ICD-9-CM	2009 2011	12734 13059 (+2.55%) 34963 (+2.64%) 11962 (+2.95 %) 34065 11619
	SNOMED-CT	2010 2012	386965 395346 (+2.12%) 1570504 (+2.50%) 539245 (+2.83%) 1531288 523958
	MeSH	2012 2013	50367 50971 (+1.18%) 264783 (+1.97%) 59844 (+1.09%) 259565 59191

Table 3 .

 3 Performance of the identification method by using the LR ranking for transfer CP. Numbers in parentheses correspond to the difference between P, R, F obtained by LR comparatively to τ of the baselineMAX of GR.

	τ P P P P P P P CP	P	R	total	Transfer of attributes F P R partial	F
		(∆P )	(∆R)	(∆F )	(∆P )	(∆R)	(∆F )
	baselineMAX 0.89	0.64	0.75	0.00	0.00	0.00
	0.2	0.50 (-43.82%)	0.67 (+4.69%) (-24.00%) 0.57	0.00 (0.00%)	0.00 (0.00%)	0.00 (0.00%)
	0.4	0.50 (-43.82%)	0.67 (+4.69%) (-24.00%) 0.57	0.00 (0.00%)	0.00 (0.00%)	0.00 (0.00%)
	0.6	0.53 (-40.45%)	0.67 (+4.69%) (-21.33%) 0.59	0.33 (INF)	1.00 (INF)	0.50 (INF)
	0.75	0.79 (-11.24%)	0.67 (+4.69%) (-4.00%) 0.72	0.05 (INF)	1.00 (INF)	0.10 (INF)
	0.8	0.79 (-11.24%)	0.67 (+4.69%) (-4.00%) 0.72	0.00 (0.00%)	0.00 (0.00%)	0.00 (0.00%)

Table 4 .

 4 Performance of the identification method by using the LR ranking for copy CP. Numbers between parentheses correspond to the difference between P, R, F obtained by LR comparatively to τ of the baselineMAX of GR.

	τ P P P P P P P CP	P	R	total	F	Copy of attributes P	R	partial	F
		(∆P )	(∆R)	(∆F )	(∆P )	(∆R)	(∆F )
	baselineMAX 0.66	0.66	0.66	0.51	0.14	0.22
	0.2	0.18 (-72.73%)	0.65 (-1.52%)	0.28 (-57.58%)	0.00 (-100.00%)	0.00 (-100.00%)	0.00 (-100.00%)
	0.4	0.18 (-72.73%)	0.63 (-4.55%)	0.28 (-57.58%)	0.63 (+23.53%) (-78.57%) 0.03	0.06 (-72.73%)
	0.6	0.21 (-68.18%)	0.58 (-12.12%)	0.31 (-53.03%)	0.56 (+9.80%)	0.20 (+42.86%) (+36.36%) 0.30
	0.75	0.53 (-19.70%)	0.56 (-15.15%)	0.55 (-16.67%)	0.66 (+29.41%) (+378%) 0.67	0.67 (+204%)
	0.8	0.56 (-15.15%)	0.41 (-37.88%)	0.47 (-28.79%)	0.61 (+19.61%) (+100%) 0.28	0.39 (+77.27%)

www.cdc.gov/nchs/icd/icd9cm.htm

www.ihtsdo.org/snomed-ct

Acknowledgment

The National Research Fund (FNR) of Luxembourg entirely supports this work under the DynaMO research project (Grant #C10/IS/786147).


Matthew B Blaschko

Arpit Mittal

Esa Rahtu

An O(n log n) Cutting Plane Algorithm for Structured Output Ranking

In this work, we consider ranking as a training strategy for structured output prediction. Recent work has begun to explore structured output prediction in the ranking setting, but has mostly focused on the special case of bipartite preference graphs. The bipartite special case is computationally efficient as there exists a linear time cutting plane training strategy for hinge loss bounded regularized risk, but it is unclear how to feasibly extend the approach to complete preference graphs. We develop here a highly parallelizable O(n log n) algorithm for cutting plane training with complete preference graphs that is scalable to millions of samples on a single core. We explore theoretically and empirically the relationship between slack rescaling and margin rescaling variants of the hinge loss bound to structured losses, showing that the slack rescaling variant has better stability properties and empirical performance with no additional computational cost per cutting plane iteration. We further show generalization bounds based on uniform convergence. Finally, we demonstrate the effectiveness of the proposed family of approaches on the problem of object detection in computer vision.

Introduction

Learning to rank is a core task in machine learning and information retrieval [START_REF] Manning | Introduction to Information Retrieval[END_REF]. We consider here a generalization to structured output prediction of the pairwise ranking SVM introduced in [START_REF] Herbrich | Large margin rank boundaries for ordinal regression[END_REF]. Similar extensions of ranking to the structured output setting [START_REF] Bakır | Predicting Structured Data[END_REF] have recently been explored in [START_REF] Blaschko | Simultaneous object detection and ranking with weak supervision[END_REF][START_REF] Rahtu | Learning a category independent object detection cascade[END_REF][START_REF] Zhang | Proposal generation for object detection using cascaded ranking SVMs[END_REF]. In these works, pairwise constraints were introduced between elements in a structured output space, enforcing a margin between a lower ranked item and a higher ranked item proportional to the difference in their structured output losses. These works consider only bipartite preference graphs. Although efficient algorithms exist for cutting plane training in the bipartite special case, no feasible algorithm has previously been proposed for extending this approach to fully connected preference graphs for arbitrary loss functions.

Our work makes feasible structured output ranking with a complete preference graph for arbitrary loss functions. Joachims previously proposed an algorithm for ordinal regression with 0-1 loss and R possible ranks in O(nR) time for n samples [START_REF] Joachims | Training linear SVMs in linear time[END_REF]. This effectively enables a complete preference graph in this special setting. In practice, however, for structured output prediction with a sufficiently rich output space, the loss values may not be discrete, and may grow linearly with the number of samples. In this case, R is O(n). Mittal et al. have extended Joachims' O(nR) result to the structured output ranking setting in the case that there are a discrete set of loss values [START_REF] Mittal | Taxonomic multi-class prediction and person layout using efficient structured ranking[END_REF]. A direct extension of these approaches to the structured output setting with a fully connected preference graph and arbitrary loss functions results in a O(n 2 ) cutting plane iteration. One of the key contributions of our work is to show that this can be improved to O(n log n) time. This enables us to train an objective with 5 × 10 7 samples on standard hardware (Section 5). Furthermore, straightforward parallelization schemes enable e.g. O(n) computation time on O(log n) processors (Section 3.1). These results hold not only for the structured output prediction setting, but can be used to improve the computational efficiency of related ranking SVM approaches, e.g. [START_REF] Joachims | Training linear SVMs in linear time[END_REF].

Analogous to the structured output SVM [START_REF] Taskar | Max-margin Markov networks[END_REF][START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF], we formulate structured output ranking in slack rescaling and margin rescaling variants. We show uniform convergence bounds for our ranking objective in a unified setting for both variants. Interestingly, the bounds for slack rescaling are dependent on the range of the loss values, while those for margin rescaling are not. Further details are given in Section 4. Structured output ranking is a natural strategy for cascade learning, in which an inexpensive feature function, φ, is used to filter a set of possible outputs y. We show empirical results in the cascade setting (Section 5) supporting the efficiency, accuracy, and generalization of the proposed solution to structured output prediction.

Structured Output Ranking

The setting considered here is to learn a compatibility function g : X × Y → R that maps an input-output tuple to a real value indicating the prediction of how suitable the input is to a given output. We assume that there is an underlying ground truth prediction for a given input so that every x i ∈ X in a training set is associated with a y * i corresponding to the optimal prediction for that input. Additionally, we assume that a loss function ∆ : Y × Y → R is provided that measures the similarity of a hypothesized output to the optimal prediction ∆(y * i , y) ≥ 0. A training set will consist of input-ground truth-output tuples, where the input-ground truth pairs may be repeated, and the outputs are sampled over the output space: S = {(x i , y * i , y i )} 1≤i≤n and (x i , y * i ) may equal (x j , y * j ) for j = i (cf. Section 5). We will use the notation ∆ i to denote ∆(y * i , y i ). In structured output ranking, we minimize with respect to a compatibility function, g, a risk of the form [START_REF] Agarwal | Generalization bounds for ranking algorithms via algorithmic stability[END_REF]

R(g) = E ((Xi,Yi),(Xj ,Yj )) |∆ Yj -∆ Yi | • 1((∆ Yj -∆ Yi )(g(X i , Y i ) -g(X j , Y j )) < 0) + 1 2 1(g(X i , Y i ) = g(X j , Y j ) , (1)
where 1(•) evaluates to 1 if the argument is true and 0 otherwise, and the term penalizing equality is multiplied by 1 2 in order to avoid double counting the penalty over the expectation. Here ∆ Yi is the structured output loss associated with an output, Y i . In contrast to other notions of risk, we take the expectation not with respect to a single sample, but with respect to pairs indexed by the structured output. Given two possible outputs sampled from some prior, the risk determines whether the samples are properly ordered according to the loss associated with predicting that output, and if not pays a penalty proportional to the difference in the losses. This risk penalizes pairs for which sample i has lower loss than sample j and also lower ranking score, i.e. we would like elements with low loss to be ranked higher than elements with high loss.

Two piecewise linear convex upper bounds are commonly used in structured output prediction: a margin rescaled hinge loss, and a slack rescaled hinge loss. The structured output ranking objectives corresponding to regularized risk minimization with these choices are min w∈H,ξ∈R

λΩ(w) + ξ (2) s.t.
(i,j)∈E

ν ij margin rescaling ( w, φ(x i , y i ) -w, φ(x j , y j ) + ∆ i -∆ j ) ≥ -ξ (3)
or

(i,j)∈E ν ij ( w, φ(x i , y i ) -φ(x j , y j ) -1) (∆ j -∆ i ) slack rescaling ≥ -ξ (4)
ξ ≥ 0 ∀ν ∈ {0, 1} |E| (5)
where E is the edge set associated with a preference graph G, 4 and Ω is a regularizer monotonically increasing in some function norm applied to w [START_REF] Lafferty | Kernel conditional random fields: representation and clique selection[END_REF]. We have presented the one-slack variant here [START_REF] Joachims | Cutting-plane training of structural SVMs[END_REF]. For a finite sample of (x i , y * i , y i ), such objectives can be solved using a cutting plane approach [START_REF] Joachims | Training linear SVMs in linear time[END_REF][START_REF] Mittal | Taxonomic multi-class prediction and person layout using efficient structured ranking[END_REF][START_REF] Rahtu | Learning a category independent object detection cascade[END_REF][START_REF] Vedaldi | Learning equivariant structured output SVM regressors[END_REF].

The form of G defines risk variants that encode different preferences in ranking. If an edge exists from node i to node j, this indicates that i should be ranked higher than j. Of particular interest in this work are bipartite graphs, which have efficiencies in computation, and fully connected graphs, which attempt to enforce a total ordering on the samples. Structured output ranking with bipartite preference graphs was previously explored in [START_REF] Rahtu | Learning a category independent object detection cascade[END_REF], in which a linear time algorithm was presented for a cutting plane iteration. The algorithm presented in that work shares key similarities with previous strategies for cutting plane training of ranking support vector machines [START_REF] Joachims | Training linear SVMs in linear time[END_REF], but extends the setting to rescaled structured output losses. A linear time algorithm for fully connected preference graphs was presented in [START_REF] Mittal | Taxonomic multi-class prediction and person layout using efficient structured ranking[END_REF] in the special case that the loss values are in a small discrete set. Previous algorithms all degenerate to O(n 2 ) when applied to fully connected preference graphs with arbitrary loss values.

O(n log n) Cutting Plane Algorithm

Algorithm 1 Finding maximally violated slack-rescaled constraint for structured output ranking with a complete bipartite preference graph. Input: ∆, a list of loss values sorted from lowest to highest; s, a vector of the current estimate of compatibility scores (su = w, φ(xu, yu) H) in the same order as ∆; p, a vector of indices such that sp v > sp u whenever v > u; t, a threshold such that (u, v) ∈ E whenever u ≤ t and v > t Output:

Maximally violated constraint is δ -w, i αiφ(xi, yi) ≤ ξ 1: p + = p {u|pu≤t} , p -= p {v|pv >t} 2: i = 1, δ = ∆+ = 0, ∆ cum = 0, α = 0 3: ∆ cum n-t = ∆ p - n-t 4: for k = n -t -1 to 1 descending do 5: ∆ cum p - k = ∆ p - k + ∆ cum p - k+1 6: end for 7: for j = 1 to n -t do 8: while s p - j + 1 > s p + i ∧ i ≤ t + 1 do 9: α p + i = α p + i + ∆ cum p - j -(n -t -j + 1)∆ p + i 10: ∆+ = ∆+ + ∆ p + i , i = i + 1 11:
end while 12: Cutting plane optimization of (2)-( 5) consists of alternating between optimizing the objective with a finite set of active constraints, finding a maximally violated constraint of the current function estimate and adding it to the active constraint set [START_REF] Joachims | Cutting-plane training of structural SVMs[END_REF]. Algorithm 1 gives a linear time procedure for finding the maximally violated constraint in the case of a complete bipartite preference graph [START_REF] Joachims | Training linear SVMs in linear time[END_REF][START_REF] Rahtu | Learning a category independent object detection cascade[END_REF] and slack rescaling. 5 This algorithm follows closely the ordinal regression cutting plane algorithm of [START_REF] Joachims | Training linear SVMs in linear time[END_REF], and works by performing an initial sort on the current estimate of the sample scores. The algorithm subsequently makes use of the transitivity of violated pairwise constraints to sum all violated pairs in a single pass through the sorted list of samples.

α p - j = α p - j -((j -1)∆ p - j -∆+) 13: δ = δ + (j -1)∆ p - j -∆+ 14
In the case of fully connected preference graphs, Algorithm 2 is a recursive function that ensures that all pairs of samples are considered. Algorithm 2 uses a divide and conquer strategy and works by repeatedly calling Algorithm 1 for various bipartite subgraphs with disjoint edge sets, ensuring that the union of the edge sets of all bipartite subgraphs is the edge set of the preference graph. The set of bipartite subgraphs is constructed by partitioning the set of samples into two roughly equal parts by thresholding the loss function. As the samples are assumed to be sorted by their structured output loss, we simply divide the set by computing the index of the median element. In the event that there are multiple samples with the same loss, the partitioning (Algorithm 2, line 5) may do a linear time search from the median loss value to find a partitioning of the samples such that the first set has strictly lower loss than the second. The notation p a = p {u|pu≤t} indicates that p a contains the elements satisfying the condition in the subscript in the same order that they occured in p. Source code is available for download. 6

Complexity

Prior to calling either of the algorithms, the current data sample must be sorted by its structured output loss. Additionally an index vector, p, must be computed that encodes a permutation matrix that sorts the training sample by the current estimate of its compatibility scores, w, φ i . Each of these operations has complexity O(n log n). The serial complexity of computing the most violated 1-slack constraint is O(n log 2 n), matching the complexity of the sorting operation. To show this, we consider the recursion in Algorithm 2. The computational costs of each call consist of (i) the processing needed to find the sorted list of scores for the higher ranked and lower ranked subsets in the bipartite graph, (ii) the cost of calling Algorithm 1, and (iii) the cost of recursion. We will show that items (i) and (ii) can be computed in time linear in the number of samples.

That item (i) is linear in its complexity can be seen by noting that an index p already exists to sort the complete data sample. Rather than pay O(n log n) to re-sort the subsets of samples, we may iterate through the elements of p once. As we do so, if p i ≤ t, we may add this element to the index that sorts the higher ranked subset. If p j > t, we may add p j -t to the index that sorts the lower ranked subset. Item (ii) is also linear as the algorithm loops once over each data sample, executing a constant number of operations each time.

We calculate the complexity of Algorithm 2 by a recursive formula

R n = C n + 2R n
2 where C n is the O(n) cost of processing items (i) and (ii). It follows that

R n = log 2 n i=0 C n 2 i 2 i . ( 6
)
Examining the term C n 2 i 2 i , we note that C n 2 i is O( n 2 i ) and must be paid 2 i times, resulting in a cost of O(n) per summand. As there are O(log 2 n) summands, the total cost is O(n log n). Graphically, the recursion tree is a binary tree in which the cost of each node is proportional to 1 2 d , where d is the depth of the node (Figure 1). A C implementation of the algorithm takes a fraction second for 10 5 samples on a 2.13 GHz processor.

Fig. 1. The recursion tree for Algorithm 2. Each node in the tree corresponds to a set of constraints resulting from a bipartite preference graph. The cost of computing these constraints is labeled in each of the nodes. A straightforward parallelization scheme can be achieved by placing each recursive call in its own thread. Doing so results in O(n) computation on O(log n) processors: each level of a tree at depth i can be computed independently in C n 2 i 2 i instructions, and there are O(log n) levels of the tree. Each of log n processors can be assigned the nodes corresponding to a given level of the tree.

0: GFED @ABC C n v v m m m m m m m m m m m m ( ( Q Q Q Q Q Q Q Q Q Q Q Q 1: ONML HIJK C n 2 } } | | | | | | ! ! B B B B B B ONML HIJK C n 2 } } | | | | | | ! ! B B B B B B 2

Generalization Bounds

In this section, we develop generalization bounds based on the uniform convergence bounds for ranking algorithms presented in [START_REF] Agarwal | Generalization bounds for ranking algorithms via algorithmic stability[END_REF]. For ∆ ∈ [0, 1) we have tighter bounds for slack rescaling as compared to margin rescaling. For ∆ ∈ [0, σ] where σ > 1 bounds are tighter for margin rescaling.

Definition 1 (Uniform loss stability (β)).

A ranking algorithm which is trained on the sample S of size n has a uniform loss stability β with respect to the ranking loss function if,

| (S) -(S k )| ≤ β(n), ∀n ∈ N, 1 ≤ k ≤ n (7)
where S k is a sample resulting from changing the kth element of S, i.e., changing the input training sample by a single example leads to a difference of at most β(n) in the loss incurred by the output ranking function on any pair of examples. Thus, a smaller value of β(n) corresponds to a greater loss stability.

Definition 2 (Uniform score stability (ν)). A ranking algorithm with an output g S on the training sample S of size n, has a uniform score stability ν if

|g S (x) -g S k (x)| ≤ ν(n), ∀ n ∈ N, 1 ≤ k ≤ n, ∀x ∈ X (8)
i.e., changing an input training sample by a single example leads to a difference of at most ν(n) in the score assigned by the ranking function to any instance x.

The hinge losses for margin and slack rescaling formulations are given by:

m =(|∆ j -∆ i | -w, φ(x i , y i ) -φ(x j , y j ) • sign(∆ j -∆ i )) + , (9)
s =(|∆ j -∆ i | • (1 -w, φ(x i , y i ) -φ(x j , y j ) • sign(∆ j -∆ i ))) + . ( 10
)
Theorem 1. Let A be a ranking algorithm whose output on a training sample S ∈ (X , Y) n we denote by f S . Let ν : N → R be such that A has uniform score stability ν. A has uniform loss stability β with respect to the slack rescaling loss s , where for all n ∈ N β(n) = 2σν(n) [START_REF] Joachims | Cutting-plane training of structural SVMs[END_REF] where σ ≥ ∆ is an upper bound on the structured output loss function.

Proof. Without loss of generality we assume that s (S) > s (S k ). There are two non-trivial cases.

Case (i): Margin is violated by both g S and g S k .

| s (S) -s (S k )| =|∆ j -∆ i | • (1 -(g S (x i ) -g S (x j )) • sign(∆ j -∆ i ))-( 12
)
|∆ j -∆ i | • (1 -(g S k (x i ) -g S k (x j )) • sign(∆ j -∆ i )) ≤σ(|g S (x i ) -g S k (x i )| + |g S (x j ) -g S k (x j )|) ≤ 2σν(n) (13)
Case (ii): Margin is violated by either of g S or g S k . This is a symmetric case, so we assume that the margin is violated by g S .

| s (S) -s (S k )| =|∆ j -∆ i | • (1 -(g S (x i ) -g S (x j )) • sign(∆ j -∆ i )) ( 14
)
≤|∆ j -∆ i | • (1 -(g S (x i ) -g S (x j )) • sign(∆ j -∆ i ))-(15) |∆ j -∆ i | • (1 -(g S k (x i ) -g S k (x j )) • sign(∆ j -∆ i )) ≤σ(|g S (x i ) -g S k (x i )| + |g S (x j ) -g S k (x j )|) ≤ 2σν(n) (16)
Theorem 2 (Slack Rescaling Generalization Bound). Let H be a RKHS with a joint-kernel7 k such that ∀(x, y) ∈ X × Y, k((x, y), (x, y)) ≤ κ 2 < ∞.

Let λ > 0 and r be a rescaled ramp loss. The training algorithm trained on sample S of size n outputs a ranking function g S ∈ H that satisfies g S = arg min g∈H { R s (g; S) + λ||g|| 2 H }. Then for any 0 < δ < 1, with probability at least 1 -δ over the draw of S, the expected ranking error of the function is bounded by:

R(g S ) < R r (g S ; S) + 32σ 2 κ 2 λn + 16σ 2 κ 2 λ + σ 2 ln(1/δ) n (17)
Proof. From [1, Theorem 11], ν(n) = 8σκ 2 λn . Substituting this value of ν(n) in Equation (11) β(n) = 16σ 2 κ 2
λn . Inequality [START_REF] Taskar | Max-margin Markov networks[END_REF] then follows by an application of [START_REF] Agarwal | Generalization bounds for ranking algorithms via algorithmic stability[END_REF]Theorem 6] which gives the generalization bound as a function of β(n).

The proof of [START_REF] Agarwal | Generalization bounds for ranking algorithms via algorithmic stability[END_REF]Theorem 6] follows closely that of [START_REF] Bousquet | Stability and generalization[END_REF] for regression and classification, relying at its core on McDiarmid's inequality [START_REF] Mcdiarmid | On the method of bounded differences[END_REF].

Theorem 3 (Margin Rescaling Generalization Bound). Under the conditions of Theorem 2, and a ranking function

f S ∈ H that satisfies f S = arg min f ∈H { R m (f ; S) + λ||f || 2 H }.
Then for any 0 < δ < 1, with probability at least 1 -δ over the draw of S, the expected ranking error of the function is bounded by:

R(f S ) < R r (f S ; S) + 32κ 2 λn + 16κ 2 λ + σ 2 ln(1/δ) n (18)
The proof of Theorem 3 follows the outline given in [1, Section 5.2.1].

Experimental Results

Results are presented as an evaluation of a cascade architecture [START_REF] Viola | Robust real-time object detection[END_REF], following the evaluation protocol of Rahtu et al. [START_REF] Rahtu | Learning a category independent object detection cascade[END_REF]. The experiments are presented on the VOC 2007 dataset [START_REF] Everingham | The Pascal visual object classes (VOC) challenge[END_REF]. The images are annotated with ground-truth bounding boxes of objects from 20 classes. VOC 2007 train and validation sets are used only to construct the distribution for the initial window sampling, and the ranking function is learned using the dataset presented in [START_REF] Alexe | What is an object?[END_REF]. This is done in order to obtain results comparable to those in [START_REF] Alexe | What is an object?[END_REF][START_REF] Rahtu | Learning a category independent object detection cascade[END_REF]. The performance is measured using a recall-overlap curve, which indicates the recall rate of ground truth boxes in the VOC 2007 test set for a given minimum value of the overlap score [START_REF] Vedaldi | Multiple kernels for object detection[END_REF]

o(y, ỹ) = Area(y ∩ ỹ) Area(y ∪ ỹ) , (19)
where y and ỹ denote the ground truth and predicted bounding box, respectively. We also report the area under the curve (AUC) between overlap scores 0.5 and 1, and normalize its value so that the maximum is 1 for perfect recall. The overlap limit 0.5 is chosen here since less accurately localized boxes have little practical importance.

Our framework for creating the set of predicted bounding boxes broadly follows that of [START_REF] Rahtu | Learning a category independent object detection cascade[END_REF]. This setting has three main stages: (i) construction of the initial bounding boxes, (ii) feature extraction, and (iii) window selection. In the first stage we generate a pool of approximately 100,000 initial windows per image using random sampling and superpixel bounding boxes. The random samples are drawn from a distribution learned using the ground truth object boxes in the training and validation sets. The superpixels are computed by a graph based method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], which is selected for its computational efficiency. At overlap 0.5, the initial windows achieve approximately 98% recall.

In the second stage, the tentative bounding boxes are scored using several publicly available features. These features are window symmetry (WS), boundary edge distribution (BE), superpixel boundary integral (BI), color contrast (CC), superpixel straddling (SS), and multiscale saliency (MS). The WS, BE, and BI features are described in [START_REF] Rahtu | Learning a category independent object detection cascade[END_REF] and SS, CC, and MS are from [START_REF] Alexe | What is an object?[END_REF]. The joint feature map, φ(x i , y i ), applied in learning is the feature vector corresponding to the bounding box y i . In the last stage, we select the final set of bounding boxes (10, 100 or 1000) based on the learned score. The feature weights for the linear combination are learned by using the structured output ranking framework presented in this paper and the loss function proposed in [START_REF] Blaschko | Learning to localize objects with structured output regression[END_REF]. This loss is based on the overlap ratio [START_REF] Vedaldi | Multiple kernels for object detection[END_REF] and is defined as ∆ i ≡ 1 -o(y, y i ).

In order to run the proposed algorithm, we further need to define the structure of the preference graph G. Three variants were considered: a bipartite graph in which 1000 best samples per image are ranked higher than all other initial windows (as in [START_REF] Rahtu | Learning a category independent object detection cascade[END_REF]), a fully connected graph (denoted "Allpairs" in the legend of Figure 2(b)) where full ranking is pursued, or a bipartite graph in which only ground truth windows are to be ranked higher than all sampled windows (denoted "Star" in the legend, as the topology of a bipartite graph with one singleton set is a star graph). Finally, we have trained a standard structured output SVM (labeled "SOSVM") in the same manor as [START_REF] Blaschko | Learning to localize objects with structured output regression[END_REF]. To ensure a diverse set of predictions, we have applied the non-maximal suppression approach described in [START_REF] Vedaldi | Multiple kernels for object detection[END_REF].

The overlap-recall curves are shown in Figure 2. The legend in Figure 2 encodes the experimental setting for each curve. First, the structure of the preference graph, G, is specified. The second component of the legend indicates whether slack rescaling or margin rescaling was employed. The third component states the number of top ranked windows used for evaluating the recall. Finally, the fourth component (in parentheses) gives the AUC value.

Discussion

The experiments described in Section 5 show that structured output ranking is a natural objective to apply to cascade detection models.

On average, a bipartite preference graph performs best if we require 1000 windows as output, which matches the training conditions. The bipartite graph was constructed such that constraints were included between the top 1000 sampled windows, and the remaining 99000 windows. However, when the number of returned windows deviates from 1000, the relative performance of the bipartite ranking decreases and other preference graphs give better performance. The objective is tuned to give the highest performance under a single evaluation setting, at the expense of other settings.

The complete preference graph ranking, labeled "Allpairs" in Figure 2, gives good performance and tends to have higher performance at high overlap levels. While the difference between slack rescaling and margin rescaling was minimal when using a bipartite preference graph, a much more noticeable difference is present in the case of a complete preference graph. While the bipartite preference graph performs better at certain overlap levels when 1000 windows are returned, the complete preference graph is much more stable across a wide number of windows, and gives the best performance at all overlap levels if 10 windows are returned per image. Finally, the standard structured output SVM (labeled "SOSVM") performs substantially worse than all ranking variants.

Conclusions

In this work, we have explored the use of ranking for structured output prediction. We have analyzed both margin and slack rescaling variants of a ranking SVM style approach, showing better empirical results for slack rescaling, and proving generalization bounds for both variants in a unified framework. Furthermore, we have proposed an efficient and parallelizable algorithm for cutting plane training that scales to millions of data points on a single core. We have shown an example application of object detection in computer vision, demonstrating that ranking methods outperform a standard structured output SVM in this setting, and that fully connected preference graphs give excellent performance across a range of settings, particularly at high overlap with the ground truth.

The O(n log n) algorithm presented here can be adapted to a wide variety of settings, improving the computational efficiency in a range of ranking approaches and applications. In the setting of [START_REF] Joachims | Training linear SVMs in linear time[END_REF][START_REF] Mittal | Taxonomic multi-class prediction and person layout using efficient structured ranking[END_REF], the O(nR) approach for ranking with a complete preference graph and a fixed number, R, of loss values can be improved in an analogous manner to O(n log R).

2 6 :

 6 p a = p {u|pu≤t} 7: (α1, δ1) = Algorithm 2(∆1:t, s1:t, p a ) 8: p b = p {v|pv >t} 9: p b = p b -t (subtract t from each element of p b ) 10: (α2, δ2) = Algorithm 2(∆t+1:n, st+1:n, p b ) 11: (α0, δ0) = Algorithm 1(∆, s, p, t) 12: α = α0 + α1 + α2, δ = δ0 + δ1 + δ2 13: return (α, δ)

: ONML HIJK C n 4 ONML HIJK C n 4 ONML HIJK C n 4 ONML HIJK C n 4 .

 4444

  (a) Example detections with a complete preference graph and slack rescaling. This setting corresponds to "Allpairs slack, 1000" in Fig. (b).(b) Overlap/recall curves. Results are presented for varying preference graphs, margin and slack rescaling, and various numbers of returned windows. The AUC score is given in parentheses (a higher number at a given number of returned windows indicates better performance).

Fig. 2 .

 2 Fig. 2. Example detections and overlap vs. recall for an object detection task. See Section 5 for a complete description of the experimental setting. This figure is best viewed in color.

An edge from i to j in G indicates that output i should be ranked above output j. It will generally be the case that ∆j ≥ ∆i for all (i, j) ∈ E.

An analogous algorithm for margin rescaling was given in[START_REF] Rahtu | Learning a category independent object detection cascade[END_REF] and has the same computational complexity.

http://pages.saclay.inria.fr/matthew.blaschko/projects/structrank/

We assume a joint kernel map of the form given in[START_REF] Taskar | Max-margin Markov networks[END_REF][START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF].

Acknowledgements

This work is partially funded by ERC Grant 259112, and FP7-MC-CIG 334380.