Zhengyuan Zhou
email: <zyzhou@stanford.edu>.

Panayotis Mertikopoulos

Nicholas Bambos

Peter Glynn

Yinyu Ye

Li-Jia Li

Li Fei-Fei

Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?

One of the most widely used training methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue in its implementation is that of delays: when a "worker" node asynchronously contributes a gradient update to the "master", the global model parameter may have changed, rendering this information stale. In massively parallel computing grids, these delays can quickly add up if a node is saturated, so the convergence of DASGD is uncertain under these conditions. Nevertheless, by using a judiciously chosen quasilinear step-size sequence, we show that it is possible to amortize these delays and achieve global convergence with probability 1, even under polynomially growing delays, reaffirming in this way the successful application of DASGD to large-scale optimization problems.

Introduction

With the advent of high-performance computing infrastructures that are capable of handling massive amounts of data, distributed asychronous optimization has become the predominant paradigm in a broad range of large-scale machine learning and data science applications -ranging from statistical inference (Meshi & Schwing, 2017;[START_REF] Smyth | Asynchronous distributed learning of topic models[END_REF][START_REF] Grover | Variational bayes on monte carlo steroids[END_REF][START_REF] Anand | Contextual symmetries in probabilistic graphical models[END_REF] and matrix completion [START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF][START_REF] Yun | Nomad: Non-locking, stochastic multi-machine algorithm for asynchronous and decentralized matrix completion[END_REF][START_REF] Petroni | Gasgd: stochastic gradient descent for distributed asynchronous matrix completion via graph partitioning[END_REF], to training deep neural networks (Dean et al., 2012a;[START_REF] Zhang | Asynchronous stochastic gradient descent for dnn training[END_REF][START_REF] Paine | Gpu asynchronous stochastic gradient descent to speed up neural network training[END_REF][START_REF] Zhang | Deep learning with elastic averaging sgd[END_REF][START_REF] Grover | A deep hybrid model for weather forecasting[END_REF][START_REF] Jiang | Mentornet: Regularizing very deep neural networks on corrupted labels[END_REF] and representation learning [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF]Grover et al., 2018a;b). As a result, recent years have witnessed a Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s). commensurate surge of interest in the asynchronous parallelization of first-order methods such as (stochastic) gradient descent (Agarwal & Duchi, 2011;[START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF][START_REF] Paine | Gpu asynchronous stochastic gradient descent to speed up neural network training[END_REF][START_REF] Chaturapruek | Asynchronous stochastic convex optimization: the noise is in the noise and sgd don't care[END_REF][START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF][START_REF] Feyzmahdavian | An asynchronous mini-batch algorithm for regularized stochastic optimization[END_REF][START_REF] Mania | Perturbed iterate analysis for asynchronous stochastic optimization[END_REF], coordinate descent [START_REF] Liu | An asynchronous parallel stochastic coordinate descent algorithm[END_REF][START_REF] Avron | Revisiting asynchronous linear solvers: Provable convergence rate through randomization[END_REF][START_REF] Liu | Asynchronous stochastic coordinate descent: Parallelism and convergence properties[END_REF][START_REF] Tappenden | On the complexity of parallel coordinate descent[END_REF][START_REF] Fercoq | Accelerated, parallel, and proximal coordinate descent[END_REF], dual coordinate descent [START_REF] Tran | Scaling up stochastic dual coordinate ascent[END_REF], block coordinate descent [START_REF] Wang | Parallel and distributed block-coordinate frank-wolfe algorithms[END_REF][START_REF] Marecek | Distributed block coordinate descent for minimizing partially separable functions[END_REF][START_REF] Wright | Coordinate descent algorithms[END_REF], ADMM [START_REF] Zhang | Asynchronous distributed admm for consensus optimization[END_REF][START_REF] Hong | A distributed, asynchronous and incremental algorithm for nonconvex optimization: An admm approach[END_REF], etc. This popularity is a direct consequence of Moore's law of silicon integration and the commensurately increased distribution of computing power. For instance, in a typical supercomputer cluster, up to several thousands of "workers" perform independent computations with little to no synchronization between them (as the cost of such coordination quickly becomes prohibitive in terms of overhead and energy spillage). Similarly, massively parallel computing grids and data centers may house up to several million computing nodes and/or servers, all working asynchronously to execute a variety of different tasks. Finally, taking the concept of distributed computing to its logical extreme, volunteer computing grids (such as Berkeley's BOINC infrastructure or Stanford's folding@home project) essentially span the entire globe and harness the computing power of a vast, heterogeneous network of non-clustered nodes that receive and process computational requests in a non-concurrent fashion, rendering syncrhonization impossible. In this way, by eliminating the required coordination overhead, asynchronous operations become simultaneously more appealing (in physically clustered systems) and more scalable (in massively parallel and volunteer computing grids).

In this broad landscape, distributed asynchronous stochastic gradient descent (DASGD) is one of the most widely deployed methods for training large-scale machine learning models, particularly when a stochastic gradient of the underlying learning objective is easily computable (Dean et al., 2012a;b;Krizhevsky et al., 2012;[START_REF] Zhang | Asynchronous stochastic gradient descent for dnn training[END_REF][START_REF] Paine | Gpu asynchronous stochastic gradient descent to speed up neural network training[END_REF][START_REF] Zhang | Deep learning with elastic averaging sgd[END_REF]. More concretely, there are two types of distributed computing architectures that are common in practice: The first is a shared-memory multicore/multi-GPU cluster where different processors independently compute stochastic gradients and update a global model parameter using a shared memory (see e.g., [START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF][START_REF] Chaturapruek | Asynchronous stochastic convex optimization: the noise is in the noise and sgd don't care[END_REF][START_REF] Feyzmahdavian | An asynchronous mini-batch algorithm for regularized stochastic optimization[END_REF]. The second is a "master-slave" architecture where each worker independently computes a stochastic gradient of the objective; these gradients are sent asynchronously to the master as they become available, and the master sends out new computation requests after updating the model's global parameter (for instance, as in [START_REF] Agarwal | Distributed delayed stochastic optimization[END_REF]Duchi, 2011 and[START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF].

In both cases, DASGD is inherently susceptible to delays, a key impediment that is absent in centralized stochastic optimization settings. For instance, in a master-slave system, when a worker sends its gradient update to the master, the master may have already updated the model parameters several times (using updates from other workers), so the received gradient is already stale by the time it is received. In fact, even in the perfectly synchronized setting where all workers have the same speed and send input to the master in an exact round-robin fashion, there is still a constant delay that grows roughly proportinally to the number of workers in the system (Agarwal & Duchi, 2011). This situation is exacerbated further in volunteer computing grids: here, workers typically volunteer their time and resources following a highly erratic and inconstant update/work schedule, often being turned off and/or being used for different tasks for hours (or even days) on end. In such cases, there is no lower bound on the fraction of resources used by a worker to compute an update at any given time (this is especially true in heterogeneous computing grids such as BOINC and SimGrid), meaning in turn that there is no upper bound on the induced delays (this can also happen in parallel computing environments where many tasks with different priorities are executed at the same time across different machines).

Our Contributions and Related Work. In this paper, we focus on the impact of outdated information on the convergence of DASGD. To begin with, in distributed deterministic optimization, it is well-known that convex problems can be solved by asynchronous descent with perfect gradient computations, even if the delays grow sublinearly over time [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF]. In the context of stochastic convex programming (where the objective is to minimize a function of the form f (x) = E[F (x, ω)] for some random variable ω), recent works by Agarwal & Duchi (2011[START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF][START_REF] Chaturapruek | Asynchronous stochastic convex optimization: the noise is in the noise and sgd don't care[END_REF], [START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF], [START_REF] Feyzmahdavian | An asynchronous mini-batch algorithm for regularized stochastic optimization[END_REF] and [START_REF] Mania | Perturbed iterate analysis for asynchronous stochastic optimization[END_REF] have derived convergence rates for DASGD under bounded delays, typically in the sense of mean ergodic averages. Extending these results to a non-convex setting, [START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF] showed that the global state parameter X n of DASGD enjoys the guarantee This analysis extends the works mentioned above in several directions: it shows that a) convexity is not required to obtain almost sure global convergence; and b) bounded delays are not necessary to ensure the robustness of DASGD (in particular, even in the determinstic case, our analysis improves the sublinear requirement of [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF] to polynomial). From this point of view, our results can be viewed as a contribution to the following question: is vanilla DASGD robust to delays, and if so, to what extent? We provide an affirmative answer to this question which, together with the existing rich literature on the topic, helps explain and reaffirm the prolific empirical success of DASGD in large-scale machine learning problems.

n -1 n k=1 E[ ∇ f (X k ) 2 2 ] → 0 as n → ∞,
Our analysis relies on several novel ideas from the theory of stochastic approximation that were leveraged in a series of recent papers to examine descent schemes in a game-theoretic/continuous-time setting [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF][START_REF] Mertikopoulos | On the convergence of gradient-like flows with noisy gradient input[END_REF]b;[START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF]. Specifically, instead of focusing on the discrete-time algorithm directly, we first establish the convergence of an underlying, deterministic dynamical system, and then connect the continuous-and discrete-time systems via the stochastic approximation machinery of asymptotic pseudotrajectories (APTs), as pioneered by [START_REF] Benaïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF] and [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF].

Problem Setup

Let X be a convex and compact subset of R d and let (Ω, F, P) be some underlying (complete) probability space. Throughout this paper, we will focus on the stochastic opti-mization problem:

minimize f (x) subject to x ∈ X , (Opt)
where the objective function f : X → R is of the form

f (x) = E[F (x; ω)] (2.1)
for some random function F : X × Ω → R (not necessarily convex on X ). As is well-known in the distributed optimization literature (Agarwal & Duchi, 2011;Krizhevsky et al., 2012;[START_REF] Zhang | Asynchronous stochastic gradient descent for dnn training[END_REF][START_REF] Paine | Gpu asynchronous stochastic gradient descent to speed up neural network training[END_REF][START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF], the stochastic expectation in Eq. (2.1) contains as a special case the common machine learning objectives of the form

N -1 N i=1 f i (x)
, where each f i (x) is the loss associated with the i-th training sample.2 Objectives of the form

N -1 N i=1 f i (x)
in fact encompasses a wide variety of machine learning tasks. For instance, even when f i is assumed to be convex, least squares, logistic regression, SVM, matrix completion with trace norm (see [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF] for more examples) can be seamlessly cast in this form.

In terms of regularity, we also make the following standard assumptions in the rest of our paper: Assumption 1. F satisfies the following:

1. F (x; ω) is differentiable in x for P-almost all ω ∈ Ω. 2. ∇ F (x; ω) has bounded second moments, that is, E[ ∇F (x; ω) 2 2 ] < ∞ for all x ∈ X . 3. ∇F (x; ω) is Lipschitz continuous in the mean: E[∇F (x; ω)] is Lipschitz on X .
Assumptions 1 and 2 together imply that f is differentiable because, by the dominated convergence theorem, ∇f

(x) = ∇ E[F (x; ω)] = E[∇F (x; ω)].
3 Assumption 3 then implies that ∇f is Lipschitz continuous. Since f is continuous and X is compact, the solution set X * ≡ arg min f of (Opt) is closed and nonempty.

Gradient Descent in Master-Slave Systems

Our main goal in this paper is to solve the optimization problem (Opt) in master-slave architectures, a widely used distributed computing framework for data-centers and parallel computing grids. The standard way of deploying stochastic gradient descent in such systems -and that which we adopt here -is for the workers to asychronously compute stochastic gradients and then send them to the master,4 while the master updates the global state of the system and pushes the update back to the workers (Agarwal & Duchi, 2011;[START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF]. This process is presented in Algorithm 1:

Algorithm 1 Running SGD on a Master-Slave Architecture

Require: 1 Master and K workers, k = 1, . . . , K 1: repeat 2:

Master: As discussed in the introduction, since workers asychronously compute the gradients and then send updates to the master, a gradient received by the master on any given iteration can be stale (i.e., from a long-ago iteration). Since the master is the node that updates the global state of the system (the current solution candidate), we can get a clearer representation of this scheme by taking the master's point of view. The resulting process, aptly called distributed asynchronous stochastic gradient descent (DASGD) is encoded in pseudocode form in Algorithm 2 below.

Algorithm 2 Distributed asynchronous stochastic gradient descent Require:

Initial state Y 0 ∈ R d , step-size sequence α n 1: n ← 0; 2: repeat 3: X n = proj X (Y n ); 4: Y n+1 = Y n -α n+1 ∇F (X s(n) , ω s(n)+1 ); 5: n ← n + 1; 6: until end 7: return solution candidate X n
In more detail, the master keeps track of a global counter n and increments it every time it updates the current solution candidate X n . In what follows, we will write s(n) for the iteration from which the gradient received at time n originated. In other words, the delay associated with iteration s(n) is n -s(n), since it took n -s(n) iterations for the gradient computed on iteration s(n) to be received by the master at stage n. Notation-wise, we will write d n for the delay required to compute a gradient requested at iteration n. This gradient is received at stage n + d n , whereas the delay for a gradient received at n is d s(n) = n -s(n).

Mean Variational Coherence

Our goal in this paper is to establish the convergence of DASGD in as wide a class of problems as possible. Of course, global convergence 5 will not hold for all non-convex stochastic optimization problems (even without delays). As such, following Zhou et al. (2017a), we will focus on a class of non-convex functions called coherent: Assumption 2. The optimization problem (Opt) is variationally coherent in the mean if

E[ ∇ F (x; ω), x -x * ] ≥ 0, (VC)
for all x ∈ X , x * ∈ X * , with equality if and only if x ∈ X * .

By Assumption 1, we can interchange expectation and differentiation in (VC) to obtain ∇f (x), x -x * > 0, for all x / ∈ X * , x * ∈ X * . As a result, mean variational coherence can be interpreted as an averaged coherence condition for the deterministic optimization problem with objective f (x). A simple case of this, where X = R d and a unique minimizer x * exists, is discussed in [START_REF] Bottou | Online learning and stochastic approximations[END_REF], where many examples are given. Among others, this class of functions properly contains all star-and pseudo-convex functions; see Zhou et al. (2017a) for a detailed presentation of (VC). Remark 2.1. It should be noted that (VC) is a significantly weaker requirement than the monotonicity condition ∇f (x ) -∇f (x), x -x ≥ 0 for all x, x ∈ X , that characterizes convex functions. (VC) only concerns the minimum set of f and gives no information on generic point pairs (thus allowing for highly non-convex profiles).

Deterministic analysis

To streamline our presentation and build intuition along the way, we will begin with the deterministic case, where there is no randomness in the calculation of a gradient update. In this case,DASGD boils down to a distributed asynchronous gradient descent (DAGD), as illustrated in Algorithm 3:

Algorithm 3 Master's DAGD Update Require: Initial state y 0 ∈ R d , step-size sequence α n 1: n ← 0 2: repeat 3:
x n = proj X (y n );

4:

y n+1 = y n -α n+1 ∇f (x s(n) ); 5:
n ← n + 1; 6: until end 7: return solution candidate x n 5 Our focus in this paper is on global convergence. Other types of non-convex functions exist for which variants of SGD would converge to local optima [START_REF] Zhang | A hitting time analysis of stochastic gradient langevin dynamics[END_REF]. Further, there can exist specific structured class of non-convex problems, that neither contain nor belong to VC, for which SGD converges to global optima [START_REF] Chen | Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval[END_REF].

Energy Function

A key role in the analysis of Algorithm 3 is played by the energy function

E(y) = p 2 2 -proj X (y) 2 2 +2 y, proj X (y)-p , (3.1)
where p is a fixed base point in X (typically a global minimizer x * ∈ arg min f ) and y is a gradient variable (typically a gradient iterate of Algorithm 2 or Algorithm 3, depending on the context). 6Lemma 3.1. For all p ∈ X , y ∈ R d , we have:

1. E(y) ≥ 0 with equality if and only if proj X (y) = x.

The sequence {y

n } ∞ n=1 has lim n→∞ proj X (y n ) = p if and only if lim n→∞ E(y n ) = p.
The proof of Lemma 3.1 is given in the appendix, but it is helpful to make a few quick remarks. The first statement justifies the terminology of "energy", as E(y) is always non-negative. This energy function will also be the tool we use to establish an important component of the global convergence result. Further, it should also be clear that if proj X (y) = x, then E(y) = 0; it is the "only if" part that is less obvious. For the second part of the lemma, it is again clear that if proj X (y n ) → x, then E(y n ) → 0; the "only if" part is less obvious, but it is also what provides us with a way to establish convergence to optimal solutions. If we can show that E(y n ) → 0, Lemma 3.1 would guarantee that x n = proj X (y n ) → x * .

Main Convergence Result

Going back to Algorithm 3, and with a fair bit of hindsight, we will make the following assumption relating the delays and the algorithm's step-size sequence: Assumption 3. The gradient delay process d n and the stepsize sequence α n of Algorithms 2 and 3 satisfy one of the following conditions:

1. Bounded delays: sup n d n < ∞ and ∞ n=1 α 2 n < ∞, ∞ n=1 α n = ∞. 2. Linearly growing delays: d n = O(n) and α n ∝ 1/(n log n) for large n.
3. Polynomially growing delays: d n = O(n q ) for some q ≥ 1 and α n ∝ 1/(n log n log log n) for large n.

The heavy lifting for our converence analysis is then provided by the following technical result:

Proposition 3.2. Under Assumptions 1-3, DAGD admits a subsequence x n k that converges to X * as k → ∞.

We highlight the main steps below and refer the reader to the appendix for the details:

1. Letting b n = ∇ f (x s(n) ) -∇ f (x n ),
we can rewrite the gradient update in DAGD as:

y n+1 = y n -α n+1 ∇ f (x s(n) ) = y n -α n+1 ∇ f (x n ) -α n+1 {∇ f (x s(n) ) -∇ f (x n )} = y n -α n+1 (∇ f (x n ) + b n ). (3.2)
Recall here that s(n) denotes the previous iteration count whose gradient becomes available only at the current iteration n. By bounding the magnitude of b n using the delay sequence through a careful analysis, we establish that under any of the three conditions in Assumption 3, lim n→∞ b n 2 = 0. The analysis here, particularly the one for the last two conditions, reveals the following pattern: as the magnitude of the delays gets larger and larger in the order of growth, one needs to use a more conservative step-size sequence in order to mitigate the damage done by the stale gradient information. Intuitively, smaller step-sizes are more helpful in larger delays because they carry a better "amortization" effect that makes DAGD more tolerant to delays.

2. With the defintion of b n , DAGD can be written as:

x n = proj X (y n ),

y n+1 = y n -α n+1 (∇ f (x n ) + b n ). (3.3)
We then use the energy function to study the behavior of y n and x n . More specifically, we look at the quantity E(y n+1 ) -E(y n ) and bound this one-step change using the step size α n , the b n sequence and the defining quantity ∇ f (x n ), x n -x * of a variationally coherent function (as well as another term that will prove inconsequential). We then telescope on E(y n+1 ) -E(y n ) to obtain an upper bound for E(y n+1 ) -E(y 0 ). Since the energy function is always non-negative (by Lemma 3.1), E(y n+1 ) -E(y 0 ) is at least -E(y 0 ) for every n. However, utilizing the fact that b n converges to 0 and that ∇ f (x n ), x n -x * is always positive (unless the iterate is exactly an optimal solution), we show that the upper bound will approach -∞ if X n only enters N (X * , ), an open -neighborhood of X * , a finite number of times (for an arbitrary > 0). This generates an immediate contradiction, and thereby establishes that X n will get arbitrarily close to X * for an infinite number of times. This then implies that there exists a subsequence of DAGD iterates that converges to the solution set of (Opt), i.e, x n k → X * as k → ∞.

Theorem 3.3. Under Assumptions 1-3, the global state variable x n of DAGD (Algorithm 3) converges to the solution set X * of (Opt).

We give an outline of the proof below, referring to the appendix for the details. Also, for notational simplicity, we assume below that X * is a singleton; the general case is no more difficult to prove.

Sketch of proof. Fix a δ > 0. Since x n k → x * , as k → ∞, it must be E(y n k ) → 0 as k → ∞ per Lemma 3.1. So we can pick an n that is sufficiently large and E(y n ) < δ. Now, there are two cases:

1. Case 1: E(y n ) < δ/2. 2. Case 2: δ/2 ≤ E(y n ) < δ.
For Case 1, we show in the appendix that

E(y n+1 ) -E(y n ) ≤ 2BC 4 α n+1 + 2α 2 n+1 (C 2 + B 2 ),
(3.4) for suitable constants B and C. Now for n sufficiently large, we can make the right-hand arbitrarily small, and in particular, smaller than δ/2. This means E(y n+1 ) < δ.

For Case 2, we show in the appendix that

E(y n+1 ) -E(y n ) ≤ -2α n+1 a 2 -α n+1 (C 2 + B 2 ) , (3.5
) where a is a positive constant that depends only on δ. Again, since n is sufficiently large, we can make a 2 -α n+1 (C 2 + B 2 ) positive, thereby making the right-hand side negative. Consequently, E(y n+1 ) < E(y n ) < δ.

The key conclusion from the above is that, for large enough n, once E(y n ) is less than δ, E(y n+1 ) is less than δ as well and so are all the iterates afterwards. Convergence of x n to x * is then immediate by the second part of Lemma 3.1.

Stochastic analysis

The main ideas behind our deterministic analysis are relatively simple and intuitive. On the other hand, the stochastic case is much more involved because randomness can lead to very volatile behavior in the presence of delays. To streamline our presentation, we break the theoretical development into several sections, each comprising an important component of the overall analysis.

Recurrence of DASGD

We begin with the stochastic equivalent of Proposition 3.2: Proposition 4.1. Under Assumptions 1-3, DAGD admits a subsequence X n k that converges to X * almost surely; concretely, X n k → X * with probability 1 as k → ∞. Sketch of proof. We outline the two main steps of the proof below, referring the reader to the appendix for the details.

1. We begin by rewriting the gradient update step in DASGD as:

Y n+1 -Y n α n+1 = -∇F (X s(n) , ω s(n)+1 ) = -∇ f (X n ) -[∇ f (X s(n) ) -∇ f (X n )] -[∇F (X s(n) , ω s(n)+1 ) -∇ f (X s(n) )]. (4.1) Letting B n = ∇ f (X s(n) ) -∇ f (X n ) and U n+1 = ∇F (X s(n) , ω s(n)+1 ) -∇ f (X s(n) )
, we may then rewrite the DASGD update as

Y n+1 = Y n -α n+1 {∇ f (X n ) + B n + U n+1 }. (4.2)
We then establish the following two facts in this step. First, we verify that n r=0 U n+1 is a martingale adapted to Y 1 , Y 2 . . . , Y n+1 . Second, we show that lim n→∞ B n 2 = 0, a.s..

The second claim is done by first giving an upper bound on

B n 2 by writing ∇ f (X s(n) ) -∇ f (X n ) as a sum of one-step changes (∇ f (X s(n) ) -∇ f (X s(n)+1 ) + ∇ f (X s(n)+1 ) -• • • + ∇ f (X n-1 ) -∇ f (X n ))
and analyzing each such successive change. We then break that upper bound into two parts, one deterministic and one stochastic. For the deterministic part, the same analysis in the proof of Proposition 3.2 yields convergence to 0.

The stochastic part turns out to be the tail of a martingale. By leveraging the property of the step-size and a crucial property of martingale differences (two martingale differences at different time steps are uncorrelated), we establish that said martingale is L 2 -bounded. Then, by applying a version of Doob's martingale convergence theorem, it follows that said martingale converges almost surely to a limit random variable with finite second moment (and hence almost surely finite). Consequently, writing the tail as a difference between two terms (each of which converges to the same limit variablewith probability 1), we conclude that the tail converges to 0 (a.s.).

2. The full DASGD update may then be written as

X n = proj X (Y n ) Y n+1 = Y n -α n+1 [∇ f (X n ) + B n + U n+1 ]. (4.3)
As in Step 2 of the proof of Proposition 3.2, we again bound the one-step change of the energy function

E(Y n+1
) -E(Y n ) and then telescope the differences. The two distinctions from the determinstic case are: 1) Everything is now a random variable. 2) We have three terms: in addition to B n , we also have a martingale term U n+1 . Since B n converges to 0 almost surely (as shown in the previous step), its effect is the same as b n in the deterministic case. Futher, the analysis utilizes law of large numbers for martingale as well as Doob's martingale convergence theorem to bound the effect of the various martingale terms and to establish that the final dominating term is still the same term as in the deterministic case: a term that converges to -∞ (which generates a contradiction since the energy function is always positive) unless a subsequence X n k converges almost surely to X * .

Mean-Field Approximation of DASGD

With all this at hand, we can rewrite the DASGD update as:

X n = proj X (Y n ) Y n+1 = Y n -α n+1 {∇ f (X n ) + B n + U n+1 }. (4.4)
Written in this way, DASGD can be viewed as a discretization of the "mean-field" ODE

x = proj X (y), ẏ = -∇ f (x). (4.5)
The intuition is that this ODE provides a "mean" approximation of the DASGD update, because in (4.4), the noise term U n+1 has 0 mean, and the term B n converges to 0 (and therefore has negilible effect in the long run). Thes leaves only the term Y n+1 = Y n -α n+1 ∇ f (X n ), which can be seen as a Euler discretization of the ODE.

Next, writing Equation (4.5) solely in terms of y yields ẏ = -∇ f (proj X (y)). Since ∇ f and proj X are both Lipschitz continuous and X is a compact set, the composition ∇ f •proj X is itself Lipschitz continuous and bounded.

Standard results from the theory of dynamical systems then show that(4.5) admits a unique global solution y(t) for any initial condition y(0). On the other hand, since proj X is not a one-to-one map, it is not invertible; consequently, there need not exist a unique solution trajectory for x(t). By this token, the rest of our analysis will focus on the trajetory of y(t).

With the guarantee of the existence and uniqueness of the y trajectory, let P : R + × R d → R d be the flow of (4.5), i.e., P (t, y 0 ) denotes the state of (4.5) at time t when the initial condition is y 0 . In other words, when viewed as a function of time, P (•, y 0 ) is the solution trajectory to ẏ = -∇ f (proj X (y)). It is worth pointing out that writing it in this double-argument form also allows us to interpret P as a function of the initial condition: for a fixed t, P (t, •)

gives different states at t when the ODE starts from different initial conditions (in particular, P (0, y) = y). Both views will be useful later.

We end this subsection with a "sufficient decrease" property of the mean dynamics (4.5):

Lemma 4.2. With notation as above, we have:

1. If proj X (P (t, y)) / ∈ X * , then E(P (t, y)) is strictly decreasing for all y ∈ R d .

2. For all δ > 0, there exists some T ≡ T (δ) > 0 such that, for all t ≥ T , we have To be more specific, there are two things that need to be more precisely defined from the preceding high-level discussion.

sup
First, what does it mean to be a trajectory generated by the discrete-time iterates of DASGD? Second, what does it mean to be "close"?

The answer to the first question is rather intuitive: (perhaps) the simplest way to generate a continuous trajectory from a sequence of discrete points is the affine interpolation: connect the iterates Y 0 , Y 1 , . . . , Y n at times 0, α 1 , . . . , n=1 r=1 α r . We call this curve the affine interpolation curve of DASGD and denote it by A(t). Note that A(t) is a random curve because the DASGD iterates Y 0 , Y 1 , . . . , Y n are random. To avoid confusion, we summarize the three different objects discussed so far:

1. The DASGD iterates Y 0 , Y 1 , . . . , Y n .

The affine interpolation curve

A(t) of Y n .
3. The flow P (t, y) of the ODE (4.5).

The answer to the second question lies in the notion of an asymptotic pseudotrajectory (APT) , a concept introduced by [START_REF] Benaïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF] and [START_REF] Benaïm | Ergodic properties of weak asymptotic pseudotrajectories for semiflows[END_REF]. Specifically, the affine interpolation curve is considered close to ODE solution P (t, y) if the following holds: Intuitively, the definition matches exactly the naming: s is an APT for P if, for sufficiently large t, the flow lines of P remain arbitrarily close to X(t) over a time window of any (fixed)length. More precisely, for each fixed T > 0, one can find a large enough t 0 ,such that for all t > t 0 , the curve s(t + h) approximates the trajectory P (h, s(t)) on the interval h ∈ [0, T ] with any predetermined degree of accuracy.

Thanks to [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF], we can easily verify that in our case A(t) is in fact an APT for P :

Theorem 4.4 [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF]. The affine interpolation curve of the iterates generated by the difference equation

Y n+1 = Y n -α n+1 {G(X n ) + B n + U n+1
} is an APT for the solution to the ODE ẏ = -G(y) if the following three conditions all hold:

1. G is Lipschitz continuous and bounded.

2. lim n→∞ B n = 0 (a.s.).

3. U n+1 is a martingale difference sequence with

sup n E[ U n+1 p 2 ] < ∞ and ∞ n=0 α 1+ p 2 n+1 < ∞ for some p > 2.
Remark 4.1. The above theorem is a combination of Proposition 4.1, Proposition 4.2 and Remark 4.5 in [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF]. We emphasize that A(t) is an APT for P almost surely means that almost all realizations of the random paths A(t) are asymptotic pseudotrajectories for P (recall that A(t) is a random trajectory).

Corollary 4.5. A(t) is an APT of P .

Proof. It suffices to verify the conditions of Theorem 4.4. The first condition is immediate: as argued before ∇ f (proj X (•)) is Lipschitz continuous. It is also bounded because proj X (•)'s domain is X , which is compact. The second condition follows from part 1 in Proposition 4.1. The third condition is immediate by setting p = 2.

Main Convergence Result

We are now in a position to combine all of the previous pieces to obtain our main convergence result: Theorem 4.6. Under Assumptions 1-3, the global state variable X n of DASGD (Algorithm 2) converges (a.s.) to the solution set X * of (Opt).

Again, we only give an outline of the proof below, referring to the appendix for the more technical details. Proof. By Proposition 4.1, Y n gets arbitrarily close to X * infinitely often. Thus, it suffices to show that, if Y n ever gets -close to X * , all the ensuing iterates are -close to X * (a.s.).

• • • • • • • • • • • • • • • • •••••••• •• •• • • •••••• • ••• ••• •••• •• ••••• ••••••••••• ••••••• ••••• •••• ••• ••• •• •• •• • • • • • • • • • • • • • • • • • •• △ △ △ △ △ △ △ △ △ △ △ △ △△△
• • • • • • • • • • • • • • •• •• • •• • • •• • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • •• • • •• • •• •• •• ••• •••• •••••• •••••••• •••••• •••• ••• ••• •• •• •• •• •• • • • • • △ △ △ △ △ △ △ △ △ △ △△ △△△ △△△ △△ △△△ △△ △△ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △
The way we show this "trapping" property is to use the energy function. Specifically, we consider E(A(t)) and show that no matter how small is, for all sufficiently large t, if E(A(t 0 )) is less than for some t 0 , then E(A(t)) < , ∀t > t 0 . This would then complete the proof because A(t) actually contains all the DASGD iterates, and hence if E(A(t)) < , ∀t > t 0 , then E(Y n ) < for all sufficiently large n. Furthermore, since A(t) contains all the iterates, the hypothesis that " if E(A(t 0 )) is less than for some t 0 " will be satisfied due to Proposition 4.1.

We expand on one more layer of detail and defer the rest into appendix. Controlling E(A(t)), requires control of the energy on the ODE path E(P (t, y)) and the discrepancy between E(P (t, y)) and E(A(t)). The former can be made arbitrarily small as a result of Lemma 4.2; the latter can also be made arbitrarily small as a result of Corollary 4.5: since A(t) is an APT for P , the two paths are close. Therefore, the discrepancy between E(P ) and E(A) should also be vanishingly small. Consequently, since E(A(t)) = E(P (t, y)) + {E(A(t)) -E(P (t, y))}, and both terms on the right can be made arbitrarily small, so can E(A(t)) be made arbitrarily small.

Numerical results

To validate our analysis, we test the convergence of Algorithm 2 against a standard Rosenbrock test function with d = 101 degrees of freedom, i.e., f Ros (x) = 100 i=1

[100(x i+1 -x 2 i ) 2 + (1 -x i ) 2 ], (5.1) with x i ∈ [0, 2], i = 1, . . . , 101. The global minimum of f Ros is located at (1, . . . , 1), at the end of a very thin and very flat parabolic valley which is notoriously difficult for first-order methods to traverse [START_REF] Rosenbrock | An automatic method for finding the greatest or least value of a function[END_REF]. Since the minimum of the Rosenbrock function is known, (VC) is easily checked over the problem's feasible region.

For our numerical experiments, we considered a) a synchronous update schedule as a baseline; and b) an asynchronous master-slave framework with random delays that scale as d n = Θ(n). In both cases, Algorithm 2 was run with a decreasing step-size of the form α n ∝ 1/(n log n) and stochastic gradients drawn from a standard multivariate Gaussian distribution (i.e., zero mean and identity covariance matrix).

Our results are shown in Fig. 1. Starting from a random (but otherwise fixed) initial condition, we ran S = 100 realizations of DASGD (with and without delays). We then plotted a randomly chosen trajectory ("test sample" in Fig. 1), the sample average, and the min/max over all samples at every update epoch. For comparison purposes, we also plotted the value of the so-called "ergodic average"

Xn = n k=1 α k X k n k=1 α k , (5.2)
which is often used in the analysis of DASGD in the convex case (see e.g., Agarwal & Duchi, 2011). Even though this averaging leads to very robust convergence rate estimates in the convex case, we see here that it performs worse than the worst realization of DASGD. The reason for this is the lack of convexity: due to the ridges and talwegs of the Rosenbrock function, Jensen's inequality fails dramatically to produce an improvement over X n (and, in fact, causes delays as it causes X n to deviate from its gradient path).

  a) Receive a stochastic gradient from worker k (b) Update current iterate (c) Send updated iterate to worker k Compute an i.i.d. stochastic gradient (c) Send gradient update to master 4: until end

  Definition 4.3. A continuous function s : R + → R d is an APT for P if for every T > 0, lim t→∞ sup 0≤h≤T d(s(t + h), P (h, s(t))) = 0. (4.6)

