# Stability Analysis of Learning Algorithms for Ontology Similarity Computation

Authors: Wei Gao; Tianwei Xu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Ontology, as a useful tool, is widely applied in lots of areas such as social science, computer science, and medical science. Ontology concept similarity calculation is the key part of the algorithms in these applications. A recent approach is to make use of similarity between vertices on ontology graphs. It is, instead of pairwise computations, based on a function that maps the vertex set of an ontology graph to real numbers. In order to obtain this, the ranking learning problem plays an important and essential role, especiallyk-partite ranking algorithm, which is suitable for solving some ontology problems. A ranking function is usually used to map the vertices of an ontology graph to numbers and assign ranks of the vertices through their scores. Through studying a training sample, such a function can be learned. It contains a subset of vertices of the ontology graph. A good ranking function means small ranking mistakes and good stability. For ranking algorithms, which are in a well-stable state, we study generalization bounds via some concepts of algorithmic stability. We also find that kernel-based ranking algorithms stated as regularization schemes in reproducing kernel Hilbert spaces satisfy stability conditions and have great generalization abilities.


---

## Body

## 1. Introduction and Motivations

The study of ontology deals with questions concerning what entities exist and how such entities can be grouped, related within a hierarchy, and subdivided according to similarities and differences. The developed tools have been widely applied in medicine, biology, and social science. In computer science, ontology is defined as a model for sharing formal concepts and has been applied in intelligent information integration, cooperative information systems, information retrieval, electronic commerce, and knowledge management. After a decade’s development, ontology technology has matured as an effective model of hierarchical structure and semantics for concepts, supported by systematic and comprehensive engineering theory, representation, and construction tools.Ontology similarity computation is an essential part in practical applications. In information retrieval, it has been used to compute semantic similarity and search for concepts. We take a graph-theory approach and represent an ontology by a weighted graphG=(V,E,w). In this setting, V={v1,…,vn} is the (finite) set of vertices corresponding to concepts or objects of the ontology, E⊂V×V is a set of edges, and w:E→ℝ+ is a weight function. For two vertices vi and vj representing two concepts, the weight w(vi,vj) measures their similarity in the ontology.Example 1.
In some applications of ontology similarity computation, the weight functionw takes values on [0,1]. Then the case w(vi,vj)=1 means that vi and vj represent the same concept while w(vi,vj)=0 means that these two concepts have no similarity. In information retrieval, with a threshold parameter 0<ϵ<1, when one tries to find related information of the concept vi, all concepts vj satisfying w(vi,vj)>ϵ are returned, which means that vj and vi have a high similarity.Traditional methods for ontology similarity computation are based on pairwise similarity calculation. Their computational complexity is high, and they required selection of many parameters, which are not so intuitive. In this paper, we use a learning theory approach. The idea is to learn a scoring functionf:V→ℝ and then to determine the similarity between vertices (concepts) vi and vj by their value difference |f(vi)-f(vj)|: the smaller the difference the higher the similarity. Formally, Sim(vi,vj1)≥Sim(vi,vj2) if and only if |f(vi)-f(vj1)|≤|f(vi)-f(vj2)|. Such an inspiring approach was introduced from the viewpoint of ranking in [1] where a ranking algorithm is used for learning from samples a scoring function f with small ranking error. The method was employed in the ontology setting in [2] which demonstrates accuracy and efficiency. Another possible way to learn such a function f is by a graph Laplacian and taking an eigenvector associated with its second smallest eigenvalue. See [3–6] for details. This method requires a positive definiteness condition for a similarity matrix which is hard to check in our setting. Also, when the size of the graph is large, the computational complexity is high.In this paper, we explore the learning theory approach for ontology similarity computations in a setting when the ontology graph is a tree. It is a connected graph without cycle. Thus, there is a unique path between any two vertices. The tree structure gives restrictions on similarity of vertices (concepts). For example, we assign a top vertexvtop and let it be the root, then denote k the degree (the number of edges that link to a vertex) of the top vertex. Let NG(vtop)={v1,v2,…,vk} be the neighbor set of vtop. If there is a path from one vertex to vtop through vi, then it belongs to branch i. Thus, we have k branches in the tree and any two vertices belonging to different branches have no edge between them. The concepts in the same branch of the tree should have higher similarity, compared with concepts in different branches. This observation motivates us to apply the k-partite ranking algorithm [7] in which the k parts correspond to the k classes of vertices of k rates. The rate values of all classes are decided by experts. Intuitively, a vertex of a higher rate b is ranked higher than any vertex of rate a if 1≤a<b≤k. Thus, the k-partite ranking algorithm is reasonable to learn a similarity function for an ontology graph with a tree structure.The main contribution of this paper is to state some ontology computations as ak-partite ranking problem and to conduct stability analysis of the algorithms with mild conditions, which leads to useful error bounds for ontology applications.The organization of the rest part of this paper is as follows. The setting and main results are given in the next section. The generalization bounds for learning algorithms will be shown in Section4. The stability and generalization bounds for the learning algorithms stated as regularization schemes in reproducing kernel Hilbert spaces will be discussed in Section 5.


## 2. Formal Setting and Main Results

