情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

行と列の生成による線形計画ブースティング
Linear Programming Boosting by Column and Row Generation
畑埜 晃平∗
Kohei Hatano

瀧本 英二†
Eiji Takimoto

Abstract: We propose a new boosting algorithm based on a linear programming formulation. Our algorithm can take advantage of the sparsity of the solution of the underlying
optimization problem. In preliminary experiments, our algorithm outperforms a state-ofthe-art LP solver and LPBoost especially when the solution is given by a small set of
relevant hypotheses and support vectors.
Keywords: ブースティング，ソフトマージン，線形計画法

1

はじめに
近年，機械学習や関連分野において踈な分類器が注目を集めている．例えばテキスト分類においては，特徴のサイズが１０万以上になるがそのうち重要な特徴はほんのごく一部となるとなることがある．このような場合，
踈な分類器は分類だけでなく特徴選択にも有効である．
踈な分類器を学習する主なアプローチとして，1 ソ
フトマージン最適化問題として定式化する方法が挙げられる．この問題では，マージンを大きくするような線形分類器を重みの 1 ノルムを正則化することによって求める．マージンを用いた一般化誤差の研究によって，
このアプローチは分類において頑健であることが保証されている [12, 5]．また，近年，1 ソフトマージン最適化問題は類似性指標を用いた学習にも応用されている [6, 8, 1, 14]．

1 ソフトマージン最適化問題は線形計画問題である
ため，シンプレックス法や内点法など標準的な最適化手法によって解くことが可能である．しかし，特徴や例のサイズが１万以上の場合，多大な計算時間を要することがある．

LPBoost は Demiriz らによって提案されたよく知られたブースティング手法であり，1 ソフトマージン最∗ 九州大学大学院システム情報科学研究院情報学部門, 〒 819-0395

福岡市西区元岡 744, tel. 092-802-3787, e-mail hatano@i.kyushuu.ac.jp,
Department of Informatics, Kyushu University, 744 Motooka,
Nishi-ku, Fukuoka, Japan† 九州大学大学院システム情報科学研究院情報学部門, 〒 8190395 福岡市西区元岡 744, tel. 092-802-3782, e-mail eiji@i.kyushuu.ac.jp
Department of Informatics, Kyushu University, 744 Motooka,
Nishi-ku, Fukuoka, Japan

適化問題を解くように設計されている [5]．LPBoost におけるブースティングの繰り返し回数の上限は知られておらず，また，最悪時の繰り返し回数の下界は他のブースティング手法よりも指数的に悪いことがわかっているものの（後述），実際多くの場合十分に高速である（LPBoost のハードマージン最適化問題に関する初期の結果については [7] が知られている）．
定義域 X 上 の m 個のラベル付き事例 (x1 , y1 ), . . . ,(xm , ym ) (xi ∈ X , yi ∈ {−1, +1}) と n 個の仮説（特徴）h1 , . . . , hn (hj : X → [−1, +1]) が与えられたとする. 直接ソフトマージン最適化問題を解く代わりに，LPBoostは以下の操作を繰り返す：(1) 各繰り返し t において，事
例上の現在の分布 dt に対してよい仮説

ht を見つける．(2) 仮説の集合を {h1 , . . . , ht } に制限した 小さな
ソフトマージン最適化問題を解くことによって次の分布

dt+1 を構成する．最終的な仮説は過去に選ばれた仮説の線形結合である，ただし，各仮説の係数は最後に解いた
小さな ソフトマージン最適化問題のラグランジュ乗数
によって与えられる．ここで，m×n の行列を考える. 行
列の各成分は uij = yi h(xi ) (i = 1, . . . , m, j = 1, . . . , n)とする. ここで，各行が事例に，各列が仮説に対応している．この行列は 1 ソフトマージン最適化問題の制約行列を表しており，行列の視点から見れば，LPBoost は列を生成しながら線形計画問題を繰り返し解いていることになる．実際，LPBoost は Column Generation [11]と呼ばれる最適化手法における古典的なテクニックを用いた線形計画問題の解法と見なすこともできる.
しかしながら，LPBoost は問題の疎性を十分に活かしきれていない．実際，1 ソフトマージン最適化問題には２種類の疎性がある．最初の疎性は仮説間に現れる．

