# Online Manifold Regularization by Dual Ascending Procedure

Authors: Boliang Sun; Guohui Li; Li Jia; Hui Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We propose a novel online manifold regularization framework based on the notion of duality in constrained optimization. The Fenchel conjugate of hinge functions is a key to transfer manifold regularization from offline to online in this paper. Our algorithms are derived by gradient ascent in the dual function. For practical purpose, we propose two buffering strategies and two sparse approximations to reduce the computational complexity. Detailed experiments verify the utility of our approaches. An important conclusion is that our online MR algorithms can handle the settings where the target hypothesis is not fixed but drifts with the sequence of examples. We also recap and draw connections to earlier works. This paper paves a way to the design and analysis of online manifold regularization algorithms.


---

## Body

## 1. Introduction

Semisupervised learning (S2L) of different classifiers is an important problem in machine learning with interesting theoretical properties and practical applications [1–5]. Different from standard supervised learning (SL), the S2L paradigm learns from both labeled and unlabeled examples. In this paper, we investigate the online semisupervised learning (OS2L) problems which have three features as follows:(i)
data is abundant but the resources to label them are limited;(ii)
data arrives in a stream and cannot even store them all;(iii)
no statistical assumptions are found, which means thatp(x,y) can change over time.OS2L algorithms take place in a sequence of consecutive rounds. On each round, the learner is given a training example and is required to predict the label if the example is unlabeled. To label the examples, the learner uses a prediction mechanism which builds a mapping from the set of examples to the set of labels. The quality of an OS2L algorithm is measured by the cumulative loss it makes along its run. The challenge of OS2L is that we do not observe the true label for unlabeled examples to evaluate the performance of prediction mechanism. Thus, if we want to update the prediction mechanism, we have to rely on indirect forms of feedback.Lots of OS2L algorithms have been proposed in recent years. A popular idea [5, 6] is using a heuristic method to greedily label the unlabeled examples, which is essentially still employing an online supervised learning framework. References [7–9] also treat OS2L problem as online semisupervised clustering in that there are some must-linkspairs (in the same cluster) and cannot-linkspairs (cannot in the same cluster), but the effects of these methods are often influenced by “bridge points” (see a survey in [10]).For solving OS2L problem, we introduce a novel online manifold regularization (MR) framework for the design and analysis of new online MR algorithms in this paper. Manifold regularization is a geometric framework for learning from examples. This idea of regularization exploits the geometry of the probability distribution that generates the data and incorporates it as an additional regularization term. Hence, the objective function has two regularization terms: one controls the complexity of the classifier in the ambient space and the other controls the complexity as measured by the geometry of the distribution.Since decreasing the primal MR objective function is impossible before obtaining all the training examples, we propose a Fenchel conjugate transform to optimize the dual problem in an online manner. Unfortunately, the basic online MR algorithms derived from our framework have to store all the incoming examples and the time complexity on each learning round isO(t2). Therefore, we propose two buffering strategies and two sparse approximations to make our online MR algorithms practical. We also discuss the applicability of our framework to the settings where the target hypothesis is not fixed but drifts with the sequence of examples.To the best of our knowledge, the closest prior work is an empirical online version of manifold regularization of SVMs [11]. Their method defines an instantaneous regularized risk to avoid optimizing the primal MR problem directly. The learning process is based on convex programming with stochastic gradient descent in kernel space. The update scheme of this work can be derived from our online MR framework.This paper is structured as follows. In Section2 we begin with a primal view of semisupervised learning problem based on manifold regularization. In Section 3, our new framework for designing and analyzing online MR algorithms is introduced. Next, in Section 4, we derive new algorithms from our online MR framework by gradient ascent. In Section 5, we propose two sparse approximations for kernel representation to reduce computational complexity. Connections to earlier analysis techniques are in Section 6. Experiments and analyses are in Section 7. In Section 8, possible extensions of our work are given.


## 2. Problem Setting

Our notation and problem setting are formally introduced in this section. The italic lower case letters refer to scalars (e.g.,α and w), and the bold letters refer to vectors (e.g., ω and λ). (xt,yt,σt) denotes the tth training example, where xt∈ℝn is the point, yt is its label, and σt is a flag to determine whether the label can be seen. If σ=1, the example is labeled; and if σ=0, the example is unlabeled. The hinge function is denoted by[a]+=max{a,0}. 〈ω,x〉 denotes the inner product between vectors ω and x. For any t≥1, the set of integers {1,2,…,t} is denoted by [t].Consider an input sequence(x1,y1,σ1),(x2,y2,σ2),…,(xT,yT,σT), where xt∈ℝn and σt∈{0,1} (t∈{1,2,…,T}). Let K be a kernel over the training points x and ℋK the corresponding reproducing kernel Hilbert space (RKHS). The S2L problem based on manifold regularization [12] can be written as minimizing
(1)J(f)=12∥f∥K2+c1∑t=1Tσth(f(xt),yt)+c2∑i,j=1Twijd(f(xi),f(xj)),
where f∈ℋK, ∥f∥K2 is the RKHS norm of f, h is a loss function for the predictions of the training points, c1 and c2 are trade-off parameters, d(f(xi),f(xj)) is the distance function which measures the difference between the predictions of xi and xj, and wij are the edge weights which define a graph over the T examples, for example, a fully connected graph with Gaussian weights wij=e-∥xi-xj∥2/2σ2 or k-NN binary weights.In (1), the objective function J(f) can be composed of three sums. The first sum measures the complexity of f, the second measures the loss for labeled examples, and the last one is the manifold regularizer which encourages prediction smoothness over the graph which means that similar examples tend to have same predictions.Denote thatf*=argminf∈ℋKJ(f). Obviously, it is easy to seek f* using existing optimization tools after all the training examples arrived, which is called offline MR. Different from offline methods, an online MR process is performed in sequence of consecutive rounds. On each round, when an example (x,y,σ) arrives, the online MR algorithm is required to present its predictive label and update its prediction mechanism so as to be more accurate later.For simplicity and concreteness, we focus on semisupervised binary linear classifiers in this paper, which means thatf(x)=〈ω,x〉 and the data labels belong to {-1,+1}. h is chosen as a popular convex loss function in supervised classification: hinge-loss, defined as
(2)h(f(xt),yt)=[1-ytf(xt)]+=[1-yt〈ω,xt〉]+.
The function d(f(xi),f(xj)) is defined as an absolute function in this paper, where
(3)d(f(xi),f(xj))=|f(xi)-f(xj)|.
Furthermore,   (3) is composed of two hinge functions (see Figure 1 for an illustration) as follows:
(4)d(f(xi),f(xj))=[f(xi)-f(xj)]++[f(xj)-f(xi)]+.The absolute distance function and its components. The absolute function|x| (a) can be decomposed into the sum of two hinge functions [x]+ (b) and [-x]+ (c).
(a)
(b)
(c)To learn a max-margin decision boundary, we can rewrite (1) as
(5)J(ω)=12ω2+c1∑t=1Tσt[1-yt〈ω,xt〉]++c2∑i,j=1T|wij〈ω,xi-xj〉|.
Let edge weights wij=wji and gt(ω)=c1σt[1-yt〈ω,xt〉]++2c2∑i=1t-1|wij〈ω,xi-xj〉|, and we can get a simple version of (5), as
(6)J(ω)=12ω2+∑t=1Tgt(ω).The minimization problem of (6) in an online manner is what we consider in the rest of this paper.


## 3. Online Manifold Regularization in the Dual Problem