Now, we state our learning algorithm for ontology similarity computation.LetV={v1,…,vn} be the finite set of vertices of an ontology graph. It is divided into k disjoint subsets {Vi}i=1k corresponding to k rates. Let 𝒟 be a probability measure on V.The performance of a ranking functionf:V→ℝ can be measured by the following concept.Definition 2.
A ranking loss function is a functionl:ℝV×V×V→ℝ+∪{0} that assigns, for f:V→ℝ and v,v′∈V, a nonnegative real number l(f,v,v′) interpreted as the loss of f in its relative ranking of v and v′. The expected k-partite ranking error on the ontology graph for a ranking function f:V→ℝ associated with the ranking loss function l is defined as
(1)erl(f)=∑a=1k-1‍∑b=a+1k‍Ev~𝒟a,v′~𝒟b{l(f,v,v′)},
where 𝒟a is the conditional distribution of 𝒟 on Va.Example 3.
One commonly used ranking loss function is the hinge ranking loss defined as(2)lh(f,v,v′)=(1-(f(v)-f(v′)))+,
where x+=max{x,0}. Another ranking loss function is the γ-ranking loss with a smoothing parameter γ>0 defined as
(3)lγ(f,v,v′)={1,if(f(v)-f(v′))<0,1-1γ(f(v)-f(v′)),if0≤(f(v)-f(v′))≤γτ(v,v′),0,otherwise.Learning algorithms are implemented with a sample𝒯={ti}i=1M of size M, called a preference graph, which is assumed here to be independently drawn according to 𝒟. It can also be divided into k parts {𝒯1,…,𝒯k}, where 𝒯a={ti:ti∈Va} consists of those sampling points of rate a.In [8], Agarwal and Niyogi have studied the algorithmic stability in a general setting, where the training examples take labels y∈[0,M1] for some M1>0. A goal ranking function ranks future instances with larger labels higher than those with smaller labels. Here, our setting is more specific. The learner is given a preference graph 𝒯 consisting of k disjoint parts corresponding to the k classes of vertices. Every part has a rate value. The target ranking function ranks future instances in higher-rate parts higher than those in lower-rate parts.A large class of learning algorithms is generated by regularization schemes. They penalize an empirical error which is chosen here to be theempiricalk-partite ranking error on the ontology graph defined for a f:V→ℝ associated with the sample 𝒯 as
(4)er^𝒯,l(f)=1M2∑a=1k-1‍∑b=a+1k‍∑i:ti∈𝒯a‍∑j:tj∈𝒯b‍l(f,ti,tj).In this paper, we study a learning algorithm generated by a regularization scheme in a reproducing kernel Hilbert space (RKHS)(ℋK,∥·∥K) associated with a Mercer kernel K:V×V→ℝ. Now, the regularization scheme is defined by
(5)f𝒯=argminf∈ℋK{er^𝒯,l(f)+λ∥f∥K2},
where λ>0 is a regularization parameter. On the selection of the regularized parameter, readers are referred to [9, 10] for more details about the method of cross-validation.One point we need to emphasize that we abuse terminology for the sake of better readability. If the ranking functionf does not associate with RKHS (for instance, in Lemma 9, Theorems 10 and 12), then the second term in the right-hand side of (5) vanishes.Our error analysis provides a learning rate of algorithm (5) when the ranking loss is σ-admissible.Definition 4.
Letl be a ranking loss, σ>0, and ℱ a class of real-valued functions on V. We say that l is σ-admissible with respect to ℱ if for any f1, f2∈ℱ and v,v′∈V,
(6)|l(f1,v,v′)-l(f2,v,v′)|≤σ(|f1(v)-f2(v)|+|f1(v′)-f2(v′)|).Let us state the estimate of learning rates which will be proved in Section5.Theorem 5.
LetℋK be a RKHS such that K(v,v)≤κ2<∞ for all v∈V. Let l be a ranking loss, σ-admissible with respect to ℋK, and bounded by some B>0, such that l(f,v,v′) is convex with respect to f. Let fl* be a fixed function in ℋK satisfying
(7)erl(fl*)≤inff∈ℋKerl(f)+1M′
for some M′>0. Then, for any 0<δ<1, with confidence at least 1-δ, one has
(8)erl(f𝒯)≤inff∈ℋKerl(f)+λ∥fl*∥K2+1M′+16σ2κ2λM+(24σ2κ2λ+B)ln(2/δ)2M.Form Theorem5, we see that if λ→0 and λM→∞ (e.g., λ=M-1/4), then erl(f𝒯) converges with confidence to inff∈ℋKerl(f). The quantity inff∈ℋKerl(f) is well understood in the literature related to learning theory (e.g., [11–14]).


## 3. Stability Analysis

An algorithm is stable if any change of a single point in a training set yields only a small change in the output. It is natural to consider that a good ranking algorithm is one with good stability; that is, a mild change of samples does not necessarily lead to too much change in the ranking function. Some analysis of the stability of ranking algorithms is given in [1, 8, 15].Letna=|𝒯a| and taia be the iath element in 𝒯a for 1≤a≤k,1≤ia≤na. Let 𝒯(taia,ta) be the sequence obtained by replacing taia in 𝒯 by a new sampling point ta of rate a. We define some notions of stability for k-partite ranking algorithms.Definition 6 (uniform loss stability for ak-partite ranking algorithm on ontology graph).
Let A be ak-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯. Let l be a ranking loss function and αa:ℕk→ℝ for 1≤a≤k. We say that A has uniform loss stability (α1,…,αk) with respect to l if for all 1≤a≤k, na∈ℕ, taia∈𝒯a and ia∈{1,…,na}, we have for all ta∈Va, v,v′∈V but belong to different rate,
(9)|l(f𝒯,v,v′)-l(f𝒯(tjij,tj),v,v′)|≤αj(n1,…,nk),j=1,…,k.Definition 7 (uniform score stability for ak-partite ranking algorithm on ontology graph).
Let A be ak-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯. Let l be a ranking loss function and μa:ℕk→ℝ for 1≤a≤k. We say that A has uniform score stability (μ1,…,μk) with respect to l if for all 1≤a≤k, na∈ℕ, taia∈𝒯a, ia∈{1,…,na}, and ta∈Va, and for all v∈V,
(10)|f𝒯(v)-f𝒯(tjij,tj)(v)|≤μj(n1,…,nk),j=1,…,k.The main tool used here is McDiarmid’s inequality, which bounds the deviation of any function of a sample on which a single change in the sample has limited effect.Theorem 8 (see [16]).
LetX1,…,XN be independent random variables, each taking values in a set A. Let ϕ:AN→ℝ such that for each i∈{1,…,N}, there exists a constant ci>0 such that
(11)supx1,…,xN∈A,xi′∈A|ϕ(x1,…,xN)-ϕ(x1,…,xi-1,xi′,xi+1,…,xN)|≤ci.
Then, for any ɛ>0,
(12)P{ϕ(X1,…,XN)-E{ϕ(X1,⋯,XN)}≥ɛ}≤e-2ɛ2/∑i=1Nci2.In what follows,𝒯(t1i1,t1),…,(tkik,tk) denotes a training sample set obtained by replacing t1i1 in 𝒯 by t1,…,tkik by tk for taia∈𝒯a, and ia∈{1,…,na}. Also, αa(n1,…,nk) and μa(n1,…,nk) are simply denoted by αa and μa, respectively. We only consider the case of sample replacements with the same rate: for some ontology graphs, the graph structure is fixed; hence the members of vertices and edges in each branch are fixed.


## 4. Generalization Bounds for Stablek-Partite Ranking Algorithms on Ontology Graph

From this section, our analysis for stability ofk-partite ranking algorithms is stated on an ontology graph and our organization follows [8]. In this section, generalization bounds for ranking algorithms that exhibit good stability properties will be derived. Our tricks are based on those of [17]. We start with the following technical lemma.Lemma 9.
Let A be a symmetrick-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯, and let l be a ranking loss function. Then, for all taia∈𝒯a, ia∈{1,…,na}, and ta∈Va, tb∈Vb, one has
(13)E𝒯[erl(f𝒯)-er^𝒯,l(f𝒯)]=1M2∑a=1k-1∑b=a+1kE𝒯,ta,tb{(f𝒯(taia,ta),(tbib,tb),ta,tb)nanb[(f𝒯(taia,ta),(tbib,tb),ta,tb)l(f𝒯,ta,tb)·E𝒯,ta,tbnanbE𝒯E𝒯,ta,tb-l(f𝒯(taia,ta),(tbib,tb),ta,tb)]}.Proof.
We have(14)E𝒯[er^𝒯,l(f𝒯)]=1M2∑a=1k-1∑b=a+1kE𝒯[∑i:ti∈𝒯a‍∑j:tj∈𝒯b‍l(f𝒯,ti,tj)].
By symmetry, the term in the summation is the same for all i,j. Therefore, we get
(15)E𝒯[er^𝒯,l(f𝒯)]=1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb[∑i:ti∈𝒯a‍∑j:tj∈𝒯b‍l(f𝒯,ti,tj)].
Interchanging the roles of ti with ta and tj with tb, we get
(16)E𝒯[er^𝒯,l(f𝒯)]=1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{nanb[l(f𝒯(taia,ta),(tbib,tb),ta,tb)]}.
Since
(17)E𝒯[erl(f𝒯)]=1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{nanb[l(f𝒯)]},
the results follow.We are now ready to give our main result of this section, which bounds the expectedl-error of a ranking function learned by a k-partite ranking algorithm with good uniform loss stability in terms of its empirical l-error on the training sample. The proof follows [18].Theorem 10.
Let A be a symmetrick-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯, and let l be ranking loss function such that 0≤l(f,v,v′)≤B for all f:V→ℝ and v,v′∈𝒯. Let αa:ℕk→ℝ for 1≤a≤k such that A has uniform loss stability (α1,…,αk) with respect to l. Let αmax=max{α1,…,αk}. Then, for any 0<δ<1, with confidence at least 1-δ, one has
(18)erl(f𝒯)≤er^𝒯,l(f𝒯)+2αmax+(2αmax+BM)Mln(1/δ)2.Proof.
Letϕ:VM→ℝ be defined by
(19)ϕ(𝒯)=erl(f𝒯)-er^𝒯,l(f𝒯).
We show that ϕ satisfies the condition for McDiarmid’s inequality. To this end, let ta∈Va. For each i1∈{1,…,n1}, we have
(20)|erl(f𝒯)-erl(f𝒯(t1i1,t1))|=|∑a=1k-1‍∑b=a+1k‍Ev~𝒟a,v′~𝒟b{l(f𝒯,v,v′)-l(f𝒯(t1i1,t1),v,v′)}|≤α1,|er^𝒯,l(f𝒯)-er^𝒯,l(f𝒯(t1i1,t1))|≤1M2∑a=1k-1‍∑b=a+1k‍∑i:{ti∈𝒯a,ti≠t1i1}‍∑j:tj∈𝒯b‍|l(f𝒯,ti,tj)≤1M2∑a=1k-1‍∑b=a+1k‍∑i:{ti∈𝒯a,ti≠t1i1}‍∑j:tj∈𝒯b‍-l(f𝒯(t1i1,t1),ti,tj)|+1M2∑b=2k‍∑j:tj∈𝒯b‍|l(f𝒯,t1i1,tj,)-l(f𝒯(t1i1,t1),t1i1,tj)|≤α1+B∑b=2knbM2≤α1+BM.
These give
(21)|ϕ(𝒯)-ϕ(𝒯(t1i1,t1))|≤2α1+BM.
Similarly, it can be shown that for any ia∈{1,…,na}, 1≤a≤k,
(22)|ϕ(𝒯)-ϕ(𝒯(taia,ta))|≤2αa+BM.
Thus, applying McDiarmid’s inequality to ϕ, we get for any ɛ>0,
(23)P𝒯{{erl(f𝒯)-er^𝒯,l(f𝒯)}-E𝒯{erl(f𝒯)-er^𝒯,l(f𝒯)}≥ɛ}≤exp{-2ɛ2M(2αmax+B/M)2}.
Now, by Lemma 9, we know that the expectation E𝒯[erl(f𝒯)-er^𝒯,l(f𝒯)] can be bounded as
(24)1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{(f𝒯(taia,ta),(tbib,tb),ta,tb)nanb[(f𝒯(taia,ta),(tbib,tb),ta,tb)l(f𝒯,ta,tb)1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb-l(f𝒯(taia,ta),(tbib,tb),ta,tb)]}=1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{(f𝒯(taia,ta),ta,tb)nanb[(f𝒯(taia,ta),ta,tb)l(f𝒯,ta,tb)1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb-l(f𝒯(taia,ta),ta,tb)]}+1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{(f𝒯(taia,ta),(tbib,tb),ta,tb)nanb[(f𝒯(taia,ta),(tbib,tb),ta,tb)l(f𝒯(taia,ta),ta,tb)+1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb-l(f𝒯(taia,ta),(tbib,tb),ta,tb)]}≤1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{nanbαa}+1M2∑a=1k-1‍∑b=a+1k‍E𝒯,ta,tb{nanbαb}≤2αmax.
Thus, for anyɛ>0,
(25)P𝒯{erl(f𝒯)-er^𝒯,l(f𝒯)-2αmax≥ɛ}≤exp{-2ɛ2M(2αmax+B/M)2}.
The result follows by setting the right-hand side equal to δ and solving it for ɛ.For anyγ>0, and any k-partite ranking algorithm with good uniform loss stability with respect to lγ, Theorem 10 can be applied to bound the expected ranking error of a learned ranking function in terms of its empirical lγ-error on the training sample. The following lemma shows that, for every γ>0, a ranking algorithm with good uniform score stability also has good uniform loss stability with respect to lγ. Using the techniques of Lemma 2 in [17], and taking τ(vi,vj) in Example 3 as 1, the following lemma can be obtained immediately.Lemma 11.
Let A be ak-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯. Let μa:ℕk→ℝ for 1≤a≤k such that A has uniform score stability (μ1,…,μk). Then, for every γ>0, A has uniform loss stability (α1γ,…,αkγ) with respect to the γ ranking loss lγ, where for all n1,…,nk∈ℕ,
(26)αjγ(n1,…,nk)=2μjγ,j=1,…,k.Combining Theorem10 and Lemma 11, we get the following result which bounds the expected ranking error of a learned ranking function in terms of its empirical lγ-error for any ranking algorithm with good uniform score stability.Theorem 12.
Let A be ak-partite ranking algorithm for ontology whose output on a preference graph 𝒯=(𝒯1,…,𝒯k) is denoted by f𝒯. Let μa:ℕk→ℝ for 1≤a≤k such that A has uniform score stability (μ1,…,μk), and γ>0. Denote μmax=max{μ1,…,μk}. If l is a ranking loss satisfying 0≤l(f,v,v′)≤B for all f:V→ℝ and v,v′∈𝒯, then for any 0<δ<1, with probability of at least 1-δ,
(27)erl(f𝒯)≤er^𝒯,l(f𝒯)+4γμmax+(4γμmax+BM)Mln(1/δ)2.Proof.
One applies Theorem10 to A with the ranking loss lγ (using Lemma 11), which satisfies 0≤lγ≤B. One finishes the proof thanks to the fact that er≤erlγ


## 5. Stable Ranking Algorithms

In this section, we will demonstrate stability of some ranking algorithms in which a ranking function is selected by minimizing a regularized objective function. A general result for regularization-basedk-partite ranking algorithms will be derived in Section 5.1. In Section 5.2, this result is used to illustrate stability of kernel-based k-partite ranking algorithms that perform regularization in a reproducing kernel Hilbert space. These stability results are also used to achieve consistency theorem for kernel-based k-partite ranking algorithms in Section 5.3.


### 5.1. General Regularizers

Letl be given a ranking loss function, ℱ a class of real-valued functions on V, and N:ℱ→ℝ+∪{0} a regularization functional. Consider the following regularized empirical l-error of a ranking function f∈ℱ (with respect to a preference graph 𝒯) with regularization parameter λ>0,
(28)er^𝒯,lλ=1M2∑a=1k-1‍∑b=a+1k‍∑i:ti∈𝒯a‍∑j:tj∈𝒯b‍l(f,ti,tj)+λN(f).
We consider k-partite ranking algorithms that minimize such a regularized objective function; that is, ranking algorithms that, given a preference graph 𝒯, output a ranking function f𝒯∈ℱ that satisfies
(29)f𝒯=argminf∈ℱer^𝒯,lλ=argminf∈ℱ{er^𝒯,l+λN(f)},
for some fixed choice of ranking loss l, function class ℱ, regularized N, and regularization parameter λ. We derive a general result below that will be useful for showing stability of such regularization-based algorithms.Lemma 13.
Letl be a ranking loss such that l(f,v,v′) is convex in f. Let ℱ be a convex set of real-valued functions on V, and let σ>0 such that l is σ-admissible with respect to ℱ. Let λ>0, and let N:ℱ→ℝ+∪{0} be a functional defined on ℱ such that for preference graph 𝒯=(𝒯1,…,𝒯k), the regularized empirical l-error er^𝒯,lλ has a minimum (not necessarily unique) in ℱ. Let A be a k-partite ranking algorithm for ontology defined by (29). Let ta∈Va, taia∈𝒯a, and ia∈{1,…,na}. For brevity, denote
(30)f≡f𝒯,f1,i1≡f𝒯((t1i1,t1)),…,fk,ik≡f𝒯((tkik,tk)),
and let
(31)Δf1,i1=(f1,i1-f),…,Δfk,ik=(fk,ik-f).
Then for any t∈[0,1] and q=1,…,k, one has
(32)N(f)-N(f+tΔfq,iq)+N(fq,iq)-N(fq,iq-tΔfq,iq)≤tσλM2∑b≠q‍∑j:tj∈𝒯b‍{|Δfq,iq(tqiq)|≤tσλM2∑b≠q‍∑j:tj∈𝒯b‍+2|Δfq,iq(tj)|+|Δfq,iq(tq)|}.Proof.
Recall that a convex functiong satisfies
(33)g(x+t(y-x))-g(x)≤t(g(y)-g(x)),∀t∈[0,1].
Since l(f,v,v′) is convex in f, er^𝒯,l(f) is convex in f. Therefore, for any t∈[0,1], we have
(34)er^𝒯,l(f+tΔf1,i1)-er^𝒯,l(f)≤t(er^𝒯,l(f1,i1)-er^𝒯,l(f)),
and also (interchanging the roles of f and f1,i1),
(35)er^𝒯,l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1)≤t(er^𝒯,l(f)-er^𝒯,l(f1,i1)).
Adding the above two inequalities yields
(36)er^𝒯,l(f+tΔf1,i1)-er^𝒯,l(f)+er^𝒯,l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1)≤0.
Now, since ℱ is convex, (f+tΔf1,i1)∈ℱ and (f1,i1-tΔf1,i1)∈ℱ. Since f minimizes er^𝒯,lλ(f) in ℱ and f1,i1 minimizes er^𝒯(t1i1,t1),lλ(f) in ℱ, we have
(37)er^𝒯,lλ(f)-er^𝒯,lλ(f+tΔf1,i1)≤0,er^𝒯(t1i1,t1),lλ(f1,i1)-er^𝒯(t1i1,t1),lλ(f1,i1-tΔf1,i1)≤0.
Adding these two inequalities and applying (36), we get
(38)λ(N(f)-N(f+tΔf1,i1)+N(f1,i1)-N(f1,i1-tΔf1,i1))≤er^𝒯,l(f1,i1)-er^𝒯(t1i1,t1),l(f1,i1)+er^𝒯(t1i1,t1),l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1-tΔf1,i1)=1M2∑b=2k‍∑j:tj∈𝒯b‍{(l(f1,i1,t1i1,tj)-l(f1,i1-tΔf1,i1,t1i1,tj))=1M2∑b=2k‍∑j:tj∈𝒯b‍+(l(f1,i1-tΔf1,i1,t1,tj)-l(f1,i1,t1,tj))}≤tσM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Similarly, for q=2,…,k, we have
(39)λ(N(f)-N(f+tΔfq,iq)+N(fq,iq)-N(fq,iq-tΔfq,iq))≤tσM2∑b≠q‍∑j:tj∈𝒯b‍{|Δfq,iq(tqiq)|≤tσM2∑b≠q‍∑j:tj∈𝒯b‍+2|Δfq,iq(tj)|+|Δfq,iq(tq)|}.
The results follow.As we will see below, the above result can be used to establish stability of some regularization-based ranking algorithms.