仮説のみが非は X に属し，各ラベル yi は −1 または +1 の値をとる

負の係数を持つ．そして，もう１つの疎性は事例間に現とする (i = 1, . . . , m)．仮説の集合を H とする，ただし，れる．より正確には，いくつかの事例（しば各仮説 h ∈ H は事例の空間 X から [−1, +1] への関数とも呼ばれる）だけが，最とする．自然数 k に対して，P k を k 次元の確率分布の
k集合，つまり，P k = {p ∈ [0, 1]k :i=1 pi = 1} とおすなわち，最適解においては，

しばサポートベクター

重要な重要な適解に影響し, それら以外の事例を取り除いても最適解は変化しない．
本稿では，我々は仮説間と事例間の両方の疎性を利用

く．仮説の（正規化された）重み付け α ∈ P n に対する
n
ラベル付き事例 (x, y) のマージンを yi j=1 αj hj (xi )Sparse LPBoost は行と列の両方を生成するアプローチと定義する．事例の集合上の分布 d ∈ P m に対する仮m説 h ∈ H のエッジを i=1 yi di h(xi ) と定義し，γd (h)を取る．Sparse LPBoost はと表記する．

した新しいブースティング手法を提案する．本提案手法
重要そうな

列（仮説）

と行（事例）を選択しながら線形計画問題を繰り返し解
く．我々は，精度パラメータ ε > 0 が与えられたとき，

Sparse LPBoost はソフトマージンが γ ∗ − ε以上であるような仮説の線形結合を出力することを示す，ここ2.1

1 ソフトマージン最適化問題

1 ソフトマージン最適化問題は以下のように定式化される（例えば，[5, 16] など参照）．

で，γ ∗ は最適なソフトマージンである．
m1
max ρ −
ξi
ν i=1
ρ,α,ξ

本稿では，人工データおよび実データにおける準備的な実験において，Sparse LPBoost が，従来手法である
線形計画ソルバや LPBoost よりも 1 ソフトマージン
最適化問題をより高速に解くことを示す．特に，事例やyi

仮説の総数が１万以上であるような大規模なデータにお(1)

sub.toαj hj (xi ) ≥ ρ − ξi (i = 1, . . . , m),j

いて，Sparse LPBoost は他の手法に比べて数倍以上のα ∈ P n , ξ ≥ 0,

高速化を達成した．
いくつかの関連研究を挙げておく．Warmuth らは En-

tropy Regularized LPBoost [16] と呼ばれる LPBoost のmin γ

改良版を提案している．Entropy Regularized LPBoostγ,dも 1 ソフトマージン最適化問題を近似的に解くことが可能であり，繰返し回数 O(log(m/ν)/ε2 ) で実行できる
ことが示されている．一方，LPBoost の繰り返し回数のγd (hj ) =(2)

sub.todi yi hj (xi ) ≤ γ (j = 1, . . . , n),i

最悪時の下界は Ω(m) であることも知られている [15]．

d≤この手法も LPBoost と同様，仮説間の疎性を利用して

1
1, d ∈ P m ,ν

いる．

Mangasarian [10] や Sra [13] の手法は元の線形計画
問題を目的関数に２次の項を加えることにより，２次計画問題に変換しそれぞれニュートン法や Bregman 法 [3]を用いて解を求める．彼らの手法は仮説間，事例間のいずれの疎性も利用していない．

Bradley と Mangasarian [2] は，本手法と同様に，元の線形計画問題をより小さな問題に分解して解く手法を提案している．しかしながら，この手法は LPBoost と同様に行（仮説）だけを生成する．
以上，いずれの既存手法も，本手法のように事例間，仮説間両方の疎性を利用しているわけではない．

2

準備
事例の空間を X とする．与えられた事例の集合を

S = ((x1 , y1 ), . . . , (xm , ym )) とする，ここで，各事例 x