In this section, we propose a unified online manifold regularization framework of semisupervised binary classification problems. Our presentation reveals how the S2L problem based on MR in Section 2 can be optimized in an online manner.Before describing our framework, let us recall the definition of Fenchel conjugate that we use as a main analysis tool. The Fenchel conjugate of a functionf:domf→ℝ is defined as
(7)f*(λ)=sup{〈λ,ω〉-f(ω):ω∈domf}.
Specially, the Fenchel conjugate of hinge functions is a key to transfer manifold regularization from offline to online in this paper.Proposition 1.
Letf(ω)=∑i=1k[bi-〈ω,xi〉]+, where for all i∈{1,2,…,k}, bi∈ℝ, and xi∈ℝn. The Fenchel conjugate of f(ω) is
(8)f*(λ)={-∑i=1kαibiifλ∈{-∑i=1kαixi:∀i∈{1,2,…,k},αi∈[0,1]}∞otherwise.Proof.
We first rewrite thef(ω) as the following:
(9)f(ω)=∑i=1k[bi-〈ω,xi〉]+=maxα1,α2,…,αk∈[0,1]∑i=1kαi(bi-〈ω,xi〉),
where αi∈[0,1] for all i∈{1,2,…,k}. Based on the definition of Fenchel conjugate, we can obtain that
(10)f*(λ)=maxω(〈λ,ω〉-f(ω))=maxω(〈λ,ω〉-maxα1,α2,…,αk∈[0,1]∑i=1kαi(bi-〈ω,xi〉))=maxωminα1,α2,…,αk∈[0,1](〈λ,ω〉-∑i=1kαi(bi-〈ω,xi〉))=minα1,α2,…,αk∈[0,1]maxω(-∑i=1kαibi+〈λ+∑i=1kαixi,ω〉)=minα1,α2,…,αk∈[0,1](-∑i=1kαibi+maxω〈λ+∑i=1kαixi,ω〉).
Since the third equality aforementioned follows from the strong max-min property, it can be transferred into a min-max problem. Ifλ+∑i=1kαixi≠0, maxω〈λ+∑i=1kαixi,ω〉 is ∞; otherwise, if λ+∑i=1kαixi=0, we have f*(λ)=-∑i=1kαibi.Back to the primal problem, we want to get a sequence of boundaryω0,ω1,…,ωT which makes J(ω0)≥J(ω1)≥⋯≥J(ωT). In (6), decreasing the objective function J(ω) directly is impossible in the condition of not getting all the training examples. In practice, we only get the example set {(x1,y1,σ1),(x2,y2,σ2),…,(xt,yt,σt)} on round t, when the training examples arrive in a steam. In order to avoid the previous contradiction, we propose a Fenchel conjugate transform of S2L problems based on MR.An equivalent problem of (6) is
(11)minω0,ω1,…,ωT12ω02+∑t=1Tgt(ωt),s.t.∀i∈1,2…,T,ωi=ω0.Using the Lagrange dual function, we can rewrite (11) by introducing a vector group (λ1,λ2,…,λT):
(12)maxλ1,λ2,…,λTminω0,ω1,…,ωT12ω02+∑t=1Tgt(ωt)+∑t=1T〈λt,ω0-ωt〉.
Consider the dual function
(13)D(λ1,λ2,…,λT)=minω0,ω1,…,ωT12ω02+∑t=1Tgt(ωt)+∑t=1T〈λi,ω0-ωt〉=-maxω0(∑t=1T〈-λt,ω0〉-12ω02)-∑t=1Tmaxωt(〈λt,ωt〉-gt(ωt))=-12(-∑t=1Tλt)2-∑t=1Tgt*(λt),
where gt* is the Fenchel conjugate of gt. The primal problem can be described by Fenchel conjugate transform as follows:
(14)minω12ω2+∑t=1Tgt(ω)=maxλ1,λ2,…,λTD(λ1,λ2,…,λT)=maxλ1,λ2,…,λT-12(-∑t=1Tλt)2-∑t=1Tgt*(λt).In (14), we can see that our goal has been transferred from minimizing the primal problem J(ω) to maximizing the dual function D(λ1,λ2,…,λT). In the following, we show how to ascend the dual function without the unobserved examples.Based on Proposition1, the Fenchel conjugate of gt(ω) is
(15)gt*(λ)=-c1αt0σt
if λt∈{-c1αt0σtytxt-∑i=1t-12c2(αti1-αti2)wti(xt-xi), αt0∈[0,1] and for all i∈{1,2,…,t-1}, αti1, αti2∈[0,1]}; otherwise, gt*(λt)=∞.Since our goal is to maximize the dual function, we can restrict to the case thatλt∈{-c1αt0σtytxt-∑i=1t-12c2(αti1-αti2)wti(xt-xi), αt0∈[0,1] and for all i∈{1,2,…,t-1}, αti1, αti2∈[0,1]}, where t∈{1,2,…,T}. gt*(λt) has 2t-1 associated coefficients which are αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2.Based on the previous analysis, the dual function can be rewritten using a new coefficient vectorα=[α10,α20,α211,α212,…,αT0,αT11,αT12,…,αT(T-1)1,αT(T-1)2],
(16)D(α)=D(α10,α20,α211,α212,…,αT0,αT11,αT12,…,αT(T-1)1,αT(T-1)2)=-12(∑t=1T(c1αt0σtytxt+∑i=1t-12c2(αti1-αti2)wti(xt-xi)))2+∑t=1Tc1αt0σt.And our online MR task can be redescribed as ascending the dual functionD(α) by updating the coefficient vector α. Obviously, unobserved examples would make no influence on the value of dual function in (16) by setting their associate coefficients to zero.Denoteαt to be the coefficient vector α on round t, and its elements can be written as (α10)t,(α20)t,(α211)t,(α212)t,…,(αT0)t,(αT11)t,(αT12)t,…,(αT(T-1)1)t,(αT(T-1)2)t. The update process of coefficient vector α on round t should satisfy the following conditions:(i)
Ift+1≤i≤T, (αi0)t,(αi11)t,(αi12)t,…,(αi(i-1)1)t,(αi(i-1)2)t=0;(ii)
D(αt)≥D(αt-1).The first one means that the unobserved examples do not make influence on the value of dual functionD(αt), and the second means that the value of dual function never decreases along the online MR process. Therefore, the dual function on round t can be written as
(17)D(αt)=-12(∑i=1t({∑i=1t}c1(αi0)tσiyixi11111101+∑j=1i-12c2((αij1)t-(αij2)t)wij(xi-xj)))2+∑i=1tc1(αi0)tσi.Based on Lemmas2 and 3 in the appendix, we can obtain that each coefficient vector α has an associated boundary vector ω. On round t, the associated boundary vector of αt is
(18)ωt=∑i=1t({∑i=1t}c1(αi0)tσiyixi+∑j=1i-12c2((αij1)t-(αij2)t)wij(xi-xj))=∑i=1t(c1(αi0)tσiyi+∑j=1i-12c2((αij1)t-(αij2)t)wij-∑j=i+1t2c2((αji1)t-(αji2)t)wji)xi.Using a more general form, the associate vectorωt in (18) also can be written as
(19)ωt=∑i=1t(βi)txi,
where (βi)t=c1(αi0)tσiyi+∑j=1i-12c2((αij1)t-(αij2)t)wij-∑j=i+1t2c2((αji1)t-(αji2)t)wji.To make a summary, we propose a template online MR algorithm by dual ascending procedure in Algorithm1.Algorithm 1:A template online manifold regularization algorithm for semi-supervised binary classification. Based on dual ascending procedure, this template algorithm aims for an increment of the dual function on each round.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive an example (xt,yt,σt),
Choose a new coefficient vector αt that satisfies D(αt)≥D(αt-1),
Return a new associated boundary vector ωt in (18),
If σt=0, predict yt^=sign(〈ωt,xt〉).


## 4. Deriving New Algorithms by Gradient Ascent

In the previous section, a template algorithm framework for online MR is proposed based on the idea of ascending the dual function. In this section we derive different online MR algorithms using different update schemes of coefficient vectorα in the dual function.LetIt denote a subset of dual coefficients and α is an element of coefficient vector α. Our online MR algorithms simply perform a gradient ascent step over It (t∈{1,2,…,T}) on round t that aims to increase the value of dual function:
(20)(α)t=(α)t-1+ρt∂D(αt-1)∂(α)t-1,
where α∈It and ρt≥0 is a step size. We now propose three update schemes which modify different coefficients on each learning round.


### 4.1. Example-Associate (EA) Update

In traditional online supervised learning, the prediction mechanism is always updated only using the new arrived example, for example, Perceptron. Based on this notion, we propose an example-associate update scheme to ascend the dual function by updating the associated coefficients of the new training example(xt,yt,σt) on round t that means It∈{αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2}.In online MR process, the coefficientsαt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2 do not need to be grounded to zero on round t. Based on Proposition 1, we have already obtained that every element of coefficient vector α belongs to [0,1]. Using a gradient ascent step in (20), the example-associate update process can be written as
(21)(αt0)t=ρtc1σt[1-〈ytxt,ωt-1〉]+,(22)(αti1)t=2c2ρt[-wti〈(xt-xi),ωt-1〉]+,i∈{1,2,…,t-1},(23)(αti2)t=2c2ρt[wti〈(xt-xi),ωt-1〉]+,i∈{1,2,…,t-1}.Equation (21) implies that if 1-〈ytxt,ωt-1〉<0, we have (αt0)t=(αt0)t-1=0, and otherwise (αt0)t=ρtc1σt(1-〈ytxt,ωt-1〉). Equations (22) and (23) also imply that the gradient ascent must satisfy (α)t≥0, and otherwise we do not perform a gradient ascent on α.Unfortunately, this update scheme will not work in practice because it needs to store every input point to update the boundary vector; it also has an increasing time complexityO(t). Here, we propose two buffering strategies to use a small buffer of examples on each learning round. Denote that St⊆[t-1], and the example (xi,yi,σi) belongs to the buffer on round t if i∈St.(i)
Buffer-N. Let the buffer size be τ. τ-buffer replaces the oldest point xt-τ in the buffer with the new incoming point xt after each learning round, which means that St={t-τ,t-τ+1,…,t-1}.(ii)
Buffer-U. This buffering strategy replaces the oldest unlabeled point in the buffer with the incoming point while keeping labeled points. The oldest labeled point is evicted from the buffer only when it is filled with labeled points.Based on the previous analysis, the sub set of dual coefficientsIt can be chosen using the process in Algorithm 2.Algorithm 2:The process of getting It for example-associate update.
PROCESS:It=∅,
If1-〈ytxt,ωt-1〉>0, It=It∪{αt0}.
For eachi∈St
If-wti〈(xt-xi),ωt-1〉>0, It=It∪{αti1};
Ifwti〈(xt-xi),ωt-1〉>0, It=It∪{αti2}.
ReturnIt.Denoteρtmax as the maximal step size on round t. Since every dual coefficient belongs to [0,1], we have ρtmax=min{1/c1σt[1-〈ytxt,ωt-1〉]+, 1/2c2[-wti〈(xt-xi),ωt-1〉]+,  1/2c2[wti〈(xt-xi),ωt-1〉]+}, i∈St. The optimal step size ρt* is
(24)ρt*=〈∂D(αt-1)/∂It,∂D(αt-1)/∂It〉〈∂D(αt-1)/∂It,H(αt-1)(∂D(αt-1)/∂It)〉,
where H(αt-1) is the Hessian of D(αt-1) over It. Then, we obtain that if ρt∈[0,min{ρtmax,ρt*}], D(αt)≥D(αt-1).Combining (22) and (23), we have
(25)(αti1)t-(αti2)t=2c2ρt([-wti〈(xt-xi),ωt-1〉]+-[wti〈(xt-xi),ωt-1〉]+)=-2c2ρtwti〈(xt-xi),ωt-1〉.We also can rewrite the update process using the form of (19) as follows:
(26)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.
The new associate boundary vector is
(27)ωt=ωt-1+ρtc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).Algorithm3 shows an online MR algorithm based on EA update.Algorithm 3:Online manifold regularization algorithm based on EA update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive an example (xt,yt,σt),
Get It using the process in Algorithm 2,
Choose a step size ρt∈[0,min{ρtmax,ρt*}],
Update the boundary vector using (27),
If σt=0, predict yt^=sign(〈ωt,xt〉),
Renew the buffer.Specially, while choosing a small stationaryρ on each learning round, we must have D(αt)≥D(αt-1). In this condition, the update process of boundary vector can be written as
(28)ωt=ωt-1+ρc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
This update scheme is called ρ-EA update.For an aggressive gradient ascent, we can chooseρt=min{ρtmax,ρt*}, which is called aggressive-EA update.