### 5.2.  Regularization in Reproducing Kernel Hilbert Spaces

Letℱ be a reproducing kernel Hilbert space (RKHS) of real-valued functions on V associated with a Mercer kernel K:V×V→ℝ. Here, Kv:V→ℝ is defined as Kv(v′)=K(v,v′), and the reproducing property of ℱ gives that for all f∈ℱ and all v∈V,
(40)f(v)=〈f,Kv〉K,
where 〈·,·〉K denotes the RKHS inner product in ℱ. By the Schwartz inequality, it is easy to show that for all f∈ℱ and all v∈V,
(41)|f(v)|≤∥f∥K∥Kv∥K=∥f∥KK(v,v),
where ∥·∥K denotes the RKHS norm in ℱ. We consider ranking algorithms that perform regularization in the RKHS ℱ using the squared norm in ℱ as regularizers. Specifically, let N:ℱ→ℝ+∪{0} be the regularizer defined by
(42)N(f)=∥f∥K2.
It will be demonstrated below that if for some 0≤κ<∞, K(v,v)≤κ for any v∈V, then a ranking algorithm that minimizes an appropriate regularized error over ℱ, with regularizer N defined as above, has good uniform score stability.Theorem 14.
Letℱ be an RKHS with kernel K such that for all v∈V,K(v,v)≤κ2<∞. Let l be a ranking loss such that l(f,v,v′) is convex in f and l is σ-admissible with respect to ℱ. Let λ>0, and let N be given by (42). Let A be the k-partite ranking algorithm for ontology that, given a preference graph 𝒯, outputs a ranking function f𝒯∈ℱ defined by (29). Then, A has uniform score stability (μ1,…,μk) with
(43)μq(n1,…,nk)=4σκ2λM,q=1,…,k.Proof.
Letva∈Va and ia∈{1,…,na}.
Applying Lemma13 with t=1/2, we get (using the notation in the proof of Lemma 13) that
(44)∥f∥K2-∥f+12Δf1,i1∥K2+∥f1,i1∥K2-∥f1,i1-12Δf1,i1∥K2≤σ2λM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Since ℱ is a vector space, Δf1,i1∈ℱ, (f+(1/2)Δf1,i1)∈ℱ, and (f1,i1-(1/2)Δf1,i1)∈ℱ, so ∥f+(1/2)Δf1,i1∥k2 and ∥f1,i1-(1/2)Δf1,i1∥k2 are well defined. It is easy to check that
(45)∥f∥K2-∥f+12Δf1,i1∥K2+∥f1,i1∥K2-∥f1,i1-12Δf1,i1∥K2=12∥Δf1,i1∥K2.
Combined with (44), this gives
(46)∥Δf1,i1∥K2≤σλM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|∑b=2k‍∑j:tj∈𝒯b‍≤σλM2+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Since (as noted above) Δf1,i1∈ℱ, this together with (41) gives
(47)∥Δf1,i1∥K2≤σλM2∥Δf1,i1∥K∑b=2k‍∑j:tj∈𝒯b{K(t1i1,t1i1)≤σλM2∥Δf1,i1∥K∑b=2k‍∑j:tj∈𝒯b‍+2K(tj,tj)+K(t1,t1)}≤4σκλM∥Δf1,i1∥K.
It follows that
(48)∥Δf1,i1∥K≤4σκλM.
This together with (41) tells us that for any v∈V,
(49)|f𝒯(v)-f𝒯t1i1,t1(v)|≤4σκ2λM.
Similarly, we can also obtain
(50)|f𝒯(v)-f𝒯tqiq,tq(v)|≤4σκ2λM,q=2,…,k.
The conclusion follows.Theorems12 and 14 give the following generalization bound for kernel-based ranking algorithms.Corollary 15.
Under the conditions of Theorem14, one has that for any 0<δ<1, with probability of at least 1-δ over the draw of 𝒯, the expected ranking error of the ranking function f𝒯 learned by the regularized algorithm associated with the l1 ranking loss is bounded by
(51)erl1(f𝒯)≤er^𝒯,l1(f𝒯)+16σκ2λM+(16σκ2λM+1M)Mln(1/δ)2.The result of Corollary15 shows that a larger regularization parameter λ leads to better stability and, therefore, a tighter confidence interval in the resulting generalization bound.Under the conditions of the above results, a kernel-based ranking algorithm minimizing a regularized empiricall-error also has good uniform loss stability with respect to l; this follows from the following simple lemma.Lemma 16.
Letℱ be a class of real-valued functions on V, and let A be a k-partite ranking algorithm for ontology that, given a preference graph 𝒯, outputs a ranking function f𝒯∈ℱ. If A has uniform score stability (μ1,…,μk) and l is a ranking loss that is σ-admissible with respect to ℱ, then A has uniform loss stability (α1,…,αk) with respect to l, where for all m∈ℕ,
(52)αj(n1,…,nk)=2σμj(n1,…,nk),j=1,…,k.The proof of this result can follow the proof of Lemma 13 in [8]. Using Theorem 14 and Lemma 16, we can immediately get the following corollary.Corollary 17.
Under the conditions of Theorem14, A has uniform loss stability (α1,…,αk) with respect to l, where for all na∈ℕ,
(53)αj(n1,…,nk)=8σ2κ2λM,j=1,…,k.


