Prior Knowledge and Preferential Structures in Gradient Descent Learning Algorithms
勾配降下法学習アルゴリズムにおける事前知識と優先構造
A family of gradient descent algorithms for learning linearfunctions in an online setting is considered. The familyincludes the classical LMS algorithm as well as new variants suchas the Exponentiated Gradient (EG) algorithm due to Kivinen andWarmuth. The algorithms are based on prior distributions definedon the weight space. Techniques from differential geometry areused to develop the algorithms as gradient descent iterationswith respect to the natural gradient in the Riemannian structureinduced by the prior distribution. The proposed frameworksubsumes the notion of “link-functions”.
オンライン設定で線形関数を学習するための勾配降下アルゴリズムのファミリが考慮されます。このファミリには、従来のLMSアルゴリズムだけでなく、KivinenやWarmuthによるExponentiated Gradient(EG)アルゴリズムなどの新しいバリアントも含まれています。アルゴリズムは、重み空間で定義された事前分布に基づいています。微分幾何学の手法を使用して、事前分布によって誘導されたリーマン構造の自然勾配に対する勾配降下反復としてアルゴリズムを開発します。提案されたフレームワークは、「リンク機能」の概念を包含しています。
Tracking the Best Linear Predictor
最適な線形予測子の追跡
In most on-line learning research the total on-line loss of thealgorithm is compared to the total loss of the best off-line predictoru from a comparison class of predictors. We call such bounds static bounds. The interesting feature of these bounds is that theyhold for an arbitrary sequence of examples. Recently some work hasbeen done where the predictor ut at each trial t is allowed tochange with time, and the total on-line loss of the algorithm iscompared to the sum of the losses of ut at each trial plus thetotal “cost” for shifting to successive predictors. This is tomodel situations in which the examples change over time, and differentpredictors from the comparison class are best for different segmentsof the sequence of examples. We call such bounds shiftingbounds. They hold for arbitrary sequences of examples and arbitrarysequences of predictors.Naturally shifting bounds are much harder to prove. The only knownbounds are for the case when the comparison class consists of asequences of experts or boolean disjunctions. In this paper we developthe methodology for lifting known static bounds to the shifting case.In particular we obtain bounds when the comparison class consists oflinear neurons (linear combinations of experts). Our essentialtechnique is to project the hypothesis of the static algorithmat the end of each trial into a suitably chosen convex region. Thiskeeps the hypothesis of the algorithm well-behaved and the staticbounds can be converted to shifting bounds.
ほとんどのオンライン学習研究では、アルゴリズムのオンライン損失の合計が、比較クラスの予測子からの最良のオフライン予測子の合計損失と比較されます。このような境界を静的境界と呼びます。これらの境界の興味深い特徴は、任意の例のシーケンスに対して保持されることです。最近、各試行tにおける予測子utが時間とともに変化することを許し、アルゴリズムのオンライン損失の合計を、各試行におけるutの損失の合計と、次の予測子へのシフトにかかる「コスト」の合計と比較する研究が行われました。これは、例が時間とともに変化し、比較クラスの異なる予測子が例のシーケンスの異なるセグメントに最適である状況をモデル化するためのものです。このような境界をシフト境界と呼びます。これらは、任意の例のシーケンスと任意の予測子のシーケンスに当てはまります。当然、シフト境界は証明するのがはるかに困難です。既知の境界は、比較クラスがエキスパートのシーケンスまたはブール論理和で構成される場合のみです。この論文では、既知の静的境界をシフトケースに引き上げる方法論を開発します。特に、比較クラスが線形ニューロン(エキスパートの線形結合)で構成される場合の境界を取得します。私たちの基本的な手法は、各試行の終了時に静的アルゴリズムの仮説を適切に選択された凸領域に投影することです。これにより、アルゴリズムの仮説が適切に維持され、静的境界をシフト境界に変換できるようになります。
Bayes Point Machines
ベイズポイントマシン
Kernel-classifiers comprise a powerful class of non-linear decisionfunctions for binary classification. The support vector machine is anexample of a learning algorithm for kernel classifiers that singlesout the consistent classifier with the largest margin, i.e. minimalreal-valued output on the training sample, within the set ofconsistent hypotheses, the so-called version space. We suggestthe Bayes point machine as a well-founded improvement whichapproximates the Bayes-optimal decision by the centre of mass ofversion space. We present two algorithms to stochastically approximatethe centre of mass of version space: a billiard sampling algorithm anda sampling algorithm based on the well known perceptron algorithm. Itis shown how both algorithms can be extended to allow forsoft-boundaries in order to admit training errors. Experimentally, wefind that – for the zero training error case – Bayes pointmachines consistently outperform support vector machines on bothsurrogate data and real-world benchmark data sets. In thesoft-boundary/soft-margin case, the improvement over support vectormachines is shown to be reduced. Finally, we demonstrate that thereal-valued output of single Bayes points on novel test points is avalid confidence measure and leads to a steady decrease ingeneralisation error when used as a rejection criterion.
カーネル分類器は、バイナリ分類のための強力な非線形決定関数のクラスを構成します。サポートベクターマシンは、カーネル分類器の学習アルゴリズムの例であり、一貫性のある仮説のセット、いわゆるバージョン空間内で、最大のマージン、つまりトレーニングサンプルの最小の実数値出力を持つ一貫性のある分類器を選択します。ベイズポイントマシンは、バージョン空間の質量中心によってベイズ最適決定を近似する根拠のある改善として提案されています。バージョン空間の質量中心を確率的に近似する2つのアルゴリズム、ビリヤードサンプリングアルゴリズムと、よく知られているパーセプトロンアルゴリズムに基づくサンプリングアルゴリズムを紹介します。両方のアルゴリズムを拡張して、トレーニングエラーを許容するためにソフト境界を可能にする方法を示します。実験的に、トレーニング エラーがゼロの場合、ベイズ ポイント マシンは、代理データと実際のベンチマーク データ セットの両方で、一貫してサポート ベクター マシンよりも優れていることがわかりました。ソフト境界/ソフト マージンの場合、サポート ベクター マシンに対する改善は低下することが示されています。最後に、新しいテスト ポイントでの単一のベイズ ポイントの実数値出力は有効な信頼度測定であり、拒否基準として使用した場合、一般化エラーが着実に減少することを示します。
Sparse Bayesian Learning and the Relevance Vector Machine
スパースベイズ学習と関連性ベクトルマシン
This paper introduces a general Bayesian framework for obtaining sparse solutions to regression and classification tasks utilising models linear in the parameters. Although this framework is fully general, we illustrate our approach with a particular specialisation that we denote the ‘relevance vector machine’ (RVM), a model of identical functional form to the popular and state-of-the-art ‘support vector machine’ (SVM). We demonstrate that by exploiting a probabilistic Bayesian learning framework, we can derive accurate prediction models which typically utilise dramatically fewer basis functions than a comparable SVM while offering a number of additional advantages. These include the benefits of probabilistic predictions, automatic estimation of ‘nuisance’ parameters, and the facility to utilise arbitrary basis functions (e.g. non-‘Mercer’ kernels). We detail the Bayesian framework and associated learning algorithm for the RVM, and give some illustrative examples of its application along with some comparative benchmarks. We offer some explanation for the exceptional degree of sparsity obtained, and discuss and demonstrate some of the advantageous features, and potential extensions, of Bayesian relevance learning.
この論文では、パラメータに線形なモデルを利用して回帰および分類タスクのスパース解を得るための一般的なベイジアン フレームワークを紹介します。このフレームワークは完全に一般的なものですが、私たちは「関連性ベクター マシン」(RVM)と呼ばれる特定の特殊化を使用してアプローチを説明します。これは、人気があり最先端の「サポート ベクター マシン」(SVM)と同一の機能形式のモデルです。確率的ベイジアン学習フレームワークを利用することで、同等のSVMよりも大幅に少ない基底関数を使用する正確な予測モデルを導き出すことができ、さらにいくつかの利点も得られることを実証します。これには、確率的予測の利点、「迷惑」パラメータの自動推定、および任意の基底関数(「Mercer」以外のカーネルなど)を使用する機能が含まれます。ベイジアン フレームワークとRVMの関連学習アルゴリズムについて詳しく説明し、その適用例といくつかの比較ベンチマークを示します。得られた例外的なスパース性について説明し、ベイズ関連性学習のいくつかの有利な特徴と潜在的な拡張について議論し、実証します。
Regularized Principal Manifolds
正則化主多様体
Many settings of unsupervised learning can be viewed asquantization problems – the minimization of the expected quantizationerror subject to some restrictions. This allows the use of tools such asregularization from the theory of (supervised) risk minimization forunsupervised learning. This setting turns out to be closely related toprincipal curves, the generative topographic map, and robust coding. We explore this connection in two ways: (1) we propose an algorithm forfinding principal manifolds that can be regularized in a variety of ways;and (2) we derive uniform convergence bounds and hence bounds on thelearning rates of the algorithm. In particular, we give bounds on thecovering numbers which allows us to obtain nearly optimal learning ratesfor certain types of regularization operators. Experimental resultsdemonstrate the feasibility of the approach.
教師なし学習の多くの設定は、量子化問題-予想される量子化誤差の最小化は、いくつかの制限を受ける。これにより、教師なし学習の(教師あり)リスク最小化の理論からの正則化などのツールの使用が可能になります。この設定は、主曲線、生成地形図、およびロバスト コーディングと密接に関連していることがわかります。この接続を2つの方法で探求します:(1)さまざまな方法で正則化できる主多様体を見つけるためのアルゴリズムを提案します。(2)一様な収束範囲を導き出し、したがってアルゴリズムの学習率の範囲を導き出します。特に、特定の種類の正則化演算子に対してほぼ最適な学習率を得ることを可能にするカバー数に境界を与えます。実験結果は、アプローチの実現可能性を示しています。
Lagrangian Support Vector Machines
Lagrangeサポートベクターマシン
An implicit Lagrangian for the dual of a simple reformulation of thestandard quadratic program of a linear support vector machine isproposed. This leads to the minimization of an unconstraineddifferentiable convex function in a space of dimensionality equal tothe number of classified points. This problem is solvable by anextremely simple linearly convergent Lagrangian support vector machine(LSVM) algorithm. LSVM requires the inversion at the outset of asingle matrix of the order of the much smaller dimensionality of theoriginal input space plus one. The full algorithm is given in thispaper in 11 lines of MATLAB code without any special optimizationtools such as linear or quadratic programming solvers. This LSVM codecan be used “as is” to solve classification problems with millions ofpoints. For example, 2 million points in 10 dimensional input spacewere classified by a linear surface in 82 minutes on a Pentium III 500MHz notebook with 384 megabytes of memory (and additional swap space),and in 7 minutes on a 250 MHz UltraSPARC II processor with 2 gigabytesof memory. Other standard classification test problems were alsosolved. Nonlinear kernel classification can also be solved by LSVM.Although it does not scale up to very large problems, it can handleany positive semidefinite kernel and is guaranteed to converge. Ashort MATLAB code is also given for nonlinear kernels and tested on anumber of problems.
線形サポート ベクター マシンの標準的な2次計画の単純な再定式化の双対に対する暗黙のラグランジアンが提案されています。これにより、分類されたポイントの数に等しい次元の空間で、制約のない微分可能な凸関数が最小化されます。この問題は、非常に単純な線形収束ラグランジアン サポート ベクター マシン(LSVM)アルゴリズムによって解決できます。LSVMでは、最初に、元の入力空間のはるかに小さい次元に1を加えたオーダーの単一の行列の反転が必要です。この論文では、線形または2次計画ソルバーなどの特別な最適化ツールを使用せずに、完全なアルゴリズムが11行のMATLABコードで提供されています。このLSVMコードは、数百万のポイントを持つ分類問題を解決するために「そのまま」使用できます。たとえば、10次元の入力空間にある200万点を線形表面で分類すると、384 MBのメモリ(および追加のスワップ スペース)を搭載したPentium III 500 MHzノートブックでは82分、2 GBのメモリを搭載した250 MHz UltraSPARC IIプロセッサでは7分で分類できました。その他の標準的な分類テスト問題も解決されました。非線形カーネル分類もLSVMで解決できます。非常に大規模な問題には対応できませんが、任意の正の半定値カーネルを処理でき、収束することが保証されています。非線形カーネル用の短いMATLABコードも提供されており、いくつかの問題でテストされています。
SVMTorch: Support Vector Machines for Large-Scale Regression Problems
SVMTorch:大規模な回帰問題に対応するベクターマシンのサポート
Support Vector Machines (SVMs) for regression problems are trained by solvinga quadratic optimization problem which needs on the order of l squarememory and time resources to solve, where l is the number of trainingexamples. In this paper, we propose a decomposition algorithm, SVMTorch (available at http://www.idiap.ch/learning/SVMTorch.html), which is similar to SVM-Light proposed by Joachims (1999) for classification problems, but adapted to regression problems. With this algorithm, one can now efficiently solvelarge-scale regression problems (more than 20000 examples). Comparisons with Nodelib, another publicly availableSVM algorithm for large-scale regression problemsfrom Flake and Lawrence (2000) yielded significant time improvements.Finally, based on a recent paper from Lin (2000), we show that a convergence proof exists for our algorithm.
回帰問題のサポートベクターマシン(SVM)は、l平方メモリと時間リソースのオーダーで解決する必要がある二次最適化問題を解くことによって訓練されます(lは訓練例の数です)。この論文では、分類問題に対してJoachims(1999)によって提案されたSVM-Lightに似ていますが、回帰問題に適応した分解アルゴリズムSVMTorch(http://www.idiap.ch/learning/SVMTorch.htmlで入手可能)を提案します。このアルゴリズムにより、大規模な回帰問題(20000件以上)を効率的に解くことができるようになりました。Flake and Lawrence(2000)の大規模回帰問題に対する別の公開SVMアルゴリズムであるNodelibとの比較では、大幅な時間改善が見られました。最後に、Lin (2000)の最近の論文に基づいて、アルゴリズムに収束証明が存在することを示します。
Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers
多クラスからバイナリへの削減: マージン分類器の統一アプローチ
We present a unifying framework for studying the solution ofmulticlass categorization problems by reducing them to multiple binaryproblems that are then solved using a margin-based binary learningalgorithm. The proposed framework unifies some of the most popularapproaches in which each class is compared against all others, or inwhich all pairs of classes are compared to each other, or in whichoutput codes with error-correcting properties are used. We propose ageneral method for combining the classifiers generated on the binaryproblems, and we prove a general empirical multiclass lossbound given the empirical loss of the individual binary learningalgorithms. The scheme and the corresponding bounds apply to manypopular classification learning algorithms including support-vectormachines, AdaBoost, regression, logistic regression and decision-treealgorithms. We also give a multiclass generalization error analysisfor general output codes with AdaBoost as the binary learner.Experimental results with SVM and AdaBoost show that our schemeprovides a viable alternative to the most commonly used multiclassalgorithms.
私たちは、マルチクラス分類問題を複数のバイナリ問題に縮小し、マージンベースのバイナリ学習アルゴリズムを使用して解決することで、マルチクラス分類問題の解決方法を研究するための統一的なフレームワークを提示します。提案されたフレームワークは、各クラスを他のすべてのクラスと比較する、すべてのクラスのペアを互いに比較する、またはエラー訂正特性を持つ出力コードを使用する、最も一般的なアプローチのいくつかを統合します。私たちは、バイナリ問題で生成された分類器を組み合わせるための一般的な方法を提案し、個々のバイナリ学習アルゴリズムの実験的損失を前提として、一般的な実験的マルチクラス損失の境界を証明します。このスキームと対応する境界は、サポートベクターマシン、AdaBoost、回帰、ロジスティック回帰、決定木アルゴリズムなど、多くの一般的な分類学習アルゴリズムに適用されます。また、バイナリ学習器としてAdaBoostを使用した一般的な出力コードのマルチクラス一般化エラー分析も提供します。SVMとAdaBoostを使用した実験結果は、私たちの方式が最も一般的に使用されるマルチクラスアルゴリズムの実行可能な代替手段を提供することを示しています。
Learning Evaluation Functions to Improve Optimization by Local Search
ローカルサーチによる最適化改善のための学習評価関数
This paper describes algorithms that learn to improve search performance on large-scale optimization tasks. The main algorithm, STAGE, works by learning an evaluation function that predicts the outcome of a local search algorithm, such as hillclimbing or Walksat, from features of states visited during search. The learned evaluation function is then used to bias future search trajectories toward better optima on the same problem. Another algorithm, X-STAGE, transfers previously learned evaluation functions to new, similar optimization problems. Empirical results are provided on seven large-scale optimization domains: bin-packing, channel routing, Bayesian network structure-finding, radiotherapy treatment planning, cartogram design, Boolean satisfiability, and Boggle board setup.
この論文では、大規模な最適化タスクでの検索パフォーマンスを向上させることを学習するアルゴリズムについて説明します。メイン アルゴリズムであるSTAGEは、探索中に訪れた州の特徴から、ヒルクライミングやWalksatなどのローカル探索アルゴリズムの結果を予測する評価関数を学習することで機能します。次に、学習した評価関数を使用して、同じ問題で将来の探索軌道をより最適なものにバイアスします。別のアルゴリズムであるX-STAGEは、以前に学習した評価関数を新しい類似の最適化問題に転送します。経験的結果は、ビンパッキング、チャネルルーティング、ベイジアンネットワーク構造検出、放射線治療治療計画、カートグラム設計、ブール充足可能性、およびボグルボードのセットアップという7つの大規模最適化ドメインで提供されます。
Dependency Networks for Inference, Collaborative Filtering, and Data Visualization
推論、協調フィルタリング、およびデータ可視化のための依存関係ネットワーク
We describe a graphical model for probabilistic relationships–analternative to the Bayesian network–called a dependency network. Thegraph of a dependency network, unlike a Bayesian network, ispotentially cyclic. The probability component of a dependencynetwork, like a Bayesian network, is a set of conditionaldistributions, one for each node given its parents. We identifyseveral basic properties of this representation and describe acomputationally efficient procedure for learning the graph andprobability components from data. We describe the application of thisrepresentation to probabilistic inference, collaborative filtering(the task of predicting preferences), and the visualization of acausalpredictive relationships.
私たちは、確率的関係のグラフィカルモデル(ベイジアンネットワークの代替)を、依存性ネットワークと呼びます。依存関係ネットワークのグラフは、ベイジアン ネットワークとは異なり、潜在的に循環的です。ベイジアン ネットワークと同様に、依存関係ネットワークの確率コンポーネントは、親が与えられるノードごとに1つずつ、条件付き分布のセットです。この表現のいくつかの基本特性を特定し、データからグラフと確率成分を学習するための計算効率の高い手順について説明します。この表現の確率的推論、協調フィルタリング(選好を予測するタスク)、および非因果予測関係の視覚化への適用について説明します。
Learning with Mixtures of Trees
木の混合で学ぶ
This paper describes the mixtures-of-trees model, a probabilistic model for discrete multidimensional domains. Mixtures-of-trees generalize the probabilistic trees of Chow and Liu (1968) in a different and complementary direction to that of Bayesian networks.We present efficient algorithms for learning mixtures-of-trees models in maximum likelihood and Bayesian frameworks. We also discuss additional efficiencies that can be obtained when data are “sparse,” and we present data structures and algorithms that exploit such sparseness. Experimental results demonstrate the performance of the model for both density estimation and classification. We also discuss the sense in which tree-based classifiers perform an implicit form of feature selection, and demonstrate a resulting insensitivity to irrelevant attributes.
この論文では、離散多次元ドメインの確率モデルであるMixtures-of-Treesモデルについて説明します。Mixtures-of-treesは、Chow and Liu (1968)の確率的木を、ベイジアン ネットワークのそれとは異なる補完的な方向に一般化します。最尤法で木の混合モデルを学習するための効率的なアルゴリズムとベイジアンフレームワークを提示します。また、データが「スパース」である場合に得られる追加の効率についても説明し、そのようなスパース性を利用するデータ構造とアルゴリズムを示します。実験結果は、密度推定と分類の両方に対するモデルのパフォーマンスを示しています。また、ツリーベースの分類子が暗黙的な形式の機能選択を実行する意味についても説明し、その結果、無関係な属性に対する鈍感さを示します。