### 4.2. Overall Update

In EA update scheme, we employ an additive way to update the boundary vector by updating the associated coefficients of the new training example. In fact, all the associated coefficients of arrived examples can be updated on each learning round. Here, we propose another new update scheme which is called overall update.Using EA update, the dual functionD(αt) on round t can be rewritten as
(29)D(αt)=-12({∑i=1t-1}ωt-1+c1(αt0)tσtytxt+∑i=1t-12c2((αti1)t-(αti2)t)wti(xt-xi))2+∑i=1tc1(αi0)tσi.
In fact, the dual coefficients in ωt-1 also can be updated in (28). Since ωt-1 has (t-1)2 dual coefficients, it is impossible to update them, respectively. We introduce a new variable ηt into (29), as
(30)D(αt)=-12({∑i=1t-1}(1-ηt)ωt-1+c1(αt0)tσtytxt+∑i=1t-12c2((αti1)t-(αti2)t)wti(xt-xi))2+(1-ηt)∑i=1t-1c1(αi0)t-1σi+c1(αt0)tσt.From (30), we can get that a gradient ascent update on ηt actually means to multiply all the dual coefficients in ωt-1 by 1-ηt. Since every dual coefficient in ωt-1 belongs to [0,1], we constrain ηt∈[0,1]. The initial value of ηt is zero. Using a gradient ascent on ηt, we obtain
(31)ηt=ρt[〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi]+.Therefore, we chooseIt∈{ηt,αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2} on each learning round for overall update. A buffering strategy also can be used in overall update, St⊆[t-1]. Like EA update, we propose a process to get It for overall update in Algorithm 4.Algorithm 4:The process of getting It for overall update.
PROCESS:It=∅,
If〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi>0,
It=It∪{ηt}.
If1-〈ytxt,ωt-1〉>0, It=It∪{αt0}.
For eachi∈St
If -wti〈(xt-xi),ωt-1〉>0, It=It∪{αti1};
If wti〈(xt-xi),ωt-1〉>0, It=It∪{αti2}.
ReturnIt.The gradient ascent for{αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2} is same as the EA update which has been shown in (21), (22), and (23). Combined with the constraint of ηt, the maximal step size for overall update is ρtmax=min{1/[〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi]+,   1/c1σt[1-〈ytxt,ωt-1〉]+,   1/2c2[-wti〈(xt-xi),ωt-1〉]+,    1/2c2[wti〈(xt-xi),ωt-1〉]+},i∈St. The optimal step size ρt* also can be obtained using (24). Obviously, if ρt∈[0,min{ρtmax,ρt*}], D(αt)≥D(αt-1). Rewriting the overall update process using the form of (19), we have
(32)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(1-ηt)(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.The new associate boundary vector is(33)ωt=(1-ηt)ωt-1+ρtc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
Algorithm 5 shows the online MR algorithm based on overall update.Algorithm 5:Online manifold regularization algorithm based on overall update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive an example (xt,yt,σt),
Get It using the process in Algorithm 4,
Choose a step size ρt∈[0,min{ρtmax,ρt*}],
Update the boundary vector using (33),
If σt=0, predict yt^=sign(〈ωt,xt〉),
Renew the buffer.Like EA update, we also can deriveρ-overall update and aggressive-overall update from the previous analysis.


### 4.3. Two-Step Update

In the two update schemes aforementioned, we actually make an assumption that the elements of an example(xt,yt,σt) arrive at the same time. But in some practical applications, the label yt is received after receiving training point xt occasionally. There is no need to update the boundary vector after receiving all the elements of an example. Here, we propose a two-step update scheme.The two-step update scheme has twice updates on each learning round. The first update takes place after the training pointxt arrives which updates the boundary vector using the geometry of the training points. The second update takes place after yt,σt arrive which updates the boundary vector using the label. Obviously, EA update and overall update can be used in each update process of two-step update scheme. For example, we use EA update to describe the update process of two-step update scheme.Denote asαt-1/2 the coefficient vector after the first update on round t and ωt-1/2 its associate boundary. The example-associate coefficients in the first update on round t are αt11,αt12,…,αt(t-1)1,αt(t-1)2, and new associate boundary vector can be written as
(34)ωt-1/2=ωt-1+4ρt-1/2c22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
In the second update process, the example-associate coefficient is αt0, and new associate boundary vector is
(35)ωt=ωt-1/2+ρtc12σtyt[1-〈ytxt,ωt-1/2〉]+xt.
If σt=0, the second update process in (35) would not happen, and the two-step update degenerates into EA update. The range of ρt-1/2 and ρt can be obtained by the same process in Section 4.1. Similar as the previous analysis, the overall update also can be used in each update process of two-step update scheme.The online MR algorithm based on the two-step update can be described in Algorithm6.Algorithm 6:A template online manifold regularization algorithm based on two-step update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive a training point xt,
Choose a new coefficient vector αt-(1/2) that satisfies D(αt-(1/2))≥D(αt-1),
Return a new associated boundary vector ωt-(1/2) in (18).
Receive yt,σt,
If σt=0, αt=αt-(1/2), ωt=ωt-(1/2), predict yt^=sign(〈ωt,xt〉);
Else if σt=1, choose a new coefficient vector αt that satisfies D(αt)≥D(αt-(1/2)), return a new associated
boundary vector ωt in (18).This update scheme is more like a new perspective of online MR problem, and its effect is influenced by the update schemes on each step. Therefore, we pay more attentions to the first two update schemes aforementioned in this paper.


## 4.1. Example-Associate (EA) Update

In traditional online supervised learning, the prediction mechanism is always updated only using the new arrived example, for example, Perceptron. Based on this notion, we propose an example-associate update scheme to ascend the dual function by updating the associated coefficients of the new training example(xt,yt,σt) on round t that means It∈{αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2}.In online MR process, the coefficientsαt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2 do not need to be grounded to zero on round t. Based on Proposition 1, we have already obtained that every element of coefficient vector α belongs to [0,1]. Using a gradient ascent step in (20), the example-associate update process can be written as
(21)(αt0)t=ρtc1σt[1-〈ytxt,ωt-1〉]+,(22)(αti1)t=2c2ρt[-wti〈(xt-xi),ωt-1〉]+,i∈{1,2,…,t-1},(23)(αti2)t=2c2ρt[wti〈(xt-xi),ωt-1〉]+,i∈{1,2,…,t-1}.Equation (21) implies that if 1-〈ytxt,ωt-1〉<0, we have (αt0)t=(αt0)t-1=0, and otherwise (αt0)t=ρtc1σt(1-〈ytxt,ωt-1〉). Equations (22) and (23) also imply that the gradient ascent must satisfy (α)t≥0, and otherwise we do not perform a gradient ascent on α.Unfortunately, this update scheme will not work in practice because it needs to store every input point to update the boundary vector; it also has an increasing time complexityO(t). Here, we propose two buffering strategies to use a small buffer of examples on each learning round. Denote that St⊆[t-1], and the example (xi,yi,σi) belongs to the buffer on round t if i∈St.(i)
Buffer-N. Let the buffer size be τ. τ-buffer replaces the oldest point xt-τ in the buffer with the new incoming point xt after each learning round, which means that St={t-τ,t-τ+1,…,t-1}.(ii)
Buffer-U. This buffering strategy replaces the oldest unlabeled point in the buffer with the incoming point while keeping labeled points. The oldest labeled point is evicted from the buffer only when it is filled with labeled points.Based on the previous analysis, the sub set of dual coefficientsIt can be chosen using the process in Algorithm 2.Algorithm 2:The process of getting It for example-associate update.
PROCESS:It=∅,
If1-〈ytxt,ωt-1〉>0, It=It∪{αt0}.
For eachi∈St
If-wti〈(xt-xi),ωt-1〉>0, It=It∪{αti1};
Ifwti〈(xt-xi),ωt-1〉>0, It=It∪{αti2}.
ReturnIt.Denoteρtmax as the maximal step size on round t. Since every dual coefficient belongs to [0,1], we have ρtmax=min{1/c1σt[1-〈ytxt,ωt-1〉]+, 1/2c2[-wti〈(xt-xi),ωt-1〉]+,  1/2c2[wti〈(xt-xi),ωt-1〉]+}, i∈St. The optimal step size ρt* is
(24)ρt*=〈∂D(αt-1)/∂It,∂D(αt-1)/∂It〉〈∂D(αt-1)/∂It,H(αt-1)(∂D(αt-1)/∂It)〉,
where H(αt-1) is the Hessian of D(αt-1) over It. Then, we obtain that if ρt∈[0,min{ρtmax,ρt*}], D(αt)≥D(αt-1).Combining (22) and (23), we have
(25)(αti1)t-(αti2)t=2c2ρt([-wti〈(xt-xi),ωt-1〉]+-[wti〈(xt-xi),ωt-1〉]+)=-2c2ρtwti〈(xt-xi),ωt-1〉.We also can rewrite the update process using the form of (19) as follows:
(26)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.
The new associate boundary vector is
(27)ωt=ωt-1+ρtc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).Algorithm3 shows an online MR algorithm based on EA update.Algorithm 3:Online manifold regularization algorithm based on EA update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive an example (xt,yt,σt),
Get It using the process in Algorithm 2,
Choose a step size ρt∈[0,min{ρtmax,ρt*}],
Update the boundary vector using (27),
If σt=0, predict yt^=sign(〈ωt,xt〉),
Renew the buffer.Specially, while choosing a small stationaryρ on each learning round, we must have D(αt)≥D(αt-1). In this condition, the update process of boundary vector can be written as
(28)ωt=ωt-1+ρc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
This update scheme is called ρ-EA update.For an aggressive gradient ascent, we can chooseρt=min{ρtmax,ρt*}, which is called aggressive-EA update.


