Convergence of Distributed Asynchronous Learning Vector Quantization Algorithms
分散非同期学習ベクトル量子化アルゴリズムの収束
Motivated by the problem of effectively executing clustering algorithms on very large data sets, we address a model for large scale distributed clustering methods. To this end, we briefly recall some standards on the quantization problem and some results on the almost sure convergence of the competitive learning vector quantization (CLVQ) procedure. A general model for linear distributed asynchronous algorithms well adapted to several parallel computing architectures is also discussed. Our approach brings together this scalable model and the CLVQ algorithm, and we call the resulting technique the distributed asynchronous learning vector quantization algorithm (DALVQ). An in-depth analysis of the almost sure convergence of the DALVQ algorithm is performed. A striking result is that we prove that the multiple versions of the quantizers distributed among the processors in the parallel architecture asymptotically reach a consensus almost surely. Furthermore, we also show that these versions converge almost surely towards the same nearly optimal value for the quantization criterion.
非常に大規模なデータセットに対してクラスタリング アルゴリズムを効果的に実行するという問題に着目し、大規模分散クラスタリング法のモデルについて検討します。このために、量子化問題に関するいくつかの標準と、競合学習ベクトル量子化(CLVQ)手順のほぼ確実な収束に関するいくつかの結果について簡単に説明します。また、いくつかの並列コンピューティング アーキテクチャによく適合する線形分散非同期アルゴリズムの一般的なモデルについても説明します。私たちのアプローチは、このスケーラブルなモデルとCLVQアルゴリズムを組み合わせたもので、結果として得られる手法を分散非同期学習ベクトル量子化アルゴリズム(DALVQ)と呼びます。DALVQアルゴリズムのほぼ確実な収束の詳細な分析を実行します。注目すべき結果は、並列アーキテクチャのプロセッサ間に分散された量子化器の複数のバージョンが漸近的にほぼ確実にコンセンサスに達することを証明したことです。さらに、これらのバージョンが量子化基準のほぼ最適な同じ値にほぼ確実に収束することも示します。
A Simpler Approach to Matrix Completion
行列補完へのよりシンプルなアプローチ
This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix. These results improve on prior work by Candès and Recht (2009), Candès and Tao (2009), and Keshavan et al. (2009). The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.
この論文では、未知の低ランク行列を再構築するために必要なランダムにサンプリングされたエントリの数について、これまでの最良の範囲を提供します。これらの結果は、Candès and Recht (2009)、Candès and Tao (2009)、Keshavanら(2009)による先行研究を改良したものです。再構成は、提供されたエントリとの一致を条件として、隠れ行列の核ノルム、または特異値の合計を最小化することによって達成されます。基になる行列が特定のインコヒーレンス条件を満たす場合、必要なエントリの数は、2次対数因子に特異値分解のパラメーターの数を掛けたものに等しくなります。この主張の証明は短く、自己完結型であり、非常に基本的な分析を使用します。ここで紹介する新しい手法は、量子情報理論における最近の研究に基づいています。
Learning with Structured Sparsity
構造化されたスパース性による学習
This paper investigates a learning formulation called structured sparsity, which is a natural extension of the standard sparsity concept in statistical learning and compressive sensing. By allowing arbitrary structures on the feature set, this concept generalizes the group sparsity idea that has become popular in recent years. A general theory is developed for learning with structured sparsity, based on the notion of coding complexity associated with the structure. It is shown that if the coding complexity of the target signal is small, then one can achieve improved performance by using coding complexity regularization methods, which generalize the standard sparse regularization. Moreover, a structured greedy algorithm is proposed to efficiently solve the structured sparsity problem. It is shown that the greedy algorithm approximately solves the coding complexity optimization problem under appropriate conditions. Experiments are included to demonstrate the advantage of structured sparsity over standard sparsity on some real applications.
この論文では、統計学習と圧縮センシングにおける標準的なスパース性概念の自然な拡張である構造化スパース性と呼ばれる学習定式化について検討します。この概念は、特徴セットに任意の構造を許可することにより、近年人気が高まっているグループスパース性の考え方を一般化します。構造化スパース性による学習の一般理論は、構造に関連付けられたコーディング複雑性の概念に基づいて開発されています。ターゲット信号のコーディング複雑性が小さい場合、標準的なスパース正則化を一般化するコーディング複雑性正則化法を使用することで、パフォーマンスを向上できることが示されています。さらに、構造化スパース性の問題を効率的に解決するための構造化貪欲アルゴリズムが提案されています。貪欲アルゴリズムは、適切な条件下でコーディング複雑性の最適化問題を近似的に解決することが示されています。いくつかの実際のアプリケーションで構造化スパース性が標準スパース性よりも優れていることを示す実験が含まれています。
Semi-Supervised Learning with Measure Propagation
メジャープロパゲーションによる半教師あり学習
We describe a new objective for graph-based semi-supervised learning based on minimizing the Kullback-Leibler divergence between discrete probability measures that encode class membership probabilities. We show how the proposed objective can be efficiently optimized using alternating minimization. We prove that the alternating minimization procedure converges to the correct optimum and derive a simple test for convergence. In addition, we show how this approach can be scaled to solve the semi-supervised learning problem on very large data sets, for example, in one instance we use a data set with over 108 samples. In this context, we propose a graph node ordering algorithm that is also applicable to other graph-based semi-supervised learning approaches. We compare the proposed approach against other standard semi-supervised learning algorithms on the semi-supervised learning benchmark data sets (Chapelle et al., 2007), and other real-world tasks such as text classification on Reuters and WebKB, speech phone classification on TIMIT and Switchboard, and linguistic dialog-act tagging on Dihana and Switchboard. In each case, the proposed approach outperforms the state-of-the-art. Lastly, we show that our objective can be generalized into a form that includes the standard squared-error loss, and we prove a geometric rate of convergence in that case.
私たちは、クラス メンバーシップ確率をエンコードする離散確率測度間のKullback-Leiblerダイバージェンスの最小化に基づくグラフベースの半教師あり学習の新しい目的について説明します。提案された目的を交代最小化を使用して効率的に最適化する方法を示します。交代最小化手順が正しい最適値に収束することを証明し、収束の簡単なテストを導出します。さらに、このアプローチを拡張して、非常に大規模なデータ セットの半教師あり学習問題を解決する方法を示します。たとえば、1つの例では、108を超えるサンプルを含むデータ セットを使用します。このコンテキストでは、他のグラフベースの半教師あり学習アプローチにも適用できるグラフ ノード順序付けアルゴリズムを提案します。提案手法を、半教師あり学習ベンチマークデータセット(Chapelle他、2007)およびReutersとWebKBでのテキスト分類、TIMITとSwitchboardでの音声音素分類、DihanaとSwitchboardでの言語対話行為タグ付けなどの他の実際のタスクで、他の標準的な半教師あり学習アルゴリズムと比較します。いずれの場合も、提案手法は最先端の手法よりも優れています。最後に、私たちの目的が標準二乗誤差損失を含む形式に一般化できることを示し、その場合の幾何収束率を証明します。
An Asymptotic Behaviour of the Marginal Likelihood for General Markov Models
一般マルコフ模型の周辺尤度の漸近振る舞い
The standard Bayesian Information Criterion (BIC) is derived under regularity conditions which are not always satisfied in the case of graphical models with hidden variables. In this paper we derive the BIC for the binary graphical tree models where all the inner nodes of a tree represent binary hidden variables. This provides an extension of a similar formula given by Rusakov and Geiger for naive Bayes models. The main tool used in this paper is the connection between the growth behavior of marginal likelihood integrals and the real log-canonical threshold.
標準のベイズ情報量基準(BIC)は、隠れ変数を持つグラフィカルモデルの場合、常に満たされるとは限らない規則性条件下で導出されます。この論文では、木のすべての内部ノードがバイナリ隠れ変数を表すバイナリグラフィカルツリーモデルのBICを導き出します。これは、RusakovとGeigerが単純ベイズモデルに対して与えた同様の式の拡張を提供します。この論文で使用される主なツールは、周辺尤積分の成長挙動と実際の対数正準閾値との関係です。
The Sample Complexity of Dictionary Learning
辞書学習のサンプルの複雑さ
A large set of signals can sometimes be described sparsely using a dictionary, that is, every element can be represented as a linear combination of few elements from the dictionary. Algorithms for various signal processing applications, including classification, denoising and signal separation, learn a dictionary from a given set of signals to be represented. Can we expect that the error in representing by such a dictionary a previously unseen signal from the same source will be of similar magnitude as those for the given examples? We assume signals are generated from a fixed distribution, and study these questions from a statistical learning theory perspective. We develop generalization bounds on the quality of the learned dictionary for two types of constraints on the coefficient selection, as measured by the expected L2 error in representation when the dictionary is used. For the case of l1 regularized coefficient selection we provide a generalization bound of the order of O(√np ln(mλ)/m), where n is the dimension, p is the number of elements in the dictionary, λ is a bound on the l1 norm of the coefficient vector and m is the number of samples, which complements existing results. For the case of representing a new signal as a combination of at most k dictionary elements, we provide a bound of the order O(√np ln(mk)/m) under an assumption on the closeness to orthogonality of the dictionary (low Babel function). We further show that this assumption holds for most dictionaries in high dimensions in a strong probabilistic sense. Our results also include bounds that converge as 1/m, not previously known for this problem. We provide similar results in a general setting using kernels with weak smoothness requirements.
大規模な信号セットは、辞書を使用してスパースに記述できる場合があります。つまり、すべての要素は、辞書内の少数の要素の線形結合として表すことができます。分類、ノイズ除去、信号分離などのさまざまな信号処理アプリケーションのアルゴリズムは、表現する特定の信号セットから辞書を学習します。このような辞書で、同じソースからの以前に見たことのない信号を表現する際のエラーが、与えられた例の場合と同程度の大きさになると期待できますか?信号は固定分布から生成されると仮定し、統計学習理論の観点からこれらの質問を検討します。係数選択に対する2種類の制約について、学習した辞書の品質に関する一般化境界を開発します。これは、辞書を使用した場合の表現における予想されるL2エラーによって測定されます。l1正規化係数選択の場合、O(√np ln(mλ)/m)のオーダーの一般化境界を提供します。ここで、nは次元、pは辞書内の要素数、λ は係数ベクトルのl1ノルムの境界、mはサンプル数であり、既存の結果を補完します。新しい信号を最大k個の辞書要素の組み合わせとして表す場合、辞書の直交性(低バベル関数)への近さに関する仮定の下で、O(√np ln(mk)/m)のオーダーの境界を提供します。さらに、この仮定は、強い確率的意味で高次元のほとんどの辞書に当てはまることを示します。私たちの結果には、この問題ではこれまで知られていなかった1/mに収束する境界も含まれています。弱い平滑性要件を持つカーネルを使用した一般的な設定でも同様の結果を提供します。
Robust Gaussian Process Regression with a Student-t Likelihood
スチューデントのt尤度を持つロバストなガウス過程回帰
This paper considers the robust and efficient implementation of Gaussian process regression with a Student-t observation model, which has a non-log-concave likelihood. The challenge with the Student-t model is the analytically intractable inference which is why several approximative methods have been proposed. Expectation propagation (EP) has been found to be a very accurate method in many empirical studies but the convergence of EP is known to be problematic with models containing non-log-concave site functions. In this paper we illustrate the situations where standard EP fails to converge and review different modifications and alternative algorithms for improving the convergence. We demonstrate that convergence problems may occur during the type-II maximum a posteriori (MAP) estimation of the hyperparameters and show that standard EP may not converge in the MAP values with some difficult data sets. We present a robust implementation which relies primarily on parallel EP updates and uses a moment-matching-based double-loop algorithm with adaptively selected step size in difficult cases. The predictive performance of EP is compared with Laplace, variational Bayes, and Markov chain Monte Carlo approximations.
この論文では、非対数凹尤度を持つStudent-t観測モデルによるガウス過程回帰の堅牢で効率的な実装について検討します。Student-tモデルの課題は、解析的に扱いにくい推論であるため、いくつかの近似方法が提案されています。期待値伝播(EP)は、多くの実証研究で非常に正確な方法であることがわかっていますが、非対数凹サイト関数を含むモデルではEPの収束に問題があることが知られています。この論文では、標準EPが収束しない状況を示し、収束を改善するためのさまざまな修正と代替アルゴリズムを確認します。ハイパーパラメータのタイプII最大事後確率(MAP)推定中に収束の問題が発生する可能性があることを示し、一部の困難なデータ セットでは標準EPがMAP値に収束しない可能性があることを示します。主に並列EP更新に依存し、困難なケースでは適応的に選択されたステップ サイズでモーメント マッチング ベースの二重ループ アルゴリズムを使用する堅牢な実装を示します。EPの予測性能を、ラプラス近似、変分ベイズ近似、マルコフ連鎖モンテカルロ近似と比較します。
Group Lasso Estimation of High-dimensional Covariance Matrices
高次元共分散行列のグループLasso推定
In this paper, we consider the Group Lasso estimator of the covariance matrix of a stochastic process corrupted by an additive noise. We propose to estimate the covariance matrix in a high-dimensional setting under the assumption that the process has a sparse representation in a large dictionary of basis functions. Using a matrix regression model, we propose a new methodology for high-dimensional covariance matrix estimation based on empirical contrast regularization by a group Lasso penalty. Using such a penalty, the method selects a sparse set of basis functions in the dictionary used to approximate the process, leading to an approximation of the covariance matrix into a low dimensional space. Consistency of the estimator is studied in Frobenius and operator norms and an application to sparse PCA is proposed.
この論文では、加法的なノイズによって破損した確率過程の共分散行列のGroup Lasso推定量について考察します。私たちは、プロセスが基底関数の大規模な辞書でスパース表現を持つという仮定の下で、高次元設定で共分散行列を推定することを提案します。行列回帰モデルを使用して、グループLassoペナルティによる経験的コントラスト正則化に基づく高次元共分散行列推定の新しい方法論を提案します。このようなペナルティを使用して、このメソッドは、プロセスを近似するために使用されるディクショナリ内の基底関数のスパース セットを選択し、共分散行列を低次元空間に近似します。推定量の一貫性は、Frobeniusと演算子のノルムで研究され、スパースPCAへの適用が提案されています。
Adaptive Exact Inference in Graphical Models
グラフィカルモデルにおける適応的正確推論
Many algorithms and applications involve repeatedly solving variations of the same inference problem, for example to introduce new evidence to the model or to change conditional dependencies. As the model is updated, the goal of adaptive inference is to take advantage of previously computed quantities to perform inference more rapidly than from scratch. In this paper, we present algorithms for adaptive exact inference on general graphs that can be used to efficiently compute marginals and update MAP configurations under arbitrary changes to the input factor graph and its associated elimination tree. After a linear time preprocessing step, our approach enables updates to the model and the computation of any marginal in time that is logarithmic in the size of the input model. Moreover, in contrast to max-product our approach can also be used to update MAP configurations in time that is roughly proportional to the number of updated entries, rather than the size of the input model. To evaluate the practical effectiveness of our algorithms, we implement and test them using synthetic data as well as for two real-world computational biology applications. Our experiments show that adaptive inference can achieve substantial speedups over performing complete inference as the model undergoes small changes over time.
多くのアルゴリズムやアプリケーションでは、同じ推論問題のバリエーションを繰り返し解決する必要があります。たとえば、モデルに新しい証拠を導入したり、条件付き依存関係を変更したりします。モデルが更新されるにつれて、適応型推論の目標は、以前に計算された量を利用して、最初から行うよりも迅速に推論を実行することです。この論文では、入力因子グラフとそれに関連する消去ツリーに任意の変更を加えた場合に、効率的に周辺を計算し、MAP構成を更新するために使用できる、一般的なグラフでの適応型正確推論のアルゴリズムを紹介します。線形時間の前処理ステップの後、私たちのアプローチでは、モデルの更新と、入力モデルのサイズの対数である時間での周辺計算が可能になります。さらに、max-productとは対照的に、私たちのアプローチでは、入力モデルのサイズではなく、更新されたエントリの数にほぼ比例する時間でMAP構成を更新することもできます。私たちのアルゴリズムの実際の有効性を評価するために、合成データと2つの実際の計算生物学アプリケーションを使用して実装およびテストします。私たちの実験では、モデルが時間の経過とともに少しずつ変化するため、適応型推論は完全な推論を実行するよりも大幅な高速化を実現できることが示されています。
Unsupervised Supervised Learning II: Margin-Based Classification Without Labels
教師なし教師あり学習 II: ラベルなしのマージンベースの分類
Many popular linear classifiers, such as logistic regression, boosting, or SVM, are trained by optimizing a margin-based risk function. Traditionally, these risk functions are computed based on a labeled data set. We develop a novel technique for estimating such risks using only unlabeled data and the marginal label distribution. We prove that the proposed risk estimator is consistent on high-dimensional data sets and demonstrate it on synthetic and real-world data. In particular, we show how the estimate is used for evaluating classifiers in transfer learning, and for training classifiers with no labeled data whatsoever.
ロジスティック回帰、ブースティング、SVMなど、多くの一般的な線形分類器は、マージンベースのリスク関数を最適化することによって学習されます。従来、これらのリスク関数は、ラベル付けされたデータセットに基づいて計算されていました。私たちは、ラベルなしデータと周辺ラベル分布のみを使用してそのようなリスクを推定する新しい手法を開発します。提案されたリスク推定量が高次元データセットで一貫していることを証明し、合成データと実世界でそれを実証します。特に、転移学習における分類器の評価や、ラベル付けされたデータがまったくない分類器の学習に、推定値がどのように使用されるかを示します。
Efficient and Effective Visual Codebook Generation Using Additive Kernels
加法カーネルを使用した効率的かつ効果的なビジュアルコードブック生成
Common visual codebook generation methods used in a bag of visual words model, for example, k-means or Gaussian Mixture Model, use the Euclidean distance to cluster features into visual code words. However, most popular visual descriptors are histograms of image measurements. It has been shown that with histogram features, the Histogram Intersection Kernel (HIK) is more effective than the Euclidean distance in supervised learning tasks. In this paper, we demonstrate that HIK can be used in an unsupervised manner to significantly improve the generation of visual codebooks. We propose a histogram kernel k-means algorithm which is easy to implement and runs almost as fast as the standard k-means. The HIK codebooks have consistently higher recognition accuracy over k-means codebooks by 2-4% in several benchmark object and scene recognition data sets. The algorithm is also generalized to arbitrary additive kernels. Its speed is thousands of times faster than a naive implementation of the kernel k-means algorithm. In addition, we propose a one-class SVM formulation to create more effective visual code words. Finally, we show that the standard k-median clustering method can be used for visual codebook generation and can act as a compromise between the HIK / additive kernel and the k-means approaches.
バッグ オブ ビジュアル ワード モデルで使用される一般的なビジュアル コードブック生成方法(たとえば、k-meansやガウス混合モデル)では、ユークリッド距離を使用して特徴をビジュアル コード ワードにクラスタ化します。ただし、最も一般的なビジュアル記述子は、画像測定のヒストグラムです。ヒストグラム特徴の場合、教師あり学習タスクでは、ヒストグラム交差カーネル(HIK)がユークリッド距離よりも効果的であることがわかっています。この論文では、HIKを教師なし方式で使用して、ビジュアル コードブックの生成を大幅に改善できることを示します。実装が簡単で、標準のk-meansとほぼ同じ速度で実行されるヒストグラム カーネルk-meansアルゴリズムを提案します。HIKコードブックは、いくつかのベンチマーク オブジェクトおよびシーン認識データ セットで、k-meansコードブックよりも一貫して2～4%高い認識精度を示しています。このアルゴリズムは、任意の加法カーネルにも一般化されています。その速度は、カーネルk-meansアルゴリズムの単純な実装よりも数千倍高速です。さらに、より効果的なビジュアル コード ワードを作成するための1クラスSVM定式化を提案します。最後に、標準的なk-medianクラスタリング法をビジュアル コードブックの生成に使用でき、HIK/加法カーネルとk-meansアプローチの妥協点として機能できることを示します。
In All Likelihood, Deep Belief Is Not Enough
おそらく、深い信念だけでは十分ではありません
Statistical models of natural images provide an important tool for researchers in the fields of machine learning and computational neuroscience. The canonical measure to quantitatively assess and compare the performance of statistical models is given by the likelihood. One class of statistical models which has recently gained increasing popularity and has been applied to a variety of complex data is formed by deep belief networks. Analyses of these models, however, have often been limited to qualitative analyses based on samples due to the computationally intractable nature of their likelihood. Motivated by these circumstances, the present article introduces a consistent estimator for the likelihood of deep belief networks which is computationally tractable and simple to apply in practice. Using this estimator, we quantitatively investigate a deep belief network for natural image patches and compare its performance to the performance of other models for natural image patches. We find that the deep belief network is outperformed with respect to the likelihood even by very simple mixture models.
自然画像の統計モデルは、機械学習や計算神経科学の分野の研究者にとって重要なツールを提供します。統計モデルのパフォーマンスを定量的に評価および比較するための標準的な尺度は、尤度です。最近ますます人気が高まり、さまざまな複雑なデータに適用されている統計モデルの1つのクラスは、ディープ ビリーフ ネットワークによって形成されます。ただし、これらのモデルの尤度の計算上の扱いにくさのため、これらのモデルの分析は、サンプルに基づく定性的な分析に限定されることがよくあります。これらの状況に動機付けられて、本記事では、計算上扱いやすく、実際に適用するのが簡単な、ディープ ビリーフ ネットワークの尤度の一貫した推定量を紹介します。この推定量を使用して、自然画像パッチのディープ ビリーフ ネットワークを定量的に調査し、そのパフォーマンスを自然画像パッチの他のモデルのパフォーマンスと比較します。ディープ ビリーフ ネットワークは、非常に単純な混合モデルでさえ、尤度に関して優れていることがわかりました。
The Stationary Subspace Analysis Toolbox
定常部分空間解析ツールボックス
The Stationary Subspace Analysis (SSA) algorithm linearly factorizes a high-dimensional time series into stationary and non-stationary components. The SSA Toolbox is a platform-independent efficient stand-alone implementation of the SSA algorithm with a graphical user interface written in Java, that can also be invoked from the command line and from Matlab. The graphical interface guides the user through the whole process; data can be imported and exported from comma separated values (CSV) and Matlab’s .mat files.
定常部分空間解析(SSA)アルゴリズムは、高次元の時系列を定常成分と非定常成分に線形分解します。SSA Toolboxは、Javaで記述されたグラフィカル ユーザー インターフェイスを備えた、プラットフォームに依存しない効率的なスタンドアロンのSSAアルゴリズムの実装であり、コマンド ラインやMATLABからも呼び出すことができます。グラフィカルインターフェースは、プロセス全体を通じてユーザーをガイドします。データは、カンマ区切り値(CSV)とMatlabの.matファイルからインポートおよびエクスポートできます。
Robust Approximate Bilinear Programming for Value Function Approximation
値関数近似のためのロバスト近似双線形計画法
Value function approximation methods have been successfully used in many applications, but the prevailing techniques often lack useful a priori error bounds. We propose a new approximate bilinear programming formulation of value function approximation, which employs global optimization. The formulation provides strong a priori guarantees on both robust and expected policy loss by minimizing specific norms of the Bellman residual. Solving a bilinear program optimally is NP-hard, but this worst-case complexity is unavoidable because the Bellman-residual minimization itself is NP-hard. We describe and analyze the formulation as well as a simple approximate algorithm for solving bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. We also briefly analyze the behavior of bilinear programming algorithms under incomplete samples. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on simple benchmark problems.
価値関数近似法は多くのアプリケーションで効果的に使用されてきたが、一般的な手法には有用な事前誤差境界が欠けていることが多い。私たちは、グローバル最適化を採用した価値関数近似の新しい近似双線形計画定式化を提案します。この定式化は、ベルマン残差の特定のノルムを最小化することにより、堅牢なポリシー損失と期待されるポリシー損失の両方について強力な事前保証を提供します。双線形計画を最適に解くことはNP困難であるが、ベルマン残差最小化自体がNP困難であるため、この最悪のケースの複雑さは避けられない。私たちは、定式化と、双線形計画を解くための単純な近似アルゴリズムについて説明し、分析します。分析は、このアルゴリズムが近似ポリシー反復の収束一般化を提供することを示す。我々はまた、不完全なサンプルでの双線形計画アルゴリズムの動作を簡単に分析します。最後に、提案されたアプローチが単純なベンチマーク問題でベルマン残差を一貫して最小化できることを示す。
High-dimensional Covariance Estimation Based On Gaussian Graphical Models
ガウスグラフモデルに基づく高次元共分散推定
Undirected graphs are often used to describe high dimensional distributions. Under sparsity conditions, the graph can be estimated using l1-penalization methods. We propose and study the following method. We combine a multiple regression approach with ideas of thresholding and refitting: first we infer a sparse undirected graphical model structure via thresholding of each among many l1-norm penalized regression functions; we then estimate the covariance matrix and its inverse using the maximum likelihood estimator. We show that under suitable conditions, this approach yields consistent estimation in terms of graphical structure and fast convergence rates with respect to the operator and Frobenius norm for the covariance matrix and its inverse. We also derive an explicit bound for the Kullback Leibler divergence.
無向グラフは、高次元分布を記述するためによく使用されます。スパース性条件下では、グラフはl1-ペナルティ法を使用して推定できます。以下の方法を提案し、検討します。私たちは、重回帰アプローチを閾値化および再適合のアイデアと組み合わせます:まず、多くのl1ノルムペナルティ付き回帰関数のうちのそれぞれの閾値化を通じて、まばらな無向グラフィカルモデル構造を推論します。次に、最尤推定量を使用して共分散行列とその逆行列を推定します。適切な条件下では、このアプローチにより、共分散行列とその逆行列の演算子とフロベニウスノルムに関するグラフィカル構造と高速収束率の点で一貫した推定が得られることを示します。また、Kullback Leibler発散の明示的な境界も導出します。
Hierarchical Knowledge Gradient for Sequential Sampling
シーケンシャルサンプリングのための階層的知識勾配
We propose a sequential sampling policy for noisy discrete global optimization and ranking and selection, in which we aim to efficiently explore a finite set of alternatives before selecting an alternative as best when exploration stops. Each alternative may be characterized by a multi-dimensional vector of categorical and numerical attributes and has independent normal rewards. We use a Bayesian probability model for the unknown reward of each alternative and follow a fully sequential sampling policy called the knowledge-gradient policy. This policy myopically optimizes the expected increment in the value of sampling information in each time period. We propose a hierarchical aggregation technique that uses the common features shared by alternatives to learn about many alternatives from even a single measurement. This approach greatly reduces the measurement effort required, but it requires some prior knowledge on the smoothness of the function in the form of an aggregation function and computational issues limit the number of alternatives that can be easily considered to the thousands. We prove that our policy is consistent, finding a globally optimal alternative when given enough measurements, and show through simulations that it performs competitively with or significantly better than other policies.
私たちは、ノイズの多い離散グローバル最適化とランキングおよび選択のための順次サンプリング ポリシーを提案します。このポリシーでは、探索が停止したときに最良の選択肢を選択する前に、有限セットの代替案を効率的に探索することを目指します。各代替案は、カテゴリ属性と数値属性の多次元ベクトルによって特徴付けられ、独立した正規報酬を持ちます。各代替案の未知の報酬にはベイズ確率モデルを使用し、知識勾配ポリシーと呼ばれる完全な順次サンプリング ポリシーに従います。このポリシーは、各期間のサンプリング情報の値の予想される増分を近視眼的に最適化します。私たちは、代替案に共有される共通機能を使用して、単一の測定からでも多くの代替案について学習する階層的集約手法を提案します。このアプローチは、必要な測定労力を大幅に削減しますが、集約関数の形で関数の滑らかさに関する事前知識が必要であり、計算の問題により、簡単に検討できる代替案の数は数千に制限されます。私たちのポリシーは一貫性があり、十分な測定値が与えられた場合にグローバルに最適な代替案を見つけることを証明し、シミュレーションを通じて、他のポリシーと同等か、または大幅に優れたパフォーマンスを発揮することを示します。
On Equivalence Relationships Between Classification and Ranking Algorithms
分類アルゴリズムとランク付けアルゴリズムの等価関係について
We demonstrate that there are machine learning algorithms that can achieve success for two separate tasks simultaneously, namely the tasks of classification and bipartite ranking. This means that advantages gained from solving one task can be carried over to the other task, such as the ability to obtain conditional density estimates, and an order-of-magnitude reduction in computational time for training the algorithm. It also means that some algorithms are robust to the choice of evaluation metric used; they can theoretically perform well when performance is measured either by a misclassification error or by a statistic of the ROC curve (such as the area under the curve). Specifically, we provide such an equivalence relationship between a generalization of Freund et al.’s RankBoost algorithm, called the “P-Norm Push,” and a particular cost-sensitive classification algorithm that generalizes AdaBoost, which we call “P-Classification.” We discuss and validate the potential benefits of this equivalence relationship, and perform controlled experiments to understand P-Classification’s empirical performance. There is no established equivalence relationship for logistic regression and its ranking counterpart, so we introduce a logistic-regression-style algorithm that aims in between classification and ranking, and has promising experimental performance with respect to both tasks.
私たちは、分類と二部ランク付けという2つの別々のタスクを同時に成功させることができる機械学習アルゴリズムがあることを示します。これは、条件付き密度推定値を取得する機能や、アルゴリズムのトレーニングのための計算時間の桁違いの削減など、1つのタスクを解決することで得られる利点を他のタスクに引き継ぐことができることを意味します。また、一部のアルゴリズムは、使用する評価基準の選択に対して堅牢であることも意味します。これらのアルゴリズムは、誤分類エラーまたはROC曲線の統計(曲線の下の領域など)のいずれかでパフォーマンスを測定すると、理論的に優れたパフォーマンスを発揮できます。具体的には、FreundらのRankBoostアルゴリズムの一般化である「P-Norm Push」と、AdaBoostを一般化した特定のコスト重視の分類アルゴリズム(「P-Classification」と呼ぶ)の間に、そのような同等関係を示します。この同等関係の潜在的な利点について説明して検証し、P-Classificationの実験的パフォーマンスを理解するために制御された実験を実行します。ロジスティック回帰とそのランキング対応物の間には確立された同等関係がないため、分類とランキングの中間を目的とし、両方のタスクに関して有望な実験パフォーマンスを持つロジスティック回帰スタイルのアルゴリズムを導入します。
Convergence Rates of Efficient Global Optimization Algorithms
効率的なグローバル最適化アルゴリズムの収束率
In the efficient global optimization problem, we minimize an unknown function f, using as few observations f(x) as possible. It can be considered a continuum-armed-bandit problem, with noiseless data, and simple regret. Expected-improvement algorithms are perhaps the most popular methods for solving the problem; in this paper, we provide theoretical results on their asymptotic behaviour. Implementing these algorithms requires a choice of Gaussian-process prior, which determines an associated space of functions, its reproducing-kernel Hilbert space (RKHS). When the prior is fixed, expected improvement is known to converge on the minimum of any function in its RKHS. We provide convergence rates for this procedure, optimal for functions of low smoothness, and describe a modified algorithm attaining optimal rates for smoother functions. In practice, however, priors are typically estimated sequentially from the data. For standard estimators, we show this procedure may never find the minimum of f. We then propose alternative estimators, chosen to minimize the constants in the rate of convergence, and show these estimators retain the convergence rates of a fixed prior.
効率的なグローバル最適化問題では、できるだけ少ない観測値f(x)を使用して、未知の関数fを最小化します。これは、ノイズのないデータと単純な後悔を伴う連続体アームドバンディット問題と考えることができます。期待改善アルゴリズムは、おそらくこの問題を解決するための最も一般的な方法です。この論文では、その漸近的動作に関する理論的結果を提供します。これらのアルゴリズムを実装するには、ガウス過程事前分布の選択が必要です。これにより、関連する関数の空間、つまりその再生核ヒルベルト空間(RKHS)が決定されます。事前分布が固定されている場合、期待改善は、そのRKHS内の任意の関数の最小値に収束することが知られています。この手順の収束率(滑らかさが低い関数に最適)を示し、より滑らかな関数に対して最適な率を達成する修正アルゴリズムについて説明します。ただし、実際には、事前分布は通常、データから順番に推定されます。標準的な推定量の場合、この手順ではfの最小値が見つからない可能性があることを示します。次に、収束率の定数を最小化するように選択された代替推定量を提案し、これらの推定量が固定事前収束率を保持することを示します。
Efficient Learning with Partially Observed Attributes
部分的に観察された属性による効率的な学習
We investigate three variants of budgeted learning, a setting in which the learner is allowed to access a limited number of attributes from training or test examples. In the “local budget” setting, where a constraint is imposed on the number of available attributes per training example, we design and analyze an efficient algorithm for learning linear predictors that actively samples the attributes of each training instance. Our analysis bounds the number of additional examples sufficient to compensate for the lack of full information on the training set. This result is complemented by a general lower bound for the easier “global budget” setting, where it is only the overall number of accessible training attributes that is being constrained. In the third, “prediction on a budget” setting, when the constraint is on the number of available attributes per test example, we show that there are cases in which there exists a linear predictor with zero error but it is statistically impossible to achieve arbitrary accuracy without full information on test examples. Finally, we run simple experiments on a digit recognition problem that reveal that our algorithm has a good performance against both partial information and full information baselines.
私たちは、学習者がトレーニングまたはテスト例から限られた数の属性にアクセスできる設定である、予算学習の3つのバリエーションを調査します。トレーニング例ごとに利用可能な属性の数に制約が課される「ローカル予算」設定では、各トレーニング インスタンスの属性をアクティブにサンプリングする線形予測子を学習するための効率的なアルゴリズムを設計および分析します。分析では、トレーニング セットの完全な情報の欠如を補うのに十分な追加例の数を制限します。この結果は、より簡単な「グローバル予算」設定の一般的な下限によって補完されます。この設定では、アクセス可能なトレーニング属性の総数のみが制約されます。3番目の「予算に基づく予測」設定では、制約がテスト例ごとに利用可能な属性の数に課される場合、エラーがゼロの線形予測子が存在するが、テスト例の完全な情報なしで任意の精度を達成することは統計的に不可能であるケースがあることを示します。最後に、数字認識問題で簡単な実験を実行し、部分情報ベースラインと完全情報ベースラインの両方に対してアルゴリズムが優れたパフォーマンスを発揮することを示します。
Neyman-Pearson Classification, Convexity and Stochastic Constraints
ネイマン・ピアソン分類、凸性、確率的制約
Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss φ. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with high probability: (i) its φ-type I error is below a pre-specified level and (ii), it has φ-type II error close to the minimum possible. The proposed classifier is obtained by minimizing an empirical convex objective with an empirical convex constraint. The novelty of the method is that the classifier output by this computationally feasible program is shown to satisfy the original constraint on type I error. New techniques to handle such problems are developed and they have consequences on chance constrained programming. We also evaluate the price to pay in terms of type II error for being conservative on type I error.
この論文では、異常検出の問題に動機付けられて、Neyman-Pearsonパラダイムを実装して、凸損失φによるバイナリ分類の非対称エラーに対処します。分類子の有限のコレクションが与えられた場合、それらを組み合わせて、次の2つの特性を高い確率で同時に満たす新しい分類子を取得します: (i)その φ型I誤差が事前に指定されたレベルを下回っている、(ii)φ型II誤差が可能な限り最小に近い。提案された分類器は、経験的凸制約を使用して経験的凸目的を最小化することによって得られます。この方法の新規性は、この計算上実現可能なプログラムによって出力される分類器が、タイプIエラーの元の制約を満たすことが示されていることです。このような問題を処理するための新しい手法が開発され、偶然制約のあるプログラミングに影響を及ぼします。また、タイプIのエラーに対して保守的であるために、タイプIIのエラーの観点から支払うべき価格も評価します。
Scikit-learn: Machine Learning in Python
scikit-learn: Python での機械学習
Scikit-learn is a Python module integrating a wide range of state-of-the-art machine learning algorithms for medium-scale supervised and unsupervised problems. This package focuses on bringing machine learning to non-specialists using a general-purpose high-level language. Emphasis is put on ease of use, performance, documentation, and API consistency. It has minimal dependencies and is distributed under the simplified BSD license, encouraging its use in both academic and commercial settings. Source code, binaries, and documentation can be downloaded from http://scikit-learn.sourceforge.net.
Scikit-learnは、中規模の教師あり問題と教師なし問題に対応する幅広い最先端の機械学習アルゴリズムを統合したPythonモジュールです。このパッケージは、汎用の高級言語を使用して、専門家以外の人々に機械学習を提供することに焦点を当てています。使いやすさ、パフォーマンス、ドキュメント、APIの一貫性に重点が置かれています。依存関係が最小限に抑えられており、簡略化されたBSDライセンスの下で配布されているため、学術的および商業的な設定での使用が奨励されています。ソースコード、バイナリ、およびドキュメントは、http://scikit-learn.sourceforge.netからダウンロードできます。
Structured Variable Selection with Sparsity-Inducing Norms
スパース性誘導ノルムによる構造化変数選択
We consider the empirical risk minimization problem for linear supervised learning, with regularization by structured sparsity-inducing norms. These are defined as sums of Euclidean norms on certain subsets of variables, extending the usual l1-norm and the group l1-norm by allowing the subsets to overlap. This leads to a specific set of allowed nonzero patterns for the solutions of such problems. We first explore the relationship between the groups defining the norm and the resulting nonzero patterns, providing both forward and backward algorithms to go back and forth from groups to patterns. This allows the design of norms adapted to specific prior knowledge expressed in terms of nonzero patterns. We also present an efficient active set algorithm, and analyze the consistency of variable selection for least-squares linear regression in low and high-dimensional settings.
私たちは、線形教師あり学習の経験的リスク最小化問題と、構造化されたスパース性誘導規範による正則化について考えます。これらは、変数の特定のサブセット上のユークリッドノルムの合計として定義され、サブセットが重なるようにすることで、通常のl1-ノルムとグループl1-ノルムを拡張します。これにより、このような問題の解法として許容される非ゼロ パターンの特定のセットが得られます。まず、ノルムを定義するグループと結果として生じる非ゼロパターンとの関係を調査し、グループからパターンに行ったり来たりするための前方アルゴリズムと後方アルゴリズムの両方を提供します。これにより、ゼロ以外のパターンで表現される特定の事前知識に適応した規範の設計が可能になります。また、効率的なアクティブセットアルゴリズムを提示し、低次元および高次元の設定での最小二乗線形回帰の変数選択の一貫性を分析します。
Non-Parametric Estimation of Topic Hierarchies from Texts with Hierarchical Dirichlet Processes
階層的ディリクレ過程を持つテキストからのトピック階層のノンパラメトリック推定
This paper presents hHDP, a hierarchical algorithm for representing a document collection as a hierarchy of latent topics, based on Dirichlet process priors. The hierarchical nature of the algorithm refers to the Bayesian hierarchy that it comprises, as well as to the hierarchy of the latent topics. hHDP relies on nonparametric Bayesian priors and it is able to infer a hierarchy of topics, without making any assumption about the depth of the learned hierarchy and the branching factor at each level. We evaluate the proposed method on real-world data sets in document modeling, as well as in ontology learning, and provide qualitative and quantitative evaluation results, showing that the model is robust, it models accurately the training data set and is able to generalize on held-out data.
この論文では、ディリクレプロセスの事前確率に基づいて、ドキュメントコレクションを潜在的なトピックの階層として表現するための階層的アルゴリズムであるhHDPを紹介します。アルゴリズムの階層的な性質は、アルゴリズムを構成するベイズ階層と、潜在的なトピックの階層を指します。hHDPはノンパラメトリックなベイズ事前分布に依存しており、学習した階層の深さや各レベルでの分岐係数について仮定することなく、トピックの階層を推測できます。提案手法をドキュメントモデリングやオントロジー学習における実世界のデータセットで評価し、定性的および定量的な評価結果を提供することで、モデルがロバストであること、学習データセットを正確にモデル化すること、およびホールドアウトデータに対して一般化できることを示しました。
Large Margin Hierarchical Classification with Mutually Exclusive Class Membership
相互に排他的なクラスメンバーシップを持つ大マージン階層分類
In hierarchical classification, class labels are structured, that is each label value corresponds to one non-root node in a tree, where the inter-class relationship for classification is specified by directed paths of the tree. In such a situation, the focus has been on how to leverage the inter-class relationship to enhance the performance of flat classification, which ignores such dependency. This is critical when the number of classes becomes large relative to the sample size. This paper considers single-path or partial-path hierarchical classification, where only one path is permitted from the root to a leaf node. A large margin method is introduced based on a new concept of generalized margins with respect to hierarchy. For implementation, we consider support vector machines and ψ-learning. Numerical and theoretical analyses suggest that the proposed method achieves the desired objective and compares favorably against strong competitors in the literature, including its flat counterparts. Finally, an application to gene function prediction is discussed.
階層的分類では、クラス ラベルが構造化されています。つまり、各ラベル値はツリー内の1つの非ルート ノードに対応し、分類のクラス間関係はツリーの有向パスによって指定されます。このような状況では、クラス間関係を活用して、このような依存関係を無視するフラット分類のパフォーマンスを向上させる方法に焦点が当てられてきました。これは、サンプル サイズに比べてクラス数が多くなる場合に重要です。この論文では、ルートからリーフ ノードへのパスが1つだけ許可される、シングル パスまたは部分パスの階層的分類について検討します。階層に関する一般化マージンという新しい概念に基づいて、大マージン法が導入されています。実装には、サポート ベクター マシンと ψ 学習を検討します。数値的および理論的分析により、提案された方法は目的を達成し、フラットな対応物を含む文献の強力な競合方法と比較して優れていることが示唆されています。最後に、遺伝子機能予測への応用について説明します。
Convex and Network Flow Optimization for Structured Sparsity
構造化スパース性のための凸型およびネットワークフローの最適化
We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l2- or l∞-norms over groups of variables. Whereas much effort has been put in developing fast optimization techniques when the groups are disjoint or embedded in a hierarchy, we address here the case of general overlapping groups. To this end, we present two different strategies: On the one hand, we show that the proximal operator associated with a sum of l∞-norms can be computed exactly in polynomial time by solving a quadratic min-cost flow problem, allowing the use of accelerated proximal gradient methods. On the other hand, we use proximal splitting techniques, and address an equivalent formulation with non-overlapping groups, but in higher dimension and with additional constraints. We propose efficient and scalable algorithms exploiting these two strategies, which are significantly faster than alternative approaches. We illustrate these methods with several problems such as CUR matrix factorization, multi-task learning of tree-structured dictionaries, background subtraction in video sequences, image denoising with wavelets, and topographic dictionary learning of natural image patches.
私たちは、変数のグループに対するl2またはl∞ ノルムの合計として定義される構造化されたスパース性誘導ノルムによって正規化された学習問題のクラスを検討します。グループが分離されているか階層に埋め込まれている場合の高速最適化手法の開発には多くの努力が払われてきましたが、ここでは一般的な重複グループのケースを取り上げます。このために、2つの異なる戦略を提示します。一方では、l∞ ノルムの合計に関連付けられた近似演算子は、2次最小コストフロー問題を解くことによって多項式時間で正確に計算でき、高速近似勾配法を使用できることを示します。他方では、近似分割手法を使用し、重複しないグループを使用した同等の定式化を、より高次元で追加の制約とともに取り上げます。私たちは、他のアプローチよりも大幅に高速な、これら2つの戦略を活用した効率的でスケーラブルなアルゴリズムを提案します。これらの方法を、CUR行列分解、ツリー構造辞書のマルチタスク学習、ビデオシーケンスの背景減算、ウェーブレットによる画像ノイズ除去、自然画像パッチのトポグラフィック辞書学習などのいくつかの問題で説明します。
Bayesian Co-Training
ベイジアンコトレーニング
Co-training (or more generally, co-regularization) has been a popular algorithm for semi-supervised learning in data with two feature representations (or views), but the fundamental assumptions underlying this type of models are still unclear. In this paper we propose a Bayesian undirected graphical model for co-training, or more generally for semi-supervised multi-view learning. This makes explicit the previously unstated assumptions of a large class of co-training type algorithms, and also clarifies the circumstances under which these assumptions fail. Building upon new insights from this model, we propose an improved method for co-training, which is a novel co-training kernel for Gaussian process classifiers. The resulting approach is convex and avoids local-maxima problems, and it can also automatically estimate how much each view should be trusted to accommodate noisy or unreliable views. The Bayesian co-training approach can also elegantly handle data samples with missing views, that is, some of the views are not available for some data points at learning time. This is further extended to an active sensing framework, in which the missing (sample, view) pairs are actively acquired to improve learning performance. The strength of active sensing model is that one actively sensed (sample, view) pair would improve the joint multi-view classification on all the samples. Experiments on toy data and several real world data sets illustrate the benefits of this approach.
共トレーニング(またはより一般的には共正則化)は、2つの特徴表現(またはビュー)を持つデータにおける半教師あり学習の一般的なアルゴリズムですが、このタイプのモデルの根底にある基本的な仮定は依然として不明です。この論文では、共トレーニング、またはより一般的には半教師ありマルチビュー学習のためのベイジアン無向グラフィカル モデルを提案します。これにより、これまで明示されていなかった大規模な共トレーニング タイプのアルゴリズムの仮定が明確になり、これらの仮定が失敗する状況も明らかになります。このモデルから得られた新しい洞察に基づいて、共トレーニングの改良された方法を提案します。これは、ガウス過程分類器の新しい共トレーニング カーネルです。結果として得られるアプローチは凸型であり、局所最大値の問題を回避し、ノイズの多いビューや信頼できないビューに対応するために各ビューをどの程度信頼すべきかを自動的に推定することもできます。ベイジアン共トレーニング アプローチでは、ビューが欠落しているデータ サンプル(つまり、学習時に一部のデータ ポイントで一部のビューが利用できないデータ)も適切に処理できます。これはさらに、学習パフォーマンスを向上させるために欠落している(サンプル、ビュー)ペアをアクティブに取得するアクティブ センシング フレームワークに拡張されます。アクティブ センシング モデルの強みは、アクティブにセンシングされた1つの(サンプル、ビュー)ペアによって、すべてのサンプルの結合マルチビュー分類が向上することです。おもちゃのデータといくつかの実際のデータ セットでの実験により、このアプローチの利点が実証されています。
Theoretical Analysis of Bayesian Matrix Factorization
ベイズ行列因数分解の理論解析
Recently, variational Bayesian (VB) techniques have been applied to probabilistic matrix factorization and shown to perform very well in experiments. In this paper, we theoretically elucidate properties of the VB matrix factorization (VBMF) method. Through finite-sample analysis of the VBMF estimator, we show that two types of shrinkage factors exist in the VBMF estimator: the positive-part James-Stein (PJS) shrinkage and the trace-norm shrinkage, both acting on each singular component separately for producing low-rank solutions. The trace-norm shrinkage is simply induced by non-flat prior information, similarly to the maximum a posteriori (MAP) approach. Thus, no trace-norm shrinkage remains when priors are non-informative. On the other hand, we show a counter-intuitive fact that the PJS shrinkage factor is kept activated even with flat priors. This is shown to be induced by the non-identifiability of the matrix factorization model, that is, the mapping between the target matrix and factorized matrices is not one-to-one. We call this model-induced regularization. We further extend our analysis to empirical Bayes scenarios where hyperparameters are also learned based on the VB free energy. Throughout the paper, we assume no missing entry in the observed matrix, and therefore collaborative filtering is out of scope.
最近、変分ベイズ(VB)手法が確率的行列分解に適用され、実験で非常に良好なパフォーマンスを示すことが示されています。この論文では、VB行列分解(VBMF)法の特性について理論的に説明します。VBMF推定量の有限サンプル分析により、VBMF推定量には、正の部分James-Stein (PJS)収縮とトレースノルム収縮の2種類の収縮係数が存在することが示され、どちらも各特異成分に個別に作用して低ランクの解を生成します。トレースノルム収縮は、最大事後確率(MAP)アプローチと同様に、非平坦な事前情報によって単純に誘導されます。したがって、事前情報が有益でない場合はトレースノルム収縮は残りません。一方、PJS収縮係数は平坦な事前情報でもアクティブのままであるという直感に反する事実を示します。これは、行列分解モデルの非識別性によって引き起こされることが示されています。つまり、ターゲット行列と分解行列間のマッピングは1対1ではありません。これをモデル誘導正則化と呼びます。さらに、VB自由エネルギーに基づいてハイパーパラメータも学習される経験的ベイズ シナリオに分析を拡張します。この論文全体を通じて、観測された行列に欠落エントリがないと想定しているため、協調フィルタリングは範囲外です。
Kernel Analysis of Deep Networks
ディープネットワークのカーネル解析
When training deep networks it is common knowledge that an efficient and well generalizing representation of the problem is formed. In this paper we aim to elucidate what makes the emerging representation successful. We analyze the layer-wise evolution of the representation in a deep network by building a sequence of deeper and deeper kernels that subsume the mapping performed by more and more layers of the deep network and measuring how these increasingly complex kernels fit the learning problem. We observe that deep networks create increasingly better representations of the learning problem and that the structure of the deep network controls how fast the representation of the task is formed layer after layer.
深層ネットワークを学習させると、問題の効率的でよく一般化された表現が形成されることは周知の事実です。この論文では、新しい表現が成功する理由を解明することを目指しています。ディープネットワークにおける表現のレイヤーごとの進化を解析するために、ディープネットワークのレイヤーごとに実行されるマッピングを包含する、より深く深いカーネルのシーケンスを構築し、これらのますます複雑化するカーネルが学習問題にどのように適合するかを測定します。ディープネットワークは、学習問題の表現をますます改善し、ディープネットワークの構造がタスクの表現が層ごとに形成される速度を制御することを観察します。
Weisfeiler-Lehman Graph Kernels
Weisfeiler-Lehman グラフカーネル
In this article, we propose a family of efficient kernels for large graphs with discrete node labels. Key to our method is a rapid feature extraction scheme based on the Weisfeiler-Lehman test of isomorphism on graphs. It maps the original graph to a sequence of graphs, whose node attributes capture topological and label information. A family of kernels can be defined based on this Weisfeiler-Lehman sequence of graphs, including a highly efficient kernel comparing subtree-like patterns. Its runtime scales only linearly in the number of edges of the graphs and the length of the Weisfeiler-Lehman graph sequence. In our experimental evaluation, our kernels outperform state-of-the-art graph kernels on several graph classification benchmark data sets in terms of accuracy and runtime. Our kernels open the door to large-scale applications of graph kernels in various disciplines such as computational biology and social network analysis.
この記事では、離散ノードラベルを持つ大きなグラフ用の効率的なカーネルのファミリーを提案します。私たちの方法の鍵は、グラフ上の同型のWeisfeiler-Lehman検定に基づく迅速な特徴抽出スキームです。元のグラフを一連のグラフにマップし、そのノード属性がトポロジ情報とラベル情報をキャプチャします。カーネルのファミリーは、このWeisfeiler-Lehmanのグラフシーケンスに基づいて定義でき、サブツリーのようなパターンを比較する非常に効率的なカーネルが含まれます。その実行時間は、グラフのエッジの数とワイスファイラー・リーマングラフ・シーケンスの長さに比例してのみスケーリングされます。私たちの実験的評価では、私たちのカーネルは、精度と実行時間の点で、いくつかのグラフ分類ベンチマークデータセットで最先端のグラフカーネルを上回っています。私たちのカーネルは、計算生物学やソーシャルネットワーク分析などのさまざまな分野でのグラフカーネルの大規模なアプリケーションへの扉を開きます。
Natural Language Processing (Almost) from Scratch
ゼロからの自然言語処理(ほぼ)
We propose a unified neural network architecture and learning algorithm that can be applied to various natural language processing tasks including part-of-speech tagging, chunking, named entity recognition, and semantic role labeling. This versatility is achieved by trying to avoid task-specific engineering and therefore disregarding a lot of prior knowledge. Instead of exploiting man-made input features carefully optimized for each task, our system learns internal representations on the basis of vast amounts of mostly unlabeled training data. This work is then used as a basis for building a freely available tagging system with good performance and minimal computational requirements.
私たちは、品詞のタグ付け、チャンキング、名前付きエンティティ認識、意味的役割のラベリングなど、さまざまな自然言語処理タスクに適用できる統一されたニューラルネットワークアーキテクチャと学習アルゴリズムを提案します。この汎用性は、タスク固有のエンジニアリングを避け、多くの事前知識を無視することで実現されます。私たちのシステムは、各タスクに慎重に最適化された人工の入力機能を利用する代わりに、ほとんどラベルのない膨大な量のトレーニングデータに基づいて内部表現を学習します。この作業は、優れたパフォーマンスと最小限の計算要件を備えた、自由に利用できるタグ付けシステムを構築するための基礎として使用されます。
LPmade: Link Prediction Made Easy
LPmade:リンク予測が簡単に
LPmade is a complete cross-platform software solution for multi-core link prediction and related tasks and analysis. Its first principal contribution is a scalable network library supporting high-performance implementations of the most commonly employed unsupervised link prediction methods. Link prediction in longitudinal data requires a sophisticated and disciplined procedure for correct results and fair evaluation, so the second principle contribution of LPmade is a sophisticated GNU make architecture that completely automates link prediction, prediction evaluation, and network analysis. Finally, LPmade streamlines and automates the procedure for creating multivariate supervised link prediction models with a version of WEKA modified to operate effectively on extremely large data sets. With mere minutes of manual work, one may start with a raw stream of records representing a network and progress through hundreds of steps to generate plots, gigabytes or terabytes of output, and actionable or publishable results.
LPmadeは、マルチコア リンク予測および関連タスクと分析のための完全なクロスプラットフォーム ソフトウェア ソリューションです。その最初の主要な貢献は、最も一般的に使用されている教師なしリンク予測方法の高性能実装をサポートするスケーラブルなネットワーク ライブラリです。縦断的データでのリンク予測には、正しい結果と公正な評価のための高度で規律のある手順が必要です。そのため、LPmadeの2番目の主要な貢献は、リンク予測、予測評価、およびネットワーク分析を完全に自動化する高度なGNU makeアーキテクチャです。最後に、LPmadeは、非常に大規模なデータ セットで効果的に動作するように修正されたWEKAのバージョンを使用して、多変量教師ありリンク予測モデルを作成する手順を合理化および自動化します。わずか数分の手作業で、ネットワークを表すレコードの生のストリームから始めて、数百の手順を経てプロット、ギガバイトまたはテラバイトの出力、および実行可能または公開可能な結果を生成できます。
Distance Dependent Chinese Restaurant Processes
距離依存の中華料理店のプロセス
We develop the distance dependent Chinese restaurant process, a flexible class of distributions over partitions that allows for dependencies between the elements. This class can be used to model many kinds of dependencies between data in infinite clustering models, including dependencies arising from time, space, and network connectivity. We examine the properties of the distance dependent CRP, discuss its connections to Bayesian nonparametric mixture models, and derive a Gibbs sampler for both fully observed and latent mixture settings. We study its empirical performance with three text corpora. We show that relaxing the assumption of exchangeability with distance dependent CRPs can provide a better fit to sequential data and network data. We also show that the distance dependent CRP representation of the traditional CRP mixture leads to a faster-mixing Gibbs sampling algorithm than the one based on the original formulation.
私たちは、距離依存の中華料理店のプロセス、つまり要素間の依存関係を可能にするパーティション上の分布の柔軟なクラスを開発します。このクラスを使用すると、時間、空間、ネットワーク接続から生じる依存関係など、無限クラスタリング モデル内のデータ間のさまざまな種類の依存関係をモデル化できます。距離依存のCRPの特性を調べ、ベイズノンパラメトリック混合モデルとの関係について議論し、完全に観察された混合設定と潜在混合設定の両方についてギブスサンプラーを導出します。その経験的パフォーマンスを3つのテキストコーパスで研究します。距離依存のCRPとの交換可能性の仮定を緩和することで、シーケンシャルデータとネットワークデータにより適合することを示します。また、従来のCRP混合物の距離依存性CRP表現が、元の定式化に基づくものよりも高速に混合するギブス サンプリング アルゴリズムにつながることも示します。
Parallel Algorithm for Learning Optimal Bayesian Network Structure
最適なベイジアンネットワーク構造を学習するための並列アルゴリズム
We present a parallel algorithm for the score-based optimal structure search of Bayesian networks. This algorithm is based on a dynamic programming (DP) algorithm having O(n ⋅ 2n) time and space complexity, which is known to be the fastest algorithm for the optimal structure search of networks with n nodes. The bottleneck of the problem is the memory requirement, and therefore, the algorithm is currently applicable for up to a few tens of nodes. While the recently proposed algorithm overcomes this limitation by a space-time trade-off, our proposed algorithm realizes direct parallelization of the original DP algorithm with O(nσ) time and space overhead calculations, where σ>0 controls the communication-space trade-off. The overall time and space complexity is O(nσ+1 2n). This algorithm splits the search space so that the required communication between independent calculations is minimal. Because of this advantage, our algorithm can run on distributed memory supercomputers. Through computational experiments, we confirmed that our algorithm can run in parallel using up to 256 processors with a parallelization efficiency of 0.74, compared to the original DP algorithm with a single processor. We also demonstrate optimal structure search for a 32-node network without any constraints, which is the largest network search presented in literature.
私たちは、ベイジアンネットワークのスコアベースの最適構造探索のための並列アルゴリズムを紹介します。このアルゴリズムは、O(n⋅2n)の時間と空間の計算量を持つ動的計画法(DP)アルゴリズムに基づいています。これは、nノードのネットワークの最適構造探索のための最速アルゴリズムとして知られています。この問題のボトルネックはメモリ要件であるため、このアルゴリズムは現在数十ノードまでしか適用できません。最近提案されたアルゴリズムは、空間と時間のトレードオフによってこの制限を克服していますが、私たちの提案するアルゴリズムは、O(nσ)の時間と空間のオーバーヘッド計算で元のDPアルゴリズムの直接的な並列化を実現します。ここで、σ>0は通信と空間のトレードオフを制御します。全体的な時間と空間の計算量はO(nσ+1 2n)です。このアルゴリズムは、独立した計算間で必要な通信が最小限になるように検索空間を分割します。この利点により、私たちのアルゴリズムは分散メモリスーパーコンピュータで実行できます。計算実験により、当社のアルゴリズムは最大256個のプロセッサを使用して並列実行でき、並列化効率は0.74であることを確認しました。これは、単一のプロセッサを使用した元のDPアルゴリズムとの比較です。また、制約のない32ノード ネットワークの最適構造検索も実証しました。これは、文献で発表された最大のネットワーク検索です。
Union Support Recovery in Multi-task Learning
マルチタスク学習におけるユニオン支援の回復
We sharply characterize the performance of different penalization schemes for the problem of selecting the relevant variables in the multi-task setting. Previous work focuses on the regression problem where conditions on the design matrix complicate the analysis. A clearer and simpler picture emerges by studying the Normal means model. This model, often used in the field of statistics, is a simplified model that provides a laboratory for studying complex procedures.
私たちは、マルチタスク設定で関連する変数を選択する問題に対するさまざまなペナルティスキームのパフォーマンスを鋭く特徴付けます。以前の研究では、計画行列の条件が分析を複雑にする回帰問題に焦点を当てていました。正規平均モデルを研究することにより、より明確で単純な画像が浮かび上がります。このモデルは、統計学の分野でよく使用され、複雑な手順を研究するための実験室を提供する簡略化されたモデルです。
MULAN: A Java Library for Multi-Label Learning
MULAN:マルチラベル学習用のJavaライブラリ
MULAN is a Java library for learning from multi-label data. It offers a variety of classification, ranking, thresholding and dimensionality reduction algorithms, as well as algorithms for learning from hierarchically structured labels. In addition, it contains an evaluation framework that calculates a rich variety of performance measures.
MULANは、マルチラベルデータから学習するためのJavaライブラリです。さまざまな分類、ランク付け、しきい値処理、次元削減アルゴリズム、および階層構造のラベルから学習するためのアルゴリズムを提供します。さらに、豊富な種類のパフォーマンス指標を計算する評価フレームワークが含まれています。
Universality, Characteristic Kernels and RKHS Embedding of Measures
普遍性、特性カーネル、RKHSのメジャー埋め込み
Over the last few years, two different notions of positive definite (pd) kernels—universal and characteristic—have been developing in parallel in machine learning: universal kernels are proposed in the context of achieving the Bayes risk by kernel-based classification/regression algorithms while characteristic kernels are introduced in the context of distinguishing probability measures by embedding them into a reproducing kernel Hilbert space (RKHS). However, the relation between these two notions is not well understood. The main contribution of this paper is to clarify the relation between universal and characteristic kernels by presenting a unifying study relating them to RKHS embedding of measures, in addition to clarifying their relation to other common notions of strictly pd, conditionally strictly pd and integrally strictly pd kernels. For radial kernels on ℜd, all these notions are shown to be equivalent.
ここ数年、正定値(pd)カーネル—ユニバーサルと特性—の2つの異なる概念が機械学習で並行して発展してきました:ユニバーサル カーネルは、カーネルベースの分類/回帰アルゴリズムによってベイズ リスクを達成するというコンテキストで提案され、特性カーネルは、それらを再現カーネル ヒルベルト空間(RKHS)に埋め込むことによって確率尺度を区別するコンテキストで導入されます。しかし、これら2つの概念の関係はよく理解されていません。この論文の主な貢献は、厳密にpd、条件付きで厳密にPD、および完全に厳密に厳密にPDカーネルの他の一般的な概念との関係を明らかにすることに加えて、それらをRKHSのメジャー埋め込みに関連付ける統一的な研究を提示することにより、ユニバーサルカーネルと特性カーネルの関係を明確にすることです。Rd上の放射状カーネルの場合、これらの概念はすべて同等であることが示されています。
Waffles: A Machine Learning Toolkit
ワッフル:機械学習ツールキット
We present a breadth-oriented collection of cross-platform command-line tools for researchers in machine learning called Waffles. The Waffles tools are designed to offer a broad spectrum of functionality in a manner that is friendly for scripted automation. All functionality is also available in a C++ class library. Waffles is available under the GNU Lesser General Public License.
私たちは、機械学習の研究者向けに、Wafflesと呼ばれるクロスプラットフォームのコマンドラインツールの幅広いコレクションを紹介します。Wafflesツールは、スクリプト化された自動化に適した方法で、幅広い機能を提供するように設計されています。すべての機能は、C++クラス ライブラリでも使用できます。ワッフルは、GNU Lesser General Public Licenseの下で利用できます。
Producing Power-Law Distributions and Damping Word Frequencies with Two-Stage Language Models
2段階言語モデルによるべき乗則分布の生成とワード周波数の減衰
Standard statistical models of language fail to capture one of the most striking properties of natural languages: the power-law distribution in the frequencies of word tokens. We present a framework for developing statistical models that can generically produce power laws, breaking generative models into two stages. The first stage, the generator, can be any standard probabilistic model, while the second stage, the adaptor, transforms the word frequencies of this model to provide a closer match to natural language. We show that two commonly used Bayesian models, the Dirichlet-multinomial model and the Dirichlet process, can be viewed as special cases of our framework. We discuss two stochastic processes—the Chinese restaurant process and its two-parameter generalization based on the Pitman-Yor process—that can be used as adaptors in our framework to produce power-law distributions over word frequencies. We show that these adaptors justify common estimation procedures based on logarithmic or inverse-power transformations of empirical frequencies. In addition, taking the Pitman-Yor Chinese restaurant process as an adaptor justifies the appearance of type frequencies in formal analyses of natural language and improves the performance of a model for unsupervised learning of morphology.
言語の標準的な統計モデルは、自然言語の最も顕著な特性の1つである単語トークンの頻度のべき乗分布を捉えることができません。ここでは、生成モデルを2段階に分割し、一般的にべき乗を生成できる統計モデルを開発するためのフレームワークを示します。第1段階のジェネレータは、任意の標準的な確率モデルにすることができますが、第2段階のアダプタは、このモデルの単語頻度を変換して、自然言語により近い一致を提供します。一般的に使用される2つのベイズ モデル、ディリクレ多項式モデルとディリクレ過程は、このフレームワークの特殊なケースと見なすことができます。ここでは、フレームワークでアダプタとして使用して単語頻度のべき乗分布を生成することができる2つの確率過程、つまり中華料理店の過程と、ピットマン-ヨー過程に基づくその2パラメータ一般化について説明します。これらの過程は、経験的頻度の対数変換または逆べき乗変換に基づく一般的な推定手順を正当化することを示します。さらに、Pitman-Yor中華レストラン プロセスをアダプターとして採用すると、自然言語の形式的な分析におけるタイプ頻度の出現が正当化され、形態論の教師なし学習モデルのパフォーマンスが向上します。
Proximal Methods for Hierarchical Sparse Coding
階層的スパース符号化のための近位法
Sparse coding consists in representing signals as sparse linear combinations of atoms selected from a dictionary. We consider an extension of this framework where the atoms are further assumed to be embedded in a tree. This is achieved using a recently introduced tree-structured sparse regularization norm, which has proven useful in several applications. This norm leads to regularized problems that are difficult to optimize, and in this paper, we propose efficient algorithms for solving them. More precisely, we show that the proximal operator associated with this norm is computable exactly via a dual approach that can be viewed as the composition of elementary proximal operators. Our procedure has a complexity linear, or close to linear, in the number of atoms, and allows the use of accelerated gradient techniques to solve the tree-structured sparse approximation problem at the same computational cost as traditional ones using the l1-norm. Our method is efficient and scales gracefully to millions of variables, which we illustrate in two types of applications: first, we consider fixed hierarchical dictionaries of wavelets to denoise natural images. Then, we apply our optimization tools in the context of dictionary learning, where learned dictionary elements naturally self-organize in a prespecified arborescent structure, leading to better performance in reconstruction of natural image patches. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.
スパースコーディングは、信号を辞書から選択された原子のスパース線形結合として表すことです。このフレームワークの拡張を検討します。この拡張では、原子がさらにツリーに埋め込まれていると想定されます。これは、最近導入されたツリー構造のスパース正則化ノルムを使用して実現されます。このノルムは、いくつかのアプリケーションで有用であることが証明されています。このノルムは、最適化が難しい正則化された問題につながります。この論文では、それらを解決するための効率的なアルゴリズムを提案します。より正確には、このノルムに関連付けられた近似演算子は、基本的な近似演算子の合成と見なすことができるデュアルアプローチを介して正確に計算可能であることを示します。私たちの手順は、原子の数に対して線形または線形に近い複雑さを持ち、加速勾配法を使用して、l1ノルムを使用する従来の方法と同じ計算コストでツリー構造のスパース近似問題を解決できます。私たちの方法は効率的で、数百万の変数に適切に拡張できます。これを2種類のアプリケーションで示します。まず、自然画像のノイズを除去するために、ウェーブレットの固定階層辞書を検討します。次に、辞書学習のコンテキストに最適化ツールを適用します。辞書学習では、学習した辞書要素が事前に指定された樹状構造で自然に自己組織化されるため、自然な画像パッチの再構築のパフォーマンスが向上します。テキスト ドキュメントに適用すると、トピックの階層を学習するため、確率的トピック モデルに代わる競争力のある方法となります。
MSVMpack: A Multi-Class Support Vector Machine Package
MSVMpack: マルチクラス サポート ベクター マシン パッケージ
This paper describes MSVMpack, an open source software package dedicated to our generic model of multi-class support vector machine. All four multi-class support vector machines (M-SVMs) proposed so far in the literature appear as instances of this model. MSVMpack provides for them the first unified implementation and offers a convenient basis to develop other instances. This is also the first parallel implementation for M-SVMs. The package consists in a set of command-line tools with a callable library. The documentation includes a tutorial, a user’s guide and a developer’s guide.
この論文では、マルチクラス サポート ベクター マシンの汎用モデル専用のオープン ソース ソフトウェア パッケージであるMSVMpackについて説明します。これまでに文献で提案された4つのマルチクラス サポート ベクター マシン(M-SVM)はすべて、このモデルのインスタンスとして表示されます。MSVMpackは、最初の統一された実装を提供し、他のインスタンスを開発するための便利な基盤を提供します。これは、M-SVMの最初の並列実装でもあります。このパッケージは、呼び出し可能なライブラリを持つ一連のコマンドラインツールで構成されています。ドキュメントには、チュートリアル、ユーザーズガイド、および開発者ガイドが含まれています。
Smoothness, Disagreement Coefficient, and the Label Complexity of Agnostic Active Learning
非不可知論的アクティブラーニングの滑らかさ、不一致係数、およびラベルの複雑さ
We study pool-based active learning in the presence of noise, that is, the agnostic setting. It is known that the effectiveness of agnostic active learning depends on the learning problem and the hypothesis space. Although there are many cases on which active learning is very useful, it is also easy to construct examples that no active learning algorithm can have an advantage. Previous works have shown that the label complexity of active learning relies on the disagreement coefficient which often characterizes the intrinsic difficulty of the learning problem. In this paper, we study the disagreement coefficient of classification problems for which the classification boundary is smooth and the data distribution has a density that can be bounded by a smooth function. We prove upper and lower bounds for the disagreement coefficients of both finitely and infinitely smooth problems. Combining with existing results, it shows that active learning is superior to passive supervised learning for smooth problems.
私たちは、ノイズが存在する場合、つまり不可知論的設定でのプールベースの能動学習を研究します。不可知論的能動学習の有効性は、学習問題と仮説空間に依存することが知られています。能動学習が非常に有用なケースは多いが、能動学習アルゴリズムが優位性を持たない例を構築することも容易です。これまでの研究では、能動学習のラベル複雑さは、学習問題の本質的な難しさを特徴付けることが多い不一致係数に依存していることが示されています。この論文では、分類境界が滑らかで、データ分布が滑らかな関数で囲まれる密度を持つ分類問題の不一致係数を研究します。有限および無限に滑らかな問題の不一致係数の上限と下限を証明し、既存の結果と組み合わせることで、滑らかな問題では能動学習が受動的な教師あり学習よりも優れていることを示しています。
Multiple Kernel Learning Algorithms
複数のカーネル学習アルゴリズム
In recent years, several methods have been proposed to combine multiple kernels instead of using a single one. These different kernels may correspond to using different notions of similarity or may be using information coming from multiple sources (different representations or different feature subsets). In trying to organize and highlight the similarities and differences between them, we give a taxonomy of and review several multiple kernel learning algorithms. We perform experiments on real data sets for better illustration and comparison of existing algorithms. We see that though there may not be large differences in terms of accuracy, there is difference between them in complexity as given by the number of stored support vectors, the sparsity of the solution as given by the number of used kernels, and training time complexity. We see that overall, using multiple kernels instead of a single one is useful and believe that combining kernels in a nonlinear or data-dependent way seems more promising than linear combination in fusing information provided by simple linear kernels, whereas linear methods are more reasonable when combining complex Gaussian kernels.
近年、単一のカーネルを使用する代わりに複数のカーネルを組み合わせる方法がいくつか提案されています。これらの異なるカーネルは、異なる類似性の概念を使用しているか、複数のソース(異なる表現または異なる特徴サブセット)からの情報を使用している可能性があります。それらの類似点と相違点を整理して強調するために、複数のカーネル学習アルゴリズムを分類し、レビューします。既存のアルゴリズムをよりわかりやすく説明および比較するために、実際のデータセットで実験を行います。精度の点では大きな違いはないかもしれませんが、格納されているサポートベクターの数によって決まる複雑さ、使用されているカーネルの数によって決まるソリューションのスパース性、およびトレーニング時間の複雑さの点で違いがあることがわかります。全体として、単一のカーネルではなく複数のカーネルを使用することは有用であり、単純な線形カーネルによって提供される情報を融合する場合、非線形またはデータ依存の方法でカーネルを組み合わせる方が線形結合よりも有望であると思われますが、複雑なガウスカーネルを組み合わせる場合は線形方法の方が合理的です。
Discriminative Learning of Bayesian Networks via Factorized Conditional Log-Likelihood
因数分解条件付き対数尤度によるベイジアンネットワークの判別学習
We propose an efficient and parameter-free scoring criterion, the factorized conditional log-likelihood (f̂CLL), for learning Bayesian network classifiers. The proposed score is an approximation of the conditional log-likelihood criterion. The approximation is devised in order to guarantee decomposability over the network structure, as well as efficient estimation of the optimal parameters, achieving the same time and space complexity as the traditional log-likelihood scoring criterion. The resulting criterion has an information-theoretic interpretation based on interaction information, which exhibits its discriminative nature. To evaluate the performance of the proposed criterion, we present an empirical comparison with state-of-the-art classifiers. Results on a large suite of benchmark data sets from the UCI repository show that f̂CLL-trained classifiers achieve at least as good accuracy as the best compared classifiers, using significantly less computational resources.
私たちは、ベイジアンネットワーク分類器を学習するための効率的でパラメータフリーのスコアリング基準である因数分解条件付き対数尤度(f̂CLL)を提案します。提案されたスコアは、条件付き対数尤度基準の近似値です。この近似は、ネットワーク構造全体の分解可能性と、最適なパラメータの効率的な推定を保証するために考案され、従来の対数尤度スコアリング基準と同じ時間と空間の複雑さを実現します。結果として得られる基準は、相互作用情報に基づく情報理論的解釈を持ち、その識別性を示します。提案された基準の性能を評価するために、最先端の分類器との経験的比較を提示します。UCIリポジトリのベンチマーク データ セットの大規模なスイートの結果は、FLLでトレーニングされた分類子は、最も比較された分類子と少なくとも同じ精度を達成し、使用する計算リソースが大幅に少ないことを示しています。
On the Relation between Realizable and Nonrealizable Cases of the Sequence Prediction Problem
シーケンス予測問題の実現可能ケースと実現不可能ケースの関係について
A sequence x1,…,xn,… of discrete-valued observations is generated according to some unknown probabilistic law (measure) μ. After observing each outcome, one is required to give conditional probabilities of the next observation. The realizable case is when the measure μ belongs to an arbitrary but known class C of process measures. The non-realizable case is when μ is completely arbitrary, but the prediction performance is measured with respect to a given set C of process measures. We are interested in the relations between these problems and between their solutions, as well as in characterizing the cases when a solution exists and finding these solutions. We show that if the quality of prediction is measured using the total variation distance, then these problems coincide, while if it is measured using the expected average KL divergence, then they are different. For some of the formalizations we also show that when a solution exists it can be obtained as a Bayes mixture over a countable subset of C. We also obtain several characterization of those sets C for which solutions to the considered problems exist. As an illustration to the general results obtained, we show that a solution to the non-realizable case of the sequence prediction problem exists for the set of all finite-memory processes, but does not exist for the set of all stationary processes. It should be emphasized that the framework is completely general: the processes measures considered are not required to be i.i.d., mixing, stationary, or to belong to any parametric family.
離散値の観測値のシーケンスx1,…,xn,…は、未知の確率法則(測度)μ に従って生成されます。各結果を観測した後、次の観測値の条件付き確率を与える必要があります。実現可能なケースは、測度 μ がプロセス測度の任意だが既知のクラスCに属する場合です。実現不可能なケースは、μ が完全に任意であるが、予測パフォーマンスがプロセス測度の特定のセットCに関して測定される場合です。私たちは、これらの問題間およびそれらのソリューション間の関係、およびソリューションが存在する場合の特性評価とこれらのソリューションの発見に興味があります。予測の品質が総変動距離を使用して測定される場合、これらの問題は一致するが、期待平均KLダイバージェンスを使用して測定される場合は異なることを示します。いくつかの形式化では、ソリューションが存在する場合、Cの可算なサブセット上のベイズ混合としてソリューションを取得できることも示します。また、検討中の問題のソリューションが存在するセットCのいくつかの特性評価も取得します。得られた一般的な結果の例として、シーケンス予測問題の実現不可能なケースに対する解は、すべての有限メモリ プロセスの集合に対しては存在するが、すべての定常プロセスの集合に対しては存在しないことを示します。フレームワークは完全に一般的なものであることを強調する必要があります。つまり、考慮されるプロセス測定は、i.i.d.、混合、定常である必要はなく、任意のパラメトリック ファミリに属する必要もありません。
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
オンライン学習と確率最適化のための適応サブグラディエント法
We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms.
私たちは、以前の反復で観察されたデータのジオメトリに関する知識を動的に組み込んで、より有益な勾配ベースの学習を実行する新しいサブグラディエント法のファミリーを紹介します。比喩的に言えば、適応により、非常に予測的だがめったに見られない特徴の形で、干し草の山から針を見つけることができます。我々のパラダイムは、アルゴリズムの勾配ステップを制御するために近似関数を使用する確率的最適化とオンライン学習の最近の進歩に由来しています。私たちは、学習率の設定を大幅に簡素化し、後から選択できる最良の近似関数と同等のリグレット保証をもたらす、近似関数を適応的に変更する装置について説明し、分析します。私たちは、一般的で重要な正則化関数とドメイン制約を伴う経験的リスク最小化問題のためのいくつかの効率的なアルゴリズムを示します。我々は理論的分析を実験的に研究し、適応型サブグラディエント法が最先端の、しかし非適応型のサブグラディエントアルゴリズムよりも優れていることを示します。
Information Rates of Nonparametric Gaussian Process Methods
ノンパラメトリックガウス過程法の情報レート
We consider the quality of learning a response function by a nonparametric Bayesian approach using a Gaussian process (GP) prior on the response function. We upper bound the quadratic risk of the learning procedure, which in turn is an upper bound on the Kullback-Leibler information between the predictive and true data distribution. The upper bound is expressed in small ball probabilities and concentration measures of the GP prior. We illustrate the computation of the upper bound for the Matérn and squared exponential kernels. For these priors the risk, and hence the information criterion, tends to zero for all continuous response functions. However, the rate at which this happens depends on the combination of true response function and Gaussian prior, and is expressible in a certain concentration function. In particular, the results show that for good performance, the regularity of the GP prior should match the regularity of the unknown response function.
私たちは、応答関数の学習品質について、応答関数に先行するガウス過程(GP)を用いたノンパラメトリックベイズアプローチによる学習の品質を検討します。学習手順の2次リスクを上限とし、これが予測データ分布と真のデータ分布の間のKullback-Leibler情報の上限になります。上限は、GPの前の小さなボールの確率と濃度の測度で表されます。Matérnと2乗指数カーネルの上限の計算を示します。これらの事前確率では、リスク、つまり情報量基準は、すべての連続応答関数でゼロになる傾向があります。ただし、これが起こる速度は、真の応答関数とガウス事前分布の組み合わせに依存し、特定の濃度関数で表現できます。特に、結果は、良好なパフォーマンスを得るためには、GP事前分布の規則性が未知の応答関数の規則性と一致する必要があることを示しています。
Exploiting Best-Match Equations for Efficient Reinforcement Learning
効率的な強化学習のためのベストマッチ方程式の活用
This article presents and evaluates best-match learning, a new approach to reinforcement learning that trades off the sample efficiency of model-based methods with the space efficiency of model-free methods. Best-match learning works by approximating the solution to a set of best-match equations, which combine a sparse model with a model-free Q-value function constructed from samples not used by the model. We prove that, unlike regular sparse model-based methods, best-match learning is guaranteed to converge to the optimal Q-values in the tabular case. Empirical results demonstrate that best-match learning can substantially outperform regular sparse model-based methods, as well as several model-free methods that strive to improve the sample efficiency of temporal-difference methods. In addition, we demonstrate that best-match learning can be successfully combined with function approximation.
この記事では、モデルベースの方法のサンプル効率とモデルフリーの方法のスペース効率をトレードオフする強化学習の新しいアプローチであるベストマッチ学習について紹介し、評価します。ベストマッチ学習は、スパースモデルとモデルで使用されていないサンプルから構築されたモデルフリーのQ値関数を組み合わせた一連のベストマッチ方程式の解を近似することで機能します。通常のスパース モデルベースの方法とは異なり、ベストマッチ学習は表形式のケースで最適なQ値に収束することが保証されていることを証明します。経験的な結果は、ベストマッチ学習が通常のスパースモデルベースの方法や、時間差分法のサンプル効率を改善しようとするいくつかのモデルフリーの方法を大幅に上回ることを示しています。さらに、ベストマッチ学習を関数近似とうまく組み合わせることができることを実証します。
A Cure for Variance Inflation in High Dimensional Kernel Principal Component Analysis
高次元カーネル主成分分析における分散インフレーションの治療法
Small sample high-dimensional principal component analysis (PCA) suffers from variance inflation and lack of generalizability. It has earlier been pointed out that a simple leave-one-out variance renormalization scheme can cure the problem. In this paper we generalize the cure in two directions: First, we propose a computationally less intensive approximate leave-one-out estimator, secondly, we show that variance inflation is also present in kernel principal component analysis (kPCA) and we provide a non-parametric renormalization scheme which can quite efficiently restore generalizability in kPCA. As for PCA our analysis also suggests a simplified approximate expression.
小サンプルの高次元主成分分析(PCA)は、分散の膨張と一般化可能性の欠如に悩まされます。単純なleave-one-out分散繰り込みスキームで問題を解決できることは以前に指摘されました。この論文では、治療を2つの方向に一般化します:まず、計算量が少ない近似leave-one-out推定量を提案し、次に、分散インフレーションがカーネル主成分分析(kPCA)にも存在することを示し、kPCAの一般化可能性を非常に効率的に復元できるノンパラメトリック繰り込みスキームを提供します。PCAに関しては、私たちの分析では、簡略化された近似式も示唆されています。
The arules R-Package Ecosystem: Analyzing Interesting Patterns from Large Transaction Data Sets
arules R-Packageエコシステム:大規模なトランザクションデータセットからの興味深いパターンの分析
This paper describes the ecosystem of R add-on packages developed around the infrastructure provided by the package arules. The packages provide comprehensive functionality for analyzing interesting patterns including frequent itemsets, association rules, frequent sequences and for building applications like associative classification. After discussing the ecosystem’s design we illustrate the ease of mining and visualizing rules with a short example.
この論文では、パッケージarulesによって提供されるインフラストラクチャを中心に開発されたRアドオンパッケージのエコシステムについて説明します。パッケージは、頻出アイテムセット、関連ルール、頻出シーケンスなどの興味深いパターンを分析し、連想分類などのアプリケーションを構築するための包括的な機能を提供します。エコシステムの設計について説明した後、マイニングとルールの視覚化の容易さを簡単な例で説明します。
Generalized TD Learning
ジェネラライズドTDラーニング
Since the invention of temporal difference (TD) learning (Sutton, 1988), many new algorithms for model-free policy evaluation have been proposed. Although they have brought much progress in practical applications of reinforcement learning (RL), there still remain fundamental problems concerning statistical properties of the value function estimation. To solve these problems, we introduce a new framework, semiparametric statistical inference, to model-free policy evaluation. This framework generalizes TD learning and its extensions, and allows us to investigate statistical properties of both of batch and online learning procedures for the value function estimation in a unified way in terms of estimating functions. Furthermore, based on this framework, we derive an optimal estimating function with the minimum asymptotic variance and propose batch and online learning algorithms which achieve the optimality.
時間差分(TD)学習の発明(Sutton、1988)以来、モデルフリーの政策評価のための多くの新しいアルゴリズムが提案されてきました。強化学習(RL)の実用化は大きく進んでいますが、価値関数推定の統計的性質については、まだ根本的な問題が残っています。これらの問題を解決するために、モデルフリーの政策評価にセミパラメトリック統計推論という新しいフレームワークを導入します。このフレームワークは、TD学習とその拡張を一般化し、価値関数推定のためのバッチ学習手順とオンライン学習手順の両方の統計的特性を推定関数の観点から統一的に調査することを可能にします。さらに、このフレームワークに基づいて、漸近分散が最小の最適推定関数を導出し、最適性を実現するバッチ学習アルゴリズムとオンライン学習アルゴリズムを提案します。
Kernel Regression in the Presence of Correlated Errors
相関エラーが存在する場合のカーネル回帰
It is a well-known problem that obtaining a correct bandwidth and/or smoothing parameter in nonparametric regression is difficult in the presence of correlated errors. There exist a wide variety of methods coping with this problem, but they all critically depend on a tuning procedure which requires accurate information about the correlation structure. We propose a bandwidth selection procedure based on bimodal kernels which successfully removes the correlation without requiring any prior knowledge about its structure and its parameters. Further, we show that the form of the kernel is very important when errors are correlated which is in contrast to the independent and identically distributed (i.i.d.) case. Finally, some extensions are proposed to use the proposed criterion in support vector machines and least squares support vector machines for regression.
相関誤差が存在すると、ノンパラメトリック回帰で正しい帯域幅や平滑化パラメータを取得することが困難になることはよく知られた問題です。この問題に対処する方法は多岐にわたりますが、それらはすべて、相関構造に関する正確な情報を必要とする調整手順に大きく依存しています。私たちは、その構造とそのパラメータについての予備知識を必要とせずに相関を成功裏に除去するバイモーダルカーネルに基づく帯域幅選択手順を提案します。さらに、カーネルの形式は、エラーが相関している場合に非常に重要であることを示しています。これは、独立および同一に分布している(i.i.d.)ケースとは対照的です。最後に、提案された基準をサポートベクターマシンと最小二乗サポートベクターマシンで回帰に使用するために、いくつかの拡張が提案されています。
Dirichlet Process Mixtures of Generalized Linear Models
一般化線形モデルのディリクレ過程混合
We propose Dirichlet Process mixtures of Generalized Linear Models (DP-GLM), a new class of methods for nonparametric regression. Given a data set of input-response pairs, the DP-GLM produces a global model of the joint distribution through a mixture of local generalized linear models. DP-GLMs allow both continuous and categorical inputs, and can model the same class of responses that can be modeled with a generalized linear model. We study the properties of the DP-GLM, and show why it provides better predictions and density estimates than existing Dirichlet process mixture regression models. We give conditions for weak consistency of the joint distribution and pointwise consistency of the regression estimate.
私たちは、ノンパラメトリック回帰の新しいクラスの方法である一般化線形モデルのディリクレプロセス混合物(DP-GLM)を提案します。入力-応答ペアのデータセットが与えられた場合、DP-GLMは、局所的な一般化線形モデルの組み合わせを通じて、同時分布のグローバル モデルを生成します。DP-GLMは、連続入力とカテゴリカル入力の両方を許可し、一般化線形モデルでモデル化できるのと同じクラスの応答をモデル化できます。DP-GLMの特性を研究し、既存のDirichletプロセス混合回帰モデルよりも優れた予測と密度推定を提供する理由を示します。私たちは、同時分布の弱い一貫性と回帰推定値の点ごとの一貫性のための条件を与える。
Internal Regret with Partial Monitoring: Calibration-Based Optimal Algorithms
パーシャルモニタリングによる内部後悔:キャリブレーションベースの最適アルゴリズム
We provide consistent random algorithms for sequential decision under partial monitoring, when the decision maker does not observe the outcomes but receives instead random feedback signals. Those algorithms have no internal regret in the sense that, on the set of stages where the decision maker chose his action according to a given law, the average payoff could not have been improved in average by using any other fixed law. They are based on a generalization of calibration, no longer defined in terms of a Voronoï diagram but instead of a Laguerre diagram (a more general concept). This allows us to bound, for the first time in this general framework, the expected average internal, as well as the usual external, regret at stage n by O(n-1/3), which is known to be optimal.
私たちは、意思決定者が結果を観察せず、代わりにランダムなフィードバック信号を受け取る場合、パーシャルモニタリングの下での逐次決定のための一貫したランダムアルゴリズムを提供します。これらのアルゴリズムは、意思決定者が与えられた法則に従って行動を選択した一連の段階では、他の固定法則を使用して平均的に利益を向上させることができなかったという意味で、内部的な後悔はありません。これらはキャリブレーションの一般化に基づいており、もはやボロノイ図ではなく、ラゲール図(より一般的な概念)の観点から定義されています。これにより、この一般的なフレームワークで初めて、ステージnでの予想される平均内部後悔と通常の外部後悔を、最適であることが知られているO(n-1/3)だけ限定することができます。
Stochastic Methods for l1-regularized Loss Minimization
l1正則化損失最小化のための確率的手法
We describe and analyze two stochastic methods for l1 regularized loss minimization problems, such as the Lasso. The first method updates the weight of a single feature at each iteration while the second method updates the entire weight vector but only uses a single training example at each iteration. In both methods, the choice of feature or example is uniformly at random. Our theoretical runtime analysis suggests that the stochastic methods should outperform state-of-the-art deterministic approaches, including their deterministic counterparts, when the size of the problem is large. We demonstrate the advantage of stochastic methods by experimenting with synthetic and natural data sets.
私たちは、Lassoなどのl1正則化損失最小化問題に対する2つの確率的手法を記述し、分析します。最初の方法では、各反復で1つの特徴の重みを更新しますが、2番目の方法では、重みベクトル全体を更新しますが、各反復で1つのトレーニング例のみを使用します。どちらの方法でも、特徴または例の選択は一様にランダムに行われます。私たちの理論的なランタイム分析は、問題のサイズが大きい場合、確率論的手法は、決定論的対応物を含む最先端の決定論的アプローチよりも優れているはずであることを示唆しています。私たちは、合成データセットと自然データセットで実験することにより、確率的手法の利点を実証します。
A Refined Margin Analysis for Boosting Algorithms via Equilibrium Margin
平衡余裕によるアルゴリズムのブースティングのための精緻な余裕分析
Much attention has been paid to the theoretical explanation of the empirical success of AdaBoost. The most influential work is the margin theory, which is essentially an upper bound for the generalization error of any voting classifier in terms of the margin distribution over the training data. However, important questions were raised about the margin explanation. Breiman (1999) proved a bound in terms of the minimum margin, which is sharper than the margin distribution bound. He argued that the minimum margin would be better in predicting the generalization error. Grove and Schuurmans (1998) developed an algorithm called LP-AdaBoost which maximizes the minimum margin while keeping all other factors the same as AdaBoost. In experiments however, LP-AdaBoost usually performs worse than AdaBoost, putting the margin explanation into serious doubt. In this paper, we make a refined analysis of the margin theory. We prove a bound in terms of a new margin measure called the Equilibrium margin (Emargin). The Emargin bound is uniformly sharper than Breiman’s minimum margin bound. Thus our result suggests that the minimum margin may be not crucial for the generalization error. We also show that a large Emargin and a small empirical error at Emargin imply a smaller bound of the generalization error. Experimental results on benchmark data sets demonstrate that AdaBoost usually has a larger Emargin and a smaller test error than LP-AdaBoost, which agrees well with our theory.
AdaBoostの実証的な成功の理論的説明には、多くの注目が集まっています。最も影響力のある研究はマージン理論です。これは基本的に、トレーニング データ上のマージン分布の観点から、投票分類器の一般化エラーの上限です。しかし、マージンの説明については重要な疑問が提起されました。Breiman (1999)は、マージン分布の上限よりも厳しい最小マージンの観点から上限を証明しました。彼は、最小マージンの方が一般化エラーの予測に適していると主張しました。GroveとSchuurmans (1998)は、他のすべての要素をAdaBoostと同じに保ちながら最小マージンを最大化するLP-AdaBoostと呼ばれるアルゴリズムを開発しました。しかし、実験では、LP-AdaBoostは通常AdaBoostよりもパフォーマンスが悪く、マージンの説明に重大な疑問が生じています。この論文では、マージン理論の詳細な分析を行います。均衡マージン(Emargin)と呼ばれる新しいマージン測定の観点から上限を証明します。Emargin境界は、Breimanの最小マージン境界よりも一様に鋭いです。したがって、私たちの結果は、最小マージンが一般化誤差にとって重要ではない可能性があることを示唆しています。また、Emarginが大きく、Emarginでの経験的誤差が小さいということは、一般化誤差の境界が小さいことを意味します。ベンチマーク データ セットでの実験結果では、AdaBoostは通常、LP-AdaBoostよりもEmarginが大きく、テスト誤差が小さいことが示されており、これは私たちの理論とよく一致しています。
Hyper-Sparse Optimal Aggregation
ハイパースパース最適集約
Given a finite set F of functions and a learning sample, the aim of an aggregation procedure is to have a risk as close as possible to risk of the best function in F. Up to now, optimal aggregation procedures are convex combinations of every elements of F. In this paper, we prove that optimal aggregation procedures combining only two functions in F exist. Such algorithms are of particular interest when F contains many irrelevant functions that should not appear in the aggregation procedure. Since selectors are suboptimal aggregation procedures, this proves that two is the minimal number of elements of F required for the construction of an optimal aggregation procedure in every situations. Then, we perform a numerical study for the problem of selection of the regularization parameters of the Lasso and the Elastic-net estimators. We compare on simulated examples our aggregation algorithms to aggregation with exponential weights, to Mallow’s Cp and to cross-validation selection procedures.
関数の有限集合Fと学習サンプルが与えられた場合、集約手順の目的は、リスクをF内の最良の関数のリスクにできるだけ近づけることです。現在まで、最適な集約手順は、Fのすべての要素の凸結合です。この論文では、F内の2つの関数のみを結合する最適な集約手順が存在することを証明します。このようなアルゴリズムは、集約手順に出現すべきではない無関係な関数がFに多数含まれている場合に特に重要です。セレクタは次善の集約手順であるため、あらゆる状況で最適な集約手順を構築するために必要なFの要素の最小数は2であることが証明されます。次に、LassoおよびElastic-net推定量の正則化パラメータの選択問題について数値的研究を行います。シミュレーション例で、集約アルゴリズムを指数重みによる集約、MallowのCp、および交差検証選択手順と比較します。
Learning Latent Tree Graphical Models
潜在木グラフィカルモデルの学習
We study the problem of learning a latent tree graphical model where samples are available only from a subset of variables. We propose two consistent and computationally efficient algorithms for learning minimal latent trees, that is, trees without any redundant hidden nodes. Unlike many existing methods, the observed nodes (or variables) are not constrained to be leaf nodes. Our algorithms can be applied to both discrete and Gaussian random variables and our learned models are such that all the observed and latent variables have the same domain (state space). Our first algorithm, recursive grouping, builds the latent tree recursively by identifying sibling groups using so-called information distances. One of the main contributions of this work is our second algorithm, which we refer to as CLGrouping. CLGrouping starts with a pre-processing procedure in which a tree over the observed variables is constructed. This global step groups the observed nodes that are likely to be close to each other in the true latent tree, thereby guiding subsequent recursive grouping (or equivalent procedures such as neighbor-joining) on much smaller subsets of variables. This results in more accurate and efficient learning of latent trees. We also present regularized versions of our algorithms that learn latent tree approximations of arbitrary distributions. We compare the proposed algorithms to other methods by performing extensive numerical experiments on various latent tree graphical models such as hidden Markov models and star graphs. In addition, we demonstrate the applicability of our methods on real-world data sets by modeling the dependency structure of monthly stock returns in the S&P index and of the words in the 20 newsgroups data set.
私たちは、サンプルが変数のサブセットからのみ得られる潜在木グラフィカルモデルの学習問題を研究しています。私たちは、最小潜在木、つまり冗長な隠れノードのない木を学習するための、一貫性があり計算効率の高い2つのアルゴリズムを提案しています。多くの既存の方法とは異なり、観測ノード(または変数)はリーフ ノードである必要はありません。我々のアルゴリズムは、離散ランダム変数とガウス ランダム変数の両方に適用でき、学習したモデルは、すべての観測変数と潜在変数が同じドメイン(状態空間)を持つようになっています。最初のアルゴリズムである再帰グループ化は、いわゆる情報距離を使用して兄弟グループを識別することにより、潜在木を再帰的に構築します。この研究の主な貢献の1つは、CLGroupingと呼ぶ2番目のアルゴリズムです。CLGroupingは、観測変数上の木が構築される前処理手順から始まります。このグローバルステップは、真の潜在木で互いに近いと思われる観測ノードをグループ化し、それによって、はるかに小さい変数のサブセットでの後続の再帰グループ化（または近傍結合などの同等の手順）を導きます。これにより、潜在木の学習がより正確で効率的になります。また、任意の分布の潜在木近似を学習するアルゴリズムの正規化バージョンも紹介します。隠れマルコフモデルやスターグラフなどのさまざまな潜在木グラフィカルモデルで広範な数値実験を実行して、提案されたアルゴリズムを他の方法と比較します。さらに、S&Pインデックスの月次株式収益と20のニュースグループのデータセット内の単語の依存関係構造をモデル化することで、実際のデータセットへの方法の適用可能性を示します。
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes
部分的に観測可能なマルコフ決定過程における学習と計画のためのベイズアプローチ
Bayesian learning methods have recently been shown to provide an elegant solution to the exploration-exploitation trade-off in reinforcement learning. However most investigations of Bayesian reinforcement learning to date focus on the standard Markov Decision Processes (MDPs). The primary focus of this paper is to extend these ideas to the case of partially observable domains, by introducing the Bayes-Adaptive Partially Observable Markov Decision Processes. This new framework can be used to simultaneously (1) learn a model of the POMDP domain through interaction with the environment, (2) track the state of the system under partial observability, and (3) plan (near-)optimal sequences of actions. An important contribution of this paper is to provide theoretical results showing how the model can be finitely approximated while preserving good learning performance. We present approximate algorithms for belief tracking and planning in this model, as well as empirical results that illustrate how the model estimate and agent’s return improve as a function of experience.
ベイズ学習法は最近、強化学習における探索と活用のトレードオフにエレガントなソリューションを提供することが示されました。しかし、これまでのベイズ強化学習の調査のほとんどは、標準的なマルコフ決定プロセス(MDP)に焦点を当てています。この論文の主な焦点は、ベイズ適応型部分観測マルコフ決定プロセスを導入することにより、これらのアイデアを部分観測ドメインのケースに拡張することです。この新しいフレームワークを使用すると、(1)環境との相互作用を通じてPOMDPドメインのモデルを学習し、(2)部分観測下でシステムの状態を追跡し、(3) (ほぼ)最適なアクション シーケンスを計画することができます。この論文の重要な貢献は、モデルを有限に近似しながらも優れた学習パフォーマンスを維持する方法を示した理論的結果を提供することです。このモデルでの信念追跡と計画の近似アルゴリズムと、経験の関数としてモデル推定値とエージェントのリターンがどのように改善するかを示す実証結果を示します。
Domain Decomposition Approach for Fast Gaussian Process Regression of Large Spatial Data Sets
大規模空間データセットの高速ガウス過程回帰のための領域分割アプローチ
Gaussian process regression is a flexible and powerful tool for machine learning, but the high computational complexity hinders its broader applications. In this paper, we propose a new approach for fast computation of Gaussian process regression with a focus on large spatial data sets. The approach decomposes the domain of a regression function into small subdomains and infers a local piece of the regression function for each subdomain. We explicitly address the mismatch problem of the local pieces on the boundaries of neighboring subdomains by imposing continuity constraints. The new approach has comparable or better computation complexity as other competing methods, but it is easier to be parallelized for faster computation. Moreover, the method can be adaptive to non-stationary features because of its local nature and, in particular, its use of different hyperparameters of the covariance function for different local regions. We illustrate application of the method and demonstrate its advantages over existing methods using two synthetic data sets and two real spatial data sets.
ガウス過程回帰は機械学習のための柔軟で強力なツールですが、計算の複雑さが高いため、幅広い応用が妨げられています。この論文では、大規模な空間データセットに焦点を当てたガウス過程回帰の高速計算のための新しいアプローチを提案します。このアプローチでは、回帰関数のドメインを小さなサブドメインに分解し、サブドメインごとに回帰関数のローカル部分を推測します。連続性制約を課すことで、隣接するサブドメインの境界上のローカル部分の不一致の問題に明示的に対処します。新しいアプローチの計算の複雑さは他の競合方法と同等かそれ以上ですが、より高速な計算のために並列化することが容易です。さらに、この方法は、そのローカルな性質、特に異なるローカル領域に対して共分散関数の異なるハイパーパラメータを使用することにより、非定常な特徴に適応できます。2つの合成データセットと2つの実際の空間データセットを使用して、この方法の適用例を示し、既存の方法に対する利点を示します。
X-Armed Bandits
X-アームド・バンディット
We consider a generalization of stochastic bandits where the set of arms, X, is allowed to be a generic measurable space and the mean-payoff function is “locally Lipschitz” with respect to a dissimilarity function that is known to the decision maker. Under this condition we construct an arm selection policy, called HOO (hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if X is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally continuous with a known smoothness degree, then the expected regret of HOO is bounded up to a logarithmic factor by √n, that is, the rate of growth of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric. Our basic strategy has quadratic computational complexity as a function of the number of time steps and does not rely on the doubling trick. We also introduce a modified strategy, which relies on the doubling trick but runs in linearithmic time. Both results are improvements with respect to previous approaches.
私たちは、アームセットXが一般的な測定可能な空間であることが許され、平均利得関数が意思決定者に知られている非類似度関数に関して「局所的にLipschitz」である、確率的バンディットの一般化について検討します。この条件下で、我々はHOO (階層的楽観的最適化)と呼ばれるアーム選択ポリシーを構築します。このポリシーは、大規模な問題クラスに対する以前の結果と比較して、後悔の境界が改善されています。特に、我々の結果は、Xがユークリッド空間の単位超立方体であり、平均利得関数に有限数のグローバル最大値があり、その周りで関数の動作が既知の滑らかさの度合いで局所的に連続している場合、HOOの期待される後悔は √nによる対数係数に制限される、つまり、後悔の増加率は空間の次元に依存しないことを意味します。また、非類似度が測定基準である場合のアルゴリズムのミニマックス最適性も証明します。私たちの基本戦略は、時間ステップ数の関数として計算複雑度が2次関数であり、倍増トリックに依存しません。また、倍増トリックに依存しながらも線形時間で実行される修正戦略も紹介します。どちらの結果も、以前のアプローチに比べて改善されています。
Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates
高次元マルコフ森林分布の学習:エラー率の解析
The problem of learning forest-structured discrete graphical models from i.i.d. samples is considered. An algorithm based on pruning of the Chow-Liu tree through adaptive thresholding is proposed. It is shown that this algorithm is both structurally consistent and risk consistent and the error probability of structure learning decays faster than any polynomial in the number of samples under fixed model size. For the high-dimensional scenario where the size of the model d and the number of edges k scale with the number of samples n, sufficient conditions on (n,d,k) are given for the algorithm to satisfy structural and risk consistencies. In addition, the extremal structures for learning are identified; we prove that the independent (resp., tree) model is the hardest (resp., easiest) to learn using the proposed algorithm in terms of error rates for structure learning.
i.i.d.サンプルからフォレスト構造の離散グラフィカルモデルを学習する問題を検討します。適応閾値化によるChow-Liuツリーの剪定に基づくアルゴリズムが提案されています。このアルゴリズムは構造的に一貫性があり、リスクも一貫しており、構造学習の誤差確率は、固定モデルサイズの下でのサンプル数において、どの多項式よりも速く減衰することが示されています。モデルdのサイズとエッジの数kがサンプルの数nに比例する高次元のシナリオでは、アルゴリズムが構造的およびリスクの一貫性を満たすための十分な条件(n,d,k)が与えられます。さらに、学習のための極値構造が特定されます。私たちは、独立モデル(それぞれ、ツリー)が、構造学習のエラー率に関して、提案されたアルゴリズムを使用して学習するのが最も難しい(それぞれ、最も容易)であることを証明します。
Double Updating Online Learning
オンライン学習のダブルアップデート
In most kernel based online learning algorithms, when an incoming instance is misclassified, it will be added into the pool of support vectors and assigned with a weight, which often remains unchanged during the rest of the learning process. This is clearly insufficient since when a new support vector is added, we generally expect the weights of the other existing support vectors to be updated in order to reflect the influence of the added support vector. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short, that explicitly addresses this problem. Instead of only assigning a fixed weight to the misclassified example received at the current trial, the proposed online learning algorithm also tries to update the weight for one of the existing support vectors. We show that the mistake bound can be improved by the proposed online learning method. We conduct an extensive set of empirical evaluations for both binary and multi-class online learning tasks. The experimental results show that the proposed technique is considerably more effective than the state-of-the-art online learning algorithms. The source code is available to public at http://www.cais.ntu.edu.sg/~chhoi/DUOL/.
ほとんどのカーネルベースのオンライン学習アルゴリズムでは、入力されたインスタンスが誤分類されると、サポート ベクトルのプールに追加され、重みが割り当てられますが、この重みは学習プロセスの残りの間は変更されないことがよくあります。これは明らかに不十分です。新しいサポート ベクトルが追加されると、通常、追加されたサポート ベクトルの影響を反映するために、他の既存のサポート ベクトルの重みが更新されることが期待されるためです。この論文では、この問題に明示的に対処するDouble Updating Online Learning (略してDUOL)と呼ばれる新しいオンライン学習方法を提案します。提案されたオンライン学習アルゴリズムは、現在の試行で受信した誤分類された例に固定の重みを割り当てるだけでなく、既存のサポート ベクトルの1つに対する重みの更新も試みます。提案されたオンライン学習方法によって、誤りの境界を改善できることを示します。バイナリ クラスとマルチクラスの両方のオンライン学習タスクについて、広範な一連の実証的評価を実施します。実験結果から、提案された手法は最先端のオンライン学習アルゴリズムよりもかなり効果的であることがわかります。ソースコードはhttp://www.cais.ntu.edu.sg/~chhoi/DUOL/で公開されています。
Super-Linear Convergence of Dual Augmented Lagrangian Algorithm for Sparsity Regularized Estimation
スパース性正則化推定のための双対拡張ラグランジュアルゴリズムの超線形収束
We analyze the convergence behaviour of a recently proposed algorithm for regularized estimation called Dual Augmented Lagrangian (DAL). Our analysis is based on a new interpretation of DAL as a proximal minimization algorithm. We theoretically show under some conditions that DAL converges super-linearly in a non-asymptotic and global sense. Due to a special modelling of sparse estimation problems in the context of machine learning, the assumptions we make are milder and more natural than those made in conventional analysis of augmented Lagrangian algorithms. In addition, the new interpretation enables us to generalize DAL to wide varieties of sparse estimation problems. We experimentally confirm our analysis in a large scale l1-regularized logistic regression problem and extensively compare the efficiency of DAL algorithm to previously proposed algorithms on both synthetic and benchmark data sets.
私たちは、最近提案されたDual Augmented Lagrangian(DAL)と呼ばれる正則化推定アルゴリズムの収束挙動を分析します。私たちの分析は、近位最小化アルゴリズムとしてのDALの新しい解釈に基づいています。理論的には、いくつかの条件下でDALが非漸近的かつグローバルな意味で超線形に収束することを示しています。機械学習のコンテキストでは、スパース推定問題の特別なモデリングが行われるため、従来の拡張ラグランジュアルゴリズムの分析よりも穏やかで自然な仮定が得られます。さらに、新しい解釈により、DALを多種多様なスパース推定問題に一般化することができます。大規模なl1正則化ロジスティック回帰問題での分析を実験的に確認し、DALアルゴリズムの効率を、合成データセットとベンチマークデータセットの両方で以前に提案されたアルゴリズムと広く比較します。
Learning from Partial Labels
パーシャルラベルから学ぶ
We address the problem of partially-labeled multiclass classification, where instead of a single label per instance, the algorithm is given a candidate set of labels, only one of which is correct. Our setting is motivated by a common scenario in many image and video collections, where only partial access to labels is available. The goal is to learn a classifier that can disambiguate the partially-labeled training instances, and generalize to unseen data. We define an intuitive property of the data distribution that sharply characterizes the ability to learn in this setting and show that effective learning is possible even when all the data is only partially labeled. Exploiting this property of the data, we propose a convex learning formulation based on minimization of a loss function appropriate for the partial label setting. We analyze the conditions under which our loss function is asymptotically consistent, as well as its generalization and transductive performance. We apply our framework to identifying faces culled from web news sources and to naming characters in TV series and movies; in particular, we annotated and experimented on a very large video data set and achieve 6% error for character naming on 16 episodes of the TV series Lost.
私たちは、インスタンスごとに単一のラベルではなく、候補となるラベルのセットがアルゴリズムに与えられ、そのうちの1つだけが正しいという、部分的にラベル付けされたマルチクラス分類の問題に取り組んでいます。我々の設定は、多くの画像や動画のコレクションで、ラベルに部分的なアクセスしかできないという一般的なシナリオに基づいています。目標は、部分的にラベル付けされたトレーニング インスタンスを明確にし、未知のデータに一般化できる分類器を学習することです。私たちは、この設定での学習能力を明確に特徴付けるデータ分布の直感的な特性を定義し、すべてのデータが部分的にしかラベル付けされていない場合でも効果的な学習が可能であることを示します。データのこの特性を利用して、部分ラベル設定に適した損失関数の最小化に基づく凸学習定式化を提案します。損失関数が漸近的に整合する条件、およびその一般化と変換パフォーマンスを分析します。私たちは、このフレームワークを、Webニュース ソースから収集された顔の識別や、テレビ シリーズや映画の登場人物の命名に適用します。特に、非常に大規模なビデオデータセットに注釈を付けて実験し、テレビシリーズ「LOST」の16エピソードの登場人物の命名で6%の誤差を達成しました。
Computationally Efficient Convolved Multiple Output Gaussian Processes
計算効率の高い畳み込み多出力ガウス過程
Recently there has been an increasing interest in regression methods that deal with multiple outputs. This has been motivated partly by frameworks like multitask learning, multisensor networks or structured output data. From a Gaussian processes perspective, the problem reduces to specifying an appropriate covariance function that, whilst being positive semi-definite, captures the dependencies between all the data points and across all the outputs. One approach to account for non-trivial correlations between outputs employs convolution processes. Under a latent function interpretation of the convolution transform we establish dependencies between output variables. The main drawbacks of this approach are the associated computational and storage demands. In this paper we address these issues. We present different efficient approximations for dependent output Gaussian processes constructed through the convolution formalism. We exploit the conditional independencies present naturally in the model. This leads to a form of the covariance similar in spirit to the so called PITC and FITC approximations for a single output. We show experimental results with synthetic and real data, in particular, we show results in school exams score prediction, pollution prediction and gene expression data.
最近、複数の出力を扱う回帰法への関心が高まっています。これは、マルチタスク学習、マルチセンサー ネットワーク、構造化出力データなどのフレームワークによって部分的に促進されています。ガウス過程の観点から見ると、問題は、半正定値でありながら、すべてのデータ ポイント間およびすべての出力にわたる依存関係を捉える適切な共分散関数を指定することに帰着します。出力間の自明でない相関関係を考慮する1つのアプローチは、畳み込みプロセスを使用します。畳み込み変換の潜在関数解釈の下で、出力変数間の依存関係を確立します。このアプローチの主な欠点は、関連する計算とストレージの要求です。この論文では、これらの問題に対処します。畳み込み形式を通じて構築された依存出力ガウス過程のさまざまな効率的な近似を示します。モデルに自然に存在する条件付き独立性を活用します。これにより、単一の出力に対するいわゆるPITCおよびFITC近似と精神が似ている共分散の形式が生まれます。合成データと実データを用いた実験結果を示し、特に、学校の試験の得点予測、汚染予測、遺伝子発現データにおける結果を示します。
Learning a Robust Relevance Model for Search Using Kernel Methods
カーネル メソッドを使用した検索のロバストな関連性モデルの学習
This paper points out that many search relevance models in information retrieval, such as the Vector Space Model, BM25 and Language Models for Information Retrieval, can be viewed as a similarity function between pairs of objects of different types, referred to as an S-function. An S-function is specifically defined as the dot product between the images of two objects in a Hilbert space mapped from two different input spaces. One advantage of taking this view is that one can take a unified and principled approach to address the issues with regard to search relevance. The paper then proposes employing a kernel method to learn a robust relevance model as an S-function, which can effectively deal with the term mismatch problem, one of the biggest challenges in search. The kernel method exploits a positive semi-definite kernel referred to as an S-kernel. The paper shows that when using an S-kernel the model learned by the kernel method is guaranteed to be an S-function. The paper then gives more general principles for constructing S-kernels. A specific implementation of the kernel method is proposed using the Ranking SVM techniques and click-through data. The proposed approach is employed to learn a relevance model as an extension of BM25, referred to as Robust BM25. Experimental results on web search and enterprise search data show that Robust BM25 significantly outperforms baseline methods and can successfully tackle the term mismatch problem.
この論文では、ベクトル空間モデル、BM25、情報検索のための言語モデルなど、情報検索における多くの検索関連性モデルは、異なるタイプのオブジェクトのペア間の類似度関数、つまりS関数として見ることができると指摘しています。S関数は、2つの異なる入力空間からマッピングされたヒルベルト空間内の2つのオブジェクトの画像間のドット積として具体的に定義されます。この見方を取る利点の1つは、検索関連性に関する問題に対処するために、統一された原則的なアプローチをとれることです。次に、この論文では、検索における最大の課題の1つである用語の不一致の問題に効果的に対処できる堅牢な関連性モデルをS関数として学習するためにカーネル法を採用することを提案しています。カーネル法では、Sカーネルと呼ばれる半正定値カーネルを利用します。この論文では、Sカーネルを使用する場合、カーネル法によって学習されたモデルがS関数であることが保証されることを示しています。次に、Sカーネルを構築するためのより一般的な原則を示します。ランキングSVM技術とクリックスルー データを使用したカーネル メソッドの具体的な実装が提案されています。提案されたアプローチは、ロバストBM25と呼ばれるBM25の拡張として関連性モデルを学習するために使用されます。Web検索とエンタープライズ検索データでの実験結果から、ロバストBM25はベースライン メソッドを大幅に上回り、用語の不一致の問題にうまく対処できることが示されています。
Introduction to the Special Topic on Grammar Induction, Representation of Language and Language Learning
文法帰納法、言語表現、言語学習に関する特別トピックの紹介
Grammar induction refers to the process of learning grammars and languages from data; this finds a variety of applications in syntactic pattern recognition, the modeling of natural language acquisition, data mining and machine translation. This special topic contains several papers presenting some of recent developments in the area of grammar induction and language learning, as applied to various problems in Natural Language Processing, including supervised and unsupervised parsing and statistical machine translation.
文法帰納法とは、データから文法と言語を学習するプロセスを指します。これは、構文パターン認識、自然言語取得のモデリング、データマイニング、機械翻訳など、さまざまな用途に応用されています。この特別なトピックには、教師ありおよび教師なし解析や統計的機械翻訳など、自然言語処理のさまざまな問題に適用された、文法帰納法と言語学習の分野における最近の開発のいくつかを示すいくつかの論文が含まれています。
Clustering Algorithms for Chains
チェーンのクラスタリング アルゴリズム
We consider the problem of clustering a set of chains to k clusters. A chain is a totally ordered subset of a finite set of items. Chains are an intuitive way to express preferences over a set of alternatives, as well as a useful representation of ratings in situations where the item-specific scores are either difficult to obtain, too noisy due to measurement error, or simply not as relevant as the order that they induce over the items. First we adapt the classical k-means for chains by proposing a suitable distance function and a centroid structure. We also present two different approaches for mapping chains to a vector space. The first one is related to the planted partition model, while the second one has an intuitive geometrical interpretation. Finally we discuss a randomization test for assessing the significance of a clustering. To this end we present an MCMC algorithm for sampling random sets of chains that share certain properties with the original data. The methods are studied in a series of experiments using real and artificial data. Results indicate that the methods produce interesting clusterings, and for certain types of inputs improve upon previous work on clustering algorithms for orders.
私たちは、チェーンのセットをk個のクラスターにクラスタリングする問題について考えます。チェーンは、有限のアイテム セットの完全に順序付けられたサブセットです。チェーンは、一連の選択肢に対する好みを表現する直感的な方法であると同時に、アイテム固有のスコアを取得するのが難しい、測定エラーのためにノイズが多すぎる、またはアイテムに誘導する順序ほど関連性がない場合に、評価を表現する便利な方法です。まず、適切な距離関数と重心構造を提案することで、古典的なk平均法をチェーンに適応させます。また、チェーンをベクトル空間にマッピングするための2つの異なるアプローチを紹介します。最初のアプローチは、プランテッド パーティション モデルに関連するもので、2番目のアプローチは直感的な幾何学的解釈が可能です。最後に、クラスタリングの有意性を評価するためのランダム化テストについて説明します。この目的のために、元のデータと特定のプロパティを共有するチェーンのセットをランダムにサンプリングするMCMCアルゴリズムを紹介します。この方法は、実際のデータと人工データを使用した一連の実験で研究されます。結果は、これらの方法が興味深いクラスタリングを生成し、特定の種類の入力に対しては、注文のクラスタリング アルゴリズムに関する以前の研究よりも優れていることを示しています。
Faster Algorithms for Max-Product Message-Passing
最大積メッセージパッシングのための高速アルゴリズム
Maximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm or loopy belief-propagation. The exact solution to this problem is well-known to be exponential in the size of the maximal cliques of the triangulated model, while approximate inference is typically exponential in the size of the model’s factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their constituent factors, and also of the fact that many factors consist only of latent variables (i.e., they do not depend on an observation). This is a common case in a wide variety of applications that deal with grid-, tree-, and ring-structured models. In such cases, we are able to decrease the exponent of complexity for message-passing by 0.5 for both exact and approximate inference. We demonstrate that message-passing operations in such models are equivalent to some variant of matrix multiplication in the tropical semiring, for which we offer an O(N2.5) expected-case solution.
グラフィカル モデルの最大事後推論は、ジャンクション ツリー アルゴリズムやループ ビリーフ プロパゲーションなどのメッセージ パッシング アルゴリズムによって解決されることがよくあります。この問題の正確な解は、三角形モデルの最大クリークのサイズに対して指数関数的であることがよく知られていますが、近似推論は通常、モデルの因子のサイズに対して指数関数的です。この論文では、多くのモデルが構成因子よりも大きい最大クリークを持っているという事実と、多くの因子が潜在変数のみで構成されている(つまり、観測に依存しない)という事実を活用します。これは、グリッド、ツリー、およびリング構造のモデルを扱うさまざまなアプリケーションで一般的なケースです。このような場合、正確な推論と近似推論の両方で、メッセージ パッシングの複雑さの指数を0.5減らすことができます。このようなモデルにおけるメッセージパッシング操作は熱帯半環における行列乗算のある種の変形と同等であることを実証し、O(N2.5)の期待ケースソリューションを提供します。
A Family of Simple Non-Parametric Kernel Learning Algorithms
シンプルなノンパラメトリックカーネル学習アルゴリズムのファミリー
Previous studies of Non-Parametric Kernel Learning (NPKL) usually formulate the learning task as a Semi-Definite Programming (SDP) problem that is often solved by some general purpose SDP solvers. However, for N data examples, the time complexity of NPKL using a standard interior-point SDP solver could be as high as O(N6.5), which prohibits NPKL methods applicable to real applications, even for data sets of moderate size. In this paper, we present a family of efficient NPKL algorithms, termed “SimpleNPKL”, which can learn non-parametric kernels from a large set of pairwise constraints efficiently. In particular, we propose two efficient SimpleNPKL algorithms. One is SimpleNPKL algorithm with linear loss, which enjoys a closed-form solution that can be efficiently computed by the Lanczos sparse eigen decomposition technique. Another one is SimpleNPKL algorithm with other loss functions (including square hinge loss, hinge loss, square loss) that can be re-formulated as a saddle-point optimization problem, which can be further resolved by a fast iterative algorithm. In contrast to the previous NPKL approaches, our empirical results show that the proposed new technique, maintaining the same accuracy, is significantly more efficient and scalable. Finally, we also demonstrate that the proposed new technique is also applicable to speed up many kernel learning tasks, including colored maximum variance unfolding, minimum volume embedding, and structure preserving embedding.
ノンパラメトリックカーネル学習(NPKL)に関するこれまでの研究では、学習タスクは、多くの場合、いくつかの汎用SDPソルバーで解決される半正定値計画(SDP)問題として定式化されています。ただし、N個のデータ例の場合、標準の内点型SDPソルバーを使用したNPKLの時間計算量はO(N6.5)と高くなる可能性があり、中程度のサイズのデータ セットであっても、NPKL法を実際のアプリケーションに適用することはできません。この論文では、「SimpleNPKL」と呼ばれる効率的なNPKLアルゴリズムのファミリを紹介します。これは、大規模なペアワイズ制約セットからノンパラメトリックカーネルを効率的に学習できます。特に、2つの効率的なSimpleNPKLアルゴリズムを提案します。1つは線形損失のあるSimpleNPKLアルゴリズムで、Lanczosスパース固有値分解法によって効率的に計算できる閉じた形式のソリューションが得られます。もう1つは、他の損失関数(平方ヒンジ損失、ヒンジ損失、平方損失など)を使用したSimpleNPKLアルゴリズムです。これは、鞍点最適化問題として再定式化でき、高速反復アルゴリズムによってさらに解決できます。以前のNPKLアプローチとは対照的に、実験結果では、提案された新しい手法は、同じ精度を維持しながら、はるかに効率的でスケーラブルであることがわかりました。最後に、提案された新しい手法は、色付き最大分散展開、最小体積埋め込み、構造保存埋め込みなど、多くのカーネル学習タスクの高速化にも適用できることも実証しました。
Better Algorithms for Benign Bandits
良性の盗賊のためのより良いアルゴリズム
The online multi-armed bandit problem and its generalizations are repeated decision making problems, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the regret of the algorithm. The term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information.A very general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining Õ(√T) regret was discovered in this setting.In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a tighter regret bound of Õ(√Q), where Q is the total variation in the cost functions. This regret bound, previously conjectured to hold in the full information case, shows that it is possible to incur much less regret in a slowly changing environment even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.
オンライン多腕バンディット問題とその一般化は、反復意思決定問題であり、その目標は、各ラウンドで複数の可能な決定の1つを選択し、その決定に関連するコストを、すべての反復で発生した総コストが、後から見て最良の固定決定のコストに近くなるようにすることです。これらのコストの差は、アルゴリズムの後悔として知られています。バンディットという用語は、特定の反復で使用された決定のコストのみを取得し、他の情報は取得しない設定を指します。この問題の非常に一般的な形式は、非確率的バンディット線形最適化問題であり、決定のセットはユークリッド空間内の凸集合であり、コスト関数は線形です。最近になって、この設定で Õ(√T)の後悔を達成する効率的なアルゴリズムが発見されました。この論文では、より厳しい後悔の境界 Õ(√Q)を取得するバンディット線形最適化問題の新しいアルゴリズムを提案します。ここで、Qはコスト関数の総変動です。この後悔の限界は、以前は完全な情報の場合に当てはまると推測されていましたが、バンディット設定でも、ゆっくりと変化する環境では後悔を大幅に減らすことができることを示しています。私たちのアルゴリズムは効率的で、リザーバーサンプリングなどのいくつかの新しいアイデアをバンディット最適化に適用します。
Locally Defined Principal Curves and Surfaces
ローカルに定義された主曲線と主サーフェス
Principal curves are defined as self-consistent smooth curves passing through the middle of the data, and they have been used in many applications of machine learning as a generalization, dimensionality reduction and a feature extraction tool. We redefine principal curves and surfaces in terms of the gradient and the Hessian of the probability density estimate. This provides a geometric understanding of the principal curves and surfaces, as well as a unifying view for clustering, principal curve fitting and manifold learning by regarding those as principal manifolds of different intrinsic dimensionalities. The theory does not impose any particular density estimation method can be used with any density estimator that gives continuous first and second derivatives. Therefore, we first present our principal curve/surface definition without assuming any particular density estimation method. Afterwards, we develop practical algorithms for the commonly used kernel density estimation (KDE) and Gaussian mixture models (GMM). Results of these algorithms are presented in notional data sets as well as real applications with comparisons to other approaches in the principal curve literature. All in all, we present a novel theoretical understanding of principal curves and surfaces, practical algorithms as general purpose machine learning tools, and applications of these algorithms to several practical problems.
主曲線は、データの中央を通過する自己矛盾のない滑らかな曲線として定義され、一般化、次元削減、および特徴抽出ツールとして、機械学習の多くのアプリケーションで使用されています。主曲線と表面を、確率密度推定の勾配とヘッセ行列の観点から再定義します。これにより、主曲線と表面の幾何学的理解が得られるとともに、それらを異なる固有次元の主多様体と見なすことで、クラスタリング、主曲線フィッティング、および多様体学習の統一的な見方が得られます。この理論では、連続的な1次導関数と2次導関数を与える任意の密度推定器で使用できる特定の密度推定法を強制していません。したがって、最初に特定の密度推定法を想定せずに、主曲線/表面の定義を示します。その後、一般的に使用されるカーネル密度推定(KDE)とガウス混合モデル(GMM)の実用的なアルゴリズムを開発します。これらのアルゴリズムの結果は、概念的なデータセットと実際のアプリケーションで示され、主曲線の文献にある他のアプローチと比較されます。全体として、我々は主曲線と主曲面の新しい理論的理解、汎用機械学習ツールとしての実用的なアルゴリズム、そしてこれらのアルゴリズムのいくつかの実際的な問題への応用を提示します。
DirectLiNGAM: A Direct Method for Learning a Linear Non-Gaussian Structural Equation Model
DirectLiNGAM:線形非ガウス構造方程式モデルを学習するための直接法
Structural equation models and Bayesian networks have been widely used to analyze causal relations between continuous variables. In such frameworks, linear acyclic models are typically used to model the data-generating process of variables. Recently, it was shown that use of non-Gaussianity identifies the full structure of a linear acyclic model, that is, a causal ordering of variables and their connection strengths, without using any prior knowledge on the network structure, which is not the case with conventional methods. However, existing estimation methods are based on iterative search algorithms and may not converge to a correct solution in a finite number of steps. In this paper, we propose a new direct method to estimate a causal ordering and connection strengths based on non-Gaussianity. In contrast to the previous methods, our algorithm requires no algorithmic parameters and is guaranteed to converge to the right solution within a small fixed number of steps if the data strictly follows the model, that is, if all the model assumptions are met and the sample size is infinite.
構造方程式モデルとベイジアンネットワークは、連続変数間の因果関係を分析するために広く使用されています。このようなフレームワークでは、通常、線形非巡回モデルを使用して変数のデータ生成プロセスをモデル化します。最近、非ガウス性を使用すると、従来の方法では当てはまらなかったネットワーク構造に関する事前知識を使用せずに、線形非巡回モデルの完全な構造、つまり変数の因果順序とそれらの接続強度を特定できることが示されました。ただし、既存の推定方法は反復検索アルゴリズムに基づいており、有限数のステップで正しいソリューションに収束しない可能性があります。この論文では、非ガウス性に基づいて因果順序と接続強度を推定する新しい直接的な方法を提案します。以前の方法とは対照的に、私たちのアルゴリズムはアルゴリズムパラメータを必要とせず、データがモデルに厳密に従う場合、つまりすべてのモデル仮定が満たされ、サンプルサイズが無限である場合、少数の固定ステップ内で正しいソリューションに収束することが保証されています。
The Indian Buffet Process: An Introduction and Review
インドのビュッフェプロセス:紹介とレビュー
The Indian buffet process is a stochastic process defining a probability distribution over equivalence classes of sparse binary matrices with a finite number of rows and an unbounded number of columns. This distribution is suitable for use as a prior in probabilistic models that represent objects using a potentially infinite array of features, or that involve bipartite graphs in which the size of at least one class of nodes is unknown. We give a detailed derivation of this distribution, and illustrate its use as a prior in an infinite latent feature model. We then review recent applications of the Indian buffet process in machine learning, discuss its extensions, and summarize its connections to other stochastic processes.
インドのビュッフェ プロセスは、有限の行数と無制限の列数を持つスパース バイナリ行列の等価クラスに対する確率分布を定義する確率的プロセスです。この分布は、潜在的に無限の特徴配列を使用してオブジェクトを表す確率モデル、または少なくとも1つのクラスのノードのサイズが不明な二部グラフを含む確率モデルで事前分布として使用するのに適しています。この分布の詳細な導出を行い、無限潜在特徴モデルにおける事前分布としての使用を示します。次に、機械学習におけるインドのビュッフェプロセスの最近のアプリケーションをレビューし、その拡張について説明し、他の確率的プロセスとの関係を要約します。
Laplacian Support Vector Machines Trained in the Primal
Primal で訓練されたラプラシアン サポート ベクター マシン
In the last few years, due to the growing ubiquity of unlabeled data, much effort has been spent by the machine learning community to develop better understanding and improve the quality of classifiers exploiting unlabeled data. Following the manifold regularization approach, Laplacian Support Vector Machines (LapSVMs) have shown the state of the art performance in semi-supervised classification. In this paper we present two strategies to solve the primal LapSVM problem, in order to overcome some issues of the original dual formulation. In particular, training a LapSVM in the primal can be efficiently performed with preconditioned conjugate gradient. We speed up training by using an early stopping strategy based on the prediction on unlabeled data or, if available, on labeled validation examples. This allows the algorithm to quickly compute approximate solutions with roughly the same classification accuracy as the optimal ones, considerably reducing the training time. The computational complexity of the training algorithm is reduced from O(n3) to O(kn2), where n is the combined number of labeled and unlabeled examples and k is empirically evaluated to be significantly smaller than n. Due to its simplicity, training LapSVM in the primal can be the starting point for additional enhancements of the original LapSVM formulation, such as those for dealing with large data sets. We present an extensive experimental evaluation on real world data showing the benefits of the proposed approach.
過去数年間、ラベルなしデータの普及が進んだため、機械学習コミュニティでは、ラベルなしデータを利用する分類器の理解を深め、品質を向上させるために多大な努力が払われてきました。多様体正則化アプローチに続いて、ラプラシアン サポート ベクター マシン(LapSVM)は、半教師あり分類において最先端のパフォーマンスを示しました。この論文では、元のデュアル定式化の問題のいくつかを克服するために、プライマリLapSVM問題を解決するための2つの戦略を紹介します。特に、プライマリでのLapSVMのトレーニングは、前処理付き共役勾配を使用して効率的に実行できます。ラベルなしデータ、または使用可能な場合はラベル付き検証例の予測に基づく早期停止戦略を使用して、トレーニングを高速化します。これにより、アルゴリズムは最適なものとほぼ同じ分類精度で近似ソリューションをすばやく計算できるため、トレーニング時間が大幅に短縮されます。トレーニング アルゴリズムの計算量はO(n3)からO(kn2)に削減されます。ここで、nはラベル付きとラベルなしの例の合計数であり、kは経験的にnよりも大幅に小さいと評価されています。そのシンプルさにより、LapSVMをプライマリでトレーニングすることは、大規模なデータ セットを処理するための機能など、元のLapSVM定式化をさらに強化するための出発点となります。提案されたアプローチの利点を示す、実際のデータでの広範な実験評価を紹介します。
Anechoic Blind Source Separation Using Wigner Marginals
Wigner Marginals を使用した無響ブラインドソース分離
Blind source separation problems emerge in many applications, where signals can be modeled as superpositions of multiple sources. Many popular applications of blind source separation are based on linear instantaneous mixture models. If specific invariance properties are known about the sources, for example, translation or rotation invariance, the simple linear model can be extended by inclusion of the corresponding transformations. When the sources are invariant against translations (spatial displacements or time shifts) the resulting model is called an anechoic mixing model. We present a new algorithmic framework for the solution of anechoic problems in arbitrary dimensions. This framework is derived from stochastic time-frequency analysis in general, and the marginal properties of the Wigner-Ville spectrum in particular. The method reduces the general anechoic problem to a set of anechoic problems with non-negativity constraints and a phase retrieval problem. The first type of subproblem can be solved by existing algorithms, for example by an appropriate modification of non-negative matrix factorization (NMF). The second subproblem is solved by established phase retrieval methods. We discuss and compare implementations of this new algorithmic framework for several example problems with synthetic and real-world data, including music streams, natural 2D images, human motion trajectories and two-dimensional shapes.
ブラインド音源分離問題は、信号を複数の音源の重ね合わせとしてモデル化できる多くのアプリケーションで発生します。ブラインド音源分離の一般的なアプリケーションの多くは、線形瞬間混合モデルに基づいています。音源について特定の不変性特性(たとえば、並進または回転不変性)がわかっている場合は、対応する変換を含めることで単純な線形モデルを拡張できます。音源が並進(空間変位または時間シフト)に対して不変である場合、結果として得られるモデルは無響混合モデルと呼ばれます。任意の次元で無響問題を解決するための新しいアルゴリズム フレームワークを紹介します。このフレームワークは、一般的には確率的時間周波数解析から、特にWigner-Villeスペクトルの限界特性から派生しています。この方法は、一般的な無響問題を、非負制約と位相回復問題を伴う無響問題のセットに縮小します。最初のタイプのサブ問題は、既存のアルゴリズム(たとえば、非負行列因子分解(NMF)を適切に変更する)で解決できます。2番目のサブ問題は、確立された位相回復法によって解決されます。音楽ストリーム、自然な2D画像、人間の動作の軌跡、2次元形状など、合成データと実世界のデータを使用したいくつかの例題について、この新しいアルゴリズム フレームワークの実装について説明し、比較します。
Differentially Private Empirical Risk Minimization
差分私的経験的リスク最小化
Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the ε-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.
プライバシー保護機械学習アルゴリズムは、医療記録や財務記録などの個人データを分析する、ますます一般的になっている設定にとって重要です。(正規化された)経験的リスク最小化(ERM)を介して学習された分類器のプライバシー保護近似を生成するための一般的な手法を提供します。これらのアルゴリズムは、Dworkら(2006)による ε 差分プライバシー定義の下でプライベートです。まず、Dworkら(2006)の出力摂動の考え方をERM分類に適用します。次に、プライバシー保護機械学習アルゴリズム設計のための新しい方法である目的摂動を提案します。この方法では、分類器を最適化する前に目的関数を摂動します。損失と正規化子が特定の凸性および微分可能性の基準を満たす場合、アルゴリズムがプライバシーを保護することを示す理論的結果を証明し、線形カーネルと非線形カーネルの一般化境界を提供します。さらに、一般的な機械学習アルゴリズムのパラメータを調整するためのプライバシー保護技術を紹介し、トレーニング プロセスにエンドツーエンドのプライバシー保証を提供します。これらの結果を適用して、正規化ロジスティック回帰とサポート ベクター マシンのプライバシー保護類似物を作成します。実際の人口統計データ セットとベンチマーク データ セットでパフォーマンスを評価すると、有望な結果が得られました。私たちの結果は、プライバシーと学習パフォーマンスの間の固有のトレードオフを管理する上で、理論的にも経験的にも、客観的摂動が従来の最先端の出力摂動よりも優れていることを示しています。
Two Distributed-State Models For Generating High-Dimensional Time Series
高次元時系列を生成するための 2 つの分布状態モデル
In this paper we develop a class of nonlinear generative models for high-dimensional time series. We first propose a model based on the restricted Boltzmann machine (RBM) that uses an undirected model with binary latent variables and real-valued “visible” variables. The latent and visible variables at each time step receive directed connections from the visible variables at the last few time-steps. This “conditional” RBM (CRBM) makes on-line inference efficient and allows us to use a simple approximate learning procedure. We demonstrate the power of our approach by synthesizing various sequences from a model trained on motion capture data and by performing on-line filling in of data lost during capture.We extend the CRBM in a way that preserves its most important computational properties and introduces multiplicative three-way interactions that allow the effective interaction weight between two variables to be modulated by the dynamic state of a third variable. We introduce a factoring of the implied three-way weight tensor to permit a more compact parameterization. The resulting model can capture diverse styles of motion with a single set of parameters, and the three-way interactions greatly improve its ability to blend motion styles or to transition smoothly among them.Videos and source code can be found at http://www.cs.nyu.edu/~gwtaylor/publications/jmlr2011.
この論文では、高次元時系列の非線形生成モデルのクラスを開発します。まず、バイナリ潜在変数と実数値の「可視」変数を持つ無向モデルを使用する制限付きボルツマン マシン(RBM)に基づくモデルを提案します。各時間ステップの潜在変数と可視変数は、最後のいくつかの時間ステップの可視変数から有向接続を受け取ります。この「条件付き」RBM (CRBM)により、オンライン推論が効率的になり、簡単な近似学習手順を使用できます。モーション キャプチャ データでトレーニングされたモデルからさまざまなシーケンスを合成し、キャプチャ中に失われたデータをオンラインで埋め込むことで、このアプローチの威力を実証します。CRBMを拡張して、最も重要な計算特性を維持し、2つの変数間の有効な相互作用の重みを3番目の変数の動的状態によって調整できる乗法的な3方向相互作用を導入します。暗黙の3方向重みテンソルの因数分解を導入して、よりコンパクトなパラメータ化を可能にします。結果として得られるモデルは、単一のパラメータ セットで多様な動作スタイルをキャプチャでき、3方向のインタラクションによって動作スタイルをブレンドしたり、動作スタイル間をスムーズに遷移したりする機能が大幅に向上します。ビデオとソース コードは、http://www.cs.nyu.edu/~gwtaylor/publications/jmlr2011で参照できます。
Unsupervised Similarity-Based Risk Stratification for Cardiovascular Events Using Long-Term Time-Series Data
長期時系列データを用いた心血管イベントの教師なし類似性に基づくリスク層別化
In medicine, one often bases decisions upon a comparative analysis of patient data. In this paper, we build upon this observation and describe similarity-based algorithms to risk stratify patients for major adverse cardiac events. We evolve the traditional approach of comparing patient data in two ways. First, we propose similarity-based algorithms that compare patients in terms of their long-term physiological monitoring data. Symbolic mismatch identifies functional units in long-term signals and measures changes in the morphology and frequency of these units across patients. Second, we describe similarity-based algorithms that are unsupervised and do not require comparisons to patients with known outcomes for risk stratification. This is achieved by using an anomaly detection framework to identify patients who are unlike other patients in a population and may potentially be at an elevated risk. We demonstrate the potential utility of our approach by showing how symbolic mismatch-based algorithms can be used to classify patients as being at high or low risk of major adverse cardiac events by comparing their long-term electrocardiograms to that of a large population. We describe how symbolic mismatch can be used in three different existing methods: one-class support vector machines, nearest neighbor analysis, and hierarchical clustering. When evaluated on a population of 686 patients with available long-term electrocardiographic data, symbolic mismatch-based comparative approaches were able to identify patients at roughly a two-fold increased risk of major adverse cardiac events in the 90 days following acute coronary syndrome. These results were consistent even after adjusting for other clinical risk variables.
医療では、患者データの比較分析に基づいて意思決定が行われることがよくあります。この論文では、この観察に基づいて、主要な心臓有害事象について患者をリスク分類するための類似性ベースのアルゴリズムについて説明します。患者データを比較する従来のアプローチを2つの方法で進化させます。まず、長期生理学的モニタリング データの観点から患者を比較する類似性ベースのアルゴリズムを提案します。シンボリック ミスマッチは、長期信号の機能単位を識別し、患者間でのこれらの単位の形態と頻度の変化を測定します。次に、リスク分類のために既知の結果を持つ患者との比較を必要としない、教師なしの類似性ベースのアルゴリズムについて説明します。これは、異常検出フレームワークを使用して、集団内の他の患者とは異なり、潜在的に高いリスクがある可能性がある患者を識別することで実現されます。シンボリック ミスマッチ ベースのアルゴリズムを使用して、患者の長期心電図を大規模な集団の心電図と比較することで、主要な心臓有害事象のリスクが高いか低いかを分類する方法を示し、このアプローチの潜在的な有用性を実証します。シンボリック ミスマッチを3つの異なる既存の方法(1クラス サポート ベクター マシン、最近傍分析、階層的クラスタリング)でどのように使用できるかについて説明します。長期心電図データのある686人の患者集団で評価したところ、シンボリック ミスマッチに基づく比較アプローチにより、急性冠症候群後90日間で主要な有害心臓イベントのリスクが約2倍に増加した患者を特定できました。これらの結果は、他の臨床リスク変数を調整した後でも一貫していました。
lp-Norm Multiple Kernel Learning
lpノルムマルチプル カーネル学習
Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations to support interpretability and scalability. Unfortunately, this l1-norm MKL is rarely observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures that generalize well, we extend MKL to arbitrary norms. We devise new insights on the connection between several existing MKL formulations and develop two efficient interleaved optimization strategies for arbitrary norms, that is lp-norms with p ≥ 1. This interleaved optimization is much faster than the commonly used wrapper approaches, as demonstrated on several data sets. A theoretical analysis and an experiment on controlled artificial data shed light on the appropriateness of sparse, non-sparse and l∞-norm MKL in various scenarios. Importantly, empirical applications of lp-norm MKL to three real-world problems from computational biology show that non-sparse MKL achieves accuracies that surpass the state-of-the-art.Data sets, source code to reproduce the experiments, implementations of the algorithms, and further information are available at http://doc.ml.tu-berlin.de/nonsparse_mkl/.
複数のカーネルの線形結合を学習することは、適切な特徴の選択が不明な場合に魅力的な戦略です。これまでのマルチカーネル学習(MKL)のアプローチでは、解釈可能性とスケーラビリティをサポートするためにスパースカーネルの組み合わせが推奨されていました。残念ながら、このl1ノルムMKLが実際のアプリケーションで自明なベースラインを上回ることはほとんどありません。適切に一般化される堅牢なカーネル混合を可能にするために、MKLを任意のノルムに拡張します。既存のいくつかのMKL定式化間の接続に関する新しい洞察を考案し、任意のノルム、つまりp≥1のlpノルムに対する2つの効率的なインターリーブ最適化戦略を開発します。このインターリーブ最適化は、いくつかのデータ セットで実証されているように、一般的に使用されるラッパー アプローチよりもはるかに高速です。理論分析と制御された人工データでの実験により、さまざまなシナリオでのスパース、非スパース、およびl∞ ノルムのMKLの適切性が明らかになりました。重要なのは、計算生物学における3つの実際の問題にlp-norm MKLを実験的に適用した結果、非スパースMKLが最先端の精度を上回ることが示されたことです。データ セット、実験を再現するためのソース コード、アルゴリズムの実装、および詳細情報は、http://doc.ml.tu-berlin.de/nonsparse_mkl/で入手できます。
Forest Density Estimation
森林密度推定
We study graph estimation and density estimation in high dimensions, using a family of density estimators based on forest structured undirected graphical models. For density estimation, we do not assume the true distribution corresponds to a forest; rather, we form kernel density estimates of the bivariate and univariate marginals, and apply Kruskal’s algorithm to estimate the optimal forest on held out data. We prove an oracle inequality on the excess risk of the resulting estimator relative to the risk of the best forest. For graph estimation, we consider the problem of estimating forests with restricted tree sizes. We prove that finding a maximum weight spanning forest with restricted tree size is NP-hard, and develop an approximation algorithm for this problem. Viewing the tree size as a complexity parameter, we then select a forest using data splitting, and prove bounds on excess risk and structure selection consistency of the procedure. Experiments with simulated data and microarray data indicate that the methods are a practical alternative to Gaussian graphical models.
私たちは、森林構造の無向グラフィカルモデルに基づく密度推定量ファミリーを使用して、高次元でのグラフ推定と密度推定を研究します。密度推定では、真の分布が森林に対応するとは想定せず、むしろ、二変量および一変量周辺分布のカーネル密度推定値を形成し、Kruskalアルゴリズムを適用して、保持されたデータに対して最適な森林を推定します。私たちは、結果として得られる推定量の過剰リスクが最良の森林のリスクと比較して、オラクル不等式であることを証明します。グラフ推定では、木のサイズが制限された森林を推定する問題を検討します。木のサイズが制限された最大重み全域森林を見つけることがNP困難であることを証明し、この問題の近似アルゴリズムを開発します。木のサイズを複雑性パラメータと見なし、データ分割を使用して森林を選択し、過剰リスクの境界と手順の構造選択の一貫性を証明します。シミュレートされたデータとマイクロアレイデータを使用した実験は、これらの方法がガウスグラフィカルモデルの実用的な代替手段であることを示しています。
Sparse Linear Identifiable Multivariate Modeling
スパース線形識別可能な多変量モデリング
In this paper we consider sparse and identifiable linear latent variable (factor) and linear Bayesian network models for parsimonious analysis of multivariate data. We propose a computationally efficient method for joint parameter and model inference, and model comparison. It consists of a fully Bayesian hierarchy for sparse models using slab and spike priors (two-component δ-function and continuous mixtures), non-Gaussian latent factors and a stochastic search over the ordering of the variables. The framework, which we call SLIM (Sparse Linear Identifiable Multivariate modeling), is validated and bench-marked on artificial and real biological data sets. SLIM is closest in spirit to LiNGAM (Shimizu et al., 2006), but differs substantially in inference, Bayesian network structure learning and model comparison. Experimentally, SLIM performs equally well or better than LiNGAM with comparable computational complexity. We attribute this mainly to the stochastic search strategy used, and to parsimony (sparsity and identifiability), which is an explicit part of the model. We propose two extensions to the basic i.i.d. linear framework: non-linear dependence on observed variables, called SNIM (Sparse Non-linear Identifiable Multivariate modeling) and allowing for correlations between latent variables, called CSLIM (Correlated SLIM), for the temporal and/or spatial data. The source code and scripts are available from http://cogsys.imm.dtu.dk/slim/.
この論文では、多変量データの簡潔な分析のためのスパースで識別可能な線形潜在変数(因子)および線形ベイジアン ネットワーク モデルについて検討します。パラメーターとモデルの結合推論、およびモデル比較のための計算効率の高い方法を提案します。これは、スラブ事前分布とスパイク事前分布(2成分 δ 関数と連続混合)、非ガウス潜在因子、および変数の順序付けの確率的検索を使用したスパース モデルの完全なベイジアン階層で構成されます。SLIM (Sparse Linear Identifiable Multivariate modeling)と呼ぶこのフレームワークは、人工データ セットと実際の生物学的データ セットで検証およびベンチマークされています。SLIMは、LiNGAM (Shimizu他、2006)に精神が最も近いですが、推論、ベイジアン ネットワーク構造の学習、およびモデル比較の点で大きく異なります。実験的には、SLIMは、同等の計算複雑性でLiNGAMと同等かそれ以上のパフォーマンスを発揮します。これは主に、使用された確率的検索戦略と、モデルの明示的な部分である簡素性(スパース性と識別可能性)によるものです。基本的なi.i.d.線形フレームワークに2つの拡張を提案します。1つは、SNIM (スパース非線形識別可能多変量モデリング)と呼ばれる観測変数への非線形依存性、もう1つは、時間的および/または空間的データに対するCSLIM (相関SLIM)と呼ばれる潜在変数間の相関の許可です。ソース コードとスクリプトは、http://cogsys.imm.dtu.dk/slim/から入手できます。
Learning Transformation Models for Ranking and Survival Analysis
ランキング分析と生存分析のための学習変換モデル
This paper studies the task of learning transformation models for ranking problems, ordinal regression and survival analysis. The present contribution describes a machine learning approach termed MINLIP. The key insight is to relate ranking criteria as the Area Under the Curve to monotone transformation functions. Consequently, the notion of a Lipschitz smoothness constant is found to be useful for complexity control for learning transformation models, much in a similar vein as the ‘margin’ is for Support Vector Machines for classification. The use of this model structure in the context of high dimensional data, as well as for estimating non-linear, and additive models based on primal-dual kernel machines, and for sparse models is indicated. Given n observations, the present method solves a quadratic program existing of O(n) constraints and O(n) unknowns, where most existing risk minimization approaches to ranking problems typically result in algorithms with O(n2) constraints or unknowns. We specify the MINLIP method for three different cases: the first one concerns the preference learning problem. Secondly it is specified how to adapt the method to ordinal regression with a finite set of ordered outcomes. Finally, it is shown how the method can be used in the context of survival analysis where one models failure times, typically subject to censoring. The current approach is found to be particularly useful in this context as it can handle, in contrast with the standard statistical model for analyzing survival data, all types of censoring in a straightforward way, and because of the explicit relation with the Proportional Hazard and Accelerated Failure Time models. The advantage of the current method is illustrated on different benchmark data sets, as well as for estimating a model for cancer survival based on different micro-array and clinical data sets.
この論文では、ランキング問題、順序回帰、生存分析のための変換モデルを学習するタスクについて検討します。この論文では、MINLIPと呼ばれる機械学習アプローチについて説明します。重要な洞察は、曲線下面積などのランキング基準を単調な変換関数に関連付けることです。その結果、リプシッツ平滑定数の概念は、分類のサポートベクターマシンの「マージン」と同様に、変換モデルを学習するための複雑さの制御に有用であることがわかりました。このモデル構造は、高次元データのコンテキスト、およびプライマルデュアルカーネルマシンに基づく非線形および加法モデルの推定、およびスパースモデルでの使用が示されています。n個の観測値が与えられた場合、本方法は、O(n)制約とO(n)未知数が存在する二次計画を解きます。ランキング問題に対する既存のリスク最小化アプローチのほとんどは、通常、O(n2)制約または未知数を持つアルゴリズムになります。MINLIP法を3つの異なるケースに指定します。最初のケースは、選好学習問題に関するものです。次に、有限の順序付き結果セットを持つ順序回帰にこの方法を適用する方法を指定します。最後に、通常は打ち切りの対象となる故障時間をモデル化する生存分析のコンテキストでこの方法を使用する方法を示します。現在のアプローチは、生存データを分析するための標準的な統計モデルとは対照的に、すべての種類の打ち切りを簡単な方法で処理でき、比例ハザードおよび加速故障時間モデルとの明確な関係があるため、このコンテキストで特に有用であることがわかりました。現在の方法の利点は、さまざまなベンチマーク データ セットで説明されているほか、さまざまなマイクロアレイおよび臨床データ セットに基づいて癌の生存率モデルを推定する場合にも示されています。
Information, Divergence and Risk for Binary Experiments
バイナリ実験の情報、発散、リスク
We unify f-divergences, Bregman divergences, surrogate regret bounds, proper scoring rules, cost curves, ROC-curves and statistical information. We do this by systematically studying integral and variational representations of these objects and in so doing identify their representation primitives which all are related to cost-sensitive binary classification. As well as developing relationships between generative and discriminative views of learning, the new machinery leads to tight and more general surrogate regret bounds and generalised Pinsker inequalities relating f-divergences to variational divergence. The new viewpoint also illuminates existing algorithms: it provides a new derivation of Support Vector Machines in terms of divergences and relates maximum mean discrepancy to Fisher linear discriminants.
私たちは、fダイバージェンス、ブレグマンダイバージェンス、サロゲートリグレットバウンド、適切なスコアリングルール、コスト曲線、ROC曲線、統計情報を統合します。これは、これらのオブジェクトの積分表現と変分表現を体系的に研究し、そうすることで、コストに敏感なバイナリ分類に関連する表現プリミティブを特定することによって行われます。新しいメカニズムは、学習の生成的見解と差別的見解の間の関係を発展させるだけでなく、よりタイトで一般的な代理後悔の限界と、f-divergenceと変分発散を関連付ける一般化されたピンスカーの不等式につながります。新しい視点は、既存のアルゴリズムにも光を当てます:発散の観点からサポート ベクター マシンの新しい導出を提供し、最大平均不一致をフィッシャー線形判別に関連付けます。
Inverse Reinforcement Learning in Partially Observable Environments
部分的に観測可能な環境における逆強化学習
Inverse reinforcement learning (IRL) is the problem of recovering the underlying reward function from the behavior of an expert. Most of the existing IRL algorithms assume that the environment is modeled as a Markov decision process (MDP), although it is desirable to handle partially observable settings in order to handle more realistic scenarios. In this paper, we present IRL algorithms for partially observable environments that can be modeled as a partially observable Markov decision process (POMDP). We deal with two cases according to the representation of the given expert’s behavior, namely the case in which the expert’s policy is explicitly given, and the case in which the expert’s trajectories are available instead. The IRL in POMDPs poses a greater challenge than in MDPs since it is not only ill-posed due to the nature of IRL, but also computationally intractable due to the hardness in solving POMDPs. To overcome these obstacles, we present algorithms that exploit some of the classical results from the POMDP literature. Experimental results on several benchmark POMDP domains show that our work is useful for partially observable settings.
逆強化学習(IRL)は、エキスパートの行動から基礎となる報酬関数を回復する問題です。既存のIRLアルゴリズムのほとんどは、環境がマルコフ決定プロセス(MDP)としてモデル化されていることを前提としていますが、より現実的なシナリオを処理するには、部分的に観測可能な設定を処理することが望ましいです。この論文では、部分的に観測可能なマルコフ決定プロセス(POMDP)としてモデル化できる部分的に観測可能な環境のIRLアルゴリズムを紹介します。エキスパートの行動の表現に応じて、エキスパートのポリシーが明示的に与えられている場合と、エキスパートの軌跡が代わりに利用できる場合の2つのケースを扱います。POMDPのIRLは、IRLの性質上不適切であるだけでなく、POMDPを解決するのが難しいため計算的に扱いにくいため、MDPよりも大きな課題となります。これらの障害を克服するために、POMDP文献の古典的な結果のいくつかを活用するアルゴリズムを紹介します。いくつかのベンチマークPOMDPドメインでの実験結果は、私たちの研究が部分的に観測可能な設定に有用であることを示しています。
Efficient Structure Learning of Bayesian Networks using Constraints
制約条件を用いたベイジアンネットワークの効率的な構造学習
This paper addresses the problem of learning Bayesian network structures from data based on score functions that are decomposable. It describes properties that strongly reduce the time and memory costs of many known methods without losing global optimality guarantees. These properties are derived for different score criteria such as Minimum Description Length (or Bayesian Information Criterion), Akaike Information Criterion and Bayesian Dirichlet Criterion. Then a branch-and-bound algorithm is presented that integrates structural constraints with data in a way to guarantee global optimality. As an example, structural constraints are used to map the problem of structure learning in Dynamic Bayesian networks into a corresponding augmented Bayesian network. Finally, we show empirically the benefits of using the properties with state-of-the-art methods and with the new algorithm, which is able to handle larger data sets than before.
この論文では、分解可能なスコア関数に基づくデータからベイジアンネットワーク構造を学習する問題に取り組んでいます。これは、多くの既知のメソッドの時間とメモリのコストを大幅に削減するプロパティを、グローバルな最適性の保証を失うことなく説明します。これらのプロパティは、最小説明長(またはベイズ情報量基準)、赤池情報量基準、ベイジアン ディリクレ基準など、さまざまなスコア基準に対して派生します。次に、グローバルな最適性を保証する方法で構造的制約をデータに統合する分岐限定アルゴリズムが提示されます。例として、構造制約を使用して、動的ベイジアン ネットワークの構造学習の問題を対応する拡張ベイジアン ネットワークにマッピングします。最後に、最先端の方法と、以前よりも大きなデータセットを処理できる新しいアルゴリズムでプロパティを使用することの利点を経験的に示します。
Parameter Screening and Optimisation for ILP using Designed Experiments
Designed Experimentsを用いたILPのパラメータスクリーニングと最適化
Reports of experiments conducted with an Inductive Logic Programming system rarely describe how specific values of parameters of the system are arrived at when constructing models. Usually, no attempt is made to identify sensitive parameters, and those that are used are often given “factory-supplied” default values, or values obtained from some non-systematic exploratory analysis. The immediate consequence of this is, of course, that it is not clear if better models could have been obtained if some form of parameter selection and optimisation had been performed. Questions follow inevitably on the experiments themselves: specifically, are all algorithms being treated fairly, and is the exploratory phase sufficiently well-defined to allow the experiments to be replicated? In this paper, we investigate the use of parameter selection and optimisation techniques grouped under the study of experimental design. Screening and response surface methods determine, in turn, sensitive parameters and good values for these parameters. Screening is done here by constructing a stepwise regression model relating the utility of an ILP system’s hypothesis to its input parameters, using systematic combinations of values of input parameters (technically speaking, we use a two-level fractional factorial design of the input parameters). The parameters used by the regression model are taken to be the sensitive parameters for the system for that application. We then seek an assignment of values to these sensitive parameters that maximise the utility of the ILP model. This is done using the technique of constructing a local “response surface”. The parameters are then changed following the path of steepest ascent until a locally optimal value is reached. This combined use of parameter selection and response surface-driven optimisation has a long history of application in industrial engineering, and its role in ILP is demonstrated using well-known benchmarks. The results suggest that computational overheads from this preliminary phase are not substantial, and that much can be gained, both on improving system performance and on enabling controlled experimentation, by adopting well-established procedures such as the ones proposed here.
帰納的論理プログラミング システムで実施された実験のレポートには、モデルの構築時にシステムのパラメータの特定の値がどのように決定されたかがほとんど記載されていません。通常、敏感なパラメータを特定する試みは行われず、使用されるパラメータには「工場出荷時の」デフォルト値、または非体系的な探索的分析から得られた値が与えられることがよくあります。当然のことながら、この直接的な結果は、何らかのパラメータ選択と最適化が行われていれば、より優れたモデルが得られていたかどうかが明確ではないことです。必然的に、実験自体に関する疑問が生じます。具体的には、すべてのアルゴリズムが公平に扱われているのか、実験を再現できるほど探索段階が十分に明確に定義されているのか、などです。この論文では、実験設計の研究に分類されるパラメータ選択と最適化の手法の使用について調査します。スクリーニング法と応答曲面法は、敏感なパラメータとこれらのパラメータの適切な値を決定します。ここでのスクリーニングは、入力パラメータの値の体系的な組み合わせを使用して、ILPシステムの仮説の有用性をその入力パラメータに関連付ける段階的回帰モデルを構築することによって行われます(技術的には、入力パラメータの2レベルの一部実施要因設計を使用します)。回帰モデルで使用されるパラメータは、そのアプリケーションにおけるシステムの敏感なパラメータと見なされます。次に、これらの敏感なパラメータに、ILPモデルの有用性を最大化する値の割り当てを探します。これは、ローカルな「応答面」を構築する手法を使用して行われます。次に、パラメータは、ローカルに最適な値に達するまで、最も急な上昇の経路に従って変更されます。このパラメータ選択と応答面駆動の最適化の組み合わせは、産業工学で長い歴史があり、ILPにおけるその役割は、よく知られたベンチマークを使用して実証されています。結果は、この予備段階からの計算オーバーヘッドは大きくなく、ここで提案されているような確立された手順を採用することで、システム パフォーマンスの向上と制御された実験の実現の両方で多くのメリットが得られることを示しています。
Regression on Fixed-Rank Positive Semidefinite Matrices: A Riemannian Approach
固定ランク正の半正定値行列の回帰: リーマン的アプローチ
The paper addresses the problem of learning a regression model parameterized by a fixed-rank positive semidefinite matrix. The focus is on the nonlinear nature of the search space and on scalability to high-dimensional problems. The mathematical developments rely on the theory of gradient descent algorithms adapted to the Riemannian geometry that underlies the set of fixed-rank positive semidefinite matrices. In contrast with previous contributions in the literature, no restrictions are imposed on the range space of the learned matrix. The resulting algorithms maintain a linear complexity in the problem size and enjoy important invariance properties. We apply the proposed algorithms to the problem of learning a distance function parameterized by a positive semidefinite matrix. Good performance is observed on classical benchmarks.
この論文では、固定ランクの正の半正定値行列によってパラメーター化された回帰モデルを学習する問題に取り組んでいます。焦点は、探索空間の非線形性と高次元問題へのスケーラビリティにあります。数学的発展は、固定ランクの正の半正定値行列のセットの基礎となるリーマン幾何学に適応した勾配降下アルゴリズムの理論に依存しています。文献での以前の貢献とは対照的に、学習した行列の範囲空間に制限は課されません。結果として得られるアルゴリズムは、問題サイズの線形複雑さを維持し、重要な不変性特性を享受します。提案されたアルゴリズムを、正の半正定値行列によってパラメータ化された距離関数を学習する問題に適用します。古典的なベンチマークでは、良好なパフォーマンスが観察されます。
Variable Sparsity Kernel Learning
可変スパーシティ カーネル学習
This paper presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l1 norm regularization for promoting sparsity within RKHS norms of each group and ls, s≥2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels—hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O(m2ntot log nmax/ε2) where m is no. training data points, nmax,ntot are the maximum no. kernels in any group, total no. kernels respectively and ε is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency.
この論文では、混合ノルム正則化に基づくマルチカーネル学習(MKL)定式化の特定のクラスに対する新しいアルゴリズムとアプリケーションを紹介します。定式化では、与えられたカーネルがグループ化されていると想定し、各グループのRKHSノルム内でスパース性を促進するためにl1ノルム正則化を使用し、グループ間で非スパースな組み合わせを促進するためにls、s≥2ノルム正則化を使用します。カーネルを組み合わせる際のさまざまなスパース性レベルは、カーネルのグループ化を変えることによって実現できます。そのため、この定式化を可変スパースカーネル学習(VSKL)定式化と名付けました。これまでの試みは非凸定式化でしたが、ここでは効率的なミラー降下(MD)ベースの解決手法が可能な凸定式化を紹介します。提案されたMDベースのアルゴリズムは、単体の積を最適化し、計算複雑度はO(m2ntot log nmax/ε2)です。ここで、mはトレーニング データ ポイントの数、nmax、ntotはグループ内のカーネルの最大数、合計カーネル数です。カーネルはそれぞれ、ε は目的関数を近似する際の誤差です。アルゴリズムの収束の詳細な証明も提示されています。実験結果から、VSKL定式化はオブジェクト分類などのマルチモーダル学習タスクに適していることがわかります。また、計算効率の点で、MDベースのアルゴリズムが最先端のMKLソルバーよりも優れていることもわかります。
Minimum Description Length Penalization for Group and Multi-Task Sparse Learning
グループおよびマルチタスクのスパース学習に対する最小説明長のペナルティ
We propose a framework MIC (Multiple Inclusion Criterion) for learning sparse models based on the information theoretic Minimum Description Length (MDL) principle. MIC provides an elegant way of incorporating arbitrary sparsity patterns in the feature space by using two-part MDL coding schemes. We present MIC based models for the problems of grouped feature selection (MIC-GROUP) and multi-task feature selection (MIC-MULTI). MIC-GROUP assumes that the features are divided into groups and induces two level sparsity, selecting a subset of the feature groups, and also selecting features within each selected group. MIC-MULTI applies when there are multiple related tasks that share the same set of potentially predictive features. It also induces two level sparsity, selecting a subset of the features, and then selecting which of the tasks each feature should be added to. Lastly, we propose a model, TRANSFEAT, that can be used to transfer knowledge from a set of previously learned tasks to a new task that is expected to share similar features. All three methods are designed for selecting a small set of predictive features from a large pool of candidate features. We demonstrate the effectiveness of our approach with experimental results on data from genomics and from word sense disambiguation problems.
私たちは、情報理論の最小記述長(MDL)原理に基づいてスパース モデルを学習するためのフレームワークMIC (多重包含基準)を提案します。MICは、2部構成のMDLコーディング スキームを使用して、任意のスパース パターンを特徴空間に組み込むための洗練された方法を提供します。グループ化された特徴選択(MIC-GROUP)とマルチタスク特徴選択(MIC-MULTI)の問題に対するMICベースのモデルを紹介します。MIC-GROUPは、特徴がグループに分割されていると想定し、2レベルのスパース性を誘導して、特徴グループのサブセットを選択し、選択した各グループ内の特徴も選択します。MIC-MULTIは、潜在的に予測可能な特徴の同じセットを共有する複数の関連タスクがある場合に適用されます。また、2レベルのスパース性を誘導して、特徴のサブセットを選択し、各特徴を追加するタスクを選択します。最後に、以前に学習したタスクのセットから、同様の特徴を共有することが予想される新しいタスクに知識を転送するために使用できるモデルTRANSFEATを提案します。これら3つの方法はすべて、候補となる特徴の大きなプールから少数の予測特徴を選択するように設計されています。私たちは、ゲノミクスと語義の曖昧さ解消問題のデータを用いた実験結果によって、このアプローチの有効性を実証しています。
Learning Multi-modal Similarity
マルチモーダル類似性の学習
In many applications involving multi-media data, the definition of similarity between items is integral to several key tasks, including nearest-neighbor retrieval, classification, and recommendation. Data in such regimes typically exhibits multiple modalities, such as acoustic and visual content of video. Integrating such heterogeneous data to form a holistic similarity space is therefore a key challenge to be overcome in many real-world applications.We present a novel multiple kernel learning technique for integrating heterogeneous data into a single, unified similarity space. Our algorithm learns an optimal ensemble of kernel transformations which conform to measurements of human perceptual similarity, as expressed by relative comparisons. To cope with the ubiquitous problems of subjectivity and inconsistency in multi-media similarity, we develop graph-based techniques to filter similarity measurements, resulting in a simplified and robust training procedure.
マルチメディアデータを含む多くのアプリケーションでは、アイテム間の類似性の定義は、最近傍検索、分類、推奨など、いくつかの主要なタスクに不可欠です。このような領域のデータは、通常、ビデオの音響コンテンツや視覚コンテンツなど、複数のモダリティを示します。したがって、このような異種データを統合して全体的な類似性空間を形成することは、多くの実世界のアプリケーションで克服すべき重要な課題です。私たちは、異種データを単一の統一された類似性空間に統合するための新しいマルチカーネル学習手法を提示します。私たちのアルゴリズムは、相対的な比較によって表される人間の知覚的類似性の測定値に準拠するカーネル変換の最適なアンサンブルを学習します。主観性とマルチメディア類似性の不整合というユビキタスな問題に対処するために、類似性測定値をフィルタリングするグラフベースの手法を開発し、その結果、簡素化された堅牢なトレーニング手順を実現します。
Posterior Sparsity in Unsupervised Dependency Parsing
教師なし依存関係解析における事後スパース性
A strong inductive bias is essential in unsupervised grammar induction. In this paper, we explore a particular sparsity bias in dependency grammars that encourages a small number of unique dependency types. We use part-of-speech (POS) tags to group dependencies by parent-child types and investigate sparsity-inducing penalties on the posterior distributions of parent-child POS tag pairs in the posterior regularization (PR) framework of Graça et al. (2007). In experiments with 12 different languages, we achieve significant gains in directed attachment accuracy over the standard expectation maximization (EM) baseline, with an average accuracy improvement of 6.5%, outperforming EM by at least 1% for 9 out of 12 languages. Furthermore, the new method outperforms models based on standard Bayesian sparsity-inducing parameter priors with an average improvement of 5% and positive gains of at least 1% for 9 out of 12 languages. On English text in particular, we show that our approach improves performance over other state-of-the-art techniques.
教師なし文法誘導では、強い帰納的バイアスが不可欠です。この論文では、少数の固有の依存関係タイプを促進する依存関係文法の特定のスパース性バイアスについて検討します。品詞(POS)タグを使用して依存関係を親子タイプ別にグループ化し、Graçaら(2007)の事後正則化(PR)フレームワークで親子POSタグ ペアの事後分布に対するスパース性誘導ペナルティを調査します。12の異なる言語を使用した実験では、標準的な期待最大化(EM)ベースラインに対して、有向接続の精度が大幅に向上し、平均精度が6.5%向上し、12言語のうち9言語でEMを少なくとも1%上回りました。さらに、新しい方法は、標準的なベイジアン スパース性誘導パラメータ事前分布に基づくモデルよりも優れており、12言語のうち9言語で平均5%の向上と少なくとも1%のプラス効果が得られました。特に英語のテキストでは、私たちのアプローチが他の最先端の技術よりもパフォーマンスを向上させることを示しています。
Approximate Marginals in Latent Gaussian Models
潜在ガウスモデルにおける近似周辺分布
We consider the problem of improving the Gaussian approximate posterior marginals computed by expectation propagation and the Laplace method in latent Gaussian models and propose methods that are similar in spirit to the Laplace approximation of Tierney and Kadane (1986). We show that in the case of sparse Gaussian models, the computational complexity of expectation propagation can be made comparable to that of the Laplace method by using a parallel updating scheme. In some cases, expectation propagation gives excellent estimates where the Laplace approximation fails. Inspired by bounds on the correct marginals, we arrive at factorized approximations, which can be applied on top of both expectation propagation and the Laplace method. The factorized approximations can give nearly indistinguishable results from the non-factorized approximations and their computational complexity scales linearly with the number of variables. We experienced that the expectation propagation based marginal approximations we introduce are typically more accurate than the methods of similar complexity proposed by Rue et al. (2009).
私たちは、潜在ガウスモデルにおける期待値伝播とラプラス法によって計算されるガウス近似事後周辺分布を改善する問題について検討し、TierneyとKadane (1986)のラプラス近似に似た方法を提案します。スパース ガウス モデルの場合、並列更新スキームを使用することで、期待値伝播の計算複雑度をラプラス法と同程度にできることを示します。場合によっては、ラプラス近似が失敗する場合でも、期待値伝播は優れた推定値を与えます。正しい周辺分布の境界に着想を得て、期待値伝播とラプラス法の両方に適用できる因数分解近似に到達しました。因数分解近似は、因数分解されていない近似とほとんど区別がつかない結果を与えることができ、その計算複雑度は変数の数に比例して増加します。私たちが導入した期待伝播ベースの限界近似は、Rueら(2009)が提案した同様の複雑さを持つ方法よりも一般的に正確であることが分かりました。
Operator Norm Convergence of Spectral Clustering on Level Sets
レベル セットでのスペクトル クラスタリングの演算子ノルム収束
Following Hartigan (1975), a cluster is defined as a connected component of the t-level set of the underlying density, that is, the set of points for which the density is greater than t. A clustering algorithm which combines a density estimate with spectral clustering techniques is proposed. Our algorithm is composed of two steps. First, a nonparametric density estimate is used to extract the data points for which the estimated density takes a value greater than t. Next, the extracted points are clustered based on the eigenvectors of a graph Laplacian matrix. Under mild assumptions, we prove the almost sure convergence in operator norm of the empirical graph Laplacian operator associated with the algorithm. Furthermore, we give the typical behavior of the representation of the data set into the feature space, which establishes the strong consistency of our proposed algorithm.
Hartigan(1975)に従って、クラスターは、基礎となる密度のtレベルセットの接続されたコンポーネント、つまり、密度がtより大きいポイントのセットとして定義されます。密度推定とスペクトルクラスタリング技術を組み合わせたクラスタリングアルゴリズムが提案されています。私たちのアルゴリズムは2つのステップで構成されています。まず、ノンパラメトリック密度推定を使用して、推定密度がtより大きい値を取るデータ点を抽出します。次に、抽出された点は、グラフ ラプラシアン行列の固有ベクトルに基づいてクラスター化されます。穏やかな仮定の下で、アルゴリズムに関連付けられた経験的グラフラプラシアン演算子の演算子ノルムのほぼ確実な収束を証明します。さらに、データセットの表現の典型的な動作を特徴空間に与え、提案されたアルゴリズムの強い一貫性を確立します。
Models of Cooperative Teaching and Learning
共同教育と学習のモデル
While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects “helpful” training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C) is lower in models assuming such teachers, that is, “helpful” examples can speed up the learning process.The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using “coding tricks”, has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively “helpful” examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of “coding trick”/”collusion”. We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables.The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios.
ほとんどの教師付き機械学習モデルでは、トレーニング例がランダムまたは敵対的にサンプリングされることを前提としていますが、この記事では、「役立つ」トレーニング例を選択する協力的な教師からの学習モデルについて取り上げます。学習者が、可能なターゲット概念の特定のクラスC (サンプル複雑度C)の概念を識別するために必要なトレーニング例の数は、そのような教師を前提とするモデルでは少なくなります。つまり、「役立つ」例は学習プロセスを高速化できます。教師と学習者が「コーディング トリック」を使用せずにサンプル複雑度を減らすために協力する方法の問題は、広く取り上げられてきました。しかし、結果として得られる教育および学習プロトコルでは、教師が直感的に「役立つ」例を選択できるようには見えません。この論文で紹介する2つのモデルは、サブセット教育セットと再帰教育セットと呼ばれるものに基づいています。これらは、教師と学習者の両方がパートナーが協力的であることを知って活用できるようにすることで、以前の教育モデルを拡張します。この目的のために、「コーディング トリック」/「共謀」という新しい概念を導入します。コーディングのトリックを使わずに、サンプルの複雑さの測定値(サブセット ティーチング次元と再帰ティーチング次元)の両方が、従来のティーチング次元とその既知のバリエーションよりも任意に低くできることを示します。たとえば、単項式は、変数の数に関係なく、2つの例だけで教えることができます。サブセット ティーチング次元は、概念クラスのサブクラスに関して非単調であることがわかります。この非単調性が、多くの興味深い協力的な教育および学習シナリオに固有のものである理由について説明します。
Cumulative Distribution Networks and the Derivative-sum-product Algorithm: Models and Inference for Cumulative Distribution Functions on Graphs
累積分布ネットワークと微分和積アルゴリズム: グラフ上の累積分布関数のモデルと推論
We present a class of graphical models for directly representing the joint cumulative distribution function (CDF) of many random variables, called cumulative distribution networks (CDNs). Unlike graphs for probability density and mass functions, for CDFs the marginal probabilities for any subset of variables are obtained by computing limits of functions in the model, and conditional probabilities correspond to computing mixed derivatives. We will show that the conditional independence properties in a CDN are distinct from the conditional independence properties of directed, undirected and factor graphs, but include the conditional independence properties of bi-directed graphs. In order to perform inference in such models, we describe the `derivative-sum-product’ (DSP) message-passing algorithm in which messages correspond to derivatives of the joint CDF. We will then apply CDNs to the problem of learning to rank players in multiplayer team-based games and suggest several future directions for research.
私たちは、累積分布ネットワーク(CDN)と呼ばれる、多数のランダム変数の結合累積分布関数(CDF)を直接表現するグラフィカル モデルのクラスを紹介します。確率密度関数や質量関数のグラフとは異なり、CDFの場合、変数の任意のサブセットの周辺確率はモデル内の関数の極限を計算することによって取得され、条件付き確率は混合導関数の計算に対応します。CDNの条件付き独立性プロパティは、有向グラフ、無向グラフ、因子グラフの条件付き独立性プロパティとは異なりますが、双方向グラフの条件付き独立性プロパティは含まれていることを示します。このようなモデルで推論を実行するために、結合CDFの導関数に対応するメッセージがある「導関数和積(DSP)」メッセージ パッシング アルゴリズムについて説明します。次に、マルチプレイヤー チーム ベース ゲームでプレイヤーをランク付けする学習の問題にCDNを適用し、今後の研究の方向性をいくつか提案します。
A Bayesian Approximation Method for Online Ranking
オンラインランキングのためのベイズ近似法
This paper describes a Bayesian approximation method to obtain online ranking algorithms for games with multiple teams and multiple players. Recently for Internet games large online ranking systems are much needed. We consider game models in which a k-team game is treated as several two-team games. By approximating the expectation of teams’ (or players’) performances, we derive simple analytic update rules. These update rules, without numerical integrations, are very easy to interpret and implement. Experiments on game data show that the accuracy of our approach is competitive with state of the art systems such as TrueSkill, but the running time as well as the code is much shorter.
この論文では、複数のチームと複数のプレーヤーが参加するゲームのオンラインランキングアルゴリズムを取得するためのベイズ近似法について説明します。最近、インターネットゲームでは、大規模なオンラインランキングシステムが大いに必要とされています。kチームのゲームが複数の2チームゲームとして扱われるゲームモデルを考えます。チーム(またはプレーヤー)のパフォーマンスの期待値を近似することで、単純な分析更新ルールを導き出します。これらの更新ルールは、数値積分を使用しないため、解釈と実装が非常に簡単です。ゲームデータでの実験では、私たちのアプローチの精度はTrueSkillなどの最先端のシステムと競争力がありますが、実行時間とコードははるかに短いことが示されています。
Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm
摂動リーダーアルゴリズムに従うを使用した無制限の損失の場合のオンライン学習
In this paper the sequential prediction problem with expert advice is considered for the case where losses of experts suffered at each step cannot be bounded in advance. We present some modification of Kalai and Vempala algorithm of following the perturbed leader where weights depend on past losses of the experts. New notions of a volume and a scaled fluctuation of a game are introduced. We present a probabilistic algorithm protected from unrestrictedly large one-step losses. This algorithm has the optimal performance in the case when the scaled fluctuations of one-step losses of experts of the pool tend to zero.
この論文では、各ステップで専門家が被った損失を事前に限定できない場合について、専門家の助言による逐次予測問題について考察します。私たちは、重みが専門家の過去の損失に依存する摂動されたリーダーに従うKalaiとVempalaのアルゴリズムのいくつかの修正を提示します。ゲームのボリュームとスケーリングされた変動の新しい概念が導入されています。無制限の大きなワンステップ損失から保護された確率的アルゴリズムを提示します。このアルゴリズムは、プールの専門家の1ステップ損失のスケーリング変動がゼロになる傾向がある場合に最適なパフォーマンスを発揮します。
Logistic Stick-Breaking Process
ロジスティックブレイキングプロセス
A logistic stick-breaking process (LSBP) is proposed for non-parametric clustering of general spatially- or temporally-dependent data, imposing the belief that proximate data are more likely to be clustered together. The sticks in the LSBP are realized via multiple logistic regression functions, with shrinkage priors employed to favor contiguous and spatially localized segments. The LSBP is also extended for the simultaneous processing of multiple data sets, yielding a hierarchical logistic stick-breaking process (H-LSBP). The model parameters (atoms) within the H-LSBP are shared across the multiple learning tasks. Efficient variational Bayesian inference is derived, and comparisons are made to related techniques in the literature. Experimental analysis is performed for audio waveforms and images, and it is demonstrated that for segmentation applications the LSBP yields generally homogeneous segments with sharp boundaries.
ロジスティックスティックブレイキングプロセス(LSBP)は、一般的な空間的または時間的に依存するデータのノンパラメトリッククラスタリングに対して提案されており、近接データが一緒にクラスタリングされる可能性が高いという信念を課しています。LSBPのスティックは、複数のロジスティック回帰関数を介して実現され、収縮事前確率を使用して、連続した空間的にローカライズされたセグメントを優先します。LSBPは、複数のデータセットの同時処理にも拡張されており、階層的なロジスティックスティックブレイキングプロセス(H-LSBP)を実現します。H-LSBP内のモデルパラメータ(原子)は、複数の学習タスク間で共有されます。効率的な変分ベイズ推論が導出され、文献の関連手法と比較されます。オーディオ波形と画像について実験的分析が行われ、セグメンテーションアプリケーションの場合、LSBPは一般的に鋭い境界を持つ均質なセグメントを生成することが実証されています。
Training SVMs Without Offset
オフセットなしの SVM のトレーニング
We develop, analyze, and test a training algorithm for support vector machine classifiers without offset. Key features of this algorithm are a new, statistically motivated stopping criterion, new warm start options, and a set of inexpensive working set selection strategies that significantly reduce the number of iterations. For these working set strategies, we establish convergence rates that, not surprisingly, coincide with the best known rates for SVMs with offset. We further conduct various experiments that investigate both the run time behavior and the performed iterations of the new training algorithm. It turns out, that the new algorithm needs significantly less iterations and also runs substantially faster than standard training algorithms for SVMs with offset.
私たちは、オフセットなしのサポートベクターマシン分類器の学習アルゴリズムを開発、分析、およびテストします。このアルゴリズムの主な特徴は、統計的に動機付けられた新しい停止基準、新しいウォーム スタート オプション、および反復回数を大幅に減らす一連の安価なワーキング セット選択戦略です。これらのワーキング セット ストラテジーでは、当然のことながら、オフセットを持つSVMの既知の最も知られたレートと一致する収束レートを確立します。さらに、新しいトレーニングアルゴリズムの実行時の動作と実行された反復の両方を調査するさまざまな実験を行います。新しいアルゴリズムは、オフセットのあるSVMの標準的な学習アルゴリズムよりも大幅に少ない反復回数で、大幅に高速に実行されることがわかりました。
Bayesian Generalized Kernel Mixed Models
ベイジアン一般化カーネル混合モデル
We propose a fully Bayesian methodology for generalized kernel mixed models (GKMMs), which are extensions of generalized linear mixed models in the feature space induced by a reproducing kernel. We place a mixture of a point-mass distribution and Silverman’s g-prior on the regression vector of a generalized kernel model (GKM). This mixture prior allows a fraction of the components of the regression vector to be zero. Thus, it serves for sparse modeling and is useful for Bayesian computation. In particular, we exploit data augmentation methodology to develop a Markov chain Monte Carlo (MCMC) algorithm in which the reversible jump method is used for model selection and a Bayesian model averaging method is used for posterior prediction. When the feature basis expansion in the reproducing kernel Hilbert space is treated as a stochastic process, this approach can be related to the Karhunen-Loève expansion of a Gaussian process (GP). Thus, our sparse modeling framework leads to a flexible approximation method for GPs.
私たちは、一般化カーネル混合モデル(GKMM)のための完全なベイジアン手法を提案します。これは、再生カーネルによって誘導される特徴空間における一般化線形混合モデルの拡張です。一般化カーネルモデル(GKM)の回帰ベクトルに、質点分布とSilvermanのg事前分布の混合を配置します。この混合事前分布により、回帰ベクトルの成分の一部をゼロにすることができます。したがって、これはスパースモデリングに役立ち、ベイジアン計算に役立ちます。特に、データ拡張手法を利用して、可逆ジャンプ法をモデル選択に使用し、ベイジアンモデル平均化法を事後予測に使用するマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを開発します。再生カーネルヒルベルト空間での特徴基底展開を確率過程として扱う場合、このアプローチはガウス過程(GP)のカルーネン・レーヴ展開に関連付けることができます。したがって、私たちのスパースモデリングフレームワークは、GPの柔軟な近似方法につながります。
Multitask Sparsity via Maximum Entropy Discrimination
最大エントロピー弁別によるマルチタスクのスパース性
A multitask learning framework is developed for discriminative classification and regression where multiple large-margin linear classifiers are estimated for different prediction problems. These classifiers operate in a common input space but are coupled as they recover an unknown shared representation. A maximum entropy discrimination (MED) framework is used to derive the multitask algorithm which involves only convex optimization problems that are straightforward to implement. Three multitask scenarios are described. The first multitask method produces multiple support vector machines that learn a shared sparse feature selection over the input space. The second multitask method produces multiple support vector machines that learn a shared conic kernel combination. The third multitask method produces a pooled classifier as well as adaptively specialized individual classifiers. Furthermore, extensions to regression, graphical model structure estimation and other sparse methods are discussed. The maximum entropy optimization problems are implemented via a sequential quadratic programming method which leverages recent progress in fast SVM solvers. Fast monotonic convergence bounds are provided by bounding the MED sparsifying cost function with a quadratic function and ensuring only a constant factor runtime increase above standard independent SVM solvers. Results are shown on multitask data sets and favor multitask learning over single-task or tabula rasa methods.
識別分類および回帰のためのマルチタスク学習フレームワークが開発され、複数の大きなマージンを持つ線形分類器がさまざまな予測問題に対して推定されます。これらの分類器は共通の入力空間で動作しますが、未知の共有表現を回復するときに結合されます。最大エントロピー識別(MED)フレームワークを使用して、実装が簡単な凸最適化問題のみを含むマルチタスク アルゴリズムを導出します。3つのマルチタスク シナリオについて説明します。最初のマルチタスク メソッドは、入力空間で共有のスパースな特徴選択を学習する複数のサポート ベクター マシンを生成します。2番目のマルチタスク メソッドは、共有の円錐カーネルの組み合わせを学習する複数のサポート ベクター マシンを生成します。3番目のマルチタスク メソッドは、プールされた分類器と適応的に特化した個々の分類器を生成します。さらに、回帰、グラフィカル モデル構造推定、およびその他のスパース メソッドの拡張について説明します。最大エントロピー最適化問題は、高速SVMソルバーの最近の進歩を活用する逐次二次計画法によって実装されます。MEDスパース化コスト関数を二次関数で制限し、標準の独立SVMソルバーよりも実行時間が一定係数だけ増加するようにすることで、高速な単調収束境界が提供されます。結果はマルチタスク データ セットで示され、シングルタスクまたはタブラ ラサ メソッドよりもマルチタスク学習が優先されます。
CARP: Software for Fishing Out Good Clustering Algorithms
CARP:優れたクラスタリングアルゴリズムを釣り出すためのソフトウェア
This paper presents the CLUSTERING ALGORITHMS’ REFEREE PACKAGE or CARP, an open source GNU GPL-licensed C package for evaluating clustering algorithms. Calibrating performance of such algorithms is important and CARP addresses this need by generating datasets of different clustering complexity and by assessing the performance of the concerned algorithm in terms of its ability to classify each dataset relative to the true grouping. This paper briefly describes the software and its capabilities.
この論文では、クラスタリングアルゴリズムを評価するためのオープンソースのGNU GPLライセンスCパッケージであるCLUSTERING ALGORITHMS’ REFEEE PACKAGEまたはCARPを紹介します。このようなアルゴリズムのパフォーマンスを較正することは重要であり、CARPは、クラスタリングの複雑さが異なるデータセットを生成し、各データセットを真のグループ化に対して分類する能力の観点から関連するアルゴリズムのパフォーマンスを評価することにより、このニーズに対処します。この論文では、ソフトウェアとその機能について簡単に説明します。
Improved Moves for Truncated Convex Models
切断凸モデルの移動の改善
We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-MINCUT based move making algorithms that we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of αβ-Swap and α-Expansion respectively that fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (that is, an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (LP) relaxation in polynomial time. Compared to previous approaches based on the LP relaxation, for example interior-point algorithms or tree-reweighted message passing (TRW), our methods are faster as they use only the efficient st-MINCUT algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems.
私たちは、切断された凸モデルを形成するペアワイズポテンシャルによって特徴付けられる離散ランダムフィールドの事後推定値の近似最大値を取得する問題を考察します。この問題に対して、我々はRange SwapとRange Expansionと呼ぶ2つのst-MINCUTベースの移動作成アルゴリズムを提案します。我々のアルゴリズムは、ペアワイズポテンシャルの形式を完全に利用する、それぞれ αβ-Swapと α-Expansionの拡張版と考えることができます。具体的には、各反復で1つまたは2つのラベルを処理する代わりに、我々の方法はラベルの範囲(つまり、連続するラベルの間隔)を考慮して、大規模な検索空間を探索します。さらに、Range Expansionは、多項式時間で標準線形計画法(LP)緩和と同じ乗法境界を提供することを示します。LP緩和に基づく以前のアプローチ(たとえば、内点アルゴリズムやツリー再重み付けメッセージ パッシング(TRW))と比較すると、我々の方法は、効率的なst-MINCUTアルゴリズムのみを使用して設計されているため、より高速です。提案されたアプローチが合成データ問題と標準実データ問題の両方で有用であることを実証します。
Exploitation of Machine Learning Techniques in Modelling Phrase Movements for Machine Translation
機械翻訳のためのフレーズ移動のモデリングにおける機械学習技術の活用
We propose a distance phrase reordering model (DPR) for statistical machine translation (SMT), where the aim is to learn the grammatical rules and context dependent changes using a phrase reordering classification framework. We consider a variety of machine learning techniques, including state-of-the-art structured prediction methods. Techniques are compared and evaluated on a Chinese-English corpus, a language pair known for the high reordering characteristics which cannot be adequately captured with current models. In the reordering classification task, the method significantly outperforms the baseline against which it was tested, and further, when integrated as a component of the state-of-the-art machine translation system, MOSES, it achieves improvement in translation results.
私たちは、統計的機械翻訳(SMT)のための距離フレーズ並べ替えモデル(DPR)を提案し、フレーズ並べ替え分類フレームワークを使用して文法規則と文脈依存の変更を学習することを目的としています。最先端の構造化予測手法を含む、さまざまな機械学習技術を検討しています。手法は、現在のモデルでは適切に捉えられない高い再順序付け特性で知られる言語ペアである中国語と英語のコーパスで比較および評価されます。並べ替え分類タスクでは、この手法はテストされたベースラインを大幅に上回り、さらに、最先端の機械翻訳システムであるMOSESのコンポーネントとして統合すると、翻訳結果の改善を達成します。