Figure 1 :

 1 Figure 1: Value convergence in a non-convex stochastic optimization problem with d = 101 degrees of freedom.

  , ∀y as t → ∞. Now, if we can somehow show that the trajectory generated by the discrete-time iterates of DASGD is "close" to the continuous-time trajectory P (t, y), then likely convergence of the DASGD iterates can be guaranteed as well.

	y {E(P (t, y))-E(y) : E(P (t, y)) > δ/2} < δ/2.
	4.3. Relating DASGD Iterates to ODE Trajectories
	Lemma 4.2 essentially says E(P (t, y)) is strictly decreasing
	at a non-vanishing rate. By some additional analysis, one
	can then show 7 that Lemma Lemma 4.2 implies P (t, y) →
	X

*

  △△△△ △△△△△△ △△△ △△△△△△△△ △△△△△△△△△△△△△ △△△△△△△△△△△△△△△△△△△△ △△△△△△△△△△△△△△△△ △△△△△△△△△ △△△△△△ △△△△ △△△△ △△△ △△

				����� ����������� (�������� ���� �=��� �������)
		�
		�����
	�������� �����	�����
		�����
			���� ������
		•	������ �������
		△ ������� �������
		�� -�	������ ���/���
		�	�	��	��	���	���	����
					���������
		(a) Convergence with no delays between gradient updates