## 4.2. Overall Update

In EA update scheme, we employ an additive way to update the boundary vector by updating the associated coefficients of the new training example. In fact, all the associated coefficients of arrived examples can be updated on each learning round. Here, we propose another new update scheme which is called overall update.Using EA update, the dual functionD(αt) on round t can be rewritten as
(29)D(αt)=-12({∑i=1t-1}ωt-1+c1(αt0)tσtytxt+∑i=1t-12c2((αti1)t-(αti2)t)wti(xt-xi))2+∑i=1tc1(αi0)tσi.
In fact, the dual coefficients in ωt-1 also can be updated in (28). Since ωt-1 has (t-1)2 dual coefficients, it is impossible to update them, respectively. We introduce a new variable ηt into (29), as
(30)D(αt)=-12({∑i=1t-1}(1-ηt)ωt-1+c1(αt0)tσtytxt+∑i=1t-12c2((αti1)t-(αti2)t)wti(xt-xi))2+(1-ηt)∑i=1t-1c1(αi0)t-1σi+c1(αt0)tσt.From (30), we can get that a gradient ascent update on ηt actually means to multiply all the dual coefficients in ωt-1 by 1-ηt. Since every dual coefficient in ωt-1 belongs to [0,1], we constrain ηt∈[0,1]. The initial value of ηt is zero. Using a gradient ascent on ηt, we obtain
(31)ηt=ρt[〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi]+.Therefore, we chooseIt∈{ηt,αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2} on each learning round for overall update. A buffering strategy also can be used in overall update, St⊆[t-1]. Like EA update, we propose a process to get It for overall update in Algorithm 4.Algorithm 4:The process of getting It for overall update.
PROCESS:It=∅,
If〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi>0,
It=It∪{ηt}.
If1-〈ytxt,ωt-1〉>0, It=It∪{αt0}.
For eachi∈St
If -wti〈(xt-xi),ωt-1〉>0, It=It∪{αti1};
If wti〈(xt-xi),ωt-1〉>0, It=It∪{αti2}.
ReturnIt.The gradient ascent for{αt0,αt11,αt12,…,αt(t-1)1,αt(t-1)2} is same as the EA update which has been shown in (21), (22), and (23). Combined with the constraint of ηt, the maximal step size for overall update is ρtmax=min{1/[〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi]+,   1/c1σt[1-〈ytxt,ωt-1〉]+,   1/2c2[-wti〈(xt-xi),ωt-1〉]+,    1/2c2[wti〈(xt-xi),ωt-1〉]+},i∈St. The optimal step size ρt* also can be obtained using (24). Obviously, if ρt∈[0,min{ρtmax,ρt*}], D(αt)≥D(αt-1). Rewriting the overall update process using the form of (19), we have
(32)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(1-ηt)(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.The new associate boundary vector is(33)ωt=(1-ηt)ωt-1+ρtc12σtyt[1-〈ytxt,ωt-1〉]+xt-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
Algorithm 5 shows the online MR algorithm based on overall update.Algorithm 5:Online manifold regularization algorithm based on overall update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive an example (xt,yt,σt),
Get It using the process in Algorithm 4,
Choose a step size ρt∈[0,min{ρtmax,ρt*}],
Update the boundary vector using (33),
If σt=0, predict yt^=sign(〈ωt,xt〉),
Renew the buffer.Like EA update, we also can deriveρ-overall update and aggressive-overall update from the previous analysis.


## 4.3. Two-Step Update

In the two update schemes aforementioned, we actually make an assumption that the elements of an example(xt,yt,σt) arrive at the same time. But in some practical applications, the label yt is received after receiving training point xt occasionally. There is no need to update the boundary vector after receiving all the elements of an example. Here, we propose a two-step update scheme.The two-step update scheme has twice updates on each learning round. The first update takes place after the training pointxt arrives which updates the boundary vector using the geometry of the training points. The second update takes place after yt,σt arrive which updates the boundary vector using the label. Obviously, EA update and overall update can be used in each update process of two-step update scheme. For example, we use EA update to describe the update process of two-step update scheme.Denote asαt-1/2 the coefficient vector after the first update on round t and ωt-1/2 its associate boundary. The example-associate coefficients in the first update on round t are αt11,αt12,…,αt(t-1)1,αt(t-1)2, and new associate boundary vector can be written as
(34)ωt-1/2=ωt-1+4ρt-1/2c22∑i∈Stwti2〈(xt-xi),ωt-1〉(xt-xi).
In the second update process, the example-associate coefficient is αt0, and new associate boundary vector is
(35)ωt=ωt-1/2+ρtc12σtyt[1-〈ytxt,ωt-1/2〉]+xt.
If σt=0, the second update process in (35) would not happen, and the two-step update degenerates into EA update. The range of ρt-1/2 and ρt can be obtained by the same process in Section 4.1. Similar as the previous analysis, the overall update also can be used in each update process of two-step update scheme.The online MR algorithm based on the two-step update can be described in Algorithm6.Algorithm 6:A template online manifold regularization algorithm based on two-step update.
INPUT: two positive scalars:c1 and c2; edge weights wij.
INITIALIZE: a coefficient vectorα0 and its associated decision boundary vector ω0.
PROCESS: Fort=1,2,…,T
Receive a training point xt,
Choose a new coefficient vector αt-(1/2) that satisfies D(αt-(1/2))≥D(αt-1),
Return a new associated boundary vector ωt-(1/2) in (18).
Receive yt,σt,
If σt=0, αt=αt-(1/2), ωt=ωt-(1/2), predict yt^=sign(〈ωt,xt〉);
Else if σt=1, choose a new coefficient vector αt that satisfies D(αt)≥D(αt-(1/2)), return a new associated
boundary vector ωt in (18).This update scheme is more like a new perspective of online MR problem, and its effect is influenced by the update schemes on each step. Therefore, we pay more attentions to the first two update schemes aforementioned in this paper.


## 5. Sparse Approximations for Kernel Representation

In practice, kernel functions are always used to find a linear classifier, like SVM. Our online MR framework contains the product of two points, so we can easily introduce the kernel function in our framework. If we noteK the kernel matrix such that
(36)Kij=Φ(xi)·Φ(xj),xi can be replaced by Φ(xi) in our framework. Therefore, we can rewrite (19) as
(37)ωt=∑i=1t(βi)tΦ(xi).
Unfortunately, the online MR algorithms with kernel functions in Section 4 have to store the example sequence up to the current round (worst case). While using a buffering strategy for online MR which has a buffer size of τ, the stored matrix size is τ×t and the time complexity is O(τ×t) on round t. For practical purpose, we present two approaches to construct a sparse kernel representation for boundary vector on each round.


### 5.1. Absolute Threshold

To construct a sparse representation for the boundary vector, absolute threshold discards the examples whose associated coefficients are close to zero (more details in Section7). Let ε>0 denote the absolute threshold. When the absolute value of the associated coefficient of an input example xi does not increase in further update process, xi will be discarded if |βi|<ε. The examples in the buffer cannot be discarded since the absolute values of their associated coefficients may increase in next rounds. The process of sparse approximation based on absolute threshold can be described in Algorithm 7.Algorithm 7:The process of sparse approximation based on absolute threshold. This process only deals with the examples which will not be updated in the further update process.
INPUT: the absolute thresholdε; the kernel representation of boundary on round t: ωt=∑i∈[t](βi)tΦ(xi),
PROCESS: For eachxi in ωt
If xi is not in the buffer and |(βi)t|<ε, discard the example xi and its associated coefficient (βi)t.
Return a new boundaryωt.The process of sparse approximation based on absolute threshold for different update schemes may be a little different in practical applications. For online MR algorithms with EA update, the coefficients of input examples which are not in the buffer will not change in further update process, and this sparse approximation process only deals with the example (xt-τ for Buffer-N) which is removed from the buffer on round t. For online MR algorithms with overall update, this sparse approximation process deals with all the examples which are not in the buffer on current round since the coefficients of these examples also can be changed. This approach may not work; if we are unlucky enough that all the |βi| are larger than ε on each round, the kernel representation of boundary vector will not become sparse at all.


### 5.2.k Maximal Coefficients (k-MC)

Another way to construct a sparse kernel representation is to keep the examples of which the absolute value of associated coefficients are the firstk maximum. This approach is called k maximal coefficients (k-MC) in this paper. Similar as the absolute threshold, k-MC does not discard the examples in the buffer of which absolute values of associated coefficients may increase in next round. The process of sparse approximation based on k-MC can be described in Algorithm 8.Algorithm 8:The process of sparse approximation based on k-MC. The kernel representation for ωt contains k+τ examples at most in this condition, where τ is the buffer size.
INPUT: the parameterk; the kernel representation of boundary on round t: ωt=∑i∈[t](βi)tΦ(xi),
PROCESS: For eachxi in ωt and not in the buffer
If (βi)t does not belong to the first k maximum of the coefficients, discard the example xi and its associated
coefficient (βi)t.
Return a new boundaryωt.While usingk-MC for online MR algorithms which has a buffer size of τ, the stored kernel matrix size is at most τ×(k+τ) and the time complexity is O(1) on each round.


## 5.1. Absolute Threshold

To construct a sparse representation for the boundary vector, absolute threshold discards the examples whose associated coefficients are close to zero (more details in Section7). Let ε>0 denote the absolute threshold. When the absolute value of the associated coefficient of an input example xi does not increase in further update process, xi will be discarded if |βi|<ε. The examples in the buffer cannot be discarded since the absolute values of their associated coefficients may increase in next rounds. The process of sparse approximation based on absolute threshold can be described in Algorithm 7.Algorithm 7:The process of sparse approximation based on absolute threshold. This process only deals with the examples which will not be updated in the further update process.
INPUT: the absolute thresholdε; the kernel representation of boundary on round t: ωt=∑i∈[t](βi)tΦ(xi),
PROCESS: For eachxi in ωt
If xi is not in the buffer and |(βi)t|<ε, discard the example xi and its associated coefficient (βi)t.
Return a new boundaryωt.The process of sparse approximation based on absolute threshold for different update schemes may be a little different in practical applications. For online MR algorithms with EA update, the coefficients of input examples which are not in the buffer will not change in further update process, and this sparse approximation process only deals with the example (xt-τ for Buffer-N) which is removed from the buffer on round t. For online MR algorithms with overall update, this sparse approximation process deals with all the examples which are not in the buffer on current round since the coefficients of these examples also can be changed. This approach may not work; if we are unlucky enough that all the |βi| are larger than ε on each round, the kernel representation of boundary vector will not become sparse at all.


## 5.2.k Maximal Coefficients (k-MC)

Another way to construct a sparse kernel representation is to keep the examples of which the absolute value of associated coefficients are the firstk maximum. This approach is called k maximal coefficients (k-MC) in this paper. Similar as the absolute threshold, k-MC does not discard the examples in the buffer of which absolute values of associated coefficients may increase in next round. The process of sparse approximation based on k-MC can be described in Algorithm 8.Algorithm 8:The process of sparse approximation based on k-MC. The kernel representation for ωt contains k+τ examples at most in this condition, where τ is the buffer size.
INPUT: the parameterk; the kernel representation of boundary on round t: ωt=∑i∈[t](βi)tΦ(xi),
PROCESS: For eachxi in ωt and not in the buffer
If (βi)t does not belong to the first k maximum of the coefficients, discard the example xi and its associated
coefficient (βi)t.
Return a new boundaryωt.While usingk-MC for online MR algorithms which has a buffer size of τ, the stored kernel matrix size is at most τ×(k+τ) and the time complexity is O(1) on each round.


## 6. On the Connection to Previous Work

### 6.1. About Dual Ascending Procedure

In the area of online learning, Shalev-Shwartz and Singer [13] propose a primal-dual perspective of online supervised learning algorithms. This work has the same dual ascending perspective as ours to achieve a better boundary vector. Different from it, we deal with an online MR problem of semisupervised learning, and our emphasis is how to construct a dual ascending model in semisupervised condition. An important conclusion in this paper is that the Fenchel conjugate of hinge functions is a key to transfer manifold regularization from offline to online, and this is also the reason why we use an absolute function to describe the difference between the predictions of two points.The primal basic MR problem can degenerate into a basic supervised learning problem [14] while choosing the trade-off parameter c2=0. Consider
(38)J(ω)=12ω2+∑t=1Tc1[1-yt〈ω,xt〉]+.
Then, the dual function degenerates into
(39)D(α)=D(α10,α20,…,αT0)=-12(∑t=1T(c1αt0ytxt))2+∑t=1T(c1αt0).
Equation (39) is the dual function of basic supervised learning problem which is carefully discussed in [13].


### 6.2. About Online Manifold Regularization

Goldberg et al. [11] propose an empirical study of online MR which deals with the MR problem as follow:
(40)J(ω)=12ω2+c1l∑t=1Tσt[1-yt〈ω,xt〉]++c22T∑i,j=1T(〈ω,xi〉-〈ω,xj〉)2wij,
where c1 and c2 are trade-off parameters and l is the number of labeled examples. Different from our framework, they use a square function to measure the difference between the predictions of two points (see Figure 2).Figure 2
Different functions to measure the difference of prediction of two examples. Standard MR uses a square function, while our online MR framework uses an absolute function which can be decomposed into two hinge functions.To avoid minimizing (40) directly, they further propose an instantaneous regularized riskJt(ω) empirically on round t. Consider
(41)Jt(ω)=12ω2+Tc1lσt[1-yt〈ω,xt〉]++c2∑i=1t-1(〈ω,xt〉-〈ω,xi〉)2wti.T/l is the reverse label probability 1/pl, which it assumes to be given and easily determined based on the rate at which humans can label the data at hand. In our work, we ignore this rate since it can be involved in the trade-off parameters c1 and c2.Based on the notion thatωt has a form as ωt=∑i=1tβixi, Goldberg et al. perform a gradient descent step over ω that aims to reduce the instantaneous risk Jt(ω) on each round. The update scheme can be written as
(42)(βt)t=ρtc1σtytTl[1-〈ytxt,ωt-1〉]++2ρtc2∑i=1t-1wti〈(xi-xt),ωt-1〉,(βi)t=(1-ρt)(βi)t-1-2ρtc2wti〈(xi-xt),ωt-1〉,i∈{1,2,…,t-1}.Furthermore, this work uses an annealing heuristic trick which chooses a decaying step sizeρt=γ/t, γ=0.1. This online MR algorithm is an empirical result which demonstrates its practicability by experiments and does not have enough theoretical analysis.Compared with previous work, our online MR framework reinterprets the online MR process based on the notion of ascending the dual function, and it also can be used to derive different online MR algorithms. Here, we demonstrate that the update scheme in (42) can be derived from our online MR framework.In Section4.2, the gradient direction d of overall update for ascending the dual function on round t can be written as
(43)d=[{∂D(αt-1)∂(αt(t-1)2)t-1}∂D(αt-1)∂(ηt)t-1,∂D(αt-1)∂(αt0)t-1,∂D(αt-1)∂(αt11)t-1,∂D(αt-1)∂(αt12)t-1,…,∂D(αt-1)∂(αt(t-1)1)t-1,∂D(αt-1)∂(αt(t-1)2)t-1].
While choosing
(44)d′=[{∂D(αt-1)∂(αt(t-1)2)t-1}1,∂D(αt-1)∂(αt0)t-1,∂D(αt-1)∂(αt11)t-1,∂D(αt-1)∂(αt12)t-1,…,∂D(αt-1)∂(αt(t-1)1)t-1,∂D(αt-1)∂(αt(t-1)2)t-1],
we have
(45)〈d,d′〉=∂D(αt-1)∂(ηt)t-1+(∂D(αt-1)∂(αt0)t-1)2+∑i=1t-1((∂D(αt-1)∂(αti1)t-1)2+(∂D(αt-1)∂(αti2)t-1)2).
If 〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi>0, we must have 〈d,d′〉>0 and d′ is a feasible ascending direction to make D(αt)≥D(αt-1). Using d′ to ascend the dual function, the update scheme can be written as
(46)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(1-ρt)(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.
Equations (42) and (46) are essentially the same update scheme with different trade-off parameters and edge weights.


## 6.1. About Dual Ascending Procedure

In the area of online learning, Shalev-Shwartz and Singer [13] propose a primal-dual perspective of online supervised learning algorithms. This work has the same dual ascending perspective as ours to achieve a better boundary vector. Different from it, we deal with an online MR problem of semisupervised learning, and our emphasis is how to construct a dual ascending model in semisupervised condition. An important conclusion in this paper is that the Fenchel conjugate of hinge functions is a key to transfer manifold regularization from offline to online, and this is also the reason why we use an absolute function to describe the difference between the predictions of two points.The primal basic MR problem can degenerate into a basic supervised learning problem [14] while choosing the trade-off parameter c2=0. Consider
(38)J(ω)=12ω2+∑t=1Tc1[1-yt〈ω,xt〉]+.
Then, the dual function degenerates into
(39)D(α)=D(α10,α20,…,αT0)=-12(∑t=1T(c1αt0ytxt))2+∑t=1T(c1αt0).
Equation (39) is the dual function of basic supervised learning problem which is carefully discussed in [13].


## 6.2. About Online Manifold Regularization

Goldberg et al. [11] propose an empirical study of online MR which deals with the MR problem as follow:
(40)J(ω)=12ω2+c1l∑t=1Tσt[1-yt〈ω,xt〉]++c22T∑i,j=1T(〈ω,xi〉-〈ω,xj〉)2wij,
where c1 and c2 are trade-off parameters and l is the number of labeled examples. Different from our framework, they use a square function to measure the difference between the predictions of two points (see Figure 2).Figure 2
Different functions to measure the difference of prediction of two examples. Standard MR uses a square function, while our online MR framework uses an absolute function which can be decomposed into two hinge functions.To avoid minimizing (40) directly, they further propose an instantaneous regularized riskJt(ω) empirically on round t. Consider
(41)Jt(ω)=12ω2+Tc1lσt[1-yt〈ω,xt〉]++c2∑i=1t-1(〈ω,xt〉-〈ω,xi〉)2wti.T/l is the reverse label probability 1/pl, which it assumes to be given and easily determined based on the rate at which humans can label the data at hand. In our work, we ignore this rate since it can be involved in the trade-off parameters c1 and c2.Based on the notion thatωt has a form as ωt=∑i=1tβixi, Goldberg et al. perform a gradient descent step over ω that aims to reduce the instantaneous risk Jt(ω) on each round. The update scheme can be written as
(42)(βt)t=ρtc1σtytTl[1-〈ytxt,ωt-1〉]++2ρtc2∑i=1t-1wti〈(xi-xt),ωt-1〉,(βi)t=(1-ρt)(βi)t-1-2ρtc2wti〈(xi-xt),ωt-1〉,i∈{1,2,…,t-1}.Furthermore, this work uses an annealing heuristic trick which chooses a decaying step sizeρt=γ/t, γ=0.1. This online MR algorithm is an empirical result which demonstrates its practicability by experiments and does not have enough theoretical analysis.Compared with previous work, our online MR framework reinterprets the online MR process based on the notion of ascending the dual function, and it also can be used to derive different online MR algorithms. Here, we demonstrate that the update scheme in (42) can be derived from our online MR framework.In Section4.2, the gradient direction d of overall update for ascending the dual function on round t can be written as
(43)d=[{∂D(αt-1)∂(αt(t-1)2)t-1}∂D(αt-1)∂(ηt)t-1,∂D(αt-1)∂(αt0)t-1,∂D(αt-1)∂(αt11)t-1,∂D(αt-1)∂(αt12)t-1,…,∂D(αt-1)∂(αt(t-1)1)t-1,∂D(αt-1)∂(αt(t-1)2)t-1].
While choosing
(44)d′=[{∂D(αt-1)∂(αt(t-1)2)t-1}1,∂D(αt-1)∂(αt0)t-1,∂D(αt-1)∂(αt11)t-1,∂D(αt-1)∂(αt12)t-1,…,∂D(αt-1)∂(αt(t-1)1)t-1,∂D(αt-1)∂(αt(t-1)2)t-1],
we have
(45)〈d,d′〉=∂D(αt-1)∂(ηt)t-1+(∂D(αt-1)∂(αt0)t-1)2+∑i=1t-1((∂D(αt-1)∂(αti1)t-1)2+(∂D(αt-1)∂(αti2)t-1)2).
If 〈ωt-1,ωt-1〉-∑i=1t-1c1(αi0)t-1σi>0, we must have 〈d,d′〉>0 and d′ is a feasible ascending direction to make D(αt)≥D(αt-1). Using d′ to ascend the dual function, the update scheme can be written as
(46)(βt)t=ρtc12σtyt[1-〈ytxt,ωt-1〉]+-4ρtc22∑i∈Stwti2〈(xt-xi),ωt-1〉,(βi)t=(1-ρt)(βi)t-1+4ρtc22wti2〈(xt-xi),ωt-1〉,i∈St.
Equations (42) and (46) are essentially the same update scheme with different trade-off parameters and edge weights.


## 7. Experiments and Analyses

This section presents a series of experimental results to report the effectiveness of our derived online MR algorithms. It is known that the performance of semisupervised learning depends on the correctness of model assumptions. Thus, our focus is on comparing different online MR algorithms, rather than different semisupervised regularization methods.


### 7.1. Datasets and Protocols

We report experimental results on two artificial and two real-world datasets in Table1 with different properties.Table 1
Different datasets in our experiments. These datasets have different properties which contain number of classes, dimensions, and size.
Dataset
Classes
Dims
Points
Two moons
2
2
4000
Two rotating spirals
2
2
8000
Isolet
2
617
3119
USPS
10
100
7191The artificial datasets consist of two-class problems. The generated method of two moons dataset is available athttp://manifold.cs.uchicago.edu/manifold_regularization/manifold.html; we set the radius of two moons to 4 and the width to 2, and only one example for each class is labeled in this dataset. To demonstrate that our online MR can handle concept drift, we also perform our experiments on two rotating spirals dataset of which 2% examples are labeled. Figure 3 shows that the spirals smoothly rotate 360° during the sequence, and the target boundary drifts with the sequence of examples.Figure 3
Two rotating spirals data sequence. We spin the two spirals dataset in top left during the sequence so that the spirals smoothly rotate 360° in every 8000 examples.The real-world datasets consist of two-class and multi-class problems. The Isolet dataset derives from the Isolet database of letters of the English alphabet spoken in isolation (available from the UCI machine learning repository). The database contains utterances of 150 subjects who spoke the name of each letter of the English alphabet twice. The speakers are grouped into 5 sets of 30 speakers each, referred to as isolet1 through isolet5. We considered the task of classifying the first 13 letters of the English alphabet from the last 13 only using isolet1 and isolet5 (1 utterance is missing in isolet5 due to poor recording). During the online MR process, all 52 utterances of one speaker are labeled and all the rest are left unlabeled. Our USPS dataset contains the USPS training set on handwritten digit recognition (preprocessed using PCA to 100 dimensions), and we apply online MR algorithms to 45 binary classification problems that arise in pairwise classification; 5 examples are randomly labeled for each class.Our experimental protocols are as the following.(1)
The training sequences are generated randomly from each datasets (except for two rotating spirals).(2)
The offline MR algorithm for comparison is a state-of-the-art semisupervised learning algorithm based on manifold regularization which is called LapSVM [12].(3)
Each example in each dataset is trained once during online MR process.To avoid the influence of different training sequences, all results on each dataset are the average of five such trials except for two rotating spirals (this idea is inspired by [11]). The error bars are ±1 standard deviation.All methods use the standard RBF kernelK(xi,xj)=e-∥xi-xj∥2/2(σK)2. The edge weights are Gaussian weights which define a fully connected graph, and the edge weight parameter is σ. For online MR algorithms comparisons, we choose Buffer-N with τ=200 to avoid high computational complexity. We implemented all the experiments using MATLAB.


### 7.2. Computational Complexity

For offline MR, at×t kernel matrix needs to be stored and inverted on round t, and the time complexity approximately amounts to O(t3) if using a gradient descent algorithm. Different from it, the computational complexity of our online MR algorithms is determined by the buffer size τ and the number of examples in the kernel representation of boundary vector on each round.For our online MR without buffering strategies and sparse approximation approaches, the number of examples in the kernel representation ist, and the time complexity is O(t2). While using a buffering strategy for online MR which has a buffer size of τ, the time complexity reduces to O(τ×t), but the number of examples in the kernel representation is still t. In practice, only part of the examples have to be stored (and computed) based on the sparse approximation. Figure 4 shows the number of examples in the kernel representation of boundary vector on each learning round for different sparse approximation approaches.Figure 4
The number of examples in the kernel representation of boundary vector for different sparse approximation approaches. This experiment is on the two moons dataset which has 4000 examples. If no sparse representation approaches are used in the online MR, the kernel representation contains all the input examples. The number of examples in the kernel representation of boundary vector increases slowly while using an absolute threshold, and the number is at most(k+τ) while using k-MC for online MR algorithms.We also compare cumulative runtime curves of five different MR algorithms on the two moons and Isolet datasets. The first one is basic online MR which only usesρ-EA update, but no buffering strategies and sparse approximation approaches. The second one is online MR which uses ρ-EA update and Buffer-N (τ=200). The third one is online MR which uses ρ-EA update, Buffer-N (τ=200), and an absolute threshold ε=0.001. The fourth is online MR which uses ρ-EA update, Buffer-N (τ=200), and k-MC (k=400). The last one uses offline MR (LapSVM) on each round. Figure 5 shows that online MR with buffering strategies and sparse representation performs better than basic online MR and offline MR on the runtime growth rate. Online MR algorithms without buffering strategies and sparse approximation approaches are time consuming and memory consuming, and it is intractable to apply them to real-world long time tasks.Cumulative runtime growth curves. (a) Experiments on two moons dataset, we generate a dataset which contains 4000 examples. (b) Experiments on Isolet dataset, this dataset has a high dimension. The curves have the similar trends on different datasets. Online MR algorithms with buffering strategies and sparse representation perform better than the others on the growth rate.
(a)
(b)The cumulative runtime growth curves of online MR with buffering strategies and sparse approximation approaches scale only linearly, while the others scale quadratically.


### 7.3. Accuracies

We used the same model selection strategy both for our online MR framework and traditional offline MR algorithms.Based on the idea of “interested in the best performance and simply select the parameter values minimizing the error” [15], we select combinations of the parameter values on a finite grid in Table 2, and it is sufficient to perform algorithm comparisons.Table 2
A finite grid of parameter values. We find the best performance of each online MR algorithm on this finite grid.
Parameter
Values
RBF widthσK
2
-
3
,
2
-
2
,
2
-
1
,
2
0
,
2
1
,
2
2
,
2
3
Edge weight parameterσ
2
-
3
,
2
-
2
,
2
-
1
,
2
0
,
2
1
,
2
2
,
2
3
Penaltyc1
10
-
3
,
10
-
2
,
10
-
1
,
10
0
,
10
1
,
10
2
,
10
3
Penaltyc2
10
-
3
,
10
-
2
,
10
-
1
,
10
0
,
10
1
,
10
2
,
10
3While choosing an update scheme based on our online MR framework, we still have to select a step sizeρt on each learning round. We report the online MR error rate for three scenarios in this paper.(i)
Stationary step sizeρt=0.1.(ii)
Aggressive step sizeρt=min{ρtmax,ρt*}.(iii)
Decreasing step sizeρt=0.1/t, which is also used in [11].The best performances of all the online MR algorithms are presented in Table3 and Figure 6. The following sections provide more additional details.Table 3
Mean test error rates on different datasets. The error rates are reported for three different step size selection methods in the form of stationary step size/aggressive step size/decreasing step size. The result shows that our derived online MR algorithms achieve test accuracy comparable to offline MR. Specially, the experiments on two rotating spirals show that our online MR is able to track the changes in the sequence and maintain a much better error rate compared to offline MR. The performances of online MR algorithms are competitive with those of the state-of-the-art offline MR.
Two moons
Two rotating spirals
Isolet
Offline MR
LapSVM
0
50
19.87
Online MR
EA update
2.60/6.75/11.92
2.45/13.31/46.45
20.13/31.15/26.60
Overall update
3.43/8.40/10.80
0/0/19.50
20.38/31.22/24.36Mean test error rates for 45 binary classification problems on USPS dataset. The results show that the online MR with an aggressive step size does not perform well on this dataset, and the others achieve test accuracies that are comparable to LapSVM.
(a)
(b)


### 7.4. Additional Results

We now provide some additional results along the online MR algorithms run and discuss more precisely the effect of our derived online MR algorithms.


#### 7.4.1. Effect of the ParametersσK, c1, c2 and the Step Size ρ

The parametersσK, c1 and c2 have similar effects on generalization as in the purely offline MR approach (see [12] for an empirical study). However, one has to try many choices of parameters during the model selection. The manifold regularizer incorporates unlabeled examples and causes the decision vector to appropriately adjust according to the geometry of training examples as c2 is increased. If c2=0, the unlabeled examples are disregarded and online MR degenerates into online supervised learning.The step sizeρt controls the increment of dual function D(α) on each learning round. We used three different step size selection methods for algorithm comparisons in last section. Here, we discuss the effect of different step size selection methods.Stationary Step Size. Under mild conditions, this seemingly naive step size selection method has acceptable error rates on any input sequence. Figure 7 shows that a large stationary step size does not perform well in online MR algorithms. When one wishes to avoid optimizing the step size on each learning round, we suggest the stationary step size with a small value.Error rates using different stationary step sizes. The parametersσK, c1, c2 in this experiment are all tuned for online MR algorithm using EA update and ρt=0.1. The result implies that large step sizes lead to poor accuracies comparable to small ones.
(a)
(b)Aggressive Step Size. Since online MR algorithms adjust the boundary according to the local geometry of the incoming point and its label, the aggressive step size selection method aims to search for the optimal step size to increase the dual function more aggressively on each learning round. The experiments in Table 3 and Figure 6 imply that the aggressive selection method does not perform well on all the sequences.Decreasing Step Size. This step size selection method is based on an idea that the boundary vector is approaching the optimal boundary as the online MR algorithms run. This selection method performs well on the datasets whose target boundaries are fixed, but the experiments on the two spirals dataset show that it does not perform well for drifting target boundaries.


#### 7.4.2. Increasing Dual FunctionD(α) Achieves Comparable Risks and Error Rates

We compare the primal objective functionJ(ωt) versus the dual function D(αt) on the training sequence of two moons dataset as t increases. Figure 8 shows that the two curves approach each other along the online MR process using EA update (ρt=0.1). The value of dual function D(αt) never decreases as t increases; correspondingly, the curve of primal function J(ωt) has a downward trend and some little fluctuations. Our experiments support the theory in Section 3 that increasing the dual problem achieves comparable risks of primal MR problem.Figure 8
The value curves of the primal objective functionJ(ωt) and the dual function D(αt). The two curves approach each other as t increases.We also report the performance ofωt on the whole dataset in Figure 9. This result shows that the decision boundary is adjusted to be a better one along the online MR process. Since online MR adjusts the decision boundary according to the label of the incoming example and the local geometry of the buffer on each learning round, the error rate of ωt on the whole dataset is not always decreasing along the online MR process. It is also the reason why online MR can track the changes in the data sequence.Figure 9
Error rates ofωt on the whole two moons dataset. The error rate of ωt has a downward trend, but it is not always decreasing along the online MR process.


#### 7.4.3. Online MR Handles Concept Drift

When the underlying distributions, bothP(x) and P(y∣x), change during the course of learning, the algorithms are expected to track the changes in the data sequence. In the two rotating spirals dataset, the points will change their true labels during the sequence and every stationary boundary vector will have an error rate of 50%.We show the error rates of basic online MR versus online MR (Buffer-N) with different buffer sizes in Figure 10. This experiment illustrates that a suitable buffer size is able to adapt to the changing sequence and maintain a small error rate.Figure 10
Error rates with different buffer sizes on two spirals data sequence. The buffer size can affect the capability of online MR to track the changes in the data sequence.


## 7.1. Datasets and Protocols

We report experimental results on two artificial and two real-world datasets in Table1 with different properties.Table 1
Different datasets in our experiments. These datasets have different properties which contain number of classes, dimensions, and size.
Dataset
Classes
Dims
Points
Two moons
2
2
4000
Two rotating spirals
2
2
8000
Isolet
2
617
3119
USPS
10
100
7191The artificial datasets consist of two-class problems. The generated method of two moons dataset is available athttp://manifold.cs.uchicago.edu/manifold_regularization/manifold.html; we set the radius of two moons to 4 and the width to 2, and only one example for each class is labeled in this dataset. To demonstrate that our online MR can handle concept drift, we also perform our experiments on two rotating spirals dataset of which 2% examples are labeled. Figure 3 shows that the spirals smoothly rotate 360° during the sequence, and the target boundary drifts with the sequence of examples.Figure 3
Two rotating spirals data sequence. We spin the two spirals dataset in top left during the sequence so that the spirals smoothly rotate 360° in every 8000 examples.The real-world datasets consist of two-class and multi-class problems. The Isolet dataset derives from the Isolet database of letters of the English alphabet spoken in isolation (available from the UCI machine learning repository). The database contains utterances of 150 subjects who spoke the name of each letter of the English alphabet twice. The speakers are grouped into 5 sets of 30 speakers each, referred to as isolet1 through isolet5. We considered the task of classifying the first 13 letters of the English alphabet from the last 13 only using isolet1 and isolet5 (1 utterance is missing in isolet5 due to poor recording). During the online MR process, all 52 utterances of one speaker are labeled and all the rest are left unlabeled. Our USPS dataset contains the USPS training set on handwritten digit recognition (preprocessed using PCA to 100 dimensions), and we apply online MR algorithms to 45 binary classification problems that arise in pairwise classification; 5 examples are randomly labeled for each class.Our experimental protocols are as the following.(1)
The training sequences are generated randomly from each datasets (except for two rotating spirals).(2)
The offline MR algorithm for comparison is a state-of-the-art semisupervised learning algorithm based on manifold regularization which is called LapSVM [12].(3)
Each example in each dataset is trained once during online MR process.To avoid the influence of different training sequences, all results on each dataset are the average of five such trials except for two rotating spirals (this idea is inspired by [11]). The error bars are ±1 standard deviation.All methods use the standard RBF kernelK(xi,xj)=e-∥xi-xj∥2/2(σK)2. The edge weights are Gaussian weights which define a fully connected graph, and the edge weight parameter is σ. For online MR algorithms comparisons, we choose Buffer-N with τ=200 to avoid high computational complexity. We implemented all the experiments using MATLAB.


## 7.2. Computational Complexity

For offline MR, at×t kernel matrix needs to be stored and inverted on round t, and the time complexity approximately amounts to O(t3) if using a gradient descent algorithm. Different from it, the computational complexity of our online MR algorithms is determined by the buffer size τ and the number of examples in the kernel representation of boundary vector on each round.For our online MR without buffering strategies and sparse approximation approaches, the number of examples in the kernel representation ist, and the time complexity is O(t2). While using a buffering strategy for online MR which has a buffer size of τ, the time complexity reduces to O(τ×t), but the number of examples in the kernel representation is still t. In practice, only part of the examples have to be stored (and computed) based on the sparse approximation. Figure 4 shows the number of examples in the kernel representation of boundary vector on each learning round for different sparse approximation approaches.Figure 4
The number of examples in the kernel representation of boundary vector for different sparse approximation approaches. This experiment is on the two moons dataset which has 4000 examples. If no sparse representation approaches are used in the online MR, the kernel representation contains all the input examples. The number of examples in the kernel representation of boundary vector increases slowly while using an absolute threshold, and the number is at most(k+τ) while using k-MC for online MR algorithms.We also compare cumulative runtime curves of five different MR algorithms on the two moons and Isolet datasets. The first one is basic online MR which only usesρ-EA update, but no buffering strategies and sparse approximation approaches. The second one is online MR which uses ρ-EA update and Buffer-N (τ=200). The third one is online MR which uses ρ-EA update, Buffer-N (τ=200), and an absolute threshold ε=0.001. The fourth is online MR which uses ρ-EA update, Buffer-N (τ=200), and k-MC (k=400). The last one uses offline MR (LapSVM) on each round. Figure 5 shows that online MR with buffering strategies and sparse representation performs better than basic online MR and offline MR on the runtime growth rate. Online MR algorithms without buffering strategies and sparse approximation approaches are time consuming and memory consuming, and it is intractable to apply them to real-world long time tasks.Cumulative runtime growth curves. (a) Experiments on two moons dataset, we generate a dataset which contains 4000 examples. (b) Experiments on Isolet dataset, this dataset has a high dimension. The curves have the similar trends on different datasets. Online MR algorithms with buffering strategies and sparse representation perform better than the others on the growth rate.
(a)
(b)The cumulative runtime growth curves of online MR with buffering strategies and sparse approximation approaches scale only linearly, while the others scale quadratically.


## 7.3. Accuracies

We used the same model selection strategy both for our online MR framework and traditional offline MR algorithms.Based on the idea of “interested in the best performance and simply select the parameter values minimizing the error” [15], we select combinations of the parameter values on a finite grid in Table 2, and it is sufficient to perform algorithm comparisons.Table 2
A finite grid of parameter values. We find the best performance of each online MR algorithm on this finite grid.
Parameter
Values
RBF widthσK
2
-
3
,
2
-
2
,
2
-
1
,
2
0
,
2
1
,
2
2
,
2
3
Edge weight parameterσ
2
-
3
,
2
-
2
,
2
-
1
,
2
0
,
2
1
,
2
2
,
2
3
Penaltyc1
10
-
3
,
10
-
2
,
10
-
1
,
10
0
,
10
1
,
10
2
,
10
3
Penaltyc2
10
-
3
,
10
-
2
,
10
-
1
,
10
0
,
10
1
,
10
2
,
10
3While choosing an update scheme based on our online MR framework, we still have to select a step sizeρt on each learning round. We report the online MR error rate for three scenarios in this paper.(i)
Stationary step sizeρt=0.1.(ii)
Aggressive step sizeρt=min{ρtmax,ρt*}.(iii)
Decreasing step sizeρt=0.1/t, which is also used in [11].The best performances of all the online MR algorithms are presented in Table3 and Figure 6. The following sections provide more additional details.Table 3
Mean test error rates on different datasets. The error rates are reported for three different step size selection methods in the form of stationary step size/aggressive step size/decreasing step size. The result shows that our derived online MR algorithms achieve test accuracy comparable to offline MR. Specially, the experiments on two rotating spirals show that our online MR is able to track the changes in the sequence and maintain a much better error rate compared to offline MR. The performances of online MR algorithms are competitive with those of the state-of-the-art offline MR.
Two moons
Two rotating spirals
Isolet
Offline MR
LapSVM
0
50
19.87
Online MR
EA update
2.60/6.75/11.92
2.45/13.31/46.45
20.13/31.15/26.60
Overall update
3.43/8.40/10.80
0/0/19.50
20.38/31.22/24.36Mean test error rates for 45 binary classification problems on USPS dataset. The results show that the online MR with an aggressive step size does not perform well on this dataset, and the others achieve test accuracies that are comparable to LapSVM.
(a)
(b)


## 7.4. Additional Results

We now provide some additional results along the online MR algorithms run and discuss more precisely the effect of our derived online MR algorithms.


### 7.4.1. Effect of the ParametersσK, c1, c2 and the Step Size ρ

The parametersσK, c1 and c2 have similar effects on generalization as in the purely offline MR approach (see [12] for an empirical study). However, one has to try many choices of parameters during the model selection. The manifold regularizer incorporates unlabeled examples and causes the decision vector to appropriately adjust according to the geometry of training examples as c2 is increased. If c2=0, the unlabeled examples are disregarded and online MR degenerates into online supervised learning.The step sizeρt controls the increment of dual function D(α) on each learning round. We used three different step size selection methods for algorithm comparisons in last section. Here, we discuss the effect of different step size selection methods.Stationary Step Size. Under mild conditions, this seemingly naive step size selection method has acceptable error rates on any input sequence. Figure 7 shows that a large stationary step size does not perform well in online MR algorithms. When one wishes to avoid optimizing the step size on each learning round, we suggest the stationary step size with a small value.Error rates using different stationary step sizes. The parametersσK, c1, c2 in this experiment are all tuned for online MR algorithm using EA update and ρt=0.1. The result implies that large step sizes lead to poor accuracies comparable to small ones.
(a)
(b)Aggressive Step Size. Since online MR algorithms adjust the boundary according to the local geometry of the incoming point and its label, the aggressive step size selection method aims to search for the optimal step size to increase the dual function more aggressively on each learning round. The experiments in Table 3 and Figure 6 imply that the aggressive selection method does not perform well on all the sequences.Decreasing Step Size. This step size selection method is based on an idea that the boundary vector is approaching the optimal boundary as the online MR algorithms run. This selection method performs well on the datasets whose target boundaries are fixed, but the experiments on the two spirals dataset show that it does not perform well for drifting target boundaries.


### 7.4.2. Increasing Dual FunctionD(α) Achieves Comparable Risks and Error Rates

We compare the primal objective functionJ(ωt) versus the dual function D(αt) on the training sequence of two moons dataset as t increases. Figure 8 shows that the two curves approach each other along the online MR process using EA update (ρt=0.1). The value of dual function D(αt) never decreases as t increases; correspondingly, the curve of primal function J(ωt) has a downward trend and some little fluctuations. Our experiments support the theory in Section 3 that increasing the dual problem achieves comparable risks of primal MR problem.Figure 8
The value curves of the primal objective functionJ(ωt) and the dual function D(αt). The two curves approach each other as t increases.We also report the performance ofωt on the whole dataset in Figure 9. This result shows that the decision boundary is adjusted to be a better one along the online MR process. Since online MR adjusts the decision boundary according to the label of the incoming example and the local geometry of the buffer on each learning round, the error rate of ωt on the whole dataset is not always decreasing along the online MR process. It is also the reason why online MR can track the changes in the data sequence.Figure 9
Error rates ofωt on the whole two moons dataset. The error rate of ωt has a downward trend, but it is not always decreasing along the online MR process.


### 7.4.3. Online MR Handles Concept Drift

When the underlying distributions, bothP(x) and P(y∣x), change during the course of learning, the algorithms are expected to track the changes in the data sequence. In the two rotating spirals dataset, the points will change their true labels during the sequence and every stationary boundary vector will have an error rate of 50%.We show the error rates of basic online MR versus online MR (Buffer-N) with different buffer sizes in Figure 10. This experiment illustrates that a suitable buffer size is able to adapt to the changing sequence and maintain a small error rate.Figure 10
Error rates with different buffer sizes on two spirals data sequence. The buffer size can affect the capability of online MR to track the changes in the data sequence.


## 7.4.1. Effect of the ParametersσK, c1, c2 and the Step Size ρ

The parametersσK, c1 and c2 have similar effects on generalization as in the purely offline MR approach (see [12] for an empirical study). However, one has to try many choices of parameters during the model selection. The manifold regularizer incorporates unlabeled examples and causes the decision vector to appropriately adjust according to the geometry of training examples as c2 is increased. If c2=0, the unlabeled examples are disregarded and online MR degenerates into online supervised learning.The step sizeρt controls the increment of dual function D(α) on each learning round. We used three different step size selection methods for algorithm comparisons in last section. Here, we discuss the effect of different step size selection methods.Stationary Step Size. Under mild conditions, this seemingly naive step size selection method has acceptable error rates on any input sequence. Figure 7 shows that a large stationary step size does not perform well in online MR algorithms. When one wishes to avoid optimizing the step size on each learning round, we suggest the stationary step size with a small value.Error rates using different stationary step sizes. The parametersσK, c1, c2 in this experiment are all tuned for online MR algorithm using EA update and ρt=0.1. The result implies that large step sizes lead to poor accuracies comparable to small ones.
(a)
(b)Aggressive Step Size. Since online MR algorithms adjust the boundary according to the local geometry of the incoming point and its label, the aggressive step size selection method aims to search for the optimal step size to increase the dual function more aggressively on each learning round. The experiments in Table 3 and Figure 6 imply that the aggressive selection method does not perform well on all the sequences.Decreasing Step Size. This step size selection method is based on an idea that the boundary vector is approaching the optimal boundary as the online MR algorithms run. This selection method performs well on the datasets whose target boundaries are fixed, but the experiments on the two spirals dataset show that it does not perform well for drifting target boundaries.


## 7.4.2. Increasing Dual FunctionD(α) Achieves Comparable Risks and Error Rates

We compare the primal objective functionJ(ωt) versus the dual function D(αt) on the training sequence of two moons dataset as t increases. Figure 8 shows that the two curves approach each other along the online MR process using EA update (ρt=0.1). The value of dual function D(αt) never decreases as t increases; correspondingly, the curve of primal function J(ωt) has a downward trend and some little fluctuations. Our experiments support the theory in Section 3 that increasing the dual problem achieves comparable risks of primal MR problem.Figure 8
The value curves of the primal objective functionJ(ωt) and the dual function D(αt). The two curves approach each other as t increases.We also report the performance ofωt on the whole dataset in Figure 9. This result shows that the decision boundary is adjusted to be a better one along the online MR process. Since online MR adjusts the decision boundary according to the label of the incoming example and the local geometry of the buffer on each learning round, the error rate of ωt on the whole dataset is not always decreasing along the online MR process. It is also the reason why online MR can track the changes in the data sequence.Figure 9
Error rates ofωt on the whole two moons dataset. The error rate of ωt has a downward trend, but it is not always decreasing along the online MR process.


## 7.4.3. Online MR Handles Concept Drift

When the underlying distributions, bothP(x) and P(y∣x), change during the course of learning, the algorithms are expected to track the changes in the data sequence. In the two rotating spirals dataset, the points will change their true labels during the sequence and every stationary boundary vector will have an error rate of 50%.We show the error rates of basic online MR versus online MR (Buffer-N) with different buffer sizes in Figure 10. This experiment illustrates that a suitable buffer size is able to adapt to the changing sequence and maintain a small error rate.Figure 10
Error rates with different buffer sizes on two spirals data sequence. The buffer size can affect the capability of online MR to track the changes in the data sequence.


## 8. Conclusion and Future Directions

In this paper we presented an online manifold regularization framework based on dual ascending procedure. To ascend the dual function, we proposed three schemes to update the boundary on each learning rounds. Unfortunately, the basic online MR algorithms are time consuming and memory consuming. Therefore, we also applied buffering strategies and sparse approximation approaches to make online MR algorithms practical. Experiments show that our online MR algorithms can adjust the boundary vector with the input sequence and have risk and error rates comparable to offline MR. Specially, our online MR algorithms can handle the settings where the target boundary is not fixed but rather drifts with the sequence of examples.There are many interesting questions remaining in the online semisupervised learning setting. For instance, we plan to study new online learning algorithms for other semisupervised regularizers those, in particular that with non-convex risks for unlabeled examples like S3VMs. Another direction is how to choose more effective parameters intelligently during the model selection.



---

*Source: 838439-2013-07-02.xml*