### 5.3. Consistency

We can also use the above results to show consistency of kernel-based ranking algorithms. In particular, leterl*(ℱ) denote the optimal expected l-error in an RKHS ℱ (for a given distribution):
(54)erl*(ℱ)=inff∈ℱerl(f).
Then, for a bounded loss function l, we can show that with an appropriate choice of the regularization parameter λ, the expected l-error erl(f𝒯) of the ranking function f𝒯 learned by a kernel-based ranking algorithm that minimizes a regularized empirical l-error in ℱ converges (in probability) to this optimal value. We first show the following simple lemma.Lemma 18.
Letf:V→ℝ be a fixed ranking function, and let l be a bounded ranking loss function such that 0≤l(f,v,v′)≤B for all f:V→ℝ and v,v′∈V. Then, for any 0<δ<1, with probability of at least 1-δ,
(55)er^𝒯,l(f)≤erl(f)+8σ2κ2λln(1/δ)2M.Proof.
Defineϕ as
(56)ϕ(𝒯)=er^𝒯,l(f).
Then, E𝒯[ϕ(𝒯)]=erl(f). We show that ϕ satisfies the condition of McDiarmid’s inequality. For each ia∈{1,…,na} and va∈Va, we have
(57)|ϕ(𝒯)-ϕ(𝒯vaia,va)|=|er^𝒯,l(f)-er^𝒯(vaia,va),l(f)|≤1M2∑b=a+1k‍∑j:tj∈𝒯b‍|l(f,vaia,tj)-l(f,va,tj)|+1M2∑m=1a-1‍∑i:ti∈𝒯m‍|l(f,ti,vaia)-l(f,ti,va)|≤kBM.
Therefore, applying McDiarmid’s inequality, we know that for any ɛ>0,
(58)P𝒯(er^𝒯,l(f)-erl(f)≤ɛ)≤exp{-ɛ2λ2M32σ4κ4}.
The result follows by setting the right-hand side equal to δ and solving it for ɛ.We are now in a position to prove our main result (Theorem5).Proof of Theorem5.
We use Corollary17 and apply Theorem 10 with δ/2 to get that with probability of at least 1-δ/2,
(59)erl(f𝒯)≤er^𝒯,l(f𝒯)+16σ2κ2λM+(16σ2κ2λM+BM)Mln(2/δ)2.
Clearly,
(60)er^𝒯,l(f𝒯)≤er^𝒯,l(f𝒯)+λ∥f𝒯∥K2≤er^𝒯,l(fl*)+λ∥fl*∥K2.
Applying Lemma 18 to fl* with δ/2, we, thus, get that with probability of at least 1-δ/2:
(61)er^𝒯,l(f𝒯)≤erl(fl*)+8σ2κ2λln(2/δ)2M+λ∥fl*∥K2.
One finishes the proof by combining the inequalities in (59) and (61), each of which holds with probability at least 1-δ/2, together with the condition in (7).