[START_REF] Lian | Asynchronous parallel stochastic gradient for nonconvex optimization[END_REF] and[START_REF] Mania | Perturbed iterate analysis for asynchronous stochastic optimization[END_REF] also examined both master-slave and multi-processor with shared memory, allowing for inconsistent reads and writes in the latter case.

This setup corresponds to empirical risk minimization with N -1 N i=1 fi(x) representing an average with uniform weights.

Note that finite second moments automatically imply finite first moments, which in turns guarantees that the expectation of the gradient exists.

In machine learning applications, this is done by sampling a subset of the training data, computing the gradient for each data point and averaging over all points in the sample.

In the above, we drop the dependence of E on p to stress the fact that the dynamic variable is y.

Although this is an interesting conclusion, we do not prove it here because we are mainly concerned with establishing convergence of the DASGD iterates, rather than the ODE solution trajectory.


Anne-Marie Vercoustre
email: anne-marie.vercoustre@inria.fr

James A Thom
email: james.thom@rmit.edu.au

Jovan Pehcevski
email: jovan.pehcevski@inria.fr

Entity Ranking in Wikipedia

Keywords: H.3 [Information Storage and Retrieval]: H.3.3 Information Search and Retrieval Entity Ranking, XML Retrieval, Test collection

The traditional entity extraction problem lies in the ability of extracting named entities from plain text using natural language processing techniques and intensive training from large document collections. Examples of named entities include organisations, people, locations, or dates. There are many research activities involving named entities; we are interested in entity ranking in the field of information retrieval. In this paper, we describe our approach to identifying and ranking entities from the INEX Wikipedia document collection. Wikipedia offers a number of interesting features for entity identification and ranking that we first introduce. We then describe the principles and the architecture of our entity ranking system, and introduce our methodology for evaluation. Our preliminary results show that the use of categories and the link structure of Wikipedia, together with entity examples, can significantly improve retrieval effectiveness.