ただし主問題は (1) ，双対問題は (2) でそれぞれ表される．これらの問題は線形計画問題であり，主問題 (1) の最適解を (ρ∗ , α∗ , ξ∗ )，双対問題 (2) の最適解を (γ ∗ , d∗ )mとすると，双対性により，ρ∗ − ν1 i=1 ξi∗ = γ ∗ となることが知られている．また，本稿ではそれぞれの目的関数項をソフトマージンと呼ぶことにする．
注目すべき最適解の性質は疎ということである．KKT
条件により，最適解は次のような性質を満たす．

⎛
d∗i ⎝yijd∗i ≥ 0, yi⎞
α∗j hj (xi ) − ρ∗ + ξi∗ ⎠ = 0 (i = 1, . . . , m).
α∗j hj (xi ) − ρ∗ + ξi∗ ≥ 0 (i = 1, . . . , m).

jξi∗ (1/ν − d∗i ) = 0,ξi∗ ≥ 0, d∗i ≤ 1/ν (i = 1, . . . , m).

この性質から，以下が成り立つ．

• yi

Algorithm 1 LPBoost(S,ε)



∗
∗
∗
j αj hj (xi ) > ρ ならば，di = 0．

• 0 < d∗i < 1/ν n ならば，yi∗∗j αj hj (xi ) = ρ ．

• ξi∗ > 0 ならば，d∗i = 1/ν.

1. d1 を事例の集合 S 上の一様分布とする．γ1 = −1とする．
2. For t = 1, . . . ,(a) 分布 dt に対して γt + ε の エッジ を持つよ

特に，ラベル付き事例 (xi , yi ) の対応する重み di が非うな仮説 ht を選ぶ．

ゼロであるとき，(xi , yi ) をサポートベクターと呼ぶ．こ(b) 条件を満たす仮説が H 中に存在しなければ
T = t − 1 とし，終了．

こで，マージンが ρ∗ 未満（つまり ξi∗ > 0）であるようなラベル付き事例は高々 ν 個であることに注意してほしい．なぜなら，そうでない場合， i d∗i > 1 となり矛(c) 双 対 問 題 (2) を 限 定 さ れ た 仮 説 集 合{h1 , . . . , ht } に対して解く．得られた最適解

盾するからである．

を (γt+1 , dt+1 ) とおく．

さらに，主問題の最適解も疎な性質をもつ．

• γd∗ (hj ) < γ ∗ ならば，α∗j = 0.

(γt+1 , dt+1 ) = arg minm γγ,d∈P

対応する係数 αj が正であるとき，仮説 hj が重要であ

sub. toると言うことにする．以上から，最適解はサポートベク

γd (hj ) ≤ γ (j = 1, . . . , t)1
d ≤ 1.
ν

ターと重要な仮説のみを用いて再現することができることがわかる．

3

アルゴリズムT
3. 最終的な仮説 f (x) = t=1 αt ht (x) を出力する，
ここで，各 αt (t = 1, . . . , T ) は双対問題 (2) にお

本節では，双対問題 (2) を解く手法について詳しく述
べる．

3.1

ける Lagrange 乗数である．

3.2
LPBoost提案手法

本節では，本提案手法 Sparse LPBoost について述べ

まず，LPBoost [5] について述べる．事例の集合上の初る．本手法は LPBoost に変更を加えたものであり，大期分布 d1（一様分布とする）が与えられた時，LPBoost

まかに２つの違いがある．１つ目の違いは，分布 dt のは以下の動作を繰り返す．各ステップ t において，(i)定義域が事例の集合全てではなく，現在の仮説の重み付

LPBoost は分布 dt に対して γt +ε 以上の エッジ を持つ

け αt に対するマージンが小さい事例のみをカバーすような仮説 ht を選ぶ．(ii) 次に，新しい制約 γd (ht ) ≤ γ

る点である．２つ目の違いは，Sparse LPBoost は各繰

を現在の最適化問題に追加して解く．動作 (i) においてり返しにおいて２つ以上の仮説を選ぶ点である．Sparse

条件を満たす仮説が存在しなければ終了する. 図 1 に詳