## 5.1. General Regularizers

Letl be given a ranking loss function, ℱ a class of real-valued functions on V, and N:ℱ→ℝ+∪{0} a regularization functional. Consider the following regularized empirical l-error of a ranking function f∈ℱ (with respect to a preference graph 𝒯) with regularization parameter λ>0,
(28)er^𝒯,lλ=1M2∑a=1k-1‍∑b=a+1k‍∑i:ti∈𝒯a‍∑j:tj∈𝒯b‍l(f,ti,tj)+λN(f).
We consider k-partite ranking algorithms that minimize such a regularized objective function; that is, ranking algorithms that, given a preference graph 𝒯, output a ranking function f𝒯∈ℱ that satisfies
(29)f𝒯=argminf∈ℱer^𝒯,lλ=argminf∈ℱ{er^𝒯,l+λN(f)},
for some fixed choice of ranking loss l, function class ℱ, regularized N, and regularization parameter λ. We derive a general result below that will be useful for showing stability of such regularization-based algorithms.Lemma 13.
Letl be a ranking loss such that l(f,v,v′) is convex in f. Let ℱ be a convex set of real-valued functions on V, and let σ>0 such that l is σ-admissible with respect to ℱ. Let λ>0, and let N:ℱ→ℝ+∪{0} be a functional defined on ℱ such that for preference graph 𝒯=(𝒯1,…,𝒯k), the regularized empirical l-error er^𝒯,lλ has a minimum (not necessarily unique) in ℱ. Let A be a k-partite ranking algorithm for ontology defined by (29). Let ta∈Va, taia∈𝒯a, and ia∈{1,…,na}. For brevity, denote
(30)f≡f𝒯,f1,i1≡f𝒯((t1i1,t1)),…,fk,ik≡f𝒯((tkik,tk)),
and let
(31)Δf1,i1=(f1,i1-f),…,Δfk,ik=(fk,ik-f).
Then for any t∈[0,1] and q=1,…,k, one has
(32)N(f)-N(f+tΔfq,iq)+N(fq,iq)-N(fq,iq-tΔfq,iq)≤tσλM2∑b≠q‍∑j:tj∈𝒯b‍{|Δfq,iq(tqiq)|≤tσλM2∑b≠q‍∑j:tj∈𝒯b‍+2|Δfq,iq(tj)|+|Δfq,iq(tq)|}.Proof.
Recall that a convex functiong satisfies
(33)g(x+t(y-x))-g(x)≤t(g(y)-g(x)),∀t∈[0,1].
Since l(f,v,v′) is convex in f, er^𝒯,l(f) is convex in f. Therefore, for any t∈[0,1], we have
(34)er^𝒯,l(f+tΔf1,i1)-er^𝒯,l(f)≤t(er^𝒯,l(f1,i1)-er^𝒯,l(f)),
and also (interchanging the roles of f and f1,i1),
(35)er^𝒯,l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1)≤t(er^𝒯,l(f)-er^𝒯,l(f1,i1)).
Adding the above two inequalities yields
(36)er^𝒯,l(f+tΔf1,i1)-er^𝒯,l(f)+er^𝒯,l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1)≤0.
Now, since ℱ is convex, (f+tΔf1,i1)∈ℱ and (f1,i1-tΔf1,i1)∈ℱ. Since f minimizes er^𝒯,lλ(f) in ℱ and f1,i1 minimizes er^𝒯(t1i1,t1),lλ(f) in ℱ, we have
(37)er^𝒯,lλ(f)-er^𝒯,lλ(f+tΔf1,i1)≤0,er^𝒯(t1i1,t1),lλ(f1,i1)-er^𝒯(t1i1,t1),lλ(f1,i1-tΔf1,i1)≤0.
Adding these two inequalities and applying (36), we get
(38)λ(N(f)-N(f+tΔf1,i1)+N(f1,i1)-N(f1,i1-tΔf1,i1))≤er^𝒯,l(f1,i1)-er^𝒯(t1i1,t1),l(f1,i1)+er^𝒯(t1i1,t1),l(f1,i1-tΔf1,i1)-er^𝒯,l(f1,i1-tΔf1,i1)=1M2∑b=2k‍∑j:tj∈𝒯b‍{(l(f1,i1,t1i1,tj)-l(f1,i1-tΔf1,i1,t1i1,tj))=1M2∑b=2k‍∑j:tj∈𝒯b‍+(l(f1,i1-tΔf1,i1,t1,tj)-l(f1,i1,t1,tj))}≤tσM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Similarly, for q=2,…,k, we have
(39)λ(N(f)-N(f+tΔfq,iq)+N(fq,iq)-N(fq,iq-tΔfq,iq))≤tσM2∑b≠q‍∑j:tj∈𝒯b‍{|Δfq,iq(tqiq)|≤tσM2∑b≠q‍∑j:tj∈𝒯b‍+2|Δfq,iq(tj)|+|Δfq,iq(tq)|}.
The results follow.As we will see below, the above result can be used to establish stability of some regularization-based ranking algorithms.