INTRODUCTION

Information systems contain references to many named entities. In a well-structured database system it is exactly clear what are references to named entities, whereas in semi-structured information sources (such as web pages) it is harder to identify them within a text. An entity could be, for example, an organisation, a person, a location, or a date. Because of the importance of named entities, several very active and related research areas have emerged in recent years, including: entity extraction/tagging from texts, entity reference solving, entity disambiguation, question-answering, expert search, and entity ranking (also known as entity retrieval).

The traditional entity extraction problem is to extract named entities from plain text using natural language processing techniques or statistical methods and intensive training from large collections [START_REF] Cunningham | Gate: an architecture for development of robust HLT applications[END_REF][START_REF] Sekine | Named entity: History and future[END_REF]. Benchmarks for evaluation of entity extraction have been performed for the Message Understanding Conference (MUC) [START_REF]Proc. 3rd Message Understanding Conference (MUC)[END_REF] and for the Automatic Content Extraction (ACE) program [START_REF]The ACE 2006 evaluation plan: Evaluation of the detection and recognition of ACE entities, values, temporal expressions, relations, and events[END_REF].

Training is done on a large number of examples in order to identify extraction patterns (rules). The goal is to eventually tag those entities and use the tag names to support future information retrieval.

In the context of large collections such as the web or Wikipedia, it is not possible, nor even desirable, to tag in advance all the entities in the collection, although many occurrences of named entities in the text may be used as anchor text for sources of hypertext links. Instead, since we are dealing with semi-structured documents (HTML or XML), we could exploit the explicit document structure to infer effective extraction patterns or algorithms.