LPBoost の詳細を図 2 に述べる．
次に，Sparse LPBoost の正当性を示す．

細をまとめる．
次に LPBoost が双対問題 (2) を近似的に解くことを示す．

定理 2. Sparse LPBoost はソフトマージン γ ∗ − ε 以上の最終的な仮説を出力する．

定理 1. LPBoost はソフトマージン γ ∗ − ε 以上の最終証明. C = S − ST とおく．また，γT , dT をアルゴリ的な仮説を出力する．

ズム終了時の双対問題の解とする．アルゴリズムの終了

証明. アルゴリズムの定義から，LPBoost が最終的な条件より，γT + ε 以上の エッジをもつ仮説は存在しな仮説を出力するとき，γT ≥ maxh∈H γdT (h) − ε が成り立つ．さらに，dt は双対問題 (2) の実行可能解なので，

maxh∈H γdT (h) ≥ γ ∗ が成り立つ．これらの事実を組み合わせると， γT ≥ γ ∗ − ε を得る．

いので，γT + ε ≥ maxh∈H γdT (h)が成り立つ．さらに，dT ∈ P |ST | は事例の集合 ST に対する双対問題 (2)の実行可能解であるので，maxh∈H γdT (h) ≥ γ ∗ を満たす．したがって， γT ≥ γ ∗ − ε が成り立つ．最後に，分
布 dT = (dT , 0, . . . , 0) ∈ P |S| を考える．この分布は Cに属する事例にゼロの重みを与えるような分布である.
このとき，明らかに (γT , dT ) は，事例の集合 S に対し

このとき，エッジの高い順に上位 K 個の仮説，マー