## 5.2.  Regularization in Reproducing Kernel Hilbert Spaces

Letℱ be a reproducing kernel Hilbert space (RKHS) of real-valued functions on V associated with a Mercer kernel K:V×V→ℝ. Here, Kv:V→ℝ is defined as Kv(v′)=K(v,v′), and the reproducing property of ℱ gives that for all f∈ℱ and all v∈V,
(40)f(v)=〈f,Kv〉K,
where 〈·,·〉K denotes the RKHS inner product in ℱ. By the Schwartz inequality, it is easy to show that for all f∈ℱ and all v∈V,
(41)|f(v)|≤∥f∥K∥Kv∥K=∥f∥KK(v,v),
where ∥·∥K denotes the RKHS norm in ℱ. We consider ranking algorithms that perform regularization in the RKHS ℱ using the squared norm in ℱ as regularizers. Specifically, let N:ℱ→ℝ+∪{0} be the regularizer defined by
(42)N(f)=∥f∥K2.
It will be demonstrated below that if for some 0≤κ<∞, K(v,v)≤κ for any v∈V, then a ranking algorithm that minimizes an appropriate regularized error over ℱ, with regularizer N defined as above, has good uniform score stability.Theorem 14.
Letℱ be an RKHS with kernel K such that for all v∈V,K(v,v)≤κ2<∞. Let l be a ranking loss such that l(f,v,v′) is convex in f and l is σ-admissible with respect to ℱ. Let λ>0, and let N be given by (42). Let A be the k-partite ranking algorithm for ontology that, given a preference graph 𝒯, outputs a ranking function f𝒯∈ℱ defined by (29). Then, A has uniform score stability (μ1,…,μk) with
(43)μq(n1,…,nk)=4σκ2λM,q=1,…,k.Proof.
Letva∈Va and ia∈{1,…,na}.
Applying Lemma13 with t=1/2, we get (using the notation in the proof of Lemma 13) that
(44)∥f∥K2-∥f+12Δf1,i1∥K2+∥f1,i1∥K2-∥f1,i1-12Δf1,i1∥K2≤σ2λM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Since ℱ is a vector space, Δf1,i1∈ℱ, (f+(1/2)Δf1,i1)∈ℱ, and (f1,i1-(1/2)Δf1,i1)∈ℱ, so ∥f+(1/2)Δf1,i1∥k2 and ∥f1,i1-(1/2)Δf1,i1∥k2 are well defined. It is easy to check that
(45)∥f∥K2-∥f+12Δf1,i1∥K2+∥f1,i1∥K2-∥f1,i1-12Δf1,i1∥K2=12∥Δf1,i1∥K2.
Combined with (44), this gives
(46)∥Δf1,i1∥K2≤σλM2∑b=2k‍∑j:tj∈𝒯b‍{|Δf1,i1(t1i1)|∑b=2k‍∑j:tj∈𝒯b‍≤σλM2+2|Δf1,i1(tj)|+|Δf1,i1(t1)|}.
Since (as noted above) Δf1,i1∈ℱ, this together with (41) gives
(47)∥Δf1,i1∥K2≤σλM2∥Δf1,i1∥K∑b=2k‍∑j:tj∈𝒯b{K(t1i1,t1i1)≤σλM2∥Δf1,i1∥K∑b=2k‍∑j:tj∈𝒯b‍+2K(tj,tj)+K(t1,t1)}≤4σκλM∥Δf1,i1∥K.
It follows that
(48)∥Δf1,i1∥K≤4σκλM.
This together with (41) tells us that for any v∈V,
(49)|f𝒯(v)-f𝒯t1i1,t1(v)|≤4σκ2λM.
Similarly, we can also obtain
(50)|f𝒯(v)-f𝒯tqiq,tq(v)|≤4σκ2λM,q=2,…,k.
The conclusion follows.Theorems12 and 14 give the following generalization bound for kernel-based ranking algorithms.Corollary 15.
Under the conditions of Theorem14, one has that for any 0<δ<1, with probability of at least 1-δ over the draw of 𝒯, the expected ranking error of the ranking function f𝒯 learned by the regularized algorithm associated with the l1 ranking loss is bounded by
(51)erl1(f𝒯)≤er^𝒯,l1(f𝒯)+16σκ2λM+(16σκ2λM+1M)Mln(1/δ)2.The result of Corollary15 shows that a larger regularization parameter λ leads to better stability and, therefore, a tighter confidence interval in the resulting generalization bound.Under the conditions of the above results, a kernel-based ranking algorithm minimizing a regularized empiricall-error also has good uniform loss stability with respect to l; this follows from the following simple lemma.Lemma 16.
Letℱ be a class of real-valued functions on V, and let A be a k-partite ranking algorithm for ontology that, given a preference graph 𝒯, outputs a ranking function f𝒯∈ℱ. If A has uniform score stability (μ1,…,μk) and l is a ranking loss that is σ-admissible with respect to ℱ, then A has uniform loss stability (α1,…,αk) with respect to l, where for all m∈ℕ,
(52)αj(n1,…,nk)=2σμj(n1,…,nk),j=1,…,k.The proof of this result can follow the proof of Lemma 13 in [8]. Using Theorem 14 and Lemma 16, we can immediately get the following corollary.Corollary 17.
Under the conditions of Theorem14, A has uniform loss stability (α1,…,αk) with respect to l, where for all na∈ℕ,
(53)αj(n1,…,nk)=8σ2κ2λM,j=1,…,k.