The goal of entity ranking is to retrieve entities as answers to a query. The objective is not to tag the names of the entities in documents but rather to get back a list of the relevant entity names (possibly each entity with an associated description). For example, the query "European countries where I can pay with Euros" [START_REF] De Vries | Entity ranking -guidelines[END_REF] should return a list of entities (or pages) representing relevant countries, and not a list of entities about the Euro and similar currencies.

The Initiative for the Evaluation of XML retrieval (INEX) has a new track on entity ranking [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF], using Wikipedia as its document collection. This track proposes two tasks: a task where the category of the expected entity answers is provided; and a task where a few (two or three) examples of the expected entity answers are provided. The inclusion of target categories (in the first task) and example entities (in the second task) makes these quite different tasks from full-text retrieval. The combination of the query and example entities (in the second task) makes it quite different from an application such as Google Sets 1 where only entity examples are provided.

In this paper, we identify some important principles for entity ranking that we incorporate into an architecture which allows us to tune, evaluate, and improve our approach as it develops. Our entity ranking approach is based on three ideas: (1) using full-text similarity with the query, (2) using popular links (from highly scored pages), and (3) using category similarity with the entity examples.

RELATED WORK

Our entity ranking approach gets its inspiration from wrapping technology, entity extraction, the use of ontologies for entity extraction or entity disambiguation, and link analysis.