Algorithm 2 Sparse LPBoost(S,ε)
1. (初期化) ν 個の事例を任意に選び，それらからなる事例の集合を S1 ，S1 上の一様分布を d1 とする．また，f1 (x) = 0，ρ1 = 1，γ1 = −1, H1 = ∅ジンの低い順に上位 L 個の事例をそれぞれ選ぶ，
 t |, 2t }，L = min{|St |, 2t }ここで K = min{|H
とする．

とする．

では，どの選択方法をとるべきか議論する．以下では，

2. For t = 1, . . . ,例として，ν = 0.2m の場合を考えよう．この場合，ラベル付き事例の高々２割がマージン ρ∗ 以下となり，よっ(a) ft に対してマージンが ρt 未満の事例からなる集合 St を１つ選ぶ．

(b)てこれらは正しく分類されないかもしれない．しかしながら，この設定により，高々２割の事例の誤分類を許

条件を満たす St が存在しなければ，T = t−1

すことで，全体のマージンを向上させることができる．

とし，break.

よってラベルのノイズの大きいデータには妥当な設定といってよいだろう．また，簡単のため，事例に関する計(c) St+1 = St ∪ St とおく．

算時間のみ考える．線形計画法の計算時間は mk (k は(d) For t = 1, . . . ,定数) とする．

i. 分布 dt に対して エッジがγt + ε であるような仮説からなる集合 Ht を１つ選ぶ．

ii. 条件をみたす Ht が存在しなければbreak.
iii. Ht +1 = Ht ∪ Ht とおく.
iv. 双対問題 (2) を St およびHt +1た 解 で 更 新 す る ．ま た ，ft+1 (x) =h∈Ht +1 αh h(x) ，ρt+1 を対応する主問題の解とする，ここで，各 αh は双対問題 (2) の Lagrange 乗数である．

3. fT (x) =h∈HT αh h(x)

ν


tk >

t=1

ν k+1 − 1
= Ω(mk+1 )k+1が cm 個 (0 < c ≤ 1) の事例を選んで終了した場合，計算時間は高々，
log(cm)



前に述べた Sparse LPBoost の説明では，仮説と事例

s=0

≤

k

k s (k−s)(log(cm)+2)
ν 2
s
s=0

=

k

k s  k−sν (c m)s
s=0= O(mk ).

と事例の選択に関するヒューリスティクスについて述べジンが ρt 以下の事例をそれぞれ１つずつ選択．

t=1

k s t(k−s)ν 2s= (ν + c m)k = (0.2 + c )k mkの選択方法については指定していない．本節では，仮説閾値選択 γt +ε 以上の エッジを持つ仮説，および，マー(ν + 2 ) =log(cm) k log(cm)
k

k s 
=
2t(k−s)
ν
s
s=0
t=1

を出力．

る．具体的には以下の３つの選択方法を考える．

t k

t=1

仮説と事例を選択するためのヒューリス
ティクス

最大 / 最小選択

t=1

tk dt =

一方，最大 / 最小-指数選択を用いて，Sparse LPBoostて KKT 条件を満たす.

3.3

ν

要する．

に対して解く．(γt +1 , dt +1 ) を得られもし，閾値選択もしくは最大 / 最小選択を用いた場
合，Sparse LPBoost の計算時間は少なくともとなる．また，同様の議論が仮説の選択方法に関しても成り立つ．
したがって，上記の３つの選択方法のうち，最大 / 最小-指数選択が，計算時間の観点で頑健であるといえる．

最大のエッジを持つ仮説，および，以降では， Sparse LPBoost は最大 / 最小-指数選択を

最小のマージンを持つ事例をそれぞれ１つ選択．

用いると仮定する．注意すべき点は， Sparse LPBoost

最大 / 最小- 指数選択 分布 dt に対して γt + ε 以上の t ，ft に対してマージエッジを持つ仮説の集合を Hの利点は，元の線形計画法とは最悪時の計算時間は同じ

ンが ρt 以下となるような事例の集合を St とおく．

でも，より小さい係数をもつことである．定数倍の計算時間ではあっても，実際のデータにおいては大きな実行時間の短縮が図れる可能性がある．

4

実験

つためである．

人工データ，実データ上で線形計画法，LPBoost，およ4.2

び Sparse LPBoost の実験的評価を行う．実験は Xeon

3.8GHz の CPU，メモリ 8Gb を持つワークステーシ
ョン上で行った．実装には C++, 線形計画ソルバには

CPLEX 11.0 を用いた．

4.1

実データ

次に，実データセット上での実験結果を示す．実デー
タセットには Reuters-21578 1 , RCV1 [9], news20 を用いた．

Reuters-21578 に対しては，部分データセット mod-人工データ

本実験で使用する人工データセットは m = 104 から

106 個の X = {−1, +1}n 上のラベル付き事例から構成される．我々は線形関数 f (x) = x1 + x2 + · · · + xk + b，を１つ固定する，ここで，x1 , . . . , xk は事例 x の最初の

k 個の次元であり，b は定数項である．関数 f は各事例
x のラベル (−1 or +1) を f (x) の符号の正負によって与える．各パラメータは n = 100, k = 10 and b = 5 とした．各データセットに対して正例と負例が等確率になるようにランダムに事例を生成した．さらに，データにノイズを加えるため，0% または 5% の確率でラベルをランダムに反転させた．
各データセットに対して，n + 1 個の仮説を用意した．
最初の n 個の仮説は n 個の次元それぞれに対応する，
つまり，hj (x) = xj (j = 1, . . . , n) である．最後の仮説
は常に +1 を返す（定数項に対応）．
また，ノイズなし，ありのそれぞれのデータセットに対して，パラメータ ν を ν = 1 and ν = 0.2m に設定した．LPBoost and Sparse LPBoost に対しては

ε = 0.001 とした．
ノイズなし，ありのデータセットに対する実験結果を
表 1 にまとめる．ここで，計算時間は CPU 時間である．
注目すべき点は，他のアルゴリズムに比べて， Sparse

LPBoost は ν の選択に対してより頑健であることである．実際，異なる ν の値に対しても，計算時間は最速
ないし，最速に近い．さらに，ノイズなし，ありのそれ
ぞれのデータセットに対して，Sparse LPBoost は全事

iﬁed Apte (“ModApte”) を用いた．このデータセット
は，トピックによってラベルづけされた 10170 個の事例からなる．我々は， “acq” という主要なトピックを正例，他のトピックを負例とし，２値分類問題を構成した．仮説として，30, 839 の単語に対応した決定株を用意した．ここで，各決定株は１つの単語に対応し，与えられた文書にその単語が含まれていれば +1，そうでなければ −1 を返す．

RCV1 データセット，news20 には，LIBSVM tools [4]で提供されているものを用いた．データ数と仮説の総数
はそれぞれ，m = 20, 242, n = 47, 236, m = 19, 996,

n = 1, 355, 193 である．
各データセットに対して，さらに定数項に対応する仮説 −1 を用いる．LPBoost and Sparse LPBoost のパラメータについては，ε = 10−4 とし，Reuters-21578，

RCV1, news20 データセットそれぞれに対して ν = 0.2mとした．
実験結果を表 2 にまとめる．Sparse LPBoost は他の手法よりも数倍以上高速に動作していることがわかる．
人工データでの結果と同様，Sparse LPBoost はより少ない事例（約 0.6m から 0.8m 程度）で最適解を近似的に求めている．また，Sparse LPBoost は仮説間の疎性も利用しているように見える．実際，両データセットにおいて，Sparse LPBoost は 30, 000 以上の仮説の中か
ら数パーセントの仮説のみを用いている．

5

結論

例数 m より少ない事例を選択している．したがって，

本稿では，与えられた任意の ε > 0 に対して，1 ソ

双対問題 (2) における変数のサイズが減少し，問題を小

フトマージン最適化問題の ε 近似を求める手法を提案しさくすることにより計算時間の高速化が達成されていた．本手法は最適解における仮説間と事例間の疎性を利る．特に，事例数が m = 10 の場合，LP ソルバーや用することにより，標準的な線形計画ソルバや LPBoost

LPBoost がメモリ不足で動作しないのに対して，Sparse

よりも高速に動作する．

6

今後の課題として，計算時間の理論的保証が得られる

LPBoost は動作しており, よりメモリを消費しないことがわかる．また，ν = 1 と設定したノイズなしデータ

ように Sparse LPBoost を改良することが挙げられる．

セットに対して，得られた分布 d の非ゼロ要素数は小

また，実用的な観点では，仮説と事例を選択するためのさくなっている一方，ν = 0.2m としたノイズありデー

より良いヒューリスティクスの開発も重要である．

タセットに対して，得られた分布 d の非ゼロ要素数は増加している．結果として計算時間も増大している．これは，最適な分布が少なくとも，ν 個の非ゼロ要素を持1 http://www.daviddlewis.com/resources/testcollections/reuters21578.

ν = 0 (ノイズなし)

ν = 0.2m (ノイズあり)m

手法

計算時間 (秒)#(di > 0)(%)#(αj > 0)(%)

計算時間 (秒)#(di > 0)(%)#(αj > 0) (%)

10

4

LP
LPB

5.99
11.64

0.25
0.19

18.8
17.8(69.3)

2.8
3.16

20.0
20.0

9.9
9.9(9.9)

SLPB

6.15

0.25(23.0)

25(98)

2.99

20.0(47)

9.9(10.9)

10

5

LP
LPB

82.4
120

0.1
0.02

53.5
15.8(61.4)

33.78
43.9

20
20

9.9
9.9(10.9)

SLPB

63.9

0.03(18.9)

20.8(80)

53.1

20(58.7)

10.9(59.4)

10

6

LP
LPB

メモリ不足

n/a
n/a

メモリ不足

メモリ不足

n/a
n/a

メモリ不足

n/a
n/a

n/a
n/a

SLPB

684

0.002(25.2)

15.8(71.3)

1679

20(46.5)90(91)

表 1: ノイズなし（ν = 1），ノイズあり（ν = 0.2m) データに対する実験結果．#(di > 0)，および #(αj > 0) はそ
れぞれ，d, α における非ゼロ要素数の割合を表す．LPBoost (LPB) と Sparse LPBoost (SLPB) に対しては，選択された仮説や事例の個数の割合をかっこ内に示す．