## 5.3. Consistency

We can also use the above results to show consistency of kernel-based ranking algorithms. In particular, leterl*(ℱ) denote the optimal expected l-error in an RKHS ℱ (for a given distribution):
(54)erl*(ℱ)=inff∈ℱerl(f).
Then, for a bounded loss function l, we can show that with an appropriate choice of the regularization parameter λ, the expected l-error erl(f𝒯) of the ranking function f𝒯 learned by a kernel-based ranking algorithm that minimizes a regularized empirical l-error in ℱ converges (in probability) to this optimal value. We first show the following simple lemma.Lemma 18.
Letf:V→ℝ be a fixed ranking function, and let l be a bounded ranking loss function such that 0≤l(f,v,v′)≤B for all f:V→ℝ and v,v′∈V. Then, for any 0<δ<1, with probability of at least 1-δ,
(55)er^𝒯,l(f)≤erl(f)+8σ2κ2λln(1/δ)2M.Proof.
Defineϕ as
(56)ϕ(𝒯)=er^𝒯,l(f).
Then, E𝒯[ϕ(𝒯)]=erl(f). We show that ϕ satisfies the condition of McDiarmid’s inequality. For each ia∈{1,…,na} and va∈Va, we have
(57)|ϕ(𝒯)-ϕ(𝒯vaia,va)|=|er^𝒯,l(f)-er^𝒯(vaia,va),l(f)|≤1M2∑b=a+1k‍∑j:tj∈𝒯b‍|l(f,vaia,tj)-l(f,va,tj)|+1M2∑m=1a-1‍∑i:ti∈𝒯m‍|l(f,ti,vaia)-l(f,ti,va)|≤kBM.
Therefore, applying McDiarmid’s inequality, we know that for any ɛ>0,
(58)P𝒯(er^𝒯,l(f)-erl(f)≤ɛ)≤exp{-ɛ2λ2M32σ4κ4}.
The result follows by setting the right-hand side equal to δ and solving it for ɛ.We are now in a position to prove our main result (Theorem5).Proof of Theorem5.
We use Corollary17 and apply Theorem 10 with δ/2 to get that with probability of at least 1-δ/2,
(59)erl(f𝒯)≤er^𝒯,l(f𝒯)+16σ2κ2λM+(16σ2κ2λM+BM)Mln(2/δ)2.
Clearly,
(60)er^𝒯,l(f𝒯)≤er^𝒯,l(f𝒯)+λ∥f𝒯∥K2≤er^𝒯,l(fl*)+λ∥fl*∥K2.
Applying Lemma 18 to fl* with δ/2, we, thus, get that with probability of at least 1-δ/2:
(61)er^𝒯,l(f𝒯)≤erl(fl*)+8σ2κ2λln(2/δ)2M+λ∥fl*∥K2.
One finishes the proof by combining the inequalities in (59) and (61), each of which holds with probability at least 1-δ/2, together with the condition in (7).


## 6. Conclusion

The main focus of this paper is on studying the stability and generalization properties ofk-partite ranking algorithm used for ontology computation. This algorithm shows good intuition about the vertex in ontology graph mapping to a vertex in a line. The representation of vertices in ontology graph does not take real-valued labels, and the samples are given by preference graph (pairwise vertices in different ranking rates). This setting is suitable for ontology. We have derived generalization bounds for k-partite ranking algorithms in this setting using the notion of algorithmic stability. It is also shown that k-partite ranking algorithms revealing good stability properties have good generalization properties. Our results are applied to obtain generalization bounds for kernel-based k-partite ranking algorithms that perform regularization in a reproducing kernel Hilbert space.



---

*Source: 174802-2013-06-04.xml*