Wrappers

A wrapper is a tool that extracts information (entities or values) from a document, or a set of documents, with a purpose of reusing information in another system. A lot of research has been carried out in this field by the database community, mostly in relation to querying heterogeneous databases [START_REF] Adelberg | Nodose version 2.0[END_REF][START_REF] Kushmerick | Wrapper induction: efficiency and expressiveness[END_REF][START_REF] Sahuguet | Building light-weight wrappers for legacy web data-sources using W4F[END_REF][START_REF] Vercoustre | A descriptive language for information object reuse through virtual documents[END_REF]. More recently, wrappers have also been built to extract information from web pages with different applications in mind, such as product comparison, reuse of information in virtual documents, or build-ing experimental data sets. Most web wrappers are either based on scripting languages [START_REF] Sahuguet | Building light-weight wrappers for legacy web data-sources using W4F[END_REF][START_REF] Vercoustre | A descriptive language for information object reuse through virtual documents[END_REF] that are very close to current XML query languages, or use wrapper induction [START_REF] Adelberg | Nodose version 2.0[END_REF][START_REF] Kushmerick | Wrapper induction: efficiency and expressiveness[END_REF] that learn rules for extracting information.

To prevent wrappers breaking over time without notice when pages change, Lerman et al. [START_REF] Lerman | Wrapper maintenance: A machine learning approach[END_REF] propose using machine learning for wrapper verification and re-induction. Rather than repairing a wrapper over changes in the web data, Callan and Mitamura [START_REF] Callan | Knowledge-based extraction of named entities[END_REF] propose generating the wrapper dynamically -that is at the time of wrapping, using data previously extracted and stored in a database. The extraction rules are based on heuristics around a few pre-defined lexico-syntactic HTML patterns such as lists, tables, and links. The patterns are weighted according to the number of examples they recognise; the best patterns are used to dynamically extract new data.

Our system for entity ranking also works dynamically, at query time instead of at wrapping time. We also use weighting algorithms based on links that are well represented in web-based collections, as well as knowledge of categories, a specific Wikipedia feature.

Entity extraction

Recent research in named entity extraction has developed approaches that are not language dependant and do not require lots of linguistic knowledge. McNamee and Mayfield [START_REF] Mcnamee | Entity extraction without languagespecific resources[END_REF] developed a system for entity extraction based on training on a large set of very low level textual patterns found in tokens. Their main objective was to identify entities in multilingual texts and classify them into one of four classes (location, person, organisation, or "others"). Cucerzan and Yarowsky [START_REF] Cucerzan | Language independent named entity recognition combining morphological and contextual evidence[END_REF] describe and evaluate a language-independent bootstrapping algorithm based on iterative learning and re-estimation of contextual and morphological patterns. It achieves competitive performance when trained on a very short labelled name list.

Using ontology for entity extraction

Other approaches for entity extraction are based on the use of external resources, such as an ontology or a dictionary. Popov et al. [START_REF] Popov | Towards semantic web information extraction[END_REF] use a populated ontology for entity extraction, while Cohen and Sarawagi [START_REF] Cohen | Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods[END_REF] exploit a dictionary for named entity extraction. Tenier et al. [START_REF] Tenier | Annotation semantique de pages web. In 6mes journes francophones[END_REF] use an ontology for automatic semantic annotation of web pages. Their system firstly identifies the syntactic structure that characterises an entity in a page, and then uses subsumption to identify the more specific concept to be associated with this entity.

Using ontology for entity disambiguation