計算時間（秒） #(di > 0)(%)#(αj > 0)(%)

データ

手法

Reuters-21578(m=10,170,n=30,839)

LP
LPB

21.0
52.5

22.1
22.1

1.55
1.53(1.67)

SLPB

8.5

22.2(68)

1.52(1.96)

LP
LPB

2135
4154

25.4
24.3

5.1
3.7(4.0)

SLPB

690

24.6(63.4)

3.9(4.6)

LP
LPB

121525
7251

25.4
22.7

0.16
0.080(0.090)

SLPB

1223

23.1(68.1)

0.088(0.117)

RCV1(m=20,242,n=47,237)
news20(m=19,996,n=1,355,193)

表 2: 実データセットに対する実験結果．#(di > 0)，および #(αj > 0) はそれぞれ，d, α における非ゼロ要素数の割合を表す．LPBoost (LPB) と Sparse LPBoost (SLPB) に対しては，選択された仮説や事例の個数をかっこ内に示す．

謝辞
本研究は科研費若手研究 (B) 21700171 の援助によってなされた．また，本稿に有益なコメントを下さった豊橋技術科学大学の山本悠二氏に感謝します．

参考文献[1] N. Balcan, A. Blum, and N. Srebro. A theory oflearning with similarity functions. Machine Learning, 72(1-2):89–112, 2008.
[2] P. S. Bradley and O. L.Mangasarian. Massive data
discrimination via linear support vector machines.
Optimization Methods and Software, 13(1):1–10,
2000.