Hassell et al. [START_REF] Hassell | Ontology-driven automatic entity disambiguation in unstructured text[END_REF] use a "populated ontology" to assist in disambiguation of entities, such as names of authors using their published papers or domain of interest. They use text proximity between entities to disambiguate names (e.g. organisation name would be close to author's name). They also use text co-occurrence, for example for topics relevant to an author. So their algorithm is tuned for their actual ontology, while our algorithm is more based on the the categories and the structural properties of the Wikipedia.

Cucerzan [START_REF] Cucerzan | Large-scale named entity disambiguation based on Wikipedia data[END_REF] uses Wikipedia data for named entity disambiguation. He first pre-processed a version of the Wikipedia collection (September 2006), and extracted more than 1.4 millions entities with an average of 2.4 surface forms by entities. He also extracted more than one million (entities, category) pairs that were further filtered down to 540 thousand pairs. Lexico-syntactic patterns, such as titles, links, paragraphs and lists, are used to build coreferences of entities in limited contexts. The knowledge extracted from Wikipedia is then used for improving entity disambiguation in the context of web and news search.

Link Analysis (PageRank and HITS)

Most information retrieval (IR) systems use statistical information concerning the distribution of the query terms to calculate the querydocument similarity. However, when dealing with hyperlinked environments such as the web or Wikipedia, link analysis is also important. PageRank and HITS are two of the most popular algorithms that use link analysis to improve web search performance.

PageRank, an algorithm proposed by Brin and Page [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF], is a link analysis algorithm that assigns a numerical weighting to each page of a hyperlinked set of web pages. The idea of PageRank is that a web page is a good page if it is popular, that is if many other (also preferably popular) web pages are referring to it.

In HITS (Hyperlink Induced Topic Search), hubs are considered to be web pages that have links pointing to many authority pages [START_REF] Kleinberg | Authoritative sources in hyperlinked environment[END_REF]. However, unlike PageRank where the page scores are calculated independently of the query by using the complete web graph, in HITS the calculation of hub and authority scores is querydependent; here, the so-called neighbourhood graph includes not only the set of top-ranked pages for the query, but it also includes the set of pages that either point to or are pointed to by these pages.

We use the idea behind PageRank and HITS in our system; however, instead of counting every possible link referring to an entity page in the collection (as with PageRank), or building a neighbourhood graph (as with HITS), we only consider pages that are pointed to by a selected number of top-ranked pages for the query. This makes our link ranking algorithm query-dependent (just like HITS), allowing it to be dynamically calculated at query time.

INEX ENTITY RANKING TRACK

The INEX Entity ranking track was proposed as a new track in 2006, but will only start in 2007. It will use the Wikipedia XML document collection (described in the next section) that has been used by various INEX tracks in 2006 [START_REF] Malik | Overview of INEX[END_REF]. Two tasks are planned for the INEX Entity ranking track in 2007 [START_REF] De Vries | INEX 2007 Entity ranking track guidelines[END_REF]: task1: entity ranking, where the aim is to retrieve entities of a given category satisfying a topic described by a few query terms;

task2: list completion, where given a topic text and a number of examples, the aim is to complete this partial list of answers. Figure 1 shows an example INEX entity ranking topic; the title field contains the query terms, the description provides a natural language summary of the information need, and the narrative provides an explanation of what makes an entity answer relevant. In addition, the entities field provides a few of the expected entity answers for the topic (task 2), while the categories field provides the category of the expected entity answers (task 1).

THE INEX WIKIPEDIA CORPUS

Wikipedia is a well known web-based, multilingual, free content encyclopedia written collaboratively by contributors from around the world. As it is fast growing and evolving it is not possible to use the actual online Wikipedia for experiments. Denoyer and Gallinari [START_REF] Denoyer | The Wikipedia XML corpus[END_REF]

Entities in Wikipedia

In Wikipedia, an entity is generally associated with an article (a Wikipedia page) describing this entity. Nearly everything can be seen as an entity with an associated page, including countries, famous people, organisations, places to visit, and so forth.

The entities have a name (the name of the corresponding page) and a unique ID in the collection. When mentioning such an entity in a new Wikipedia article, authors are encouraged to link at least the first occurrence of the entity name to the page describing this entity. This is an important feature as it allows to easily locate potential entities, which is a major issue in entity extraction from plain text. Consider the following extract from the Euro page. "The euro . . . is the official currency of the Eurozone (also known as the Euro Area), which consists of the European states of Austria, Belgium, Finland, France, Germany, Greece, Ireland, Italy, Luxembourg, the Netherlands, Portugal, Slovenia and Spain, and will extend to include Cyprus and Malta from 1 January 2008."

All the underlined words (hypertext links that are usually highlighted in another colour by the browser) can be seen as occurrences of entities that are each linked to their corresponding pages. In this extract, there are 18 entity references of which 15 are country names; these countries are all "European Union member states", which brings us to the notion of category in Wikipedia.

Categories in Wikipedia

Wikipedia also offers categories that authors can associate with Wikipedia pages. New categories can also be created by authors, although they have to follow Wikipedia recommendations in both creating new categories and associating them with pages. For example, the Spain page is associated with the following categories: "Spain", "European Union member states", "Spanish-speaking countries", "Constitutional monarchies" (and some other Wikipedia administrative categories). There are 113,483 categories in the INEX Wikipedia XML collection, which are organised in a graph of categories. Each page can be associated with many categories (2.28 as an average). Some properties of Wikipedia categories (explored in more detail by Yu et al. [START_REF] Yu | Ontology evaluation using Wikipedia categories for browsing[END_REF]) include:

• a category may have many sub-categories and parent categories; • some categories have many associated pages (i.e. large extension), while others have smaller extension; • a page that belongs to a given category extension generally does not belong to its ancestors' extension; • the sub-category relation is not always a subsumption relationship; and • there are cycles in the category graph.

When searching for entities it is natural to take advantage of the Wikipedia categories since they give hints on whether the retrieved entities are of the expected type. For example, if looking for 'author' entities, pages associated with the category "novelists" may be more relevant than pages associated with the category "books".

OUR APPROACH

In this work, we are addressing the task of ranking entities in answer to a query supplied with a few examples (task 2). Our approach is based on the following principles for entity answer pages. A good page:

• answers the query (or a query extended with the examples),

• is associated with a category close to the categories of the entity examples (we use a similarity function between the categories of a page and the categories of the examples), • is pointed to by a page answering the query (this is an adaptation of the HITS [START_REF] Kleinberg | Authoritative sources in hyperlinked environment[END_REF] algorithm to the problem of entity ranking; we refer to it as a linkrank algorithm), and • is pointed to by contexts with many occurrences of the entity examples. We currently use the full page as the context when calculating the scores in our linkrank algorithm. Smaller contexts such as paragraphs, lists, or tables have been used successfully by others [START_REF] Liu | Mining data records in web pages[END_REF].

We have built a system based on the above principles, where candidate pages are ranked by combining three different scores: a linkrank score, a category score, and the initial search engine similarity score. We use Zettair,2 a full-text search engine developed by RMIT University, which returns pages ranked by their similarity score to the query. We use the Okapi BM25 similarity measure as it was effective on the INEX Wikipedia collection [START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF].

Our system involves several modules for processing a query, submitting it to the search engine, applying our entity ranking algorithms, and finally returning a ranked list of entities, including: the topic module takes an INEX topic as input (as the topic example shown in Figure 1) and generates the corresponding Zettair query and the list of entity examples (as an option, the example entities may be added to the query); the search module sends the query to Zettair and returns a list of ranked Wikipedia pages (typically 1500); and the link extraction module extracts the links from a selected number of highly ranked pages together with the XML paths of the links (we discard external links and internal collection links that do not refer to existing pages in the collection).

Using the pages found by these modules, we calculate a global score for each page (see 5.4) as a linear combination of the normalised scores coming out from the following three functions: The overall process for entity ranking is shown in Figure 2. The architecture provides a general framework for evaluating entity ranking which allows for replacing some modules by more advanced modules, or by providing a more efficient implementation of a module. It also uses an evaluation module (not shown in the figure) to assist in tuning the system by varying the parameters and to globally evaluate the entity ranking approach.

LinkRank score

The linkrank function calculates a score for a page, based on the number of links to this page, from the first N pages returned by the search engine in response to the query. We carried out some experiments with different values of N and found that N=20 was an acceptable compromise between performance and discovering more potentially good entities. The linkrank function can be implemented in a variety of ways: by weighting pages that have more links referring to them from higher ranked pages (the initial N pages), or from pages containing larger number of entity examples, or a combination of the two. We have implemented a very basic linkrank function that, for a target entity page t, takes into account the Zettair score of the referring page z(pr), the number of distinct entity examples in the referring page #ent(pr), and the number of reference links to the target page #links(pr, t):

SL(t) = N r=1 z(pr) • g(#ent(pr)) • f (#links(pr, t)) (1)
where g(x) = x + 0.5 (we use 0.5 to allow for cases where there are no entity examples in the referring page) and f (x) = x (as there is at least one reference link to the target page).

Category similarity score

There has been a lot of research on similarity between concepts of two ontologies, especially for addressing the problem of mapping or updating ontologies [START_REF] Blanchard | A typology of ontology-based semantic measures[END_REF]. Similarity measures between con-cepts of the same ontology cannot be applied directly to Wikipedia categories, mostly because the notion of sub-categories in Wikipedia is not a subsumption relationship. Another reason is that categories in Wikipedia do not form a hierarchy (or a set of hierarchies) but a graph with potential cycles. Therefore tree-based similarities [START_REF] Blanchard | A tree-based similarity for evaluating concept proximities in an ontology[END_REF] either cannot be used or their applicability is limited.

However, the notions of ancestors, common ancestors, and shorter paths between categories can still be used, which may allow us to define a distance between the set of categories associated with a given page, and the set of categories associated with the entity examples. We use a very basic similarity function that is the ratio of common categories between the set of categories associated with the target page cat(t) and the union of the categories associated with the entity examples cat(E):

SC (t) = |cat(t) ∩ cat(E)| |cat(E)| (2)

Z score

The Z score assigns the initial Zettair score to a target page. If the target page does not appear in the list of 1500 ranked pages returned by Zettair, then its Z score is zero:

SZ(t) =      z(t) if page t was returned by Zettair 0 otherwise (3)

Global score

The global score S(t) for a target entity page is calculated as a linear combination of three normalised scores, the linkrank score SL(t), the category similarity score SC (t), and the Z score SZ(t):

S(t) = αSL(t) + βSC (t) + (1 -α -β)SZ(t) (4)
where α and β are parameters that can be tuned. Some special cases let us evaluate the effectiveness of each module in our system: where only the linkrank score is used (α = 1, β = 0); where only the category score is used (α = 0, β = 1); and where only the Z score is used3 (α = 0, β = 0). More combinations of the two parameters are explored in the training phase of our system.

EXPERIMENTAL RESULTS

Evaluation Methodology

There is no existing set of topics with assessments for entity ranking, although such a set will be developed for the INEX entity ranking track in 2007. So we developed our own test collection based on a selection of topics from the INEX 2006 ad hoc track. We chose 27 topics from the INEX 2006 ad hoc track that we considered were of an "entity ranking" nature. For each page that had been assessed as containing relevant information, we reassessed whether or not it was an entity answer, that is whether it loosely belonged to a category of entity we had loosely identified as being the target of the topic. We did not require that the answers should strictly belong to a particular category in the Wikipedia. If there were example entities mentioned in the original topic, then these were usually used as entity examples in the entity topic. Otherwise, a selected number (typically 2 or 3) of entity examples were chosen somewhat arbitrarily from the relevance assessments. 1). The remaining 18 topics were our test set.

We use MAP (mean average precision) as our primary method of evaluation, but also report some results with other measures which are typically used to evaluate the retrieval performance of IR systems [START_REF] Voorhees | TREC: Experiment and Evaluation in Information Retrieval[END_REF]. We first remove the the entity examples both from the list of answers returned by each system and from the relevance assessments (as the task is to find entities other than the examples provided). We calculate precision at rank r as follows:

P [r] = r i=1 rel(i) r (5)
where rel(i) = 1 if the i th article in the ranked list was judged as a relevant entity, 0 otherwise. Average precision is calculated as the average of P [r] for each relevant entity retrieved (that is at natural recall levels); if a system does not retrieve a particular relevant entity, then the precision for that entity is assumed to be zero. MAP is the mean value of the average precisions over all the topics in the training (or test) data set. We also report on several alternative measures: mean of P [1], P [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF], P [START_REF] Cunningham | Gate: an architecture for development of robust HLT applications[END_REF] (mean precision at top 1, 5 or 10 entities returned), mean R-precision (R-precision for a topic is the P [R], where R is the number of entities that have been judged relevant for the topic).

Training data set (11 topics)

We used the training data set to determine suitable values for the parameters α and β. We varied α from 0 to 1 in steps of 0.1, and for each value of α, we varied β from 0 to (1α) in steps of 0.1. We observe in Table 1 that the highest MAP (0.2911) on the 11 topics is achieved for α = 0.3 and β = 0.6. We also tried training using mean R-precision instead of MAP as our evaluation measure where we observed somewhat different optimal values for the two parameters: α = 0.1 and β = 0.8. A reason for this is the relatively small number of topics used in the training data set. We would expect the optimal parameter values obtained by MAP and R-precision to converge if many more training topics are used.

On the training data, we also experimented with adding the names of the example entities to the query sent to Zettair. However this generally performed worse, both for the plain Zettair run and the runs using various score combinations, and so it would require a more detailed per-topic analysis in order to investigate why this oc- curs. Accordingly, for the test collection we use queries that only include terms from the topic title, and consider the plain Zettair run as a baseline while comparing our entity ranking approaches.

Test data set (18 topics)

In these experiments, we designed runs to compare six entity ranking approaches using the 18 topics in the test data set:

• full-text retrieval using Zettair (as a baseline)

• link extraction and re-ranking using the Z score (SZ)

• link extraction and re-ranking using the category score (SC )

• link extraction and re-ranking using the linkrank score (SL)

• link extraction and re-ranking using two global scores:

-(0.3 * SL + 0.6 * SC + 0.1 * SZ) -(0.1 * SL + 0.8 * SC + 0.1 * SZ)
The results for these six runs are shown in Table 2. We observe that the best entity ranking approach is the one that places most of the weight on the category score SC (run α0.1-β0.8). With both MAP and R-precision, this run performs significantly better (p < 0.05) than the plain Zettair full-text retrieval run and the other four runs that use various score combinations in the re-ranking. The run that uses the category score in the re-ranking performs the best among the three runs that represent the three individual modules; however, statistically significant performance difference (p < 0.05) is only observed when comparing this run to the worst performing run (α1.0-β0.0) which uses only the linkrank score in the re-ranking.

These results show that the global score (the combination of the three individual scores), optimised in a way to give more weight on the category score, brings the best value in retrieving the relevant entities for the INEX Wikipedia document collection.

CONCLUSION AND FUTURE WORK

We have presented our entity ranking approach for the INEX Wikipedia XML document collection which is based on exploiting the interesting structural and semantic properties of the collection. We have shown in our preliminary evaluations that simple use of the categories and the link structure of Wikipedia, together with the entity examples from the topic, can significantly improve the entity ranking performance compared to a full-text retrieval engine.

Our current implementation uses very simple linkrank and category similarity functions and offers room for improvement.

To improve the linkrank function, we plan to narrow the context around the entity examples. We expect relevant entities to frequently co-occur with the example entities in lists. The narrower context could be defined either by fixed XML elements (such as paragraphs, lists, or tables) or it could be determined dynamically. To determine it dynamically, we plan to identify coherent retrieval elements adapting earlier work by Pehcevski et al. [START_REF] Pehcevski | Hybrid XML retrieval: Combining information retrieval and a native XML database[END_REF] to identify the element contexts that are most likely to contain lists.

To improve the category similarity function, we plan to take into account the notion of existing sub-categories and parent categories found in Wikipedia.

We will also be participating in the INEX 2007 entity ranking track, which we expect would enable us to test our approach using a larger set of topics and compare it against alternative approaches.

Figure 2 :

 2 Figure 2: Process for Entity ranking • the linkrank function, which calculates a weight for a page based (among other things) on the number of links to this page (see 5.1); • the category similarity function, which calculates a weight for a page based on the similarity of the page categories with those of the entity examples (see 5.2); and • the full-text IR function, which calculates a weight for a page based on its initial Zettair score (see 5.3).

Example INEX 2007 entity ranking topic the

  have developed an XML-based corpus founded on a snapshot of the Wikipedia, which has been used by various INEX tracks in 2006. It differs from the real Wikipedia in some respects (size, document format, category tables), but it is a very realistic approximation. Specifically, the INEX Wikipedia XML document corpus retains the main characteristics of the online version, although they have been implemented through XML tags instead of initial HTML tags and the native Wikipedia structure. The corpus is composed of 8 main collections, corresponding to 8 different languages. The INEX 2007 Entity ranking track will use the 4.6 Gigabyte English sub-collection which contains 659,388 articles.

	<inex_topic>
	<title>
	European countries where I can pay with Euros
	</title>
	<description>
	I want a list of European countries where
	I can pay with Euros.
	</description>
	<narrative>
	Each answer should be the article about a specific
	European country that uses the Euro as currency.
	</narrative>
	<entities>
	<entity id="10581">France</entity>
	<entity id="11867">Germany</entity>
	<entity id="26667">Spain</entity>
	</entities>
	<categories>
	<category id="61">countries<category>
	</categories>
	</inex_topic>
	Figure 1:

Table 1 : Mean average precision scores for runs using 66 possible α-β combinations, obtained on the 11 INEX 2006 training topics. Queries sent to Zettair include only terms from the topic title (Q). The MAP score of the plain Zettair run is 0.1091. The numbers in italics show the scores obtained for each of the three individual modules. The best performing MAP score is shown in bold.

 1 We used the first 9 of the 27 topics in our training set, to which we added two more topics created by hand from the original track description (one of these extra topics is the Euro example in Fig-ure

	Beta (β)

Table 2 : Performance scores for runs obtained with differ- ent evaluation measures, using the 18 INEX 2006 test topics. Queries sent to Zettair include only terms from the topic title (Q). The best performing scores are shown in bold.

 2

			P[r]
	Run	1	5	10	R-prec MAP
	Zettair	0.2778 0.3000 0.2722 0.2258 0.2023
	α0.0-β0.0 0.2778 0.3000 0.2722 0.2363 0.2042
	α0.0-β1.0 0.5556 0.4111 0.3444 0.3496 0.3349
	α1.0-β0.0 0.0556 0.1556 0.1278 0.1152 0.1015
	α0.3-β0.6 0.5000 0.4444 0.3667 0.3815 0.3274
	α0.1-β0.8 0

.5556 0.5333 0.4222 0.4337 0.3899

http://labs.google.com/sets

http://www.seg.rmit.edu.au/zettair/

This is not the same as the plain Zettair score, as apart from the highest N pages returned by Zettair, the remaining N1 entity answers are all generated by extracting links from these pages.

Acknowledgements This work was undertaken while James Thom was visiting INRIA in 2007.