[3] Y. Censor and S. A. Zenios. Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, 1998.
[4] C. C. Chang and C. J. Lin. Libsvm: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/
libsvm, 2001.
[5] A. Demiriz, K. P. Bennett, and J. Shawe-Taylor.
Linear programming boosting via column generation. Machine Learning, 46(1-3):225–254, 2002.
[6] T. Graepel, R. Herbrich, B. Schölkopf, A. Smola,
P. Bartlett, K. Müller, K. Obermayer, and
R. Williamson. Classiﬁcation on proximity datawith LP-machines. In International Conferenceon Artificial Neural Networks, pages 304–309,
1999.
[7] A. J. Grove and D. Schuurmans. Boosting in
the limit: Maximizing the margin of learned ensembles. In Proceedings of the fifteenth National
Conference on Artificial Intelligence (AAAI-98),
pages 692–698, 1998.
[8] M. Hein, O. Bousquet, and B. Schölkopf. Maximal
margin classiﬁcation for metric spaces. Journal ofComputer ans System Sciences, 71:333–359, 2005.
[9] D. D. Lewis, Y. Yang, T. G. Rose, and F. Li.
Rcv1: A new benchmark collection for text categorization research. Journal of Machine Learning
Research, 5:361–397, 2004.
[10] O. Mangasarian. Exact 1-norm support vector
machines via unconstrained convex diﬀerentiable
minimization. Journal of Machine Learning Research, 7:1517–1530, 2006.
[11] S. Nash and A. Sofer. Linear and Nonlinear Programming. Macgraw-Hill, 1996.
[12] R. E. Schapire, Y. Freund, P. Bartlett, and W. S.
Lee. Boosting the margin: a new explanation for
the eﬀectiveness of voting methods. The Annalsof Statistics, 26(5):1651–1686, 1998.
[13] S. Sra. Eﬃcient large scale linear progamming
support vector machines. In Machine Learning:
ECML 2006, pages 767–774, 2006.
[14] L. Wang, M. Sugiyama, C. Yang, K. Hatano,
and J. Fung. Theory and algorithms for learningwith dissimilarity functions. Neural Computation,
21(5):1459–1484, 2009.
[15] M. Warmuth, K. Glocer, and G. Rätsch. Boostingalgorithms for maximizing the soft margin. In Advances in Neural Information Processing Systems
20, pages 1585–1592, 2008.
[16] M. Warmuth, K. Glocer, and S. V. N. Vishwanathan. Entropy regularized LPBoost. In
Proceedings of the 19th International Conferenceon Algorithmic Learning Theory, pages 256–271,
2008.