Kernel Bayes’ Rule: Bayesian Inference with Positive Definite Kernels
カーネルベイズの法則:正定値カーネルによるベイズ推論
A kernel method for realizing Bayes’ rule is proposed, based on representations of probabilities in reproducing kernel Hilbert spaces. Probabilities are uniquely characterized by the mean of the canonical map to the RKHS. The prior and conditional probabilities are expressed in terms of RKHS functions of an empirical sample: no explicit parametric model is needed for these quantities. The posterior is likewise an RKHS mean of a weighted sample. The estimator for the expectation of a function of the posterior is derived, and rates of consistency are shown. Some representative applications of the kernel Bayes’ rule are presented, including Bayesian computation without likelihood and filtering with a nonparametric state-space model.
ベイズの法則を実現するためのカーネル法が提案されており、再現カーネルヒルベルト空間の確率の表現に基づいています。確率は、RKHSへの正準写像の平均によって一意に特徴付けられます。事前確率と条件付き確率は、経験的サンプルのRKHS関数で表され、これらの量には明示的なパラメトリックモデルは必要ありません。後部も同様に、加重サンプルのRKHS平均です。事後関数の期待値の推定量が導出され、一貫性の割合が示されています。カーネル ベイズの法則の代表的な適用例としては、尤度なしのベイズ計算やノンパラメトリックな状態空間モデルによるフィルタリングなどがあります。
Joint Harmonic Functions and Their Supervised Connections
関節調和関数とその監視接続
The cluster assumption had a significant impact on the reasoning behind semi-supervised classification methods in graph-based learning. The literature includes numerous applications where harmonic functions provided estimates that conformed to data satisfying this well-known assumption, but the relationship between this assumption and harmonic functions is not as well- understood theoretically. We investigate these matters from the perspective of supervised kernel classification and provide concrete answers to two fundamental questions. (i) Under what conditions do semi-supervised harmonic approaches satisfy this assumption? (ii) If such an assumption is satisfied then why precisely would an observation sacrifice its own supervised estimate in favor of the cluster? First, a harmonic function is guaranteed to assign labels to data in harmony with the cluster assumption if a specific condition on the boundary of the harmonic function is satisfied. Second, it is shown that any harmonic function estimate within the interior is a probability weighted average of supervised estimates, where the weight is focused on supervised kernel estimates near labeled cases. We demonstrate that the uniqueness criterion for harmonic estimators is sensitive when the graph is sparse or the size of the boundary is relatively small. This sets the stage for a third contribution, a new regularized joint harmonic function for semi-supervised learning based on a joint optimization criterion. Mathematical properties of this estimator, such as its uniqueness even when the graph is sparse or the size of the boundary is relatively small, are proven. A main selling point is its ability to operate in circumstances where the cluster assumption may not be fully satisfied on real data by compromising between the purely harmonic and purely supervised estimators. The competitive stature of the new regularized joint harmonic approach is established.
クラスター仮定は、グラフベース学習における半教師あり分類法の根拠に大きな影響を与えました。文献には、調和関数がこのよく知られた仮定を満たすデータに適合する推定値を提供する多数のアプリケーションが含まれていますが、この仮定と調和関数の関係は理論的にはあまり理解されていません。私たちは、教師ありカーネル分類の観点からこれらの問題を調査し、2つの基本的な質問に対する具体的な回答を提供します。(i)半教師あり調和アプローチはどのような条件下でこの仮定を満たすのか? (ii)このような仮定が満たされている場合、観測はクラスターを優先して自身の教師あり推定値を犠牲にするのはなぜなのか?まず、調和関数は、調和関数の境界に関する特定の条件が満たされている場合、クラスター仮定と調和してデータにラベルを割り当てることが保証されます。次に、内部内の任意の調和関数推定値は、ラベル付きケースの近くの教師ありカーネル推定値に重みが集中する、教師あり推定値の確率加重平均であることが示されています。調和推定量の一意性基準は、グラフが疎であるか境界のサイズが比較的小さい場合に敏感であることを示します。これにより、3番目の貢献、つまり、結合最適化基準に基づく半教師あり学習用の新しい正規化結合調和関数の準備が整いました。グラフが疎であるか境界のサイズが比較的小さい場合でも一意であるなど、この推定量の数学的特性が証明されています。主なセールス ポイントは、純粋に調和的な推定量と純粋に教師ありの推定量の間で妥協することにより、実際のデータでクラスター仮定が完全に満たされない可能性がある状況でも動作できることです。新しい正規化結合調和アプローチの競争力が確立されました。
How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis
低速特徴分析の教師付き拡張を使用して高次元データに対する分類問題と回帰問題を解く方法
Supervised learning from high-dimensional data, for example, multimedia data, is a challenging task. We propose an extension of slow feature analysis (SFA) for supervised dimensionality reduction called graph-based SFA (GSFA). The algorithm extracts a label-predictive low-dimensional set of features that can be post-processed by typical supervised algorithms to generate the final label or class estimation. GSFA is trained with a so-called training graph, in which the vertices are the samples and the edges represent similarities of the corresponding labels. A new weighted SFA optimization problem is introduced, generalizing the notion of slowness from sequences of samples to such training graphs. We show that GSFA computes an optimal solution to this problem in the considered function space and propose several types of training graphs. For classification, the most straightforward graph yields features equivalent to those of (nonlinear) Fisher discriminant analysis. Emphasis is on regression, where four different graphs were evaluated experimentally with a subproblem of face detection on photographs. The method proposed is promising particularly when linear models are insufficient as well as when feature selection is difficult.
マルチメディア データなどの高次元データからの教師あり学習は、困難なタスクです。私たちは、グラフベースSFA (GSFA)と呼ばれる教師あり次元削減のための低速特徴分析(SFA)の拡張を提案します。このアルゴリズムは、ラベル予測の低次元の特徴セットを抽出し、これを一般的な教師ありアルゴリズムで後処理して、最終的なラベルまたはクラス推定を生成できます。GSFAは、頂点がサンプルで、エッジが対応するラベルの類似性を表す、いわゆるトレーニング グラフを使用してトレーニングされます。新しい重み付きSFA最適化問題が導入され、サンプルのシーケンスからこのようなトレーニング グラフに低速性の概念が一般化されます。私たちは、GSFAが、検討対象の関数空間でこの問題の最適解を計算することを示し、いくつかの種類のトレーニング グラフを提案します。分類の場合、最も単純なグラフは、(非線形)フィッシャー判別分析と同等の特徴を生み出します。回帰に重点が置かれ、写真の顔検出というサブ問題を使用して4つの異なるグラフが実験的に評価されました。提案された方法は、線形モデルが不十分な場合や特徴選択が難しい場合に特に有望です。
Efficient Program Synthesis Using Constraint Satisfaction in Inductive Logic Programming
帰納的論理プログラミングにおける制約充足性を用いた効率的なプログラム合成
We present NrSample, a framework for program synthesis in inductive logic programming. NrSample uses propositional logic constraints to exclude undesirable candidates from the search. This is achieved by representing constraints as propositional formulae and solving the associated constraint satisfaction problem. We present a variety of such constraints: pruning, input-output, functional (arithmetic), and variable splitting. NrSample is also capable of detecting search space exhaustion, leading to further speedups in clause induction and optimality. We benchmark NrSample against enumeration search (Aleph’s default) and Progol’s $A^{*}$ search in the context of program synthesis. The results show that, on large program synthesis problems, NrSample induces between 1 and 1358 times faster than enumeration (236 times faster on average), always with similar or better accuracy. Compared to Progol $A^{*}$, NrSample is 18 times faster on average with similar or better accuracy except for two problems: one in which Progol $A^{*}$ substantially sacrificed accuracy to induce faster, and one in which Progol $A^{*}$ was a clear winner. Functional constraints provide a speedup of up to 53 times (21 times on average) with similar or better accuracy. We also benchmark using a few concept learning (non-program synthesis) problems. The results indicate that without strong constraints, the overhead of solving constraints is not compensated for.
私たちは、帰納的論理プログラミングにおけるプログラム合成のフレームワークであるNrSampleを紹介します。NrSampleは命題論理制約を使用して、検索から望ましくない候補を除外します。これは、制約を命題式として表現し、関連する制約充足問題を解決することによって実現されます。私たちは、刈り込み、入出力、関数(算術)、変数分割など、さまざまな制約を紹介します。NrSampleは検索空間の枯渇を検出することもでき、節の帰納と最適性のさらなる高速化につながります。プログラム合成のコンテキストで、NrSampleを列挙検索(Alephのデフォルト)およびProgolの$A^{*}$検索と比較ベンチマークします。結果は、大規模なプログラム合成問題では、NrSampleは列挙よりも1～1358倍(平均で236倍)高速に帰納し、常に同等以上の精度を実現します。Progol $A^{*}$と比較すると、NrSampleは平均で18倍高速ですが、2つの問題を除き、精度は同等かそれ以上です。1つはProgol $A^{*}$が高速化のために精度を大幅に犠牲にしている問題、もう1つはProgol $A^{*}$が明らかに勝っている問題です。機能制約により、最大53倍(平均で21倍)の高速化が実現され、精度は同等かそれ以上です。また、いくつかの概念学習(非プログラム合成)問題を使用してベンチマークも行いました。結果は、強力な制約がないと、制約を解くオーバーヘッドが補償されないことを示しています。
A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
1ビット行列完成への最大ノルム制約付き最小化アプローチ
We consider in this paper the problem of noisy 1-bit matrix completion under a general non-uniform sampling distribution using the max-norm as a convex relaxation for the rank. A max- norm constrained maximum likelihood estimate is introduced and studied. The rate of convergence for the estimate is obtained. Information-theoretical methods are used to establish a minimax lower bound under the general sampling model. The minimax upper and lower bounds together yield the optimal rate of convergence for the Frobenius norm loss. Computational algorithms and numerical performance are also discussed.
私たちは、この論文では、rankの凸緩和としてmax-normを使用した一般的な不均一なサンプリング分布の下でのノイズの多い1ビット行列補完の問題を検討します。最大ノルム制約付き最尤推定値が導入され、研究されます。推定値の収束率が得られます。情報理論的な手法は、一般的なサンプリングモデルの下でミニマックス下限を確立するために使用されます。ミニマックスの上限と下限を合わせると、フロベニウスノルム損失の最適な収束率が得られます。また、計算アルゴリズムと数値性能についても説明します。
Classifier Selection using the Predicate Depth
述語の深さを使用した分類器の選択
Typically, one approaches a supervised machine learning problem by writing down an objective function and finding a hypothesis that minimizes it. This is equivalent to finding the Maximum A Posteriori (MAP) hypothesis for a Boltzmann distribution. However, MAP is not a robust statistic. We present an alternative approach by defining a median of the distribution, which we show is both more robust, and has good generalization guarantees. We present algorithms to approximate this median. One contribution of this work is an efficient method for approximating the Tukey median. The Tukey median, which is often used for data visualization and outlier detection, is a special case of the family of medians we define: however, computing it exactly is exponentially slow in the dimension. Our algorithm approximates such medians in polynomial time while making weaker assumptions than those required by previous work.
通常、教師あり機械学習の問題には、目的関数を書き留め、それを最小化する仮説を見つけることでアプローチします。これは、ボルツマン分布の最大A事後(MAP)仮説を見つけることと同じです。ただし、MAPは堅牢な統計ではありません。分布の中央値を定義することで、より堅牢であり、良好な一般化が保証されていることを示す別のアプローチを提示します。この中央値を近似するアルゴリズムを示します。この研究の貢献の1つは、テューキーの中央値を近似するための効率的な方法です。テューキー中央値は、データの視覚化や外れ値の検出によく使用されますが、定義する中央値のファミリーの特殊なケースですが、正確に計算すると、次元では指数関数的に遅くなります。私たちのアルゴリズムは、多項式時間でそのような中央値を近似しますが、以前の作業で必要とされた仮定よりも弱い仮定を立てます。
Classifying With Confidence From Incomplete Information
不完全な情報から自信を持って分類
We consider the problem of classifying a test sample given incomplete information. This problem arises naturally when data about a test sample is collected over time, or when costs must be incurred to compute the classification features. For example, in a distributed sensor network only a fraction of the sensors may have reported measurements at a certain time, and additional time, power, and bandwidth is needed to collect the complete data to classify. A practical goal is to assign a class label as soon as enough data is available to make a good decision. We formalize this goal through the notion of reliability—the probability that a label assigned given incomplete data would be the same as the label assigned given the complete data, and we propose a method to classify incomplete data only if some reliability threshold is met. Our approach models the complete data as a random variable whose distribution is dependent on the current incomplete data and the (complete) training data. The method differs from standard imputation strategies in that our focus is on determining the reliability of the classification decision, rather than just the class label. We show that the method provides useful reliability estimates of the correctness of the imputed class labels on a set of experiments on time- series data sets, where the goal is to classify the time-series as early as possible while still guaranteeing that the reliability threshold is met.
私たちは、不完全な情報がある場合にテスト サンプルを分類する問題について考えます。この問題は、テスト サンプルに関するデータが時間の経過とともに収集される場合、または分類機能を計算するためにコストがかかる場合に自然に発生します。たとえば、分散型センサー ネットワークでは、特定の時間にセンサーの一部だけが測定値を報告している可能性があり、分類するための完全なデータを収集するには追加の時間、電力、帯域幅が必要です。実用的な目標は、適切な決定を下すのに十分なデータが利用可能になったらすぐにクラス ラベルを割り当てることです。この目標を信頼性の概念で形式化します。信頼性とは、不完全なデータが割り当てられた場合に割り当てられるラベルが、完全なデータが割り当てられた場合に割り当てられるラベルと同じである確率です。また、信頼性のしきい値が満たされた場合のみ不完全なデータを分類する方法を提案します。私たちのアプローチでは、分布が現在の不完全なデータと(完全な)トレーニング データに依存するランダム変数として完全なデータをモデル化します。この方法は、クラス ラベルだけでなく分類決定の信頼性を決定することに重点を置いている点で、標準的な代入戦略とは異なります。この方法は、信頼性しきい値が満たされていることを保証しながら、時系列をできるだけ早く分類することを目標とする、時系列データセットの一連の実験において、補完されたクラスラベルの正確さに関する有用な信頼性推定値を提供することを示します。
Learning Trees from Strings: A Strong Learning Algorithm for some Context-Free Grammars
文字列からのツリーの学習:いくつかの文脈自由文法のための強力な学習アルゴリズム
Standard models of language learning are concerned with weak learning: the learner, receiving as input only information about the strings in the language, must learn to generalise and to generate the correct, potentially infinite, set of strings generated by some target grammar. Here we define the corresponding notion of strong learning: the learner, again only receiving strings as input, must learn a grammar that generates the correct set of structures or parse trees. We formalise this using a modification of Gold’s identification in the limit model, requiring convergence to a grammar that is isomorphic to the target grammar. We take as our starting point a simple learning algorithm for substitutable context-free languages, based on principles of distributional learning, and modify it so that it will converge to a canonical grammar for each language. We prove a corresponding strong learning result for a subclass of context-free grammars.
言語学習の標準モデルは、弱い学習に関係しています:学習者は、言語の文字列に関する情報のみを入力として受け取り、一般化し、何らかのターゲット文法によって生成された正しい、潜在的に無限の文字列のセットを生成することを学ばなければなりません。ここでは、強力な学習の対応する概念を定義します:学習者は、再び入力として文字列を受け取るだけで、正しい構造のセットを生成する文法を学習するか、ツリーを解析する必要があります。これを定式化するには、極限モデルにおけるゴールドの同定の修正を使用し、ターゲット文法と同型の文法への収束を要求します。私たちは、分散学習の原則に基づいて、代替可能な文脈自由言語の単純な学習アルゴリズムを出発点とし、各言語の正規文法に収束するように修正します。文脈自由文法のサブクラスに対応する強力な学習結果を証明します。
Lovasz theta function, SVMs and Finding Dense Subgraphs
Lovaszシータ関数、SVM、および高密度サブグラフの検索
In this paper we establish that the Lovász $\vartheta$ function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-$\vartheta$ graphs, on which Lovász $\vartheta$ function can be approximated well by a Support vector machine (SVM). We show that Erdös-Rényi random $G(n,p)$ graphs are SVM-$\vartheta$ graphs for $ \frac{\log^4 n}{n} \le p < 1 $. Even if we embed a large clique of size $\Theta\left(\sqrt{\frac{np}{1-p}}\right)$ in a $G(n,p)$ graph the resultant graph still remains a Lovász $\vartheta$ graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the $\vartheta$ function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.
この論文では、グラフ上のLovász $\vartheta$関数がカーネル学習問題として言い換えられることを確立します。SVM-$\vartheta$グラフの概念を導入し、このグラフ上でLovász $\vartheta$関数をサポート ベクター マシン(SVM)で適切に近似できます。Erdös-Rényiランダム$G(n,p)$グラフは、$ \frac{\log^4 n}{n} \le p < 1 $に対してSVM-$\vartheta$グラフであることを示します。サイズ$\Theta\left(\sqrt{\frac{np}{1-p}}\right)$の大きなクリークを$G(n,p)$グラフに埋め込んだとしても、結果として得られるグラフはLovász $\vartheta$グラフのままです。これは、ランダム グラフに埋め込まれた大きなクリークを回復するためのSVMベースのアルゴリズムを直ちに示唆します。$\vartheta$関数には、直交ラベル付けの概念が関連付けられています。ここでは、直交ラベル付けの考え方を複数のグラフに拡張する共通直交ラベル付けを導入します。これにより、複数のグラフで大きな共通の密なサブグラフを識別できる、マルチカーネル学習(MKL)ベースのソリューションを提案できます。植え付けられたクリークのケースと共通サブグラフ検出問題の両方で、提案されたソリューションは最先端のソリューションを桁違いに上回ります。
Comment on “Robustness and Regularization of Support Vector Machines” by H. Xu et al. (Journal of Machine Learning Research, vol. 10, pp. 1485-1510, 2009)
H. Xuらによる「Robustness and Regularization of Support Vector Machines」に対するコメント (Journal of Machine Learning Research, vol. 10, pp. 1485-1510, 2009)
This paper comments on the published work dealing with robustness and regularization of support vector machines (Journal of Machine Learning Research, Vol. 10, pp. 1485-1510, 2009) by H. Xu et al. They proposed a theorem to show that it is possible to relate robustness in the feature space and robustness in the sample space directly. In this paper, we propose a counter example that rejects their theorem.
この論文では、H. Xuら によるサポートベクターマシンのロバスト性と正則化に関する公開された研究(Journal of Machine Learning Research, Vol. 10, pp. 1485-1510, 2009)についてコメントしています。彼らは、特徴空間のロバスト性とサンプル空間のロバスト性を直接関連付けることができることを示す定理を提案しました。この論文では、彼らの定理を否定する反例を提案します。
Learning Theory Analysis for Association Rules and Sequential Event Prediction
アソシエーションルールと逐次イベント予測のための学習理論分析
We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce a problem for which rules are particularly natural, called âsequential event prediction.” In sequential event prediction, events in a sequence are revealed one by one, and the goal is to determine which event will next be revealed. The training set is a collection of past sequences of events. An example application is to predict which item will next be placed into a customer’s online shopping cart, given his/her past purchases. In the context of this problem, algorithms based on association rules have distinct advantages over classical statistical and machine learning methods: they look at correlations based on subsets of co-occurring past events (items a and b imply item c), they can be applied to the sequential event prediction problem in a natural way, they can potentially handle the âcold start” problem where the training set is small, and they yield interpretable predictions. In this work, we present two algorithms that incorporate association rules. These algorithms can be used both for sequential event prediction and for supervised classification, and they are simple enough that they can possibly be understood by users, customers, patients, managers, etc. We provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an âadjusted confidence” measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis.
私たちは、相関ルールに基づく予測アルゴリズムの理論的分析を紹介します。この分析の一環として、ルールが特に自然な「シーケンシャル イベント予測」と呼ばれる問題を紹介します。シーケンシャル イベント予測では、シーケンス内のイベントが1つずつ明らかにされ、次にどのイベントが明らかになるかを判断することが目標です。トレーニング セットは、過去のイベント シーケンスのコレクションです。アプリケーションの例としては、顧客の過去の購入履歴に基づいて、次にどのアイテムが顧客のオンライン ショッピング カートに追加されるかを予測することが挙げられます。この問題のコンテキストでは、相関ルールに基づくアルゴリズムには、従来の統計手法や機械学習手法に比べて明確な利点があります。つまり、同時発生する過去のイベントのサブセットに基づいて相関関係を調べ(アイテムaとbはアイテムcを意味する)、シーケンシャル イベント予測の問題に自然な方法で適用でき、トレーニング セットが小さい「コールド スタート」問題を処理できる可能性があり、解釈可能な予測を生成します。この研究では、相関ルールを組み込んだ2つのアルゴリズムを紹介します。これらのアルゴリズムは、連続イベント予測と教師あり分類の両方に使用でき、ユーザー、顧客、患者、管理者などが理解できるほど単純です。統計学習理論のアルゴリズム安定性分析に基づいて、これらのアルゴリズムの一般化を保証します。相関ルール マイニングでよく使用される厳密な最小サポートしきい値について説明し、厳密な最小サポートよりも優れた弱い最小サポート条件を提供する「調整された信頼度」尺度を紹介します。この論文では、統計学習理論、相関ルール マイニング、ベイズ分析のアイデアをまとめています。
Consistent Selection of Tuning Parameters via Variable Selection Stability
変数選択安定性によるチューニングパラメータの一貫した選択
Penalized regression models are popularly used in high- dimensional data analysis to conduct variable selection and model fitting simultaneously. Whereas success has been widely reported in literature, their performances largely depend on the tuning parameters that balance the trade-off between model fitting and model sparsity. Existing tuning criteria mainly follow the route of minimizing the estimated prediction error or maximizing the posterior model probability, such as cross validation, AIC and BIC. This article introduces a general tuning parameter selection criterion based on variable selection stability. The key idea is to select the tuning parameters so that the resultant penalized regression model is stable in variable selection. The asymptotic selection consistency is established for both fixed and diverging dimensions. Its effectiveness is also demonstrated in a variety of simulated examples as well as an application to the prostate cancer data.
ペナルティ付き回帰モデルは、変数の選択とモデルのフィッティングを同時に行うために、高次元データ分析で一般的に使用されます。成功は文献で広く報告されていますが、そのパフォーマンスは、モデルの適合とモデルのスパース性の間のトレードオフのバランスをとる調整パラメーターに大きく依存します。既存の調整基準は、主に、クロス検証、AIC、BICなど、推定された予測誤差を最小化するか、事後モデルの確率を最大化するルートをたどります。この記事では、変数選択の安定性に基づく一般的な調整パラメーター選択基準を紹介します。重要な考え方は、結果として得られるペナルティ付き回帰モデルが変数選択で安定するように、調整パラメーターを選択することです。漸近選択の一貫性は、固定寸法と発散寸法の両方で確立されます。その有効性は、さまざまなシミュレーション例や前立腺がんデータへの応用でも実証されています。
Sparse Matrix Inversion with Scaled Lasso
Scaled Lassoによるスパース行列反転
We propose a new method of learning a sparse nonnegative- definite target matrix. Our primary example of the target matrix is the inverse of a population covariance or correlation matrix. The algorithm first estimates each column of the target matrix by the scaled Lasso and then adjusts the matrix estimator to be symmetric. The penalty level of the scaled Lasso for each column is completely determined by data via convex minimization, without using cross-validation. We prove that this scaled Lasso method guarantees the fastest proven rate of convergence in the spectrum norm under conditions of weaker form than those in the existing analyses of other $\ell_1$ regularized algorithms, and has faster guaranteed rate of convergence when the ratio of the $\ell_1$ and spectrum norms of the target inverse matrix diverges to infinity. A simulation study demonstrates the computational feasibility and superb performance of the proposed method. Our analysis also provides new performance bounds for the Lasso and scaled Lasso to guarantee higher concentration of the error at a smaller threshold level than previous analyses, and to allow the use of the union bound in column-by-column applications of the scaled Lasso without an adjustment of the penalty level. In addition, the least squares estimation after the scaled Lasso selection is considered and proven to guarantee performance bounds similar to that of the scaled Lasso.
私たちは、スパースな非負定値ターゲット行列を学習する新しい方法を提案します。ターゲット行列の主な例は、母集団共分散または相関行列の逆行列です。アルゴリズムは、最初にスケールされたLassoによってターゲット行列の各列を推定し、次に行列推定量が対称になるように調整します。各列のスケールされたLassoのペナルティ レベルは、交差検証を使用せずに、凸最小化を介してデータによって完全に決定されます。私たちは、このスケールされたLasso法が、他の$\ell_1$正則化アルゴリズムの既存の分析よりも弱い形式の条件下で、スペクトル ノルムの収束の最も速い実証済み速度を保証し、ターゲット逆行列の$\ell_1$とスペクトル ノルムの比が無限大に発散する場合に、より速い収束速度を保証することを証明します。シミュレーション スタディは、提案された方法の計算上の実現可能性と優れたパフォーマンスを実証します。私たちの分析では、LassoとスケールLassoの新しいパフォーマンス境界も提供され、以前の分析よりも小さいしきい値レベルでエラーの集中度が高くなることが保証され、ペナルティ レベルの調整なしでスケールLassoの列ごとの適用で結合境界を使用できるようになります。さらに、スケールLasso選択後の最小二乗推定が考慮され、スケールLassoと同様のパフォーマンス境界を保証することが証明されています。
PC Algorithm for Nonparanormal Graphical Models
非超常グラフィックモデルのためのPCアルゴリズム
The PC algorithm uses conditional independence tests for model selection in graphical modeling with acyclic directed graphs. In Gaussian models, tests of conditional independence are typically based on Pearson correlations, and high-dimensional consistency results have been obtained for the PC algorithm in this setting. Analyzing the error propagation from marginal to partial correlations, we prove that high-dimensional consistency carries over to a broader class of Gaussian copula or nonparanormal models when using rank-based measures of correlation. For graph sequences with bounded degree, our consistency result is as strong as prior Gaussian results. In simulations, the `Rank PC’ algorithm works as well as the `Pearson PC’ algorithm for normal data and considerably better for non-normal data, all the while incurring a negligible increase of computation time. While our interest is in the PC algorithm, the presented analysis of error propagation could be applied to other algorithms that test the vanishing of low-order partial correlations.
PCアルゴリズムは、非巡回有向グラフを使用したグラフィカル モデリングにおけるモデル選択に条件付き独立性検定を使用します。ガウス モデルでは、条件付き独立性の検定は通常ピアソン相関に基づいており、この設定でPCアルゴリズムの高次元一貫性結果が得られています。限界相関から部分相関への誤差伝播を分析すると、相関のランク ベースの尺度を使用する場合、高次元一貫性がより広範なガウス コピュラまたは非超常モデルのクラスに引き継がれることが証明されます。次数が制限されたグラフ シーケンスの場合、一貫性の結果は以前のガウスの結果と同じくらい強力です。シミュレーションでは、`Rank PC’アルゴリズムは、通常のデータでは`Pearson PC’アルゴリズムと同様に機能し、非通常のデータでは大幅に優れていますが、計算時間の増加はごくわずかです。私たちの関心はPCアルゴリズムにありますが、提示された誤差伝播の分析は、低次の部分相関の消失をテストする他のアルゴリズムにも適用できます。
Communication-Efficient Algorithms for Statistical Optimization
統計的最適化のための通信効率の良いアルゴリズム
We analyze two communication-efficient algorithms for distributed optimization in statistical settings involving large-scale data sets. The first algorithm is a standard averaging method that distributes the $N$ data samples evenly to $m$ machines, performs separate minimization on each subset, and then averages the estimates. We provide a sharp analysis of this average mixture algorithm, showing that under a reasonable set of conditions, the combined parameter achieves mean-squared error (MSE) that decays as $O(N^{-1}+(N/m)^{-2})$. Whenever $m \le \sqrt{N}$, this guarantee matches the best possible rate achievable by a centralized algorithm having access to all $N$ samples. The second algorithm is a novel method, based on an appropriate form of bootstrap subsampling. Requiring only a single round of communication, it has mean-squared error that decays as $O(N^{-1}+(N/m)^{-3})$, and so is more robust to the amount of parallelization. In addition, we show that a stochastic gradient-based method attains mean- squared error decaying as $O(N^{-1}+(N/m)^{-3/2})$, easing computation at the expense of a potentially slower MSE rate. We also provide an experimental evaluation of our methods, investigating their performance both on simulated data and on a large-scale regression problem from the internet search domain. In particular, we show that our methods can be used to efficiently solve an advertisement prediction problem from the Chinese SoSo Search Engine, which involves logistic regression with $N \approx 2.4 \times 10^8$ samples and $d \approx 740,\!000$ covariates.
私たちは、大規模なデータセットを含む統計設定における分散最適化のための、通信効率の高い2つのアルゴリズムを分析します。最初のアルゴリズムは、標準的な平均化方法で、N個のデータ サンプルをm個のマシンに均等に分散し、各サブセットで個別に最小化を実行してから、推定値を平均します。この平均混合アルゴリズムを詳細に分析し、妥当な条件セットの下では、結合されたパラメーターが平均二乗誤差(MSE)を達成し、それがO(N^{-1}+(N/m)^{-2})として減少することを示します。$m \le \sqrt{N}$のときはいつでも、この保証は、N個のサンプルすべてにアクセスできる集中型アルゴリズムによって達成可能な最高のレートと一致します。2番目のアルゴリズムは、適切な形式のブートストラップ サブサンプリングに基づく新しい方法です。通信は1ラウンドのみで、平均二乗誤差は$O(N^{-1}+(N/m)^{-3})$で減少するため、並列化の量に対してより堅牢です。さらに、確率的勾配ベースの方法では平均二乗誤差が$O(N^{-1}+(N/m)^{-3/2})$で減少し、潜在的に遅いMSEレートを犠牲にして計算が楽になることを示します。また、シミュレーション データとインターネット検索ドメインからの大規模回帰問題の両方でのパフォーマンスを調査して、手法の実験的評価も提供します。特に、中国のSoSo検索エンジンからの広告予測問題を効率的に解決するために、手法を使用できることを示します。この問題には、$N \approx 2.4 \times 10^8$サンプルと$d \approx 740,\!000$共変量を含むロジスティック回帰が含まれます。
Fast MCMC Sampling for Markov Jump Processes and Extensions
マルコフジャンプ過程と拡張のための高速MCMCサンプリング
Markov jump processes (or continuous-time Markov chains) are a simple and important class of continuous-time dynamical systems. In this paper, we tackle the problem of simulating from the posterior distribution over paths in these models, given partial and noisy observations. Our approach is an auxiliary variable Gibbs sampler, and is based on the idea of uniformization. This sets up a Markov chain over paths by alternately sampling a finite set of virtual jump times given the current path, and then sampling a new path given the set of extant and virtual jump times. The first step involves simulating a piecewise-constant inhomogeneous Poisson process, while for the second, we use a standard hidden Markov model forward filtering-backward sampling algorithm. Our method is exact and does not involve approximations like time- discretization. We demonstrate how our sampler extends naturally to MJP-based models like Markov-modulated Poisson processes and continuous-time Bayesian networks, and show significant computational benefits over state-of-the-art MCMC samplers for these models.
マルコフジャンプ過程（または連続時間マルコフ連鎖）は、連続時間動的システムの単純かつ重要なクラスです。この論文では、部分的かつノイズの多い観測を与えられた場合、これらのモデルのパスの事後分布からシミュレーションを行う問題に取り組みます。私たちのアプローチは補助変数ギブスサンプラーであり、均一化の考え方に基づいています。これは、現在のパスが与えられた場合に仮想ジャンプ時間の有限セットを交互にサンプリングし、次に、実在するジャンプ時間および仮想ジャンプ時間のセットが与えられた場合に新しいパスをサンプリングすることにより、パスのマルコフ連鎖を設定します。最初のステップでは、区分的に一定の不均質なポアソン過程をシミュレーションし、2番目のステップでは、標準的な隠れマルコフモデルの順方向フィルタリング-逆方向サンプリングアルゴリズムを使用します。私たちの方法は正確であり、時間離散化などの近似を伴いません。私たちのサンプラーが、マルコフ変調ポアソン過程や連続時間ベイジアンネットワークなどのMJPベースのモデルに自然に拡張される方法を示し、これらのモデルに対する最先端のMCMCサンプラーに比べて大幅な計算上の利点があることを示します。
Multivariate Convex Regression with Adaptive Partitioning
適応分割による多変量凸回帰
We propose a new, nonparametric method for multivariate regression subject to convexity or concavity constraints on the response function. Convexity constraints are common in economics, statistics, operations research, financial engineering and optimization, but there is currently no multivariate method that is stable and computationally feasible for more than a few thousand observations. We introduce convex adaptive partitioning (CAP), which creates a globally convex regression model from locally linear estimates fit on adaptively selected covariate partitions. CAP is a computationally efficient, consistent method for convex regression. We demonstrate empirical performance by comparing the performance of CAP to other shape-constrained and unconstrained regression methods for predicting weekly wages and value function approximation for pricing American basket options.
私たちは、応答関数の凸性または凹面制約の対象となる多変量回帰のための新しいノンパラメトリック法を提案します。凸性制約は、経済学、統計学、オペレーションズ・リサーチ、金融工学、最適化では一般的ですが、現在、数千を超える観測値に対して安定して計算可能な多変量法はありません。適応的に選択された共変量分割に当てはめられた局所線形推定値からグローバル凸回帰モデルを作成する凸適応分割(CAP)を導入します。CAPは、凸回帰の計算効率が高く、一貫性のある方法です。CAPのパフォーマンスを、週給を予測するための他の形状制約付きおよび制約なし回帰方法と比較し、アメリカのバスケットオプションを価格設定するための価値関数近似と比較することにより、経験的なパフォーマンスを示します。
Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising
反事実的推論と学習システム:計算広告の例
This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select the changes that would have improved the system performance. This work is illustrated by experiments on the ad placement system associated with the Bing search engine.
この研究では、因果推論を活用して、環境と相互作用する複雑な学習システムの動作を理解し、システムへの変更の結果を予測する方法を示します。このような予測により、人間とアルゴリズムの両方が、システムのパフォーマンスを向上させる変更を選択できます。この作業は、Bing検索エンジンに関連付けられた広告配置システムでの実験によって示されています。
GURLS: A Least Squares Library for Supervised Learning
GURLS:教師あり学習のための最小二乗法ライブラリ
We present GURLS, a least squares, modular, easy-to-extend software library for efficient supervised learning. GURLS is targeted to machine learning practitioners, as well as non- specialists. It offers a number state-of-the-art training strategies for medium and large-scale learning, and routines for efficient model selection. The library is particularly well suited for multi-output problems (multi-category/multi-label). GURLS is currently available in two independent implementations: Matlab and C++. It takes advantage of the favorable properties of regularized least squares algorithm to exploit advanced tools in linear algebra. Routines to handle computations with very large matrices by means of memory-mapped storage and distributed task execution are available. The package is distributed under the BSD license and is available for download at https://github.com/LCSL/GURLS.
私たちは、GURLSは、効率的な教師あり学習のための最小二乗法、モジュール式、拡張が容易なソフトウェアライブラリです。GURLSは、機械学習の実践者だけでなく、非専門家も対象としています。中規模および大規模の学習のための最先端のトレーニング戦略と、効率的なモデル選択のためのルーチンを多数提供しています。このライブラリは、マルチ出力問題(マルチカテゴリ/マルチラベル)に特に適しています。GURLSは現在、MatlabとC ++の2つの独立した実装で利用できます。正則化最小二乗アルゴリズムの好ましい特性を利用して、線形代数の高度なツールを活用します。メモリマップドストレージと分散タスク実行によって非常に大きな行列の計算を処理するルーチンが利用可能です。パッケージはBSDライセンスの下で配布されており、https://github.com/LCSL/GURLSからダウンロードできます。
Using Symmetry and Evolutionary Search to Minimize Sorting Networks
対称性と進化的探索を使用してソートネットワークを最小化する
The marginal maximum a posteriori probability (MAP) estimation problem, which calculates the mode of the marginal posterior distribution of a subset of variables with the remaining variables marginalized, is an important inference problem in many models, such as those with hidden variables or uncertain parameters. Unfortunately, marginal MAP can be NP-hard even on trees, and has attracted less attention in the literature compared to the joint MAP (maximization) and marginalization problems. We derive a general dual representation for marginal MAP that naturally integrates the marginalization and maximization operations into a joint variational optimization problem, making it possible to easily extend most or all variational-based algorithms to marginal MAP. In particular, we derive a set of ‘mixed-product’ message passing algorithms for marginal MAP, whose form is a hybrid of max-product, sum-product and a novel ‘argmax-product’ message updates. We also derive a class of convergent algorithms based on proximal point methods, including one that transforms the marginal MAP problem into a sequence of standard marginalization problems. Theoretically, we provide guarantees under which our algorithms give globally or locally optimal solutions, and provide novel upper bounds on the optimal objectives. Empirically, we demonstrate that our algorithms significantly outperform the existing approaches, including a state-of-the-art algorithm based on local search methods.
周辺最大事後確率(MAP)推定問題は、変数のサブセットの周辺事後分布のモードを計算し、残りの変数を周辺化するものですが、隠れた変数や不確実なパラメータを持つモデルなど、多くのモデルで重要な推論問題です。残念ながら、周辺MAPはツリー上でもNP困難になる可能性があり、文献ではMAP (最大化)と周辺化の結合問題に比べてあまり注目されていません。私たちは、周辺化と最大化の操作を自然に統合して結合変分最適化問題にする、周辺MAPの一般的なデュアル表現を導出します。これにより、ほとんどまたはすべての変分ベースのアルゴリズムを周辺MAPに簡単に拡張できます。特に、私たちは周辺MAPの「混合積」メッセージ パッシング アルゴリズムのセットを導出します。これは、max-product、sum-product、および新しい「argmax-product」メッセージ更新を組み合わせた形式です。また、近点法に基づく収束アルゴリズムのクラスも導出します。これには、限界MAP問題を一連の標準的な限界化問題に変換するアルゴリズムも含まれます。理論的には、アルゴリズムがグローバルまたはローカルに最適なソリューションを提供することを保証し、最適な目標に対する新しい上限を提供します。経験的には、私たちのアルゴリズムが、ローカル検索法に基づく最先端のアルゴリズムを含む既存のアプローチを大幅に上回ることを実証します。
Divvy: Fast and Intuitive Exploratory Data Analysis
Divvy:高速で直感的な探索的データ分析
Divvy is an application for applying unsupervised machine learning techniques (clustering and dimensionality reduction) to the data analysis process. Divvy provides a novel UI that allows researchers to tighten the action-perception loop of changing algorithm parameters and seeing a visualization of the result. Machine learning researchers can use Divvy to publish easy to use reference implementations of their algorithms, which helps the machine learning field have a greater impact on research practices elsewhere.
Divvyは、教師なし機械学習手法(クラスタリングと次元削減)をデータ分析プロセスに適用するためのアプリケーションです。Divvyは、研究者がアルゴリズムパラメータを変更し、結果を視覚化するというアクションと知覚のループを強化できる新しいUIを提供します。機械学習の研究者は、Divvyを使用して、アルゴリズムの使いやすいリファレンス実装を公開できるため、機械学習分野が他の場所での研究実践に大きな影響を与えることができます。
QuantMiner for Mining Quantitative Association Rules
マイニングのためのQuantMiner定量的アソシエーションルール
In this paper, we propose QuantMiner, a mining quantitative association rules system. This system is based on a genetic algorithm that dynamically discovers âgoodâ intervals in association rules by optimizing both the support and the confidence. The experiments on real and artificial databases have shown the usefulness of QuantMiner as an interactive, exploratory data mining tool.
この論文では、マイニングの定量的アソシエーションルールシステムであるQuantMinerを提案します。このシステムは、サポートと信頼性の両方を最適化することにより、アソシエーションルールの「適切な」間隔を動的に検出する遺伝的アルゴリズムに基づいています。実際のデータベースと人工データベースでの実験では、QuantMinerがインタラクティブで探索的なデータマイニングツールとして有用であることが示されています。
Large-scale SVD and Manifold Learning
大規模SVDと多様体学習
This paper examines the efficacy of sampling-based low-rank approximation techniques when applied to large dense kernel matrices. We analyze two common approximate singular value decomposition techniques, namely the Nystrom and Column sampling methods. We present a theoretical comparison between these two methods, provide novel insights regarding their suitability for various tasks and present experimental results that support our theory. Our results illustrate the relative strengths of each method. We next examine the performance of these two techniques on the large-scale task of extracting low-dimensional manifold structure given millions of high-dimensional face images. We address the computational challenges of non-linear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about $18$ million nodes and $65$ million edges. We present extensive experiments on learning low- dimensional embeddings for two large face data sets: CMU-PIE ($35$ thousand faces) and a web data set ($18$ million faces). Our comparisons show that the Nystrom approximation is superior to the Column sampling method for this task. Furthermore, approximate Isomap tends to perform better than Laplacian Eigenmaps on both clustering and classification with the labeled CMU-PIE data set.
この論文では、大規模な密カーネル行列に適用した場合のサンプリングベースの低ランク近似手法の有効性を検証します。2つの一般的な近似特異値分解手法、つまりNystromサンプリング法と列サンプリング法を分析します。これら2つの手法の理論的比較を示し、さまざまなタスクへの適合性に関する新しい洞察を提供し、理論を裏付ける実験結果を示します。結果は、各手法の相対的な強みを示しています。次に、数百万の高次元顔画像から低次元多様体構造を抽出するという大規模なタスクで、これら2つの手法のパフォーマンスを調べます。約1,800万のノードと6,500万のエッジを含むグラフを使用して、IsomapとLaplacian Eigenmapsによる非線形次元削減の計算上の課題に対処します。2つの大規模な顔データセット、CMU-PIE (35,000の顔)とWebデータセット(1,800万の顔)の低次元埋め込みを学習する広範な実験を示します。比較の結果、このタスクではNystrom近似法が列サンプリング法よりも優れていることがわかりました。さらに、ラベル付きCMU-PIEデータ セットを使用したクラスタリングと分類の両方において、近似IsomapはLaplacian Eigenmapよりもパフォーマンスが優れている傾向があります。
Algorithms and Hardness Results for Parallel Large Margin Learning
並列大マージン学習のためのアルゴリズムと硬度結果
We consider the problem of learning an unknown large-margin halfspace in the context of parallel computation, giving both positive and negative results. As our main positive result, we give a parallel algorithm for learning a large-margin halfspace, based on an algorithm of Nesterov’s that performs gradient descent with a momentum term. We show that this algorithm can learn an unknown $\gamma$-margin halfspace over $n$ dimensions using $n \cdot \text{poly}(1/\gamma)$ processors and running in time $\tilde{O}(1/\gamma)+O(\log n)$. In contrast, naive parallel algorithms that learn a $\gamma$-margin halfspace in time that depends polylogarithmically on $n$ have an inverse quadratic running time dependence on the margin parameter $\gamma$. Our negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We prove that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized. More precisely, we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within a single boosting stage, this ability does not reduce the overall number of successive stages of boosting needed for learning by even a single stage. Our proof is information-theoretic and does not rely on unproven assumptions.
私たちは、並列計算の文脈で未知の大マージン半空間を学習する問題を考察し、肯定的な結果と否定的な結果の両方を与えています。主な肯定的な結果として、運動量項で勾配降下法を実行するネステロフのアルゴリズムに基づいて、大マージン半空間を学習する並列アルゴリズムを与える。このアルゴリズムは、$n \cdot \text{poly}(1/\gamma)$プロセッサを使用し、$\tilde{O}(1/\gamma)+O(\log n)$の時間で実行して、$n$次元上の未知の$\gamma$マージン半空間を学習できることを示す。対照的に、$n$に多重対数的に依存する時間で$\gamma$マージン半空間を学習する単純な並列アルゴリズムは、マージンパラメータ$\gamma$に逆の二次実行時間依存性を持つ。否定的な結果は、大マージン半空間を学習するための標準的なアプローチであるブースティングを扱っています。私たちは、弱い学習アルゴリズムがブースターによって呼び出されるオラクルとして提供される元のPACフレームワークでは、ブースティングを並列化できないことを証明します。より正確には、アルゴリズムが単一のブースティング ステージ内で弱い学習者を複数回並列に呼び出すことが許可されている場合、この機能によって学習に必要なブースティングの連続ステージの総数が1ステージも削減されないことを示します。我々の証明は情報理論に基づくものであり、証明されていない仮定に依存しません。
Stationary-Sparse Causality Network Learning
定常-スパース因果ネットワーク学習
Recently, researchers have proposed penalized maximum likelihood to identify network topology underlying a dynamical system modeled by multivariate time series. The time series of interest are assumed to be stationary, but this restriction is never taken into consideration by existing estimation methods. Moreover, practical problems of interest may have ultra-high dimensionality and obvious node collinearity. In addition, none of the available algorithms provides a probabilistic measure of the uncertainty for the obtained network topology which is informative in reliable network identification. The main purpose of this paper is to tackle these challenging issues. We propose the $\mathbf{S}^2$ learning framework, which stands for stationary- sparse network learning. We propose a novel algorithm referred to as the Berhu iterative sparsity pursuit with stationarity (BISPS), where the Berhu regularization can improve the Lasso in detection and estimation. The algorithm is extremely easy to implement, efficient in computation and has a theoretical guarantee to converge to a global optimum. We also incorporate a screening technique into BISPS to tackle ultra- high dimensional problems and enhance computational efficiency. Furthermore, a stationary bootstrap technique is applied to provide connection occurring frequency for reliable topology learning. Experiments show that our method can achieve stationary and sparse causality network learning and is scalable for high-dimensional problems.
最近、研究者らは、多変量時系列によってモデル化された動的システムの基礎となるネットワーク トポロジを識別するために、ペナルティ付き最大尤度を提案しました。関心のある時系列は定常であると想定されていますが、この制限は既存の推定方法では考慮されていません。さらに、関心のある実際の問題には、超高次元性と明らかなノード共線性がある場合があります。さらに、利用可能なアルゴリズムのいずれも、信頼性の高いネットワーク識別に役立つ、取得されたネットワーク トポロジの不確実性の確率的尺度を提供していません。この論文の主な目的は、これらの困難な問題に取り組むことです。定常スパース ネットワーク学習を表す$\mathbf{S}^2$学習フレームワークを提案します。定常性を伴うBerhu反復スパース追求(BISPS)と呼ばれる新しいアルゴリズムを提案します。このアルゴリズムでは、Berhu正則化によってLassoの検出と推定を改善できます。このアルゴリズムは実装が非常に簡単で、計算が効率的で、理論的にはグローバル最適値に収束することが保証されています。また、超高次元の問題に取り組み、計算効率を高めるために、スクリーニング手法をBISPSに組み込みます。さらに、定常ブートストラップ技術を適用して、信頼性の高いトポロジー学習のための接続発生頻度を提供します。実験では、この方法が定常かつスパースな因果ネットワーク学習を実現でき、高次元の問題に対してスケーラブルであることが示されています。
Experiment Selection for Causal Discovery
因果関係の発見のための実験選択
Randomized controlled experiments are often described as the most reliable tool available to scientists for discovering causal relationships among quantities of interest. However, it is often unclear how many and which different experiments are needed to identify the full (possibly cyclic) causal structure among some given (possibly causally insufficient) set of variables. Recent results in the causal discovery literature have explored various identifiability criteria that depend on the assumptions one is able to make about the underlying causal process, but these criteria are not directly constructive for selecting the optimal set of experiments. Fortunately, many of the needed constructions already exist in the combinatorics literature, albeit under terminology which is unfamiliar to most of the causal discovery community. In this paper we translate the theoretical results and apply them to the concrete problem of experiment selection. For a variety of settings we give explicit constructions of the optimal set of experiments and adapt some of the general combinatorics results to answer questions relating to the problem of experiment selection.
ランダム化比較実験は、科学者が関心のある量の間の因果関係を発見するために利用できる最も信頼性の高いツールであるとよく言われます。しかし、いくつかの与えられた（おそらく因果関係が不十分な）変数セットの間の完全な（おそらく循環的な）因果構造を識別するために、いくつの、どのような異なる実験が必要かは、しばしば不明です。因果発見の文献における最近の結果では、基礎となる因果プロセスについて行うことができる仮定に依存するさまざまな識別可能性基準が検討されていますが、これらの基準は、最適な実験セットを選択するための直接的な構成ではありません。幸いなことに、必要な構成の多くは、因果発見コミュニティのほとんどにとって馴染みのない用語ではありますが、組み合わせ論の文献にすでに存在しています。この論文では、理論的結果を翻訳し、実験選択の具体的な問題に適用します。さまざまな設定について、最適な実験セットの明示的な構成を示し、一般的な組み合わせ論の結果の一部を適応させて、実験選択の問題に関連する質問に答えます。
A Plug-in Approach to Neyman-Pearson Classification
ネイマン・ピアソン分類へのプラグインアプローチ
The Neyman-Pearson (NP) paradigm in binary classification treats type I and type II errors with different priorities. It seeks classifiers that minimize type II error, subject to a type I error constraint under a user specified level $\alpha$. In this paper, plug-in classifiers are developed under the NP paradigm. Based on the fundamental Neyman-Pearson Lemma, we propose two related plug-in classifiers which amount to thresholding respectively the class conditional density ratio and the regression function. These two classifiers handle different sampling schemes. This work focuses on theoretical properties of the proposed classifiers; in particular, we derive oracle inequalities that can be viewed as finite sample versions of risk bounds. NP classification can be used to address anomaly detection problems, where asymmetry in errors is an intrinsic property. As opposed to a common practice in anomaly detection that consists of thresholding normal class density, our approach does not assume a specific form for anomaly distributions. Such consideration is particularly necessary when the anomaly class density is far from uniformly distributed.
バイナリ分類におけるNeyman-Pearson (NP)パラダイムは、タイプIおよびタイプIIのエラーを異なる優先順位で扱います。これは、ユーザー指定のレベル$\alpha$の下でタイプIエラー制約を条件として、タイプIIエラーを最小化する分類器を求めます。この論文では、NPパラダイムに基づいてプラグイン分類器を開発します。基本的なNeyman-Pearsonの補題に基づいて、クラス条件付き密度比と回帰関数をそれぞれしきい値化する2つの関連するプラグイン分類器を提案します。これら2つの分類器は、異なるサンプリング スキームを処理します。この作業では、提案された分類器の理論的特性に焦点を当てています。特に、リスク境界の有限サンプル バージョンと見なすことができるオラクル不等式を導出します。NP分類は、エラーの非対称性が本質的な特性である異常検出の問題に対処するために使用できます。通常のクラス密度をしきい値化する異常検出の一般的な方法とは対照的に、私たちのアプローチは異常分布の特定の形式を想定しません。このような考慮は、異常クラスの密度が均一に分布していない場合、特に必要です。
Multi-Stage Multi-Task Feature Learning
マルチステージマルチタスク機能学習
Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated as a convex sparse regularization problem, which is usually suboptimal, due to its looseness for approximating an $\ell_0$-type regularizer. In this paper, we propose a non-convex formulation for multi-task sparse feature learning based on a novel non-convex regularizer. To solve the non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature Learning (MSMTFL) algorithm; we also provide intuitive interpretations, detailed convergence and reproducibility analysis for the proposed algorithm. Moreover, we present a detailed theoretical analysis showing that MSMTFL achieves a better parameter estimation error bound than the convex formulation. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of MSMTFL in comparison with the state of the art multi-task sparse feature learning algorithms.
マルチタスクスパース特徴学習は、タスク間の共有特徴を利用することで一般化パフォーマンスを向上させることを目的としています。これは、コンピュータービジョンや生物医学情報学を含む多くのアプリケーションにうまく適用されています。既存のマルチタスクスパース特徴学習アルゴリズムのほとんどは、凸スパース正則化問題として定式化されていますが、$\ell_0$型正則化を近似するための緩さのため、通常は最適ではありません。この論文では、新しい非凸正則化に基づくマルチタスクスパース特徴学習の非凸定式化を提案します。非凸最適化問題を解決するために、マルチステージマルチタスク特徴学習（MSMTFL）アルゴリズムを提案します。また、提案アルゴリズムの直感的な解釈、詳細な収束および再現性分析も提供します。さらに、MSMTFLが凸定式化よりも優れたパラメータ推定誤差境界を達成することを示す詳細な理論分析を示します。合成データセットと現実世界のデータセットの両方に関する実証的研究により、最先端のマルチタスク スパース特徴学習アルゴリズムと比較したMSMTFLの有効性が実証されています。
Parallel Vector Field Embedding
平行ベクトル場埋め込み
We propose a novel local isometry based dimensionality reduction method from the perspective of vector fields, which is called parallel vector field embedding (PFE). We first give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector fields and isometry. The problem of finding an isometry turns out to be equivalent to finding orthonormal parallel vector fields on the data manifold. Therefore, we first find orthonormal parallel vector fields by solving a variational problem on the manifold. Then each embedding function can be obtained by requiring its gradient field to be as close to the corresponding parallel vector field as possible. Theoretical results show that our method can precisely recover the manifold if it is isometric to a connected open subset of Euclidean space. Both synthetic and real data examples demonstrate the effectiveness of our method even if there is heavy noise and high curvature.
私たちは、ベクトル場の観点から、新しい局所アイソメトリに基づく次元削減法、これを並列ベクトル場埋め込み(PFE)と呼びます。まず、平行ベクトル場と等速性との間の本質的な関係を示すために、局所等量計と大域等分性について考察します。アイソメトリを見つける問題は、データ多様体上の正規直交平行ベクトル場を見つけることと同等であることがわかります。したがって、まず、多様体上の変分問題を解くことにより、正規直交平行ベクトル場を見つけます。次に、各埋め込み関数は、その勾配フィールドを対応する平行ベクトル場にできるだけ近づけるように要求することで取得できます。理論的な結果は、私たちの方法がユークリッド空間の接続された開部分集合に等角である場合、多様体を正確に回復できることを示しています。合成データの例と実データの両方の例は、激しいノイズと高い曲率がある場合でも、私たちの方法の有効性を示しています。
A Near-Optimal Algorithm for Differentially-Private Principal Components
微分プライベート主成分に対する最適に近いアルゴリズム
The principal components analysis (PCA) algorithm is a standard tool for identifying good low-dimensional approximations to high-dimensional data. Many data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We show that the sample complexity of the proposed method differs from the existing procedure in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling. We furthermore illustrate our results, showing that on real data there is a large performance gap between the existing method and our method.
主成分分析(PCA)アルゴリズムは、高次元データに対する適切な低次元近似を特定するための標準ツールです。関心のある多くのデータセットには、個人に関する個人情報や機密情報が含まれています。このようなデータを操作するアルゴリズムは、出力を公開する際のプライバシーリスクに敏感である必要があります。差分プライバシーは、プライバシーとこれらの出力の有用性とのトレードオフを開発するためのフレームワークです。この論文では、PCAへの微分プライベート近似の理論と経験的パフォーマンスを調査し、出力の有用性を明示的に最適化する新しい方法を提案します。提案手法のサンプル複雑度は、データ次元でのスケーリングにおいて既存の手順とは異なること、およびこのスケーリングに関して私たちの方法がほぼ最適であることを示します。さらに、実際のデータでは、既存の方法と私たちの方法との間に大きなパフォーマンスギャップがあることを示す結果を示します。
The CAM Software for Nonnegative Blind Source Separation in R-Java
R-Javaにおけるノンネガティブブラインドソース分離のためのCAMソフトウェア
We describe a R-Java CAM (convex analysis of mixtures) package that provides comprehensive analytic functions and a graphic user interface (GUI) for blindly separating mixed nonnegative sources. This open-source multiplatform software implements recent and classic algorithms in the literature including Chan et al. (2008), Wang et al. (2010), Chen et al. (2011a) and Chen et al. (2011b). The CAM package offers several attractive features: (1) instead of using proprietary MATLAB, its analytic functions are written in R, which makes the codes more portable and easier to modify; (2) besides producing and plotting results in R, it also provides a Java GUI for automatic progress update and convenient visual monitoring; (3) multi-thread interactions between the R and Java modules are driven and integrated by a Java GUI, assuring that the whole CAM software runs responsively; (4) the package offers a simple mechanism to allow others to plug-in additional R-functions.
私たちは、R-Java CAM(混合物の凸解析)パッケージは、包括的な分析機能と、混合した非負のソースを盲目的に分離するためのグラフィックユーザーインターフェース(GUI)を提供します。このオープンソースのマルチプラットフォームソフトウェアは、Chanら(2008)、Wangら(2010)、Chenら(2011a)、Chenら(2011b)などの文献にある最近のアルゴリズムと古典的なアルゴリズムを実装しています。CAMパッケージは、いくつかの魅力的な機能を提供します:(1)独自のMATLABを使用する代わりに、その解析機能はRで記述されているため、コードの移植性が向上し、変更が容易になります。(2)Rで結果を生成してプロットするだけでなく、進行状況の自動更新と便利な視覚的監視のためのJava GUIも提供します。(3)RモジュールとJavaモジュール間のマルチスレッドインタラクションは、Java GUIによって駆動および統合され、CAMソフトウェア全体が応答して動作することを保証します。(4)このパッケージは、他の人が追加のR機能をプラグインできるようにするためのシンプルなメカニズムを提供します。
Perturbative Corrections for Approximate Inference in Gaussian Latent Variable Models
ガウス潜在変数モデルにおける近似推論のための摂動補正
Expectation Propagation (EP) provides a framework for approximate inference. When the model under consideration is over a latent Gaussian field, with the approximation being Gaussian, we show how these approximations can systematically be corrected. A perturbative expansion is made of the exact but intractable correction, and can be applied to the model’s partition function and other moments of interest. The correction is expressed over the higher-order cumulants which are neglected by EP’s local matching of moments. Through the expansion, we see that EP is correct to first order. By considering higher orders, corrections of increasing polynomial complexity can be applied to the approximation. The second order provides a correction in quadratic time, which we apply to an array of Gaussian process and Ising models. The corrections generalize to arbitrarily complex approximating families, which we illustrate on tree- structured Ising model approximations. Furthermore, they provide a polynomial-time assessment of the approximation error. We also provide both theoretical and practical insights on the exactness of the EP solution.
期待伝播(EP)は、近似推論のフレームワークを提供します。検討中のモデルが潜在ガウス場上にあり、近似がガウスである場合、これらの近似を体系的に修正する方法を示します。正確だが扱いにくい修正から摂動展開が行われ、モデルのパーティション関数やその他の関心のあるモーメントに適用できます。修正は、EPのモーメントのローカル マッチングによって無視される高次キュムラントで表現されます。展開により、EPが1次まで正しいことがわかります。高次を考慮することで、増加する多項式の複雑さの修正を近似に適用できます。2次では、2次時間での修正が提供され、これをガウス過程およびイジング モデルの配列に適用します。修正は、任意の複雑な近似ファミリに一般化され、ツリー構造のイジング モデル近似で示します。さらに、近似エラーの多項式時間評価を提供します。また、EPソリューションの正確性に関する理論的かつ実践的な洞察も提供します。
A Binary-Classification-Based Metric between Time-Series Distributions and Its Use in Statistical and Learning Problems
時系列分布間の二項分類に基づく計量と、統計問題と学習問題におけるその使用
A metric between time-series distributions is proposed that can be evaluated using binary classification methods, which were originally developed to work on i.i.d. data. It is shown how this metric can be used for solving statistical problems that are seemingly unrelated to classification and concern highly dependent time series. Specifically, the problems of time-series clustering, homogeneity testing and the three-sample problem are addressed. Universal consistency of the resulting algorithms is proven under most general assumptions. The theoretical results are illustrated with experiments on synthetic and real-world data.
もともとi.i.d.データに取り組むために開発された二項分類法を使用して評価できる時系列分布間のメトリックが提案されています。このメトリックを使用して、分類とは一見無関係で、依存度の高い時系列に関係する統計問題を解決する方法を示します。具体的には、時系列クラスタリング、均質性テスト、および3サンプルの問題が取り上げられます。結果として得られるアルゴリズムの普遍的な一貫性は、ほとんどの一般的な仮定の下で証明されています。理論的な結果は、合成データと実世界のデータに関する実験で示されています。
Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees
連続状態空間に対する信念伝播:量的保証による確率的メッセージパッシング
The sum-product or belief propagation (BP) algorithm is a widely used message-passing technique for computing approximate marginals in graphical models. We introduce a new technique, called stochastic orthogonal series message-passing (SOSMP), for computing the BP fixed point in models with continuous random variables. It is based on a deterministic approximation of the messages via orthogonal series basis expansion, and a stochastic estimation of the basis coefficients via Monte Carlo techniques and damped updates. We prove that the SOSMP iterates converge to a $\delta$-neighborhood of the unique BP fixed point for any tree-structured graph, and for any graphs with cycles in which the BP updates satisfy a contractivity condition. In addition, we demonstrate how to choose the number of basis coefficients as a function of the desired approximation accuracy $\delta$ and smoothness of the compatibility functions. We illustrate our theory with both simulated examples and in application to optical flow estimation.
積和またはビリーフ プロパゲーション(BP)アルゴリズムは、グラフィカル モデルで近似周辺を計算するために広く使用されているメッセージ パッシング手法です。連続ランダム変数を持つモデルでBP固定点を計算するための、確率的直交級数メッセージ パッシング(SOSMP)と呼ばれる新しい手法を紹介します。これは、直交級数基底展開によるメッセージの決定論的近似と、モンテ カルロ法と減衰更新による基底係数の確率的推定に基づいています。任意のツリー構造グラフ、およびBP更新が収縮条件を満たすサイクルを持つ任意のグラフについて、SOSMP反復が一意のBP固定点の$\delta$近傍に収束することを証明します。さらに、必要な近似精度$\delta$と互換性関数の滑らかさの関数として基底係数の数を選択する方法を示します。シミュレーション例とオプティカル フロー推定への応用の両方で理論を説明します。
BudgetedSVM: A Toolbox for Scalable SVM Approximations
BudgetedSVM: スケーラブルな SVM 近似のためのツールボックス
We present BudgetedSVM, an open-source C++ toolbox comprising highly-optimized implementations of recently proposed algorithms for scalable training of Support Vector Machine (SVM) approximators: Adaptive Multi-hyperplane Machines, Low-rank Linearization SVM, and Budgeted Stochastic Gradient Descent. BudgetedSVM trains models with accuracy comparable to LibSVM in time comparable to LibLinear, solving non-linear problems with millions of high-dimensional examples within minutes on a regular computer. We provide command-line and Matlab interfaces to BudgetedSVM, an efficient API for handling large-scale, high- dimensional data sets, as well as detailed documentation to help developers use and further extend the toolbox.
私たちは、BudgetedSVMは、サポート ベクター マシン(SVM)近似器のスケーラブルなトレーニングのために最近提案されたアルゴリズムの高度に最適化された実装で構成されるオープンソースのC++ツールボックスであるBudgetedSVMです(適応型マルチプレーン マシン、低ランク線形化SVM、および予算化された確率的勾配降下法)。BudgetedSVMは、LibSVMに匹敵する精度とLibLinearに匹敵する時間でモデルをトレーニングし、通常のコンピューターで数百万の高次元の例を含む非線形問題を数分以内に解決します。BudgetedSVMへのコマンドラインおよびMatlabインターフェース、大規模で高次元のデータセットを処理するための効率的なAPIを提供するとともに、開発者がツールボックスを使用し、さらに拡張するのに役立つ詳細なドキュメントを提供します。
Optimally Fuzzy Temporal Memory
最適ファジィ時間記憶
Any learner with the ability to predict the future of a structured time-varying signal must maintain a memory of the recent past. If the signal has a characteristic timescale relevant to future prediction, the memory can be a simple shift register—a moving window extending into the past, requiring storage resources that linearly grows with the timescale to be represented. However, an independent general purpose learner cannot a priori know the characteristic prediction- relevant timescale of the signal. Moreover, many naturally occurring signals show scale-free long range correlations implying that the natural prediction-relevant timescale is essentially unbounded. Hence the learner should maintain information from the longest possible timescale allowed by resource availability. Here we construct a fuzzy memory system that optimally sacrifices the temporal accuracy of information in a scale-free fashion in order to represent prediction- relevant information from exponentially long timescales. Using several illustrative examples, we demonstrate the advantage of the fuzzy memory system over a shift register in time series forecasting of natural signals. When the available storage resources are limited, we suggest that a general purpose learner would be better off committing to such a fuzzy memory system.
構造化された時間変動信号の将来を予測する能力を持つ学習者は、最近の過去の記憶を保持する必要があります。信号が将来の予測に関連する特徴的な時間スケールを持つ場合、メモリは単純なシフト レジスタ(過去にまで及ぶ移動ウィンドウ)にすることができます。これには、表現される時間スケールに応じて線形に増加するストレージ リソースが必要です。ただし、独立した汎用学習者は、信号の特徴的な予測関連時間スケールを事前に知ることはできません。さらに、多くの自然に発生する信号はスケールフリーの長距離相関を示し、これは自然な予測関連時間スケールが本質的に無制限であることを意味します。したがって、学習者はリソースの可用性によって許される最長の時間スケールの情報を保持する必要があります。ここでは、指数関数的に長い時間スケールからの予測関連情報を表すために、スケールフリーの方法で情報の時間的正確性を最適に犠牲にするファジー メモリ システムを構築します。いくつかの例示的な例を使用して、自然信号の時系列予測におけるシフト レジスタに対するファジー メモリ システムの利点を示します。利用可能なストレージ リソースが限られている場合、汎用学習者にとっては、このようなファジー メモリ システムを採用する方がよいと考えられます。
Sparse/Robust Estimation and Kalman Smoothing with Nonsmooth Log-Concave Densities: Modeling, Computation, and Theory
非平滑対数凹密度によるスパース/ロバスト推定とカルマン平滑化: モデリング、計算、理論
We introduce a new class of quadratic support (QS) functions, many of which already play a crucial role in a variety of applications, including machine learning, robust statistical inference, sparsity promotion, and inverse problems such as Kalman smoothing. Well known examples of QS penalties include the $\ell_2$, Huber, $\ell_1$ and Vapnik losses. We build on a dual representation for QS functions, using it to characterize conditions necessary to interpret these functions as negative logs of true probability densities. This interpretation establishes the foundation for statistical modeling with both known and new QS loss functions, and enables construction of non-smooth multivariate distributions with specified means and variances from simple scalar building blocks. The main contribution of this paper is a flexible statistical modeling framework for a variety of learning applications, together with a toolbox of efficient numerical methods for estimation. In particular, a broad subclass of QS loss functions known as piecewise linear quadratic (PLQ) penalties has a dual representation that can be exploited to design interior point (IP) methods. IP methods solve nonsmooth optimization problems by working directly with smooth systems of equations characterizing their optimality. We provide several numerical examples, along with a code that can be used to solve general PLQ problems. The efficiency of the IP approach depends on the structure of particular applications. We consider the class of dynamic inverse problems using Kalman smoothing. This class comprises a wide variety of applications, where the aim is to reconstruct the state of a dynamical system with known process and measurement models starting from noisy output samples. In the classical case, Gaussian errors are assumed both in the process and measurement models for such problems. We show that the extended framework allows arbitrary PLQ densities to be used, and that the proposed IP approach solves the generalized Kalman smoothing problem while maintaining the linear complexity in the size of the time series, just as in the Gaussian case. This extends the computational efficiency of the Mayne-Fraser and Rauch-Tung- Striebel algorithms to a much broader nonsmooth setting, and includes many recently proposed robust and sparse smoothers as special cases.
私たちは、新しいクラスの二次サポート(QS)関数を導入します。これらの関数の多くは、機械学習、堅牢な統計的推論、スパース性促進、カルマン平滑化などの逆問題を含むさまざまなアプリケーションで既に重要な役割を果たしています。QSペナルティのよく知られた例としては、$\ell_2$、Huber、$\ell_1$、Vapnik損失などがあります。我々はQS関数のデュアル表現を基にして、これらの関数を真の確率密度の負の対数として解釈するために必要な条件を特徴付けます。この解釈は、既知および新しいQS損失関数の両方を使用した統計モデリングの基礎を確立し、単純なスカラー構成要素から指定された平均と分散を持つ非滑らかな多変量分布の構築を可能にします。この論文の主な貢献は、さまざまな学習アプリケーションのための柔軟な統計モデリング フレームワークと、推定のための効率的な数値手法のツールボックスです。特に、区分線形二次(PLQ)ペナルティとして知られるQS損失関数の広範なサブクラスには、内点(IP)法の設計に利用できるデュアル表現があります。IP法は、最適性を特徴付ける滑らかな方程式系を直接操作することで、滑らかでない最適化問題を解決します。一般的なPLQ問題を解決するために使用できるコードとともに、いくつかの数値例を示します。IPアプローチの効率は、特定のアプリケーションの構造によって異なります。カルマン スムージングを使用した動的逆問題のクラスを検討します。このクラスは、ノイズの多い出力サンプルから始めて、既知のプロセスおよび測定モデルを使用して動的システムの状態を再構築することを目的とする、さまざまなアプリケーションで構成されています。古典的なケースでは、このような問題のプロセス モデルと測定モデルの両方でガウス誤差が想定されています。拡張されたフレームワークでは任意のPLQ密度を使用でき、提案されたIPアプローチでは、ガウスの場合と同様に、時系列のサイズの線形複雑性を維持しながら、一般化されたカルマン スムージング問題を解決できることを示します。これにより、Mayne-FraserアルゴリズムとRauch-Tung-Striebelアルゴリズムの計算効率が、より広範な非滑らかな設定に拡張され、最近提案された多くの堅牢なスパース スムーザーが特殊なケースとして含まれるようになります。
Maximum Volume Clustering: A New Discriminative Clustering Approach
最大ボリューム・クラスタリング:新しい判別クラスタリング・アプローチ
The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a new discriminative clustering model based on the large volume principle called maximum volume clustering (MVC), and then propose two approximation schemes to solve this MVC model: A soft-label MVC method using sequential quadratic programming and a hard-label MVC method using semi-definite programming, respectively. The proposed MVC is theoretically advantageous for three reasons. The optimization involved in hard-label MVC is convex, and under mild conditions, the optimization involved in soft-label MVC is akin to a convex one in terms of the resulting clusters. Secondly, the soft-label MVC method possesses a clustering error bound. Thirdly, MVC includes the optimization problems of a spectral clustering, two relaxed $k$-means clustering and an information-maximization clustering as special limit cases when its regularization parameter goes to infinity. Experiments on several artificial and benchmark data sets demonstrate that the proposed MVC compares favorably with state-of-the-art clustering methods.
Vladimir Vapnikが提唱した大ボリューム原理は、同値類にある仮説はボリュームが大きいほど好ましいと主張しており、大マージン原理の有用な代替手段です。この論文では、最大ボリュームクラスタリング(MVC)と呼ばれる大ボリューム原理に基づく新しい識別クラスタリングモデルを紹介し、このMVCモデルを解決するための2つの近似スキームを提案します。それぞれ、逐次二次計画法を使用するソフトラベルMVC法と半正定値計画法を使用するハードラベルMVC法です。提案されたMVCは、3つの理由で理論的に有利です。ハードラベルMVCに含まれる最適化は凸であり、穏やかな条件下では、ソフトラベルMVCに含まれる最適化は、結果として得られるクラスターに関して凸に似ています。次に、ソフトラベルMVC法にはクラスタリングエラー境界があります。第三に、MVCには、正規化パラメータが無限大になる特別な極限ケースとして、スペクトル クラスタリング、2つの緩和された$k$平均クラスタリング、および情報最大化クラスタリングの最適化問題が含まれています。いくつかの人工データ セットとベンチマーク データ セットでの実験により、提案されたMVCが最先端のクラスタリング方法と比較して優れていることが実証されています。
Keep It Simple And Sparse: Real-Time Action Recognition
シンプルかつスパースに保つ:リアルタイムのアクション認識
Sparsity has been showed to be one of the most important properties for visual recognition purposes. In this paper we show that sparse representation plays a fundamental role in achieving one-shot learning and real-time recognition of actions. We start off from RGBD images, combine motion and appearance cues and extract state-of-the-art features in a computationally efficient way. The proposed method relies on descriptors based on 3D Histograms of Scene Flow (3DHOFs) and Global Histograms of Oriented Gradient (GHOGs); adaptive sparse coding is applied to capture high-level patterns from data. We then propose a simultaneous on-line video segmentation and recognition of actions using linear SVMs. The main contribution of the paper is an effective real-time system for one-shot action modeling and recognition; the paper highlights the effectiveness of sparse coding techniques to represent 3D actions. We obtain very good results on three different data sets: a benchmark data set for one-shot action learning (the ChaLearn Gesture Data Set), an in-house data set acquired by a Kinect sensor including complex actions and gestures differing by small details, and a data set created for human-robot interaction purposes. Finally we demonstrate that our system is effective also in a human-robot interaction setting and propose a memory game, âAll Gestures You Canâ, to be played against a humanoid robot.
スパース性は、視覚認識の目的において最も重要な特性の1つであることが示されています。この論文では、スパース表現がワンショット学習とアクションのリアルタイム認識を実現する上で基本的な役割を果たすことを示します。RGBD画像から開始し、動きと外観の手がかりを組み合わせて、計算効率の高い方法で最先端の機能を抽出します。提案された方法は、3Dシーン フローのヒストグラム(3DHOF)とグローバル方向勾配ヒストグラム(GHOG)に基づく記述子に依存し、適応型スパース コーディングを適用して、データから高レベルのパターンを取得します。次に、線形SVMを使用して、オンライン ビデオのセグメンテーションとアクションの認識を同時に行うことを提案します。この論文の主な貢献は、ワンショット アクションのモデリングと認識のための効果的なリアルタイム システムであり、3Dアクションを表現するためのスパース コーディング手法の有効性を強調しています。3つの異なるデータ セットで非常に良い結果が得られました。ワンショット アクション学習のベンチマーク データ セット(ChaLearnジェスチャ データ セット)、Kinectセンサーで取得した、細かい部分が異なる複雑なアクションやジェスチャを含む社内データ セット、および人間とロボットのインタラクションを目的として作成されたデータ セットです。最後に、このシステムが人間とロボットのインタラクションの設定でも効果的であることを実証し、ヒューマノイド ロボットと対戦する記憶ゲーム「All Gestures You Can」を提案します。
Efficient Active Learning of Halfspaces: An Aggressive Approach
ハーフスペースの効率的なアクティブラーニング:積極的なアプローチ
We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.
私たちは、半空間のプールベースの能動学習を研究します。実現可能なケースでの能動学習の積極的アプローチを再検討し、それが効率的かつ実用的になり得ると同時に、合理的な仮定の下で理論的な保証も持つことを示す。さらに、理論的にも実験的にも、それが穏やかなアプローチよりも好ましい場合があることを示す。我々の効率的な半空間の積極的能動学習器は、プールが余裕を持って分離可能な場合に成立する形式的な近似保証を持つ。我々の分析は実現可能な設定に焦点を当てているが、単純なヒューリスティックによって、同じアルゴリズムを低エラーのプールにもうまく使用できることを示す。さらに、積極的アプローチを穏やかなアプローチと比較し、積極的アプローチの方が穏やかなアプローチに比べてラベルの複雑性が大幅に向上するケースがあることを証明した。実現可能な設定と低エラーの設定の両方で、積極的アプローチを使用してラベルの複雑性を大幅に改善できることを実験的に実証します。
One-shot Learning Gesture Recognition from RGB-D Data Using Bag of Features
Bag of Featuresを用いたRGB-Dデータからのワンショット学習ジェスチャー認識
For one-shot learning gesture recognition, two important challenges are: how to extract distinctive features and how to learn a discriminative model from only one training sample per gesture class. For feature extraction, a new spatio-temporal feature representation called 3D enhanced motion scale-invariant feature transform (3D EMoSIFT) is proposed, which fuses RGB-D data. Compared with other features, the new feature set is invariant to scale and rotation, and has more compact and richer visual representations. For learning a discriminative model, all features extracted from training samples are clustered with the k-means algorithm to learn a visual codebook. Then, unlike the traditional bag of feature (BoF) models using vector quantization (VQ) to map each feature into a certain visual codeword, a sparse coding method named simulation orthogonal matching pursuit (SOMP) is applied and thus each feature can be represented by some linear combination of a small number of codewords. Compared with VQ, SOMP leads to a much lower reconstruction error and achieves better performance. The proposed approach has been evaluated on ChaLearn gesture database and the result has been ranked amongst the top best performing techniques on ChaLearn gesture challenge (round 2).
ワンショット学習ジェスチャ認識には、2つの重要な課題があります。1つは、特徴をどのように抽出するか、もう1つは、ジェスチャ クラスごとに1つのトレーニング サンプルのみから識別モデルをどのように学習するかです。特徴抽出については、RGB-Dデータを融合する3D拡張モーション スケール不変特徴変換(3D EMoSIFT)と呼ばれる新しい時空間特徴表現が提案されています。他の特徴と比較して、新しい特徴セットはスケールと回転に対して不変であり、よりコンパクトで豊富な視覚表現を備えています。識別モデルを学習するために、トレーニング サンプルから抽出されたすべての特徴は、k-meansアルゴリズムを使用してクラスタ化され、視覚コードブックを学習します。次に、ベクトル量子化(VQ)を使用して各特徴を特定の視覚コードワードにマッピングする従来のBag of Features (BoF)モデルとは異なり、シミュレーション直交マッチング追求(SOMP)と呼ばれるスパース コーディング メソッドが適用され、各特徴は少数のコードワードの線形結合によって表現できます。VQと比較して、SOMPは再構築エラーが大幅に低減し、パフォーマンスが向上します。提案されたアプローチはChaLearnジェスチャ データベースで評価され、その結果はChaLearnジェスチャ チャレンジ(ラウンド2)で最も優れたパフォーマンスを発揮するテクニックの1つにランクされました。
Learning Bilinear Model for Matching Queries and Documents
クエリとドキュメントを照合するためのバイリニアモデルの学習
The task of matching data from two heterogeneous domains naturally arises in various areas such as web search, collaborative filtering, and drug design. In web search, existing work has designed relevance models to match queries and documents by exploiting either user clicks or content of queries and documents. To the best of our knowledge, however, there has been little work on principled approaches to leveraging both clicks and content to learn a matching model for search. In this paper, we propose a framework for learning to match heterogeneous objects. The framework learns two linear mappings for two objects respectively, and matches them via the dot product of their images after mapping. Moreover, when different regularizations are enforced, the framework renders a rich family of matching models. With orthonormal constraints on mapping functions, the framework subsumes Partial Least Squares (PLS) as a special case. Alternatively, with a $\ell_1$+$\ell_2$ regularization, we obtain a new model called Regularized Mapping to Latent Structures (RMLS). RMLS enjoys many advantages over PLS, including lower time complexity and easy parallelization. To further understand the matching framework, we conduct generalization analysis and apply the result to both PLS and RMLS. We apply the framework to web search and implement both PLS and RMLS using a click-through bipartite with metadata representing features of queries and documents. We test the efficacy and scalability of RMLS and PLS on large scale web search problems. The results show that both PLS and RMLS can significantly outperform baseline methods, while RMLS substantially speeds up the learning process.
2つの異種ドメインからのデータをマッチングするタスクは、Web検索、協調フィルタリング、医薬品設計などのさまざまな分野で自然に発生します。Web検索では、既存の研究では、ユーザーのクリックまたはクエリとドキュメントのコンテンツのいずれかを利用して、クエリとドキュメントをマッチングする関連性モデルが設計されています。ただし、私たちの知る限りでは、クリックとコンテンツの両方を活用して検索のマッチング モデルを学習する原理的なアプローチに関する研究はほとんどありませんでした。この論文では、異種オブジェクトのマッチングを学習するためのフレームワークを提案します。フレームワークは、2つのオブジェクトそれぞれに対して2つの線形マッピングを学習し、マッピング後の画像のドット積を介してそれらをマッチングします。さらに、さまざまな正則化を適用すると、フレームワークは豊富なマッチング モデル ファミリをレンダリングします。マッピング関数に正規直交制約がある場合、フレームワークは部分最小二乗法(PLS)を特別なケースとして組み込みます。または、$\ell_1$+$\ell_2$正則化を使用すると、Regularized Mapping to Latent Structures (RMLS)と呼ばれる新しいモデルが得られます。RMLSは、時間の計算量が少なく、並列化が容易であるなど、PLSに比べて多くの利点があります。マッチング フレームワークをさらに理解するために、一般化分析を実施し、その結果をPLSとRMLSの両方に適用します。フレームワークをWeb検索に適用し、クエリとドキュメントの特徴を表すメタデータを含むクリックスルー二部を使用してPLSとRMLSの両方を実装します。大規模なWeb検索問題でRMLSとPLSの有効性とスケーラビリティをテストします。結果は、PLSとRMLSの両方がベースライン メソッドを大幅に上回り、RMLSが学習プロセスを大幅に高速化できることを示しています。
Greedy Feature Selection for Subspace Clustering
部分空間クラスタリングのための貪欲な特徴選択
Unions of subspaces provide a powerful generalization of single subspace models for collections of high-dimensional data; however, learning multiple subspaces from data is challenging due to the fact that segmentation—the identification of points that live in the same subspace—and subspace estimation must be performed simultaneously. Recently, sparse recovery methods were shown to provide a provable and robust strategy for exact feature selection (EFS)—recovering subsets of points from the ensemble that live in the same subspace. In parallel with recent studies of EFS with $\ell_1$-minimization, in this paper, we develop sufficient conditions for EFS with a greedy method for sparse signal recovery known as orthogonal matching pursuit (OMP). Following our analysis, we provide an empirical study of feature selection strategies for signals living on unions of subspaces and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. In particular, we demonstrate that sparse recovery methods provide significant advantages over NN methods and that the gap between the two approaches is particularly pronounced when the sampling of subspaces in the data set is sparse. Our results suggest that OMP may be employed to reliably recover exact feature sets in a number of regimes where NN approaches fail to reveal the subspace membership of points in the ensemble.
部分空間の和集合は、高次元データの集合に対する単一部分空間モデルの強力な一般化を提供します。しかし、データから複数の部分空間を学習することは、セグメンテーション（同じ部分空間に存在する点の識別）と部分空間推定を同時に実行する必要があるため、困難です。最近、スパース回復法は、正確な特徴選択（EFS）（同じ部分空間に存在する点の集合から部分集合を回復する）のための証明可能で堅牢な戦略を提供することが示されました。$\ell_1$最小化によるEFSの最近の研究と並行して、この論文では、直交マッチング追求（OMP）として知られるスパース信号回復のための貪欲法によるEFSの十分条件を開発します。分析に続いて、部分空間の和集合に存在する信号の特徴選択戦略の実証的研究を提供し、スパース回復法と最近傍（NN）ベースのアプローチとの間のギャップを特徴付けます。特に、スパース回復法はNN法に比べて大きな利点があり、データセット内のサブスペースのサンプリングがスパースである場合に2つのアプローチ間のギャップが特に顕著になることを実証します。私たちの結果は、NNアプローチではアンサンブル内のポイントのサブスペース メンバーシップを明らかにできない多くの状況で、OMPを使用して正確な特徴セットを確実に回復できる可能性があることを示唆しています。
Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
パスコーディングペナルティとネットワークフローのあるグラフでの教師あり特徴選択
We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or obtain results that are easier to interpret. Regularization or penalty functions for selecting features in graphs have recently been proposed, but they raise new algorithmic challenges. For example, they typically require solving a combinatorially hard selection problem among all connected subgraphs. In this paper, we propose computationally feasible strategies to select a sparse and well-connected subset of features sitting on a directed acyclic graph (DAG). We introduce structured sparsity penalties over paths on a DAG called âpath codingâ penalties. Unlike existing regularization functions that model long-range interactions between features in a graph, path coding penalties are tractable. The penalties and their proximal operators involve path selection problems, which we efficiently solve by leveraging network flow optimization. We experimentally show on synthetic, image, and genomic data that our approach is scalable and leads to more connected subgraphs than other regularization functions for graphs.
私たちは、遺伝子ネットワークにおける遺伝子発現など、グラフに特徴が埋め込まれている教師あり学習の問題を検討します。この文脈では、連結成分の少ないサブグラフを自動的に選択することが非常に重要であり、事前知識を活用することで、予測性能を向上させたり、解釈しやすい結果を得たりすることができます。グラフ内の特徴を選択するための正則化またはペナルティ関数が最近提案されましたが、それらは新しいアルゴリズム上の課題を引き起こします。たとえば、それらは通常、連結されたすべてのサブグラフの中から組み合わせ的に困難な選択問題を解決する必要があります。この論文では、有向非巡回グラフ(DAG)上にある疎で連結度の高い特徴のサブセットを選択するための計算上実行可能な戦略を提案します。私たちは、DAG上のパスに構造化された疎性ペナルティを導入します。これは「パス コーディング」ペナルティと呼ばれます。グラフ内の特徴間の長距離相互作用をモデル化する既存の正則化関数とは異なり、パス コーディング ペナルティは扱いやすいものです。ペナルティとその近似演算子はパス選択問題に関係しており、私たちはネットワーク フロー最適化を活用してこれを効率的に解決します。私たちは、合成データ、画像データ、ゲノムデータを用いて、我々のアプローチがスケーラブルであり、グラフの他の正規化関数よりも多くの接続されたサブグラフにつながることを実験的に示します。
Distance Preserving Embeddings for General n-Dimensional Manifolds
一般的なn次元多様体のための距離保存埋め込み
Low dimensional embeddings of manifold data have gained popularity in the last decade. However, a systematic finite sample analysis of manifold embedding algorithms largely eludes researchers. Here we present two algorithms that embed a general $n$-dimensional manifold into $\R^d$ (where $d$ only depends on some key manifold properties such as its intrinsic dimension, volume and curvature) that guarantee to approximately preserve all interpoint geodesic distances.
多様体のデータの低次元埋め込みは、過去10年間で人気を博しています。しかし、多様体埋め込みアルゴリズムの体系的な有限サンプル解析は、研究者からほとんど手を逃れています。ここでは、一般的な$n$次元多様体を$R^d$に埋め込む2つのアルゴリズムを紹介します(ここで、$d$は、その固有の次元、体積、曲率などの主要な多様体特性にのみ依存します)。
On the Mutual Nearest Neighbors Estimate in Regression
回帰における相互最近傍推定について
Motivated by promising experimental results, this paper investigates the theoretical properties of a recently proposed nonparametric estimator, called the Mutual Nearest Neighbors rule, which estimates the regression function $m(\mathbf{x})=\mathbb E[Y|\mathbf{X}=\mathbf{x}]$ as follows: first identify the $k$ nearest neighbors of $\mathbf{x}$ in the sample $\mathcal{D}_n$, then keep only those for which $\mathbf{x}$ is itself one of the $k$ nearest neighbors, and finally take the average over the corresponding response variables. We prove that this estimator is consistent and that its rate of convergence is optimal. Since the estimate with the optimal rate of convergence depends on the unknown distribution of the observations, we also present adaptation results by data- splitting.
有望な実験結果に動機付けられて、この論文では、最近提案されたノンパラメトリック推定量、つまり相互最近傍ルールと呼ばれる、回帰関数を推定する理論的特性を調査します$m(mathbf{x})=mathbb E[Y|mathbf{X}=mathbf{x}]$次のようにします:まず、サンプル$mathcal{D}_n$で$mathbf{x}$の$k$近傍を特定し、次に$mathbf{x}$自体が$k$の最近傍の1つであるもののみを保持します。そして最後に、対応する応答変数の平均を取ります。この推定量が一貫しており、その収束率が最適であることを証明します。最適な収束率の推定値は観測値の未知の分布に依存するため、データ分割による適応結果も提示します。
Tapkee: An Efficient Dimension Reduction Library
Tapkee: 効率的な寸法縮小ライブラリ
We present Tapkee, a C++ template library that provides efficient implementations of more than $20$ widely used dimensionality reduction techniques ranging from Locally Linear Embedding (Roweis and Saul, 2000) and Isomap (de Silva and Tenenbaum, 2002) to the recently introduced Barnes- Hut-SNE (van der Maaten, 2013). Our library was designed with a focus on performance and flexibility. For performance, we combine efficient multi-core algorithms, modern data structures and state-of-the-art low-level libraries. To achieve flexibility, we designed a clean interface for applying methods to user data and provide a callback API that facilitates integration with the library. The library is freely available as open-source software and is distributed under the permissive BSD 3-clause license. We encourage the integration of Tapkee into other open-source toolboxes and libraries. For example, Tapkee has been integrated into the codebase of the Shogun toolbox (Sonnenburg et al., 2010), giving us access to a rich set of kernels, distance measures and bindings to common programming languages including Python, Octave, Matlab, R, Java, C#, Ruby, Perl and Lua. Source code, examples and documentation are available at http://tapkee.lisitsyn.me.
私たちは、局所線形埋め込み(RoweisとSaul、2000年)やIsomap (de SilvaとTenenbaum、2002年)から最近導入されたBarnes-Hut-SNE (van der Maaten、2013年)に至るまで、20種類を超える広く使用されている次元削減手法の効率的な実装を提供するC++テンプレート ライブラリTapkeeを紹介します。我々のライブラリは、パフォーマンスと柔軟性に重点を置いて設計されました。パフォーマンスについては、効率的なマルチコア アルゴリズム、最新のデータ構造、最先端の低レベル ライブラリを組み合わせています。柔軟性を実現するために、ユーザー データにメソッドを適用するためのクリーンなインターフェイスを設計し、ライブラリとの統合を容易にするコールバックAPIを提供しています。ライブラリはオープン ソース ソフトウェアとして無料で利用でき、寛容なBSD 3条項ライセンスの下で配布されています。Tapkeeを他のオープン ソース ツールボックスやライブラリに統合することを推奨します。たとえば、TapkeeはShogunツールボックス(Sonnenburg他、2010)のコードベースに統合されており、豊富なカーネル、距離測定、Python、Octave、Matlab、R、Java、C#、Ruby、Perl、Luaなどの一般的なプログラミング言語へのバインディングにアクセスできるようになりました。ソース コード、例、ドキュメントはhttp://tapkee.lisitsyn.meで入手できます。
Orange: Data Mining Toolbox in Python
Orange: Python のデータ マイニング ツールボックス
Orange is a machine learning and data mining suite for data analysis through Python scripting and visual programming. Here we report on the scripting part, which features interactive data analysis and component-based assembly of data mining procedures. In the selection and design of components, we focus on the flexibility of their reuse: our principal intention is to let the user write simple and clear scripts in Python, which build upon C$++$ implementations of computationally-intensive tasks. Orange is intended both for experienced users and programmers, as well as for students of data mining.
Orangeは、Pythonスクリプトとビジュアルプログラミングによるデータ分析のための機械学習およびデータマイニングスイートです。ここでは、対話型のデータ分析とデータ マイニング プロシージャのコンポーネント ベースのアセンブリを特徴とするスクリプト部分について報告します。コンポーネントの選択と設計では、それらの再利用の柔軟性に焦点を当てています:私たちの主な意図は、ユーザーがPythonでシンプルで明確なスクリプトを書けるようにすることです。これは、計算集約的なタスクのC$++$実装に基づいて構築されています。Orangeは、経験豊富なユーザーとプログラマーの両方、およびデータマイニングの学生を対象としています。
The Rate of Convergence of AdaBoost
AdaBoostの収束率
The AdaBoost algorithm was designed to combine many âweakâ hypotheses that perform slightly better than random guessing into a âstrongâ hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the âexponential lossâ. Unlike previous work, our proofs do not require a weak-learning assumption, nor do they require that minimizers of the exponential loss are finite. Our first result shows that the exponential loss of AdaBoost’s computed parameter vector will be at most $\varepsilon$ more than that of any parameter vector of $\ell_1$-norm bounded by $B$ in a number of rounds that is at most a polynomial in $B$ and $1/\varepsilon$. We also provide lower bounds showing that a polynomial dependence is necessary. Our second result is that within $C/\varepsilon$ iterations, AdaBoost achieves a value of the exponential loss that is at most $\varepsilon$ more than the best possible value, where $C$ depends on the data set. We show that this dependence of the rate on $\varepsilon$ is optimal up to constant factors, that is, at least $\Omega(1/\varepsilon)$ rounds are necessary to achieve within $\varepsilon$ of the optimal exponential loss.
AdaBoostアルゴリズムは、ランダムな推測よりもわずかに優れたパフォーマンスを発揮する多くの「弱い」仮説を、エラーが非常に低い「強い」仮説に組み合わせるように設計されています。AdaBoostが「指数損失」の最小値に反復的に収束する速度を調べます。以前の研究とは異なり、私たちの証明では弱学習の仮定は不要であり、指数損失の最小化が有限であることも必要ありません。最初の結果は、AdaBoostの計算されたパラメーター ベクトルの指数損失が、最大で$B$の多項式および$1/\varepsilon$であるラウンド数で、$B$で制限される$\ell_1$ノルムのパラメーター ベクトルの指数損失より最大で$\varepsilon$大きくなることを示しています。多項式依存性が必要であることを示す下限も示しています。2つ目の結果は、$C/\varepsilon$反復内で、AdaBoostは、最高可能値よりも最大$\varepsilon$大きい指数損失の値を達成することです。ここで、$C$はデータ セットによって異なります。このレートの$\varepsilon$への依存性は、定数倍まで最適であることを示しています。つまり、最適な指数損失の$\varepsilon$以内を達成するには、少なくとも$\Omega(1/\varepsilon)$ラウンドが必要です。
Message-Passing Algorithms for Quadratic Minimization
二次最小化のためのメッセージパッシングアルゴリズム
Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean (and variances) of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite covariance matrix. As was observed by Malioutov et al. (2006), the GaBP algorithm fails to converge if the computation trees produced by the algorithm are not positive definite. In this work, we will show that the failure modes of the GaBP algorithm can be understood via graph covers, and we prove that a parameterized generalization of the min-sum algorithm can be used to ensure that the computation trees remain positive definite whenever the input matrix is positive definite. We demonstrate that the resulting algorithm is closely related to other iterative schemes for quadratic minimization such as the Gauss-Seidel and Jacobi algorithms. Finally, we observe, empirically, that there always exists a choice of parameters such that the above generalization of the GaBP algorithm converges.
ガウス確率伝播法(GaBP)は、多変量ガウス分布の平均(および分散)、または多変量正定値2次関数の最小値を計算する反復アルゴリズムです。GaBPの収束と正確性を保証する十分な条件(ウォーク加算可能性など)はわかっていますが、任意の正定値共分散行列が与えられた場合、GaBPは正しい解に収束しない可能性があります。Malioutovら(2006)が指摘したように、GaBPアルゴリズムは、アルゴリズムによって生成された計算ツリーが正定値でない場合、収束しません。この研究では、GaBPアルゴリズムの失敗モードがグラフ カバーを介して理解できることを示し、最小和アルゴリズムのパラメーター化された一般化を使用して、入力行列が正定値である場合に計算ツリーが正定値のままであることを保証できることを証明します。結果として得られるアルゴリズムは、ガウス・ザイデル法やヤコビ法などの二次方程式の最小化のための他の反復方式と密接に関連していることを示します。最後に、経験的に、上記のGaBPアルゴリズムの一般化が収束するようなパラメータの選択が常に存在することを観察します。
Gaussian Kullback-Leibler Approximate Inference
ガウス Kullback-Leibler 近似推論
We investigate Gaussian Kullback-Leibler (G-KL) variational approximate inference techniques for Bayesian generalised linear models and various extensions. In particular we make the following novel contributions: sufficient conditions for which the G-KL objective is differentiable and convex are described; constrained parameterisations of Gaussian covariance that make G-KL methods fast and scalable are provided; the lower bound to the normalisation constant provided by G-KL methods is proven to dominate those provided by local lower bounding methods; complexity and model applicability issues of G-KL versus other Gaussian approximate inference methods are discussed. Numerical results comparing G-KL and other deterministic Gaussian approximate inference methods are presented for: robust Gaussian process regression models with either Student-$t$ or Laplace likelihoods, large scale Bayesian binary logistic regression models, and Bayesian sparse linear models for sequential experimental design.
私たちは、ベイズ一般化線型モデルとさまざまな拡張に対するガウスKullback-Leibler (G-KL)変分近似推論手法を調査します。特に、次のような新しい貢献をしています。G-KL目的関数が微分可能かつ凸であるための十分条件を説明します。G-KL法を高速かつスケーラブルにするガウス共分散の制約付きパラメーター化を提供します。G-KL法によって提供される正規化定数の下限は、ローカル下限法によって提供されるものよりも優れていることが証明されています。G-KLと他のガウス近似推論法を比較した複雑性とモデルの適用性の問題について議論します。G-KLと他の決定論的ガウス近似推論法を比較した数値結果は、Student-tまたはラプラス尤度のいずれかを使用したロバストなガウス過程回帰モデル、大規模なベイズ2値ロジスティック回帰モデル、および逐次実験設計のためのベイズ疎線型モデルについて示します。
Segregating Event Streams and Noise with a Markov Renewal Process Model
マルコフ更新プロセスモデルによるイベントストリームとノイズの分離
We describe an inference task in which a set of timestamped event observations must be clustered into an unknown number of temporal sequences with independent and varying rates of observations. Various existing approaches to multi-object tracking assume a fixed number of sources and/or a fixed observation rate; we develop an approach to inferring structure in timestamped data produced by a mixture of an unknown and varying number of similar Markov renewal processes, plus independent clutter noise. The inference simultaneously distinguishes signal from noise as well as clustering signal observations into separate source streams. We illustrate the technique via synthetic experiments as well as an experiment to track a mixture of singing birds. Source code is available.
私たちは、タイムスタンプ付きのイベント観測のセットを、観測値の独立したさまざまなレートを持つ未知の数の時間シーケンスにクラスター化する必要がある推論タスクについて説明します。マルチオブジェクト追跡に対するさまざまな既存のアプローチは、固定数のソースおよび/または固定の観測率を前提としています。私たちは、未知の類似のマルコフ更新プロセスとさまざまな数の類似したマルコフ更新プロセスの混合物と、独立したクラッタノイズの組み合わせによって生成されたタイムスタンプ付きデータの構造を推論するアプローチを開発します。この推論では、信号とノイズを同時に区別するだけでなく、信号観測値を別々のソースストリームにクラスタリングします。この手法は、合成実験と、歌う鳥の混合物を追跡する実験を通じて説明します。ソースコードが利用可能です。
Language-Motivated Approaches to Action Recognition
行動認識への言語動機付けアプローチ
We present language-motivated approaches to detecting, localizing and classifying activities and gestures in videos. In order to obtain statistical insight into the underlying patterns of motions in activities, we develop a dynamic, hierarchical Bayesian model which connects low-level visual features in videos with poses, motion patterns and classes of activities. This process is somewhat analogous to the method of detecting topics or categories from documents based on the word content of the documents, except that our documents are dynamic. The proposed generative model harnesses both the temporal ordering power of dynamic Bayesian networks such as hidden Markov models (HMMs) and the automatic clustering power of hierarchical Bayesian models such as the latent Dirichlet allocation (LDA) model. We also introduce a probabilistic framework for detecting and localizing pre-specified activities (or gestures) in a video sequence, analogous to the use of filler models for keyword detection in speech processing. We demonstrate the robustness of our classification model and our spotting framework by recognizing activities in unconstrained real-life video sequences and by spotting gestures via a one-shot-learning approach.
私たちは、動画内のアクティビティやジェスチャーを検出、特定、分類するための言語に基づくアプローチを紹介します。アクティビティにおける動きの根本的なパターンに関する統計的洞察を得るために、動画内の低レベルの視覚的特徴をポーズ、動きのパターン、アクティビティのクラスと結び付ける動的階層ベイズモデルを開発します。このプロセスは、ドキュメントの単語内容に基づいてドキュメントからトピックやカテゴリを検出する方法に似ていますが、ドキュメントが動的である点が異なります。提案された生成モデルは、隠れマルコフモデル(HMM)などの動的ベイズネットワークの時間的順序付け能力と、潜在ディリクレ配分法(LDA)モデルなどの階層ベイズモデルの自動クラスタリング能力の両方を活用します。また、音声処理におけるキーワード検出のためのフィラーモデルの使用に類似した、動画シーケンス内の事前指定されたアクティビティ(またはジェスチャー)を検出して特定するための確率的フレームワークも紹介します。私たちは、制約のない現実のビデオシーケンス内のアクティビティを認識し、ワンショット学習アプローチでジェスチャーを検出することにより、分類モデルと検出フレームワークの堅牢性を実証します。
Convex and Scalable Weakly Labeled SVMs
凸型でスケーラブルな弱ラベルの SVM
In this paper, we study the problem of learning from weakly labeled data, where labels of the training examples are incomplete. This includes, for example, (i) semi- supervised learning where labels are partially known; (ii) multi-instance learning where labels are implicitly known; and (iii) clustering where labels are completely unknown. Unlike supervised learning, learning with weak labels involves a difficult Mixed-Integer Programming (MIP) problem. Therefore, it can suffer from poor scalability and may also get stuck in local minimum. In this paper, we focus on SVMs and propose the WELLSVM via a novel label generation strategy. This leads to a convex relaxation of the original MIP, which is at least as tight as existing convex Semi-Definite Programming (SDP) relaxations. Moreover, the WELLSVM can be solved via a sequence of SVM subproblems that are much more scalable than previous convex SDP relaxations. Experiments on three weakly labeled learning tasks, namely, (i) semi-supervised learning; (ii) multi-instance learning for locating regions of interest in content-based information retrieval; and (iii) clustering, clearly demonstrate improved performance, and WELLSVM is also readily applicable on large data sets.
この論文では、トレーニング例のラベルが不完全である、弱くラベル付けされたデータからの学習の問題を検討します。これには、たとえば、(i)ラベルが部分的にわかっている半教師あり学習、(ii)ラベルが暗黙的にわかっているマルチインスタンス学習、(iii)ラベルが完全にわからないクラスタリングが含まれます。教師あり学習とは異なり、弱いラベルを使用した学習には、難しい混合整数計画法(MIP)の問題が伴います。したがって、スケーラビリティが低く、局所的最小値で行き詰まる可能性もあります。この論文では、SVMに焦点を当て、新しいラベル生成戦略を介してWELLSVMを提案します。これにより、元のMIPの凸緩和が実現し、既存の凸半正定値計画法(SDP)緩和と少なくとも同程度にタイトになります。さらに、WELLSVMは、以前の凸SDP緩和よりもはるかにスケーラブルな一連のSVMサブ問題を介して解決できます。3つの弱くラベル付けされた学習タスク、すなわち(i)半教師あり学習、(ii)コンテンツベースの情報検索における関心領域を特定するためのマルチインスタンス学習、および(iii)クラスタリングは、明らかにパフォーマンスの向上を示しており、WELLSVMは大規模なデータセットにも容易に適用できます。
Distribution-Dependent Sample Complexity of Large Margin Learning
大マージン学習の分布依存サンプルの複雑さ
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with $L_2$ regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution- specific upper and lower bounds on the sample complexity, both governed by the margin-adapted dimension of the data distribution. The upper bounds are universal, and the lower bounds hold for the rich family of sub- Gaussian distributions with independent features. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. To prove the lower bound, we develop several new tools of independent interest. These include new connections between shattering and hardness of learning, new properties of shattering with linear classifiers, and a new lower bound on the smallest eigenvalue of a random Gram matrix generated by sub- Gaussian variables. Our results can be used to quantitatively compare large margin learning to other learning rules, and to improve the effectiveness of methods that use sample complexity bounds, such as active learning.
私たちは、$L_2$正則化を用いた大マージン分類のサンプル複雑性の分布固有の厳密な特徴付けを得た。すなわち、データ分布の2次統計量の単純な関数であるマージン適応次元を導入し、分布固有のサンプル複雑性の上限と下限を示した。これらは両方とも、データ分布のマージン適応次元によって支配されます。上限は普遍的であり、下限は独立した特徴を持つサブガウス分布の豊富なファミリーに当てはまる。私たちは、この新しい量が大マージン分類の真のサンプル複雑性を厳密に特徴付けると結論付けた。下限を証明するために、我々は独立した関心のあるいくつかの新しいツールを開発します。これらには、粉砕と学習の困難さの間の新しい関係、線形分類器による粉砕の新しい特性、サブガウス変数によって生成されるランダムなグラム行列の最小固有値の新しい下限などが含まれます。我々の結果は、大マージン学習を他の学習ルールと定量的に比較したり、能動学習などのサンプル複雑性境界を使用する方法の有効性を改善したりするために使用できます。
Construction of Approximation Spaces for Reinforcement Learning
強化学習のための近似空間の構築
Linear reinforcement learning (RL) algorithms like least-squares temporal difference learning (LSTD) require basis functions that span approximation spaces of potential value functions. This article investigates methods to construct these bases from samples. We hypothesize that an ideal approximation spaces should encode diffusion distances and that slow feature analysis (SFA) constructs such spaces. To validate our hypothesis we provide theoretical statements about the LSTD value approximation error and induced metric of approximation spaces constructed by SFA and the state-of-the-art methods Krylov bases and proto-value functions (PVF). In particular, we prove that SFA minimizes the average (over all tasks in the same environment) bound on the above approximation error. Compared to other methods, SFA is very sensitive to sampling and can sometimes fail to encode the whole state space. We derive a novel importance sampling modification to compensate for this effect. Finally, the LSTD and least squares policy iteration (LSPI) performance of approximation spaces constructed by Krylov bases, PVF, SFA and PCA is compared in benchmark tasks and a visual robot navigation experiment (both in a realistic simulation and with a robot). The results support our hypothesis and suggest that (i) SFA provides subspace-invariant features for MDPs with self-adjoint transition operators, which allows strong guarantees on the approximation error, (ii) the modified SFA algorithm is best suited for LSPI in both discrete and continuous state spaces and (iii) approximation spaces encoding diffusion distances facilitate LSPI performance.
最小二乗時間差分学習(LSTD)のような線形強化学習(RL)アルゴリズムには、潜在的価値関数の近似空間にまたがる基底関数が必要です。この記事では、サンプルからこれらの基底を構築する方法について調査します。理想的な近似空間は拡散距離をエンコードする必要があり、低速特徴分析(SFA)がそのような空間を構築するという仮説を立てます。仮説を検証するために、SFAと最先端の方法であるクリロフ基底とプロト価値関数(PVF)によって構築されたLSTD値近似誤差と近似空間の誘導メトリックに関する理論的なステートメントを提供します。特に、SFAが上記の近似誤差の平均(同じ環境内のすべてのタスクにわたって)境界を最小化することを証明します。他の方法と比較して、SFAはサンプリングに非常に敏感で、状態空間全体をエンコードできない場合があります。この影響を補正するために、新しい重要度サンプリング修正を導出します。最後に、クリロフ基底、PVF、SFA、PCAによって構築された近似空間のLSTDと最小二乗ポリシー反復(LSPI)のパフォーマンスを、ベンチマーク タスクと視覚ロボット ナビゲーション実験(現実的なシミュレーションとロボットの両方)で比較します。結果は私たちの仮説を裏付けており、(i) SFAは自己随伴遷移演算子を持つMDPに部分空間不変の特徴を提供し、近似誤差を強力に保証できること、(ii)修正されたSFAアルゴリズムは離散状態空間と連続状態空間の両方でLSPIに最適であること、(iii)拡散距離をエンコードした近似空間はLSPIのパフォーマンスを促進することを示唆しています。
Approximating the Permanent with Fractional Belief Propagation
フラクショナルビリーフ伝播によるパーマネントの近似
We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the belief propagation (BP) approach and its fractional belief propagation (FBP) generalization for computing the permanent of a non-negative matrix. Known bounds and Conjectures are verified in experiments, and some new theoretical relations, bounds and Conjectures are proposed. The fractional free energy (FFE) function is parameterized by a scalar parameter $\gamma\in[-1;1]$, where $\gamma=-1$ corresponds to the BP limit and $\gamma=1$ corresponds to the exclusion principle (but ignoring perfect matching constraints) mean-field (MF) limit. FFE shows monotonicity and continuity with respect to $\gamma$. For every non-negative matrix, we define its special value $\gamma_*\in[-1;0]$ to be the $\gamma$ for which the minimum of the $\gamma$-parameterized FFE function is equal to the permanent of the matrix, where the lower and upper bounds of the $\gamma$-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of $\gamma_*$ varies for different ensembles but $\gamma_*$ always lies within the $[-1;-1/2]$ interval. Moreover, for all ensembles considered, the behavior of $\gamma_*$ is highly distinctive, offering an empirical practical guidance for estimating permanents of non-negative matrices via the FFE approach.
私たちは、パーマネントの正確な計算と近似計算のスキームについて説明し、それらを比較します。具体的には、非負行列のパーマネントを計算するためのビリーフプロパゲーション(BP)アプローチとそのフラクショナルビリーフプロパゲーション(FBP)の一般化を分析します。既知の境界と予想は実験で検証され、いくつかの新しい理論的関係、境界、予想が提案されています。フラクショナル自由エネルギー(FFE)関数は、スカラーパラメーター$\gamma\in[-1;1]$によってパラメーター化されます。ここで、$\gamma=-1$はBP限界に対応し、$\gamma=1$は排他原理(ただし完全マッチング制約は無視)平均場(MF)限界に対応します。FFEは、$\gamma$に関して単調性と連続性を示します。すべての非負行列について、その特別な値$\gamma_*\in[-1;0]$を、$\gamma$パラメータ化FFE関数の最小値が行列のパーマネントに等しい$\gamma$として定義します。ここで、$\gamma$間隔の下限と上限は、パーマネントのそれぞれの境界に対応します。実験分析によると、$\gamma_*$の分布は異なるアンサンブルごとに異なりますが、$\gamma_*$は常に$[-1;-1/2]$間隔内にあります。さらに、検討したすべてのアンサンブルについて、$\gamma_*$の挙動は非常に独特であり、FFEアプローチを介して非負行列のパーマネントを推定するための経験的かつ実用的なガイダンスを提供します。
Machine Learning with Operational Costs
運用コストを伴う機械学習
This work proposes a way to align statistical modeling with decision making. We provide a method that propagates the uncertainty in predictive modeling to the uncertainty in operational cost, where operational cost is the amount spent by the practitioner in solving the problem. The method allows us to explore the range of operational costs associated with the set of reasonable statistical models, so as to provide a useful way for practitioners to understand uncertainty. To do this, the operational cost is cast as a regularization term in a learning algorithm’s objective function, allowing either an optimistic or pessimistic view of possible costs, depending on the regularization parameter. From another perspective, if we have prior knowledge about the operational cost, for instance that it should be low, this knowledge can help to restrict the hypothesis space, and can help with generalization. We provide a theoretical generalization bound for this scenario. We also show that learning with operational costs is related to robust optimization.
この研究では、統計モデリングを意思決定と連携させる方法を提案しています。予測モデリングの不確実性を運用コストの不確実性に伝播させる方法を提供します。運用コストとは、実務者が問題を解決するために費やす金額です。この方法により、合理的な統計モデルのセットに関連する運用コストの範囲を調査できるため、実務者が不確実性を理解するための便利な方法を提供できます。これを行うには、運用コストを学習アルゴリズムの目的関数の正則化項としてキャストし、正則化パラメーターに応じて、可能性のあるコストの楽観的または悲観的な見方を可能にします。別の観点から見ると、運用コストについて、たとえば運用コストは低くなければならないという事前知識がある場合、この知識は仮説空間を制限するのに役立ち、一般化に役立ちます。このシナリオの理論的な一般化境界を提供します。また、運用コストを伴う学習が堅牢な最適化に関連していることも示します。
Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting
属性重み付けによる単純ベイズ属性独立性の仮定の軽減
Despite the simplicity of the Naive Bayes classifier, it has continued to perform well against more sophisticated newcomers and has remained, therefore, of great interest to the machine learning community. Of numerous approaches to refining the naive Bayes classifier, attribute weighting has received less attention than it warrants. Most approaches, perhaps influenced by attribute weighting in other machine learning algorithms, use weighting to place more emphasis on highly predictive attributes than those that are less predictive. In this paper, we argue that for naive Bayes attribute weighting should instead be used to alleviate the conditional independence assumption. Based on this premise, we propose a weighted naive Bayes algorithm, called WANBIA, that selects weights to minimize either the negative conditional log likelihood or the mean squared error objective functions. We perform extensive evaluations and find that WANBIA is a competitive alternative to state of the art classifiers like Random Forest, Logistic Regression and A1DE.
ナイーブベイズ分類器はシンプルであるにもかかわらず、より洗練された新参者に対して優れたパフォーマンスを示し続けており、そのため機械学習コミュニティで大きな関心を集め続けています。ナイーブベイズ分類器を改良するための数多くのアプローチのうち、属性の重み付けは、本来受けるべき注目度よりも低い評価を受けています。他の機械学習アルゴリズムの属性の重み付けに影響されたと思われるほとんどのアプローチでは、重み付けを使用して、予測力の低い属性よりも予測力の高い属性に重点を置きます。この論文では、ナイーブベイズの場合、条件付き独立性の仮定を軽減するために属性の重み付けを使用する必要があると主張します。この前提に基づいて、負の条件付き対数尤度または平均二乗誤差の目的関数のいずれかを最小化する重みを選択する、WANBIAと呼ばれる重み付きナイーブベイズアルゴリズムを提案します。広範囲にわたる評価を行った結果、WANBIAは、ランダムフォレスト、ロジスティック回帰、A1DEなどの最先端の分類器に代わる競争力のある方法であることがわかりました。
Generalized Spike-and-Slab Priors for Bayesian Group Feature Selection Using Expectation Propagation
期待伝播を用いたベイジアン群特徴選択のための一般化スパイク/スラブ事前分布
We describe a Bayesian method for group feature selection in linear regression problems. The method is based on a generalized version of the standard spike-and-slab prior distribution which is often used for individual feature selection. Exact Bayesian inference under the prior considered is infeasible for typical regression problems. However, approximate inference can be carried out efficiently using Expectation Propagation (EP). A detailed analysis of the generalized spike-and-slab prior shows that it is well suited for regression problems that are sparse at the group level. Furthermore, this prior can be used to introduce prior knowledge about specific groups of features that are a priori believed to be more relevant. An experimental evaluation compares the performance of the proposed method with those of group LASSO, Bayesian group LASSO, automatic relevance determination and additional variants used for group feature selection. The results of these experiments show that a model based on the generalized spike-and-slab prior and the EP algorithm has state-of-the-art prediction performance in the problems analyzed. Furthermore, this model is also very useful to carry out sequential experimental design (also known as active learning), where the data instances that are most informative are iteratively included in the training set, reducing the number of instances needed to obtain a particular level of prediction accuracy.
私たちは、線形回帰問題におけるグループ特徴選択のためのベイズ法について説明します。この方法は、個々の特徴選択によく使用される標準スパイクアンドスラブ事前分布の一般化バージョンに基づいています。検討されている事前分布の下での正確なベイズ推論は、一般的な回帰問題では実行不可能です。ただし、近似推論は期待伝播(EP)を使用して効率的に実行できます。一般化スパイクアンドスラブ事前分布の詳細な分析により、グループレベルでスパースな回帰問題に適していることが示されています。さらに、この事前分布を使用して、事前に関連性が高いと考えられる特定の特徴グループに関する事前知識を導入できます。実験的評価では、提案された方法のパフォーマンスを、グループLASSO、ベイズ グループLASSO、自動関連性判定、およびグループ特徴選択に使用される追加のバリアントのパフォーマンスと比較します。これらの実験の結果は、一般化スパイクアンドスラブ事前分布とEPアルゴリズムに基づくモデルが、分析された問題で最先端の予測パフォーマンスを持っていることを示しています。さらに、このモデルは、最も有益なデータ インスタンスがトレーニング セットに反復的に組み込まれ、特定のレベルの予測精度を得るために必要なインスタンスの数を削減する、順次実験設計(アクティブ ラーニングとも呼ばれます)を実行する場合にも非常に役立ちます。
Cluster Analysis: Unsupervised Learning via Supervised Learning with a Non-convex Penalty
クラスター分析:非凸ペナルティを持つ教師あり学習による教師なし学習
Clustering analysis is widely used in many fields. Traditionally clustering is regarded as unsupervised learning for its lack of a class label or a quantitative response variable, which in contrast is present in supervised learning such as classification and regression. Here we formulate clustering as penalized regression with grouping pursuit. In addition to the novel use of a non-convex group penalty and its associated unique operating characteristics in the proposed clustering method, a main advantage of this formulation is its allowing borrowing some well established results in classification and regression, such as model selection criteria to select the number of clusters, a difficult problem in clustering analysis. In particular, we propose using the generalized cross-validation (GCV) based on generalized degrees of freedom (GDF) to select the number of clusters. We use a few simple numerical examples to compare our proposed method with some existing approaches, demonstrating our method’s promising performance.
クラスタリング分析は、多くの分野で広く使用されています。従来、クラスタリングは、分類や回帰などの教師あり学習には存在するクラスラベルや定量的応答変数がないため、教師なし学習と見なされています。ここでは、クラスタリングをグループ化の追求を伴うペナルティ付き回帰として定式化します。提案されたクラスタリング法における非凸グループペナルティとそれに関連する独自の動作特性の新しい使用に加えて、この定式化の主な利点は、クラスタリング分析の難しい問題であるクラスターの数を選択するためのモデル選択基準など、分類と回帰で確立されたいくつかの結果を借用できることです。特に、クラスターの数を選択するために、一般化自由度(GDF)に基づく一般化クロスバリデーション(GCV)を使用することを提案します。いくつかの簡単な数値例を使用して、提案された方法をいくつかの既存のアプローチと比較し、方法の有望なパフォーマンスを示します。
Distributions of Angles in Random Packing on Spheres
球体上のランダムパッキングにおける角度の分布
This paper studies the asymptotic behaviors of the pairwise angles among $n$ randomly and uniformly distributed unit vectors in $\mathbb{R}^p$ as the number of points $n\rightarrow \infty$, while the dimension $p$ is either fixed or growing with $n$. For both settings, we derive the limiting empirical distribution of the random angles and the limiting distributions of the extreme angles. The results reveal interesting differences in the two settings and provide a precise characterization of the folklore that âall high-dimensional random vectors are almost always nearly orthogonal to each other”. Applications to statistics and machine learning and connections with some open problems in physics and mathematics are also discussed.
この論文では、点の数$nrightarrow infty$として$mathbb{R}^p$の$n$ランダムおよび一様に分布する単位ベクトル間のペアワイズ角度の漸近的な振る舞いを研究します。一方、次元$p$は固定されているか、$n$とともに成長します。どちらの設定でも、ランダム角度の限定経験的分布と極端角度の限定分布を導き出します。その結果、2つの設定の興味深い違いが明らかになり、「すべての高次元ランダムベクトルはほぼ常に互いに直交している」という民間伝承の正確な特徴付けが提供されます。統計学や機械学習への応用、物理学や数学の未解決問題との関連性についても説明します。
Random Walk Kernels and Learning Curves for Gaussian Process Regression on Random Graphs
ランダムグラフ上のガウス過程回帰のためのランダムウォークカーネルと学習曲線
We consider learning on graphs, guided by kernels that encode similarity between vertices. Our focus is on random walk kernels, the analogues of squared exponential kernels in Euclidean spaces. We show that on large, locally treelike graphs these have some counter-intuitive properties, specifically in the limit of large kernel lengthscales. We consider using these kernels as covariance functions of Gaussian processes. In this situation one typically scales the prior globally to normalise the average of the prior variance across vertices. We demonstrate that, in contrast to the Euclidean case, this generically leads to significant variation in the prior variance across vertices, which is undesirable from a probabilistic modelling point of view. We suggest the random walk kernel should be normalised locally, so that each vertex has the same prior variance, and analyse the consequences of this by studying learning curves for Gaussian process regression. Numerical calculations as well as novel theoretical predictions for the learning curves using belief propagation show that one obtains distinctly different probabilistic models depending on the choice of normalisation. Our method for predicting the learning curves using belief propagation is significantly more accurate than previous approximations and should become exact in the limit of large random graphs.
私たちは、頂点間の類似性をエンコードするカーネルによって導かれるグラフ上の学習について考察します。我々の焦点は、ユークリッド空間における二乗指数カーネルの類似物であるランダム ウォーク カーネルです。大規模で局所的に木のようなグラフでは、特にカーネルの長さスケールが大きい場合、これらには直感に反する特性があることを示す。私たちは、これらのカーネルをガウス過程の共分散関数として使用することを検討しています。この状況では、通常、事前分布をグローバルにスケーリングして、頂点間の事前分布の分散の平均を正規化します。私たちは、ユークリッドの場合とは対照的に、これは一般に、確率モデル化の観点から望ましくない、頂点間の事前分布の分散の大きな変動につながることを示す。私たちは、ランダム ウォーク カーネルをローカルに正規化して、各頂点が同じ事前分布を持つようにすることを提案し、ガウス過程回帰の学習曲線を調べることでその結果を分析します。数値計算と、信念伝播法を使用した学習曲線の新たな理論的予測は、正規化の選択に応じて明確に異なる確率モデルが得られることを示しています。信念伝播法を使用して学習曲線を予測する私たちの方法は、以前の近似値よりも大幅に正確であり、大規模なランダム グラフの限界において正確になるはずです。
Variable Selection in High-Dimension with Random Designs and Orthogonal Matching Pursuit
ランダムデザインと直交マッチング追跡による高次元変数選択
The performance of orthogonal matching pursuit (OMP) for variable selection is analyzed for random designs. When contrasted with the deterministic case, since the performance is here measured after averaging over the distribution of the design matrix, one can have far less stringent sparsity constraints on the coefficient vector. We demonstrate that for exact sparse vectors, the performance of the OMP is similar to known results on the Lasso algorithm (Wainwright, 2009). Moreover, variable selection under a more relaxed sparsity assumption on the coefficient vector, whereby one has only control on the $\ell_1$ norm of the smaller coefficients, is also analyzed. As consequence of these results, we also show that the coefficient estimate satisfies strong oracle type inequalities.
変数選択のための直交マッチング追跡(OMP)の性能は、ランダム計画について分析されます。決定論的なケースと対比すると、ここでは性能が設計行列の分布を平均化して測定されるため、係数ベクトルに対するスパース性制約ははるかに緩やかになります。正確なスパース ベクトルの場合、OMPのパフォーマンスはLassoアルゴリズムの既知の結果と同様であることを示します(Wainwright, 2009)。さらに、係数ベクトルのより緩やかなスパース性の仮定の下での変数選択、つまり、小さい係数の$ell_1$ノルムのみを制御する変数選択も分析されます。これらの結果の結果として、係数推定値が強いオラクルタイプの不等式を満たすことも示しています。
On the Convergence of Maximum Variance Unfolding
最大分散の収束の展開について
Maximum Variance Unfolding is one of the main methods for (nonlinear) dimensionality reduction. We study its large sample limit, providing specific rates of convergence under standard assumptions. We find that it is consistent when the underlying submanifold is isometric to a convex subset, and we provide some simple examples where it fails to be consistent.
Maximum Variance Unfoldingは、(非線形)次元削減の主要な方法の1つです。その大きなサンプル制限を研究し、標準的な仮定の下で特定の収束率を提供します。基礎となる部分多様体が凸部分集合に対して等尺性である場合、それは無矛盾であることがわかりました。また、一貫性がない簡単な例をいくつか提供します。
Similarity-based Clustering by Left-Stochastic Matrix Factorization
左確率行列因数分解による類似度ベースクラスタリング
For similarity-based clustering, we propose modeling the entries of a given similarity matrix as the inner products of the unknown cluster probabilities. To estimate the cluster probabilities from the given similarity matrix, we introduce a left-stochastic non-negative matrix factorization problem. A rotation-based algorithm is proposed for the matrix factorization. Conditions for unique matrix factorizations and clusterings are given, and an error bound is provided. The algorithm is particularly efficient for the case of two clusters, which motivates a hierarchical variant for cases where the number of desired clusters is large. Experiments show that the proposed left-stochastic decomposition clustering model produces relatively high within-cluster similarity on most data sets and can match given class labels, and that the efficient hierarchical variant performs surprisingly well.
類似性ベースのクラスタリングでは、特定の類似性行列のエントリを未知のクラスター確率の内部積としてモデル化することを提案します。与えられた類似度行列からクラスター確率を推定するために、左確率的非負行列因数分解問題を導入します。行列の因数分解には、回転ベースのアルゴリズムが提案されています。一意の行列因数分解とクラスタリングの条件が示され、誤差範囲が提供されます。このアルゴリズムは、2つのクラスターの場合に特に効率的であり、目的のクラスターの数が多い場合に階層バリアントを動機付けます。実験によると、提案された左確率分解クラスタリングモデルは、ほとんどのデータセットで比較的高いクラスター内類似性を生成し、特定のクラスラベルに一致し、効率的な階層バリアントが驚くほど優れたパフォーマンスを発揮することが示されています。
Nonparametric Sparsity and Regularization
ノンパラメトリックなスパース性と正則化
In this work we are interested in the problems of supervised learning and variable selection when the input-output dependence is described by a nonlinear function depending on a few variables. Our goal is to consider a sparse nonparametric model, hence avoiding linear or additive models. The key idea is to measure the importance of each variable in the model by making use of partial derivatives. Based on this intuition we propose a new notion of nonparametric sparsity and a corresponding least squares regularization scheme. Using concepts and results from the theory of reproducing kernel Hilbert spaces and proximal methods, we show that the proposed learning algorithm corresponds to a minimization problem which can be provably solved by an iterative procedure. The consistency properties of the obtained estimator are studied both in terms of prediction and selection performance. An extensive empirical analysis shows that the proposed method performs favorably with respect to the state-of-the-art methods.
この研究では、入出力依存性が少数の変数に依存する非線形関数で記述される場合の教師あり学習と変数選択の問題に着目しています。目標は、スパースなノンパラメトリック モデルを検討し、線形モデルや加法モデルを避けることです。重要なアイデアは、偏微分を利用してモデル内の各変数の重要性を測定することです。この直感に基づいて、ノンパラメトリック スパースの新しい概念と、それに対応する最小二乗正則化スキームを提案します。再生カーネル ヒルベルト空間と近似法の理論の概念と結果を使用して、提案された学習アルゴリズムが、反復手順によって証明可能に解決できる最小化問題に対応することを示します。得られた推定量の一貫性特性は、予測と選択のパフォーマンスの両方の観点から研究されています。広範な実証分析により、提案された方法が最先端の方法と比較して優れていることが示されています。
Dynamic Affine-Invariant Shape-Appearance Handshape Features and Classification in Sign Language Videos
動的アフィン不変形状-外観:手形の特徴と手話ビデオにおける分類
We propose the novel approach of dynamic affine-invariant shape- appearance model (Aff-SAM) and employ it for handshape classification and sign recognition in sign language (SL) videos. Aff-SAM offers a compact and descriptive representation of hand configurations as well as regularized model-fitting, assisting hand tracking and extracting handshape features. We construct SA images representing the hand’s shape and appearance without landmark points. We model the variation of the images by linear combinations of eigenimages followed by affine transformations, accounting for 3D hand pose changes and improving model’s compactness. We also incorporate static and dynamic handshape priors, offering robustness in occlusions, which occur often in signing. The approach includes an affine signer adaptation component at the visual level, without requiring training from scratch a new singer-specific model. We rather employ a short development data set to adapt the models for a new signer. Experiments on the Boston- University-400 continuous SL corpus demonstrate improvements on handshape classification when compared to other feature extraction approaches. Supplementary evaluations of sign recognition experiments, are conducted on a multi-signer, 100-sign data set, from the Greek sign language lemmas corpus. These explore the fusion with movement cues as well as signer adaptation of Aff- SAM to multiple signers providing promising results.
私たちは、動的アフィン不変形状外観モデル(Aff-SAM)という新しいアプローチを提案し、それを手話(SL)ビデオにおける手形の分類と手話認識に採用します。Aff-SAMは、手の構成の簡潔で記述的な表現と正規化されたモデルフィッティングを提供し、手の追跡と手形の特徴の抽出を支援します。私たちは、ランドマーク ポイントのない手の形と外観を表すSA画像を構築します。私たちは、固有画像の線形結合とそれに続くアフィン変換によって画像の変化をモデル化し、3Dの手のポーズの変化を考慮し、モデルのコンパクトさを向上させます。我々はまた、静的および動的な手形の事前分布を組み込み、手話で頻繁に発生するオクルージョンに対する堅牢性を提供します。このアプローチには、視覚レベルでのアフィン手話者適応コンポーネントが含まれており、新しい歌手固有のモデルを最初からトレーニングする必要はありません。私たちは、むしろ、短い開発データ セットを使用して、新しい手話者にモデルを適応させます。ボストン大学400連続手話コーパスの実験では、他の特徴抽出アプローチと比較して、手形の分類が改善されていることが実証されています。手話認識実験の補足評価は、ギリシャ手話レマ コーパスの複数手話者100手話データセットで実施されています。これらは、動きの手がかりとの融合と、Aff-SAMの複数手話者への手話者適応を調査するもので、有望な結果が得られています。
Dimension Independent Similarity Computation
次元に依存しない類似性の計算
We present a suite of algorithms for Dimension Independent Similarity Computation (DISCO) to compute all pairwise similarities between very high-dimensional sparse vectors. All of our results are provably independent of dimension, meaning that apart from the initial cost of trivially reading in the data, all subsequent operations are independent of the dimension; thus the dimension can be very large. We study Cosine, Dice, Overlap, and the Jaccard similarity measures. For Jaccard similarity we include an improved version of MinHash. Our results are geared toward the MapReduce framework. We empirically validate our theorems with large scale experiments using data from the social networking site Twitter. At time of writing, our algorithms are live in production at twitter.com.
私たちは、次元に依存しない類似性計算(DISCO)の一連のアルゴリズムを提示し、非常に高次元のスパース ベクトル間のすべてのペアワイズ 類似性を計算します。すべての結果は次元に依存しないことが証明されており、データを些細に読み取る初期コストを除けば、後続のすべての操作は次元から独立しています。したがって、寸法は非常に大きくなる可能性があります。コサイン、ダイス、オーバーラップ、およびジャカード類似度測定を研究します。Jaccardの類似性のために、MinHashの改良版が含まれています。私たちの結果は、MapReduceフレームワークを対象としています。私たちは、ソーシャルネットワーキングサイトTwitterのデータを使用した大規模な実験により、定理を経験的に検証します。本稿執筆時点では、当社のアルゴリズムはtwitter.comで本番環境で稼働しています。
Sub-Local Constraint-Based Learning of Bayesian Networks Using A Joint Dependence Criterion
同時依存性基準を用いたベイジアンネットワークのサブローカル制約ベース学習
Constraint-based learning of Bayesian networks (BN) from limited data can lead to multiple testing problems when recovering dense areas of the skeleton and to conflicting results in the orientation of edges. In this paper, we present a new constraint-based algorithm, light mutual min (LMM) for improved accuracy of BN learning from small sample data. LMM improves the assessment of candidate edges by using a ranking criterion that considers conditional independence on neighboring variables at both sides of an edge simultaneously. The algorithm also employs an adaptive relaxation of constraints that, selectively, allows some nodes not to condition on some neighbors. This relaxation aims at reducing the incorrect rejection of true edges connecting high degree nodes due to multiple testing. LMM additionally incorporates a new criterion for ranking v-structures that is used to recover the completed partially directed acyclic graph (CPDAG) and to resolve conflicting v-structures, a common problem in small sample constraint-based learning. Using simulated data, each of these components of LMM is shown to significantly improve network inference compared to commonly applied methods when learning from limited data, including more accurate recovery of skeletons and CPDAGs compared to the PC, MaxMin, and MaxMin hill climbing algorithms. A proof of asymptotic correctness is also provided for LMM for recovering the correct skeleton and CPDAG.
限られたデータからのベイジアン ネットワーク(BN)の制約ベースの学習では、スケルトンの密な領域を復元するときに多重テストの問題が発生したり、エッジの向きに矛盾した結果が生じたりすることがあります。この論文では、小規模なサンプル データからのBN学習の精度を向上させるための新しい制約ベースのアルゴリズム、軽量相互最小(LMM)を紹介します。LMMは、エッジの両側の隣接変数の条件付き独立性を同時に考慮するランキング基準を使用して、候補エッジの評価を改善します。このアルゴリズムでは、制約の適応緩和も採用しており、一部のノードが一部の隣接ノードを条件付けないように選択できます。この緩和は、多重テストによる高次ノードを接続する真のエッジの誤った拒否を減らすことを目的としています。LMMには、v構造をランク付けするための新しい基準も組み込まれており、これは、完成した部分有向非巡回グラフ(CPDAG)を復元し、小規模なサンプルの制約ベースの学習でよく発生する問題であるv構造の矛盾を解決するために使用されます。シミュレーション データを使用すると、LMMのこれらの各コンポーネントは、限られたデータから学習する場合に一般的に適用される方法と比較してネットワーク推論を大幅に改善することが示され、PC、MaxMin、およびMaxMinヒル クライミング アルゴリズムと比較してスケルトンとCPDAGのより正確な回復が含まれます。正しいスケルトンとCPDAGを回復するためのLMMの漸近的正しさの証明も提供されます。
Training Energy-Based Models for Time-Series Imputation
時系列代入のためのエネルギーベースモデルの学習
Imputing missing values in high dimensional time-series is a difficult problem. This paper presents a strategy for training energy-based graphical models for imputation directly, bypassing difficulties probabilistic approaches would face. The training strategy is inspired by recent work on optimization-based learning (Domke, 2012) and allows complex neural models with convolutional and recurrent structures to be trained for imputation tasks. In this work, we use this training strategy to derive learning rules for three substantially different neural architectures. Inference in these models is done by either truncated gradient descent or variational mean-field iterations. In our experiments, we found that the training methods outperform the Contrastive Divergence learning algorithm. Moreover, the training methods can easily handle missing values in the training data itself during learning. We demonstrate the performance of this learning scheme and the three models we introduce on one artificial and two real-world data sets.
高次元時系列の欠損値の代入は難しい問題です。この論文では、確率的アプローチが直面する困難を回避し、エネルギーベースのグラフィカルモデルを代入用に直接トレーニングする戦略を紹介します。このトレーニング戦略は、最適化ベースの学習に関する最近の研究(Domke、2012)にヒントを得たもので、畳み込み構造と再帰構造を持つ複雑なニューラルモデルを代入タスク用にトレーニングできます。この研究では、このトレーニング戦略を使用して、3つの大幅に異なるニューラルアーキテクチャの学習ルールを導出します。これらのモデルでの推論は、切り捨て勾配降下法または変分平均場反復法のいずれかによって行われます。実験では、このトレーニング方法がContrastive Divergence学習アルゴリズムよりも優れていることがわかりました。さらに、このトレーニング方法は、学習中にトレーニングデータ自体の欠損値を簡単に処理できます。この学習スキームと、紹介する3つのモデルのパフォーマンスを、1つの人工データセットと2つの実世界のデータセットで実証します。
Improving CUR Matrix Decomposition and the Nystrom Approximation via Adaptive Sampling
適応サンプリングによる CUR 行列分解と Nystrom 近似の改善
The CUR matrix decomposition and the Nystrom approximation are two important low-rank matrix approximation techniques. The Nystrom method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystrom approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystrom algorithms with expected relative-error bounds. The proposed CUR and Nystrom algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystrom method and the ensemble Nystrom method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.
CUR行列分解とニストロム近似は、2つの重要な低ランク行列近似手法です。ニストロム法は対称正半正定値行列を少数の列で近似しますが、CURは任意のデータ行列を少数の列と行で近似します。したがって、CUR分解はニストロム近似の拡張と見なすことができます。この論文では、適応列/行サンプリング アルゴリズムのより一般的な誤差境界を確立し、それに基づいて、期待される相対誤差境界を持つより正確なCURアルゴリズムとニストロム アルゴリズムを提案します。提案されたCURアルゴリズムとニストロム アルゴリズムは、時間計算量も低く、データ行列全体をRAMに保持する必要がありません。さらに、標準ニストロム法とアンサンブルニストロム法の下限誤差境界の理論分析も行います。この論文で確立された主な理論的結果は新しいものであり、分析ではデータ行列に特別な仮定は行っていません。
A Risk Comparison of Ordinary Least Squares vs Ridge Regression
通常の最小二乗法とリッジ回帰のリスク比較
We compare the risk of ridge regression to a simple variant of ordinary least squares, in which one simply projects the data onto a finite dimensional subspace (as specified by a principal component analysis) and then performs an ordinary (un- regularized) least squares regression in this subspace. This note shows that the risk of this ordinary least squares method (PCA-OLS) is within a constant factor (namely 4) of the risk of ridge regression (RR).
私たちは、リッジ回帰のリスクを、データを有限次元部分空間(主成分分析で指定された)に単純に投影し、この部分空間で通常の(非正則化された)最小二乗回帰を実行する通常の最小二乗法の単純な変形と比較します。このノートでは、この通常の最小二乗法(PCA-OLS)のリスクが、リッジ回帰(RR)のリスクの一定因子(つまり4)内にあることを示しています。
Conjugate Relation between Loss Functions and Uncertainty Sets in Classification Problems
分類問題における損失関数と不確定性セットの共役関係
There are two main approaches to binary classification problems: the loss function approach and the uncertainty set approach. The loss function approach is widely used in real-world data analysis. Statistical decision theory has been used to elucidate its properties such as statistical consistency. Conditional probabilities can also be estimated by using the minimum solution of the loss function. In the uncertainty set approach, an uncertainty set is defined for each binary label from training samples. The best separating hyperplane between the two uncertainty sets is used as the decision function. Although the uncertainty set approach provides an intuitive understanding of learning algorithms, its statistical properties have not been sufficiently studied. In this paper, we show that the uncertainty set is deeply connected with the convex conjugate of a loss function. On the basis of the conjugate relation, we propose a way of revising the uncertainty set approach so that it will have good statistical properties such as statistical consistency. We also introduce statistical models corresponding to uncertainty sets in order to estimate conditional probabilities. Finally, we present numerical experiments, verifying that the learning with revised uncertainty sets improves the prediction accuracy.
バイナリ分類問題には、損失関数アプローチと不確実性セットアプローチという2つの主なアプローチがあります。損失関数アプローチは、実世界のデータ分析で広く使用されています。統計的決定理論は、統計的一貫性などのその特性を明らかにするために使用されています。条件付き確率も、損失関数の最小解を使用して推定できます。不確実性セットアプローチでは、トレーニングサンプルからの各バイナリラベルに対して不確実性セットが定義されます。2つの不確実性セット間の最適な分離超平面が決定関数として使用されます。不確実性セットアプローチは、学習アルゴリズムの直感的な理解を提供しますが、その統計的特性は十分に研究されていません。この論文では、不確実性セットが損失関数の凸共役と深く関係していることを示します。共役関係に基づいて、統計的一貫性などの優れた統計的特性を持つように不確実性セットアプローチを修正する方法を提案します。また、条件付き確率を推定するために、不確実性セットに対応する統計モデルを紹介します。最後に、修正された不確実性セットによる学習により予測精度が向上することを検証する数値実験を示します。
Asymptotic Results on Adaptive False Discovery Rate Controlling Procedures Based on Kernel Estimators
カーネル推定器に基づく適応的偽発見率制御手順の漸近結果
The False Discovery Rate (FDR) is a commonly used type I error rate in multiple testing problems. It is defined as the expected False Discovery Proportion (FDP), that is, the expected fraction of false positives among rejected hypotheses. When the hypotheses are independent, the Benjamini-Hochberg procedure achieves FDR control at any pre-specified level. By construction, FDR control offers no guarantee in terms of power, or type II error. A number of alternative procedures have been developed, including plug-in procedures that aim at gaining power by incorporating an estimate of the proportion of true null hypotheses. In this paper, we study the asymptotic behavior of a class of plug-in procedures based on kernel estimators of the density of the $p$-values, as the number $m$ of tested hypotheses grows to infinity. In a setting where the hypotheses tested are independent, we prove that these procedures are asymptotically more powerful in two respects: (i) a tighter asymptotic FDR control for any target FDR level and (ii) a broader range of target levels yielding positive asymptotic power. We also show that this increased asymptotic power comes at the price of slower, non-parametric convergence rates for the FDP. These rates are of the form $m^{-k/(2k+1)}$, where $k$ is determined by the regularity of the density of the $p$-value distribution, or, equivalently, of the test statistics distribution. These results are applied to one- and two-sided tests statistics for Gaussian and Laplace location models, and for the Student model.
偽発見率(FDR)は、多重検定問題でよく使用されるタイプIの誤り率です。これは、期待される偽発見率(FDP)、つまり棄却された仮説の中で偽陽性となる期待される割合として定義されます。仮説が独立している場合、Benjamini-Hochberg手順は、事前に指定された任意のレベルでFDR制御を実現します。構造上、FDR制御は検出力、つまりタイプIIの誤りに関して何の保証もありません。真の帰無仮説の割合の推定値を組み込むことで検出力を高めることを目的としたプラグイン手順など、多くの代替手順が開発されています。この論文では、検定された仮説の数$m$が無限大に増えるにつれて、p値の密度のカーネル推定量に基づくプラグイン手順のクラスの漸近的動作を検討します。検定される仮説が独立している設定では、これらの手順が2つの点で漸近的により強力であることを証明します。(i)任意のターゲットFDRレベルに対するより厳密な漸近的FDR制御、および(ii)正の漸近検出力をもたらすターゲット レベルの範囲の拡大です。また、この漸近検出力の向上は、FDPのより遅い、非パラメトリックな収束速度の代償となることも示します。これらの速度は、形式$m^{-k/(2k+1)}$であり、$k$は$p$値分布の密度の規則性、または同等の検定統計量分布の規則性によって決まります。これらの結果は、ガウスおよびラプラス位置モデル、およびスチューデント モデルの片側および両側検定統計量に適用されます。
JKernelMachines: A Simple Framework for Kernel Machines
JKernelMachines: カーネルマシン用のシンプルなフレームワーク
JKernelMachines is a Java library for learning with kernels. It is primarily designed to deal with custom kernels that are not easily found in standard libraries, such as kernels on structured data. These types of kernels are often used in computer vision or bioinformatics applications. We provide several kernels leading to state of the art classification performances in computer vision, as well as various kernels on sets. The main focus of the library is to be easily extended with new kernels. Standard SVM optimization algorithms are available, but also more sophisticated learning-based kernel combination methods such as Multiple Kernel Learning (MKL), and a recently published algorithm to learn powered products of similarities (Product Kernel Learning).
JKernelMachinesは、カーネルを使用して学習するためのJavaライブラリです。これは主に、構造化データのカーネルなど、標準ライブラリでは簡単に見つからないカスタムカーネルを処理するように設計されています。これらのタイプのカーネルは、コンピュータービジョンやバイオインフォマティクスのアプリケーションでよく使用されます。コンピュータビジョンの最先端の分類性能につながるいくつかのカーネルと、セット上のさまざまなカーネルを提供しています。ライブラリの主な焦点は、新しいカーネルで簡単に拡張できることです。標準のSVM最適化アルゴリズムが利用可能ですが、マルチプルカーネルラーニング(MKL)や、最近公開された類似性のパワード製品を学習するアルゴリズム(プロダクトカーネルラーニング)など、より洗練された学習ベースのカーネル組み合わせ方法も利用できます。
Finding Optimal Bayesian Networks Using Precedence Constraints
優先順位制約を使用した最適なベイジアン ネットワークの検出
We consider the problem of finding a directed acyclic graph (DAG) that optimizes a decomposable Bayesian network score. While in a favorable case an optimal DAG can be found in polynomial time, in the worst case the fastest known algorithms rely on dynamic programming across the node subsets, taking time and space $2^n$, to within a factor polynomial in the number of nodes $n$. In practice, these algorithms are feasible to networks of at most around 30 nodes, mainly due to the large space requirement. Here, we generalize the dynamic programming approach to enhance its feasibility in three dimensions: first, the user may trade space against time; second, the proposed algorithms easily and efficiently parallelize onto thousands of processors; third, the algorithms can exploit any prior knowledge about the precedence relation on the nodes. Underlying all these results is the key observation that, given a partial order $P$ on the nodes, an optimal DAG compatible with $P$ can be found in time and space roughly proportional to the number of ideals of $P$, which can be significantly less than $2^n$. Considering sufficiently many carefully chosen partial orders guarantees that a globally optimal DAG will be found. Aside from the generic scheme, we present and analyze concrete tradeoff schemes based on parallel bucket orders.
私たちは、分解可能なベイジアン ネットワーク スコアを最適化する有向非巡回グラフ(DAG)を見つける問題を考察します。最適なDAGは、状況が良ければ多項式時間で見つけることができますが、最悪の場合、既知の最速アルゴリズムは、ノード サブセット全体の動的プログラミングに依存し、ノード数$n$の多項式係数以内で、時間と空間$2^n$を要します。実際には、これらのアルゴリズムは、主に大きな空間要件のため、最大で約30ノードのネットワークで実行可能です。ここでは、動的プログラミング アプローチを一般化して、3つの次元で実行可能性を高めます。第1に、ユーザーは空間と時間をトレードできます。第2に、提案されたアルゴリズムは、数千のプロセッサ上で簡単かつ効率的に並列化できます。第3に、アルゴリズムは、ノード上の優先順位関係に関する事前の知識を活用できます。これらすべての結果の根底にあるのは、ノード上の部分順序$P$が与えられた場合、$P$と互換性のある最適なDAGは、$P$のイデアルの数にほぼ比例する時間と空間で見つけられるという重要な観察です。これは、$2^n$よりも大幅に少ない場合があります。十分に多くの慎重に選択された部分順序を考慮すると、グローバルに最適なDAGが見つかることが保証されます。一般的なスキームとは別に、並列バケット順序に基づく具体的なトレードオフ スキームを提示して分析します。
Multicategory Large-Margin Unified Machines
マルチカテゴリの大マージン統合マシン
Hard and soft classifiers are two important groups of techniques for classification problems. Logistic regression and Support Vector Machines are typical examples of soft and hard classifiers respectively. The essential difference between these two groups is whether one needs to estimate the class conditional probability for the classification task or not. In particular, soft classifiers predict the label based on the obtained class conditional probabilities, while hard classifiers bypass the estimation of probabilities and focus on the decision boundary. In practice, for the goal of accurate classification, it is unclear which one to use in a given situation. To tackle this problem, the Large-margin Unified Machine (LUM) was recently proposed as a unified family to embrace both groups. The LUM family enables one to study the behavior change from soft to hard binary classifiers. For multicategory cases, however, the concept of soft and hard classification becomes less clear. In that case, class probability estimation becomes more involved as it requires estimation of a probability vector. In this paper, we propose a new Multicategory LUM (MLUM) framework to investigate the behavior of soft versus hard classification under multicategory settings. Our theoretical and numerical results help to shed some light on the nature of multicategory classification and its transition behavior from soft to hard classifiers. The numerical results suggest that the proposed tuned MLUM yields very competitive performance.
ハード分類器とソフト分類器は、分類問題に対する2つの重要な技術グループです。ロジスティック回帰とサポート ベクター マシンは、それぞれソフト分類器とハード分類器の典型的な例です。これら2つのグループの本質的な違いは、分類タスクのクラス条件付き確率を推定する必要があるかどうかです。特に、ソフト分類器は取得したクラス条件付き確率に基づいてラベルを予測しますが、ハード分類器は確率の推定を回避して決定境界に焦点を当てます。実際には、正確な分類という目標のために、特定の状況でどちらを使用すればよいかは不明です。この問題に取り組むために、最近、両方のグループを包含する統合ファミリとしてLarge-margin Unified Machine (LUM)が提案されました。LUMファミリを使用すると、ソフト バイナリ分類器からハード バイナリ分類器への動作の変化を研究できます。ただし、マルチカテゴリの場合、ソフト分類とハード分類の概念は明確ではありません。その場合、クラス確率の推定は、確率ベクトルの推定が必要になるため、より複雑になります。この論文では、マルチカテゴリ設定におけるソフト分類とハード分類の動作を調査するための新しいマルチカテゴリLUM (MLUM)フレームワークを提案します。理論と数値の結果は、マルチカテゴリ分類の性質と、ソフト分類器からハード分類器への移行動作を明らかにするのに役立ちます。数値の結果は、提案された調整されたMLUMが非常に競争力のあるパフォーマンスを生み出すことを示唆しています。
Stochastic Variational Inference
確率的変分推論
We develop stochastic variational inference, a scalable algorithm for approximating posterior distributions. We develop this technique for a large class of probabilistic models and we demonstrate it with two probabilistic topic models, latent Dirichlet allocation and the hierarchical Dirichlet process topic model. Using stochastic variational inference, we analyze several large collections of documents: 300K articles from Nature, 1.8M articles from The New York Times, and 3.8M articles from Wikipedia. Stochastic inference can easily handle data sets of this size and outperforms traditional variational inference, which can only handle a smaller subset. (We also show that the Bayesian nonparametric topic model outperforms its parametric counterpart.) Stochastic variational inference lets us apply complex Bayesian models to massive data sets.
私たちは、事後分布を近似するためのスケーラブルなアルゴリズムである確率的変分推論を開発します。この手法は、大規模な確率モデルに対して開発し、潜在的ディリクレ割り当てと階層的ディリクレ過程トピックモデルの2つの確率的トピックモデルで実証します。確率的変分推論を使用して、Natureの300Kの記事、The New York Timesの180万の記事、Wikipediaの380万の記事など、いくつかの大規模なドキュメントコレクションを分析します。確率的推論は、このサイズのデータセットを簡単に処理でき、より小さなサブセットしか処理できない従来の変分推論よりも優れています。(また、ベイズのノンパラメトリック トピック モデルがパラメトリック トピック モデルよりも優れていることも示しています。確率的変分推論により、複雑なベイズモデルを大規模なデータセットに適用できます。
Regularization-Free Principal Curve Estimation
正則化フリーの主曲線推定
Principal curves and manifolds provide a framework to formulate manifold learning within a statistical context. Principal curves define the notion of a curve passing through the middle of a distribution. While the intuition is clear, the formal definition leads to some technical and practical difficulties. In particular, principal curves are saddle points of the mean- squared projection distance, which poses severe challenges for estimation and model selection. This paper demonstrates that the difficulties in model selection associated with the saddle point property of principal curves are intrinsically tied to the minimization of the mean-squared projection distance. We introduce a new objective function, facilitated through a modification of the principal curve estimation approach, for which all critical points are principal curves and minima. Thus, the new formulation removes the fundamental issue for model selection in principal curve estimation. A gradient-descent- based estimator demonstrates the effectiveness of the new formulation for controlling model complexity on numerical experiments with synthetic and real data.
主曲線と多様体は、統計的コンテキスト内で多様体学習を定式化するためのフレームワークを提供します。主曲線は、分布の中央を通過する曲線の概念を定義します。直感は明確ですが、正式な定義にはいくつかの技術的および実用的な困難が伴います。特に、主曲線は平均二乗投影距離の鞍点であり、推定とモデル選択に深刻な課題をもたらします。この論文では、主曲線の鞍点特性に関連するモデル選択の困難は、平均二乗投影距離の最小化に本質的に結びついていることを示します。主曲線推定アプローチの修正によって促進される新しい目的関数を導入します。この目的関数では、すべての重要なポイントが主曲線と最小値になります。したがって、新しい定式化により、主曲線推定におけるモデル選択の基本的な問題が解消されます。勾配降下ベースの推定器は、合成データと実際のデータを使用した数値実験でモデルの複雑さを制御するための新しい定式化の有効性を実証します。
Random Spanning Trees and the Prediction of Weighted Graphs
ランダムスパニングツリーと重み付きグラフの予測
We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world data sets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice.
私たちは、任意の重み付きグラフのノード上のバイナリラベルを逐次的に予測する問題を調査します。問題の適切なパラメータ化の下で、予測ミスの最適な数は、グラフのランダムスパニングツリーのカットサイズによって(対数因子まで)特徴付けることができることを示します。カットサイズは、グラフノードの未知の敵対的ラベル付けによって誘発されます。特性評価を導出する際に、多項式接続された重み付きグラフ上の最適な誤差範囲を期待値で達成する単純なランダム化アルゴリズムを取得します。このアルゴリズムは、元のグラフのランダムなスパニング ツリーを描画し、このツリーのノードを一定の予想償却時間と線形空間で予測します。実世界のデータセットでの実験では、私たちの方法はグローバル(パーセプトロン)とローカル(ラベル伝播)の両方の方法に匹敵し、実際には一般的に高速であることが示されています。
Manifold Regularization and Semi-supervised Learning: Some Theoretical Analyses
多様体正則化と半教師あり学習:いくつかの理論的解析
Manifold regularization (Belkin et al., 2006) is a geometrically motivated framework for machine learning within which several semi- supervised algorithms have been constructed. Here we try to provide some theoretical understanding of this approach. Our main result is to expose the natural structure of a class of problems on which manifold regularization methods are helpful. We show that for such problems, no supervised learner can learn effectively. On the other hand, a manifold based learner (that knows the manifold or learns it from unlabeled examples) can learn with relatively few labeled examples. Our analysis follows a minimax style with an emphasis on finite sample results (in terms of $n$: the number of labeled examples). These results allow us to properly interpret manifold regularization and related spectral and geometric algorithms in terms of their potential use in semi-supervised learning.
多様体正則化(Belkinら, 2006)は、機械学習のための幾何学的に動機付けられたフレームワークであり、その中でいくつかの半教師ありアルゴリズムが構築されています。ここでは、このアプローチの理論的な理解を提供しようとします。私たちの主な結果は、多様体正則化法が役立つ問題のクラスの自然な構造を明らかにすることです。このような問題に対しては、教師付き学習者は効果的に学習できないことを示します。一方、多様体ベースの学習器(多様体を知っている、またはラベル付けされていない例から学習する)は、比較的少数のラベル付けされた例で学習できます。私たちの分析は、有限のサンプル結果($n$:ラベル付けされた例の数)に重点を置いたミニマックススタイルに従います。これらの結果により、多様体正則化と関連するスペクトルおよび幾何学的アルゴリズムを、半教師あり学習での使用の可能性の観点から適切に解釈することができます。
Performance Bounds for λ Policy Iteration and Application to the Game of Tetris
λ 方策の反復とテトリスゲームへの適用の性能限界
We consider the discrete-time infinite-horizon optimal control problem formalized by Markov decision processes (Puterman, 1994; Bertsekas and Tsitsiklis, 1996). We revisit the work of Bertsekas and Ioffe (1996), that introduced λ policy iteration—a family of algorithms parametrized by a parameter λ—that generalizes the standard algorithms value and policy iteration, and has some deep connections with the temporal-difference algorithms described by Sutton and Barto (1998). We deepen the original theory developed by the authors by providing convergence rate bounds which generalize standard bounds for value iteration described for instance by Puterman (1994). Then, the main contribution of this paper is to develop the theory of this algorithm when it is used in an approximate form. We extend and unify the separate analyzes developed by Munos for approximate value iteration (Munos, 2007) and approximate policy iteration (Munos, 2003), and provide performance bounds in the discounted and the undiscounted situations. Finally, we revisit the use of this algorithm in the training of a Tetris playing controller as originally done by Bertsekas and Ioffe (1996). Our empirical results are different from those of Bertsekas and Ioffe (which were originally qualified as ”paradoxical” and ”intriguing”). We track down the reason to be a minor implementation error of the algorithm, which suggests that, in practice, λ policy iteration may be more stable than previously thought.
私たちは、マルコフ決定過程(Puterman、1994年、BertsekasとTsitsiklis、1996年)によって形式化された離散時間無限時間最適制御問題を考察します。私たちは、λ ポリシー反復(パラメータ λ によってパラメータ化されたアルゴリズム ファミリ)を導入したBertsekasとIoffe (1996年)の研究を再検討します。λ ポリシー反復は、標準的なアルゴリズムである値とポリシー反復を一般化し、SuttonとBarto (1998年)によって説明された時間差分アルゴリズムと深い関係があります。私たちは、例えばPuterman (1994年)によって説明された値反復の標準的な境界を一般化する収束率境界を提供することで、著者らが開発した元の理論を深める。そして、この論文の主な貢献は、近似形式で使用される場合のこのアルゴリズムの理論を展開することです。私たちは、近似値反復(Munos、2007)と近似ポリシー反復(Munos、2003)についてMunosが開発した個別の分析を拡張および統合し、割引された状況と割引されていない状況でのパフォーマンスの境界を示します。最後に、BertsekasとIoffe (1996)が最初に行ったように、テトリスをプレイするコントローラーのトレーニングでこのアルゴリズムを使用することを再検討します。我々の実験結果は、BertsekasとIoffeの結果(当初は「逆説的」かつ「興味深い」と評価されていました)とは異なります。その理由をアルゴリズムの小さな実装エラーであると突き止めました。これは、実際には λ ポリシー反復が以前考えられていたよりも安定している可能性があることを示唆しています。
GPstuff: Bayesian Modeling with Gaussian Processes
GPstuff: ガウス過程によるベイジアンモデリング
The GPstuff toolbox is a versatile collection of Gaussian process models and computational tools required for Bayesian inference. The tools include, among others, various inference methods, sparse approximations and model assessment methods.
GPstuffツールボックスは、ベイズ推論に必要なガウス プロセス モデルと計算ツールの汎用コレクションです。ツールには、さまざまな推論方法、スパース近似、モデル評価方法などが含まれます。
Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing
非線形寸法削減、近接解析、グラフ描画のための応力関数
Multidimensional scaling (MDS) is the art of reconstructing pointsets (embeddings) from pairwise distance data, and as such it is at the basis of several approaches to nonlinear dimension reduction and manifold learning. At present, MDS lacks a unifying methodology as it consists of a discrete collection of proposals that differ in their optimization criteria, called ”stress functions”. To correct this situation we propose (1) to embed many of the extant stress functions in a parametric family of stress functions, and (2) to replace the ad hoc choice among discrete proposals with a principled parameter selection method. This methodology yields the following benefits and problem solutions: (a )It provides guidance in tailoring stress functions to a given data situation, responding to the fact that no single stress function dominates all others across all data situations; (b) the methodology enriches the supply of available stress functions; (c) it helps our understanding of stress functions by replacing the comparison of discrete proposals with a characterization of the effect of parameters on embeddings; (d) it builds a bridge to graph drawing, which is the related but not identical art of constructing embeddings from graphs.
多次元尺度法(MDS)は、ペアワイズ距離データからポイントセット(埋め込み)を再構築する技術であり、非線形次元削減と多様体学習へのいくつかのアプローチの基礎となっています。現在、MDSは「ストレス関数」と呼ばれる最適化基準が異なる個別の提案の集合で構成されているため、統一的な方法論がありません。この状況を修正するために、(1)既存のストレス関数の多くをパラメトリックなストレス関数ファミリーに埋め込み、(2)個別の提案の中からアドホックに選択するのではなく、原則に基づいたパラメーター選択法に置き換えることを提案します。この方法論により、次の利点と問題解決が得られます。(a)すべてのデータ状況で1つのストレス関数が他のすべてのストレス関数を圧倒することはないという事実に対応して、特定のデータ状況に合わせてストレス関数を調整するためのガイダンスを提供します。(b)この方法論により、利用可能なストレス関数の供給が強化されます。(c)個別の提案の比較を、埋め込みに対するパラメーターの影響の特性評価に置き換えることで、ストレス関数の理解に役立ちます。(d)グラフから埋め込みを構築する、関連しているが同じではない技術であるグラフ描画への橋渡しとなります。
Sparse Activity and Sparse Connectivity in Supervised Learning
教師あり学習におけるスパースアクティビティとスパース接続
Sparseness is a useful regularizer for learning in a wide range of applications, in particular in neural networks. This paper proposes a model targeted at classification tasks, where sparse activity and sparse connectivity are used to enhance classification capabilities. The tool for achieving this is a sparseness-enforcing projection operator which finds the closest vector with a pre-defined sparseness for any given vector. In the theoretical part of this paper, a comprehensive theory for such a projection is developed. In conclusion, it is shown that the projection is differentiable almost everywhere and can thus be implemented as a smooth neuronal transfer function. The entire model can hence be tuned end-to-end using gradient-based methods. Experiments on the MNIST database of handwritten digits show that classification performance can be boosted by sparse activity or sparse connectivity. With a combination of both, performance can be significantly better compared to classical non-sparse approaches.
スパース性は、特にニューラル ネットワークにおける幅広いアプリケーションでの学習に役立つ正規化子です。この論文では、分類タスクを対象としたモデルを提案します。このモデルでは、スパースなアクティビティとスパースな接続性を使用して分類機能を強化します。これを実現するためのツールは、スパース性を強化する射影演算子です。この演算子は、任意のベクトルに対して、定義済みのスパース性を持つ最も近いベクトルを見つけます。この論文の理論部分では、このような射影の包括的な理論が開発されています。結論として、射影はほとんどどこでも微分可能であり、したがって滑らかなニューロン伝達関数として実装できることが示されています。したがって、モデル全体を、勾配ベースの方法を使用してエンドツーエンドで調整できます。手書き数字のMNISTデータベースでの実験では、スパースなアクティビティまたはスパースな接続性によって分類パフォーマンスを向上できることが示されています。両方を組み合わせると、従来の非スパース アプローチと比較してパフォーマンスが大幅に向上します。
Beyond Fano’s Inequality: Bounds on the Optimal F-Score, BER, and Cost-Sensitive Risk and Their Implications
Beyond Fano’s Inequality: Bounds on the Optimal F-Score, BER, and Cost-Sensitive Risk and Their Implications
Fano’s inequality lower bounds the probability of transmission error through a communication channel. Applied to classification problems, it provides a lower bound on the Bayes error rate and motivates the widely used Infomax principle. In modern machine learning, we are often interested in more than just the error rate. In medical diagnosis, different errors incur different cost; hence, the overall risk is cost-sensitive. Two other popular criteria are balanced error rate (BER) and F-score. In this work, we focus on the two-class problem and use a general definition of conditional entropy (including Shannon’s as a special case) to derive upper/lower bounds on the optimal F-score, BER and cost-sensitive risk, extending Fano’s result. As a consequence, we show that Infomax is not suitable for optimizing F-score or cost-sensitive risk, in that it can potentially lead to low F-score and high risk. For cost-sensitive risk, we propose a new conditional entropy formulation which avoids this inconsistency. In addition, we consider the common practice of using a threshold on the posterior probability to tune performance of a classifier. As is widely known, a threshold of 0.5, where the posteriors cross, minimizes error rate—we derive similar optimal thresholds for F-score and BER.
ファノの不等式は、通信チャネルを介した伝送エラーの確率を下限値とします。分類問題に適用すると、ベイズエラー率の下限値が提供され、広く使用されているインフォマックス原理の根拠となります。現代の機械学習では、エラー率以外のものも関心の対象になることが多い。医療診断では、エラーによって発生するコストが異なるため、全体的なリスクはコストに敏感です。他の2つの一般的な基準は、バランスエラー率(BER)とFスコアです。この研究では、2クラス問題に焦点を当て、条件付きエントロピーの一般的な定義(特殊なケースとしてシャノンの定義を含む)を使用して、最適なFスコア、BER、コストに敏感なリスクの上限/下限値を導出し、ファノの結果を拡張します。その結果、インフォマックスはFスコアやコストに敏感なリスクの最適化には適していないことが示され、低いFスコアと高いリスクにつながる可能性があります。コストに敏感なリスクについては、この矛盾を回避する新しい条件付きエントロピー定式化を提案します。さらに、事後確率のしきい値を使用して分類器のパフォーマンスを調整する一般的な方法を検討します。広く知られているように、事後確率が交差する0.5のしきい値によりエラー率が最小化されます。FスコアとBERについても同様の最適なしきい値を導き出します。
Bayesian Canonical Correlation Analysis
ベイズ正準相関分析
Mean-field variational methods are widely used for approximate posterior inference in many probabilistic models. In a typical application, mean-field methods approximately compute the posterior with a coordinate-ascent optimization algorithm. When the model is conditionally conjugate, the coordinate updates are easily derived and in closed form. However, many models of interest—like the correlated topic model and Bayesian logistic regression—are nonconjugate. In these models, mean-field methods cannot be directly applied and practitioners have had to develop variational algorithms on a case-by-case basis. In this paper, we develop two generic methods for nonconjugate models, Laplace variational inference and delta method variational inference. Our methods have several advantages: they allow for easily derived variational algorithms with a wide class of nonconjugate models; they extend and unify some of the existing algorithms that have been derived for specific models; and they work well on real-world data sets. We studied our methods on the correlated topic model, Bayesian logistic regression, and hierarchical Bayesian logistic regression.
平均場変分法は、多くの確率モデルにおける近似事後推論に広く使用されています。典型的なアプリケーションでは、平均場法は、座標上昇最適化アルゴリズムを使用して事後を近似的に計算します。モデルが条件付き共役である場合、座標更新は簡単に導出され、閉じた形式になります。ただし、相関トピックモデルやベイズロジスティック回帰などの多くの関心モデルは非共役です。これらのモデルでは、平均場法を直接適用することはできず、実践者はケースバイケースで変分アルゴリズムを開発する必要がありました。この論文では、非共役モデル用の2つの汎用的な方法、ラプラス変分推論とデルタ法変分推論を開発します。私たちの方法には、さまざまな非共役モデルで変分アルゴリズムを簡単に導出できること、特定のモデル用に導出された既存のアルゴリズムの一部を拡張および統合できること、実際のデータ セットでうまく機能することなど、いくつかの利点があります。私たちは相関トピックモデル、ベイズロジスティック回帰、階層ベイズロジスティック回帰に関する手法を研究しました。
Bayesian Canonical Correlation Analysis
ベイズ正準相関分析
Canonical correlation analysis (CCA) is a classical method for seeking correlations between two multivariate data sets. During the last ten years, it has received more and more attention in the machine learning community in the form of novel computational formulations and a plethora of applications. We review recent developments in Bayesian models and inference methods for CCA which are attractive for their potential in hierarchical extensions and for coping with the combination of large dimensionalities and small sample sizes. The existing methods have not been particularly successful in fulfilling the promise yet; we introduce a novel efficient solution that imposes group-wise sparsity to estimate the posterior of an extended model which not only extracts the statistical dependencies (correlations) between data sets but also decomposes the data into shared and data set-specific components. In statistics literature the model is known as inter-battery factor analysis (IBFA), for which we now provide a Bayesian treatment.
正準相関分析(CCA)は、2つの多変量データ セット間の相関関係を調べるための古典的な方法です。過去10年間、この方法は新しい計算定式化と多数のアプリケーションの形で、機械学習コミュニティでますます注目を集めています。階層的拡張の可能性と、大きな次元と小さなサンプル サイズの組み合わせに対処する点で魅力的な、CCAのベイズ モデルと推論方法の最近の開発についてレビューします。既存の方法はまだこの期待に応えることに特に成功していません。そこで、グループ単位のスパース性を課して拡張モデルの事後分布を推定する新しい効率的なソリューションを紹介します。このモデルは、データ セット間の統計的依存関係(相関関係)を抽出するだけでなく、データを共有コンポーネントとデータ セット固有のコンポーネントに分解します。統計の文献では、このモデルはバッテリー間因子分析(IBFA)として知られており、これに対してベイズ処理を提供します。
Query Induction with Schema-Guided Pruning Strategies
スキーマガイド付きプルーニング戦略によるクエリ誘導
Inference algorithms for tree automata that define node selecting queries in unranked trees rely on tree pruning strategies. These impose additional assumptions on node selection that are needed to compensate for small numbers of annotated examples. Pruning-based heuristics in query learning algorithms for Web information extraction often boost the learning quality and speed up the learning process. We will distinguish the class of regular queries that are stable under a given schema-guided pruning strategy, and show that this class is learnable with polynomial time and data. Our learning algorithm is obtained by adding pruning heuristics to the traditional learning algorithm for tree automata from positive and negative examples. While justified by a formal learning model, our learning algorithm for stable queries also performs very well in practice of XML information extraction.
ランク付けされていないツリーのノード選択クエリを定義するツリーオートマトンの推論アルゴリズムは、ツリープルーニング戦略に依存しています。これらは、少数の注釈付き例を補正するために必要なノード選択に追加の仮定を課します。Web情報抽出のためのクエリ学習アルゴリズムのプルーニング ベースのヒューリスティックは、多くの場合、学習品質を向上させ、学習プロセスを高速化します。特定のスキーマガイド付きプルーニング戦略の下で安定している通常のクエリのクラスを区別し、このクラスが多項式の時間とデータで学習可能であることを示します。私たちの学習アルゴリズムは、従来のツリーオートマトンの学習アルゴリズムに、正と負の例から枝刈りヒューリスティックを追加することによって得られます。正式な学習モデルによって正当化されますが、安定したクエリのための学習アルゴリズムは、XML情報抽出の実践でも非常に優れたパフォーマンスを発揮します。
Truncated Power Method for Sparse Eigenvalue Problems
スパース固有値問題に対する切り捨てべき法
This paper considers the sparse eigenvalue problem, which is to extract dominant (largest) sparse eigenvectors with at most k non-zero components. We propose a simple yet effective solution called truncated power method that can approximately solve the underlying nonconvex optimization problem. A strong sparse recovery result is proved for the truncated power method, and this theory is our key motivation for developing the new algorithm. The proposed method is tested on applications such as sparse principal component analysis and the densest k-subgraph problem. Extensive experiments on several synthetic and real-world data sets demonstrate the competitive empirical performance of our method.
この論文では、最大でk個の非ゼロ成分を持つドミナント(最大)スパース固有ベクトルを抽出するスパース固有値問題について考察します。私たちは、基礎となる非凸最適化問題を近似的に解くことができる、切り捨て累乗法と呼ばれる単純で効果的な解決策を提案します。切り捨てられたべき乗法では、強力なスパース回復結果が証明されており、この理論が新しいアルゴリズムを開発する主な動機となっています。提案手法は、スパース主成分分析や最密k-サブグラフ問題などのアプリケーションでテストされています。いくつかの合成データセットと実世界のデータセットに対する広範な実験により、私たちの方法の競争力のある経験的性能が実証されています。
A Widely Applicable Bayesian Information Criterion
広く適用可能なベイズ情報量基準
A statistical model or a learning machine is called regular if the map taking a parameter to a probability distribution is one-to-one and if its Fisher information matrix is always positive definite. If otherwise, it is called singular. In regular statistical models, the Bayes free energy, which is defined by the minus logarithm of Bayes marginal likelihood, can be asymptotically approximated by the Schwarz Bayes information criterion (BIC), whereas in singular models such approximation does not hold. Recently, it was proved that the Bayes free energy of a singular model is asymptotically given by a generalized formula using a birational invariant, the real log canonical threshold (RLCT), instead of half the number of parameters in BIC. Theoretical values of RLCTs in several statistical models are now being discovered based on algebraic geometrical methodology. However, it has been difficult to estimate the Bayes free energy using only training samples, because an RLCT depends on an unknown true distribution. In the present paper, we define a widely applicable Bayesian information criterion (WBIC) by the average log likelihood function over the posterior distribution with the inverse temperature 1/log n, where n is the number of training samples. We mathematically prove that WBIC has the same asymptotic expansion as the Bayes free energy, even if a statistical model is singular for or unrealizable by a statistical model. Since WBIC can be numerically calculated without any information about a true distribution, it is a generalized version of BIC onto singular statistical models.
統計モデルまたは学習マシンは、パラメータを確率分布に写像する写像が1対1であり、そのフィッシャー情報行列が常に正定値である場合に、正則と呼ばれます。そうでない場合は、特異と呼ばれます。正規の統計モデルでは、ベイズ周辺尤度の負の対数で定義されるベイズ自由エネルギーは、シュワルツ ベイズ情報量基準(BIC)によって漸近的に近似できますが、特異モデルでは、このような近似は成り立ちません。最近、特異モデルのベイズ自由エネルギーは、BICのパラメータ数の半分の代わりに、双有理不変量である実対数正準しきい値(RLCT)を使用する一般化式によって漸近的に与えられることが証明されました。現在、いくつかの統計モデルにおけるRLCTの理論値は、代数幾何学的方法論に基づいて発見されています。しかし、RLCTは未知の真の分布に依存するため、トレーニング サンプルのみを使用してベイズ自由エネルギーを推定することは困難でした。この論文では、逆温度1/log nの事後分布の平均対数尤度関数によって、広く適用可能なベイズ情報量基準(WBIC)を定義します(nはトレーニング サンプルの数)。統計モデルが に対して特異であるか、統計モデルによって実現不可能である場合でも、WBICはベイズ自由エネルギーと同じ漸近展開を持つことを数学的に証明します。WBICは真の分布に関する情報がなくても数値的に計算できるため、特異統計モデルへのBICの一般化バージョンです。
Quasi-Newton Method: A New Direction
準ニュートン法:新たな方向性
Four decades after their invention, quasi-Newton methods are still state of the art in unconstrained numerical optimization. Although not usually interpreted thus, these are learning algorithms that fit a local quadratic approximation to the objective function. We show that many, including the most popular, quasi-Newton methods can be interpreted as approximations of Bayesian linear regression under varying prior assumptions. This new notion elucidates some shortcomings of classical algorithms, and lights the way to a novel nonparametric quasi-Newton method, which is able to make more efficient use of available information at computational cost similar to its predecessors.
発明から40年経った今でも、準ニュートン法は制約のない数値最適化の最先端です。通常はこのように解釈されませんが、これらは目的関数に局所的な二次近似を適合させる学習アルゴリズムです。最も一般的な準ニュートン法を含む多くの法が、さまざまな事前の仮定の下でベイズ線形回帰の近似として解釈できることを示します。この新しい概念は、古典的なアルゴリズムのいくつかの欠点を解明し、新しいノンパラメトリック準ニュートン法への道を照らし、前任者と同様の計算コストで利用可能な情報をより効率的に利用できるようになります。
Greedy Sparsity-Constrained Optimization
貪欲なスパース性制約付き最適化
Sparsity-constrained optimization has wide applicability in machine learning, statistics, and signal processing problems such as feature selection and Compressed Sensing. A vast body of work has studied the sparsity-constrained optimization from theoretical, algorithmic, and application aspects in the context of sparse estimation in linear models where the fidelity of the estimate is measured by the squared error. In contrast, relatively less effort has been made in the study of sparsity-constrained optimization in cases where nonlinear models are involved or the cost function is not quadratic. In this paper we propose a greedy algorithm, Gradient Support Pursuit (GraSP), to approximate sparse minima of cost functions of arbitrary form. Should a cost function have a Stable Restricted Hessian (SRH) or a Stable Restricted Linearization (SRL), both of which are introduced in this paper, our algorithm is guaranteed to produce a sparse vector within a bounded distance from the true sparse optimum. Our approach generalizes known results for quadratic cost functions that arise in sparse linear regression and Compressed Sensing. We also evaluate the performance of GraSP through numerical simulations on synthetic and real data, where the algorithm is employed for sparse logistic regression with and without l2-regularization.
スパース性制約最適化は、機械学習、統計、および特徴選択や圧縮センシングなどの信号処理の問題に幅広く適用できます。推定値の忠実度が二乗誤差で測定される線形モデルにおけるスパース推定のコンテキストで、スパース性制約最適化を理論的、アルゴリズム的、および応用的な側面から研究した研究は数多くあります。対照的に、非線形モデルが関係している場合やコスト関数が2次でない場合のスパース性制約最適化の研究には、比較的少ない努力しか払われていません。この論文では、任意の形式のコスト関数のスパース最小値を近似する貪欲アルゴリズム、Gradient Support Pursuit (GraSP)を提案します。コスト関数に安定制限ヘッセ行列(SRH)または安定制限線形化(SRL) (どちらも本稿で紹介されています)がある場合、私たちのアルゴリズムは、真のスパース最適値から制限された距離内でスパースベクトルを生成することが保証されます。私たちのアプローチは、スパース線形回帰と圧縮センシングで生じる二次コスト関数の既知の結果を一般化します。また、合成データと実際のデータに対する数値シミュレーションを通じてGraSPのパフォーマンスを評価します。このアルゴリズムは、l2正則化の有無にかかわらず、スパース ロジスティック回帰に使用されます。
MLPACK: A Scalable C++ Machine Learning Library
MLPACK: スケーラブルな C++ 機械学習ライブラリ
MLPACK is a state-of-the-art, scalable, multi-platform C++ machine learning library released in late 2011 offering both a simple, consistent API accessible to novice users and high performance and flexibility to expert users by leveraging modern features of C++. MLPACK provides cutting-edge algorithms whose benchmarks exhibit far better performance than other leading machine learning libraries. MLPACK version 1.0.3, licensed under the LGPL, is available at www.mlpack.org.
MLPACKは、2011年後半にリリースされた最先端のスケーラブルなマルチプラットフォームC++機械学習ライブラリであり、C++の最新機能を活用して、初心者ユーザーでもアクセス可能なシンプルで一貫性のあるAPIと、エキスパート ユーザー向けの高いパフォーマンスと柔軟性の両方を提供します。MLPACKは、ベンチマークが他の主要な機械学習ライブラリよりもはるかに優れたパフォーマンスを示す最先端のアルゴリズムを提供します。LGPLの下でライセンスされたMLPACKバージョン1.0.3は、www.mlpack.orgで入手できます。
Semi-Supervised Learning Using Greedy Max-Cut
Greedy Max-Cutを用いた半教師あり学習
Graph-based semi-supervised learning (SSL) methods play an increasingly important role in practical machine learning systems, particularly in agnostic settings when no parametric information or other prior knowledge is available about the data distribution. Given the constructed graph represented by a weight matrix, transductive inference is used to propagate known labels to predict the values of all unlabeled vertices. Designing a robust label diffusion algorithm for such graphs is a widely studied problem and various methods have recently been suggested. Many of these can be formalized as regularized function estimation through the minimization of a quadratic cost. However, most existing label diffusion methods minimize a univariate cost with the classification function as the only variable of interest. Since the observed labels seed the diffusion process, such univariate frameworks are extremely sensitive to the initial label choice and any label noise. To alleviate the dependency on the initial observed labels, this article proposes a bivariate formulation for graph-based SSL, where both the binary label information and a continuous classification function are arguments of the optimization. This bivariate formulation is shown to be equivalent to a linearly constrained Max-Cut problem. Finally an efficient solution via greedy gradient Max-Cut (GGMC) is derived which gradually assigns unlabeled vertices to each class with minimum connectivity. Once convergence guarantees are established, this greedy Max-Cut based SSL is applied on both artificial and standard benchmark data sets where it obtains superior classification accuracy compared to existing state-of-the-art SSL methods. Moreover, GGMC shows robustness with respect to the graph construction method and maintains high accuracy over extensive experiments with various edge linking and weighting schemes.
グラフベースの半教師あり学習(SSL)法は、実用的な機械学習システム、特にデータ分布に関するパラメトリック情報やその他の事前知識が利用できないアグノスティック設定でますます重要な役割を果たしています。重み行列で表される構築されたグラフが与えられた場合、トランスダクティブ推論を使用して既知のラベルを伝播し、ラベルのないすべての頂点の値を予測します。このようなグラフの堅牢なラベル拡散アルゴリズムの設計は広く研究されている問題であり、最近さまざまな方法が提案されています。これらの多くは、2次コストの最小化による正規化関数推定として形式化できます。ただし、既存のラベル拡散法のほとんどは、分類関数を唯一の対象変数として単変量コストを最小化します。観測されたラベルが拡散プロセスのシードとなるため、このような単変量フレームワークは、初期ラベルの選択とラベル ノイズに非常に敏感です。初期観測ラベルへの依存を軽減するために、この記事では、グラフベースのSSLの2変量定式化を提案します。この定式化では、バイナリ ラベル情報と連続分類関数の両方が最適化の引数となります。この二変量定式化は、線形制約付きMax-Cut問題と同等であることが示されています。最後に、最小の接続性を持つ各クラスにラベルなしの頂点を徐々に割り当てる、貪欲勾配Max-Cut (GGMC)による効率的なソリューションが導出されます。収束保証が確立されると、この貪欲Max-CutベースのSSLは、人工データ セットと標準ベンチマーク データ セットの両方に適用され、既存の最先端のSSL方法と比較して優れた分類精度が得られます。さらに、GGMCはグラフ構築方法に関して堅牢性を示し、さまざまなエッジ リンクと重み付けスキームを使用した広範な実験で高い精度を維持します。
Sparsity Regret Bounds for Individual Sequences in Online Linear Regression
オンライン線形回帰における個々のシーケンスのスパース性後悔限界
We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T. We introduce the notion of sparsity regret bound, which is a deterministic online counterpart of recent risk bounds derived in the stochastic setting under a sparsity scenario. We prove such regret bounds for an online-learning algorithm called SeqSEW and based on exponential weighting and data-driven truncation. In a second part we apply a parameter-free version of this algorithm to the stochastic setting (regression model with random design). This yields risk bounds of the same flavor as in Dalalyan and Tsybakov (2012a) but which solve two questions left open therein. In particular our risk bounds are adaptive (up to a logarithmic factor) to the unknown variance of the noise if the latter is Gaussian. We also address the regression model with fixed design.
私たちは、周囲次元dが時間ラウンド数tよりはるかに大きくなる可能性がある場合の任意の決定論的シーケンス上のオンライン線形回帰の問題を考えます。スパース性後悔バウンドの概念を紹介しますが、これは、スパース性シナリオの下で確率的設定で導出された最近のリスクバウンドの決定論的なオンライン対応物です。このような後悔の範囲を、SeqSEWと呼ばれる、指数関数的重み付けとデータ駆動型の切り捨てに基づくオンライン学習アルゴリズムで証明します。第2部では、このアルゴリズムのパラメータフリーバージョンを確率的設定(ランダム設計の回帰モデル)に適用します。これにより、Dalalyan and Tsybakov (2012a)と同じフレーバーのリスク境界が得られますが、そこに未解決のまま残された2つの問題を解決します。特に、リスク境界は、ノイズがガウス分布である場合のノイズの未知の分散に対して(対数係数まで)適応します。また、固定設計による回帰モデルにも取り組みます。
Differential Privacy for Functions and Functional Data
機能と機能データの差分プライバシー
Differential privacy is a rigorous cryptographically-motivated characterization of data privacy which may be applied when releasing summaries of a database. Previous work has focused mainly on methods for which the output is a finite dimensional vector, or an element of some discrete set. We develop methods for releasing functions while preserving differential privacy. Specifically, we show that adding an appropriate Gaussian process to the function of interest yields differential privacy. When the functions lie in the reproducing kernel Hilbert space (RKHS) generated by the covariance kernel of the Gaussian process, then the correct noise level is established by measuring the “sensitivity” of the function in the RKHS norm. As examples we consider kernel density estimation, kernel support vector machines, and functions in RKHSs.
差分プライバシーは、データベースの要約をリリースするときに適用できる、データプライバシーの厳密な暗号に動機付けられた特性です。以前の研究では、主に出力が有限次元ベクトル、または離散集合の要素である方法に焦点を当ててきました。私たちは、差分プライバシーを維持しながら関数を解放する方法を開発します。具体的には、適切なガウス過程を利子の機能に加えると、差分プライバシーが得られることを示します。関数がガウス過程の共分散カーネルによって生成された再生カーネルヒルベルト空間(RKHS)にある場合、RKHSノルムの関数の「感度」を測定することにより、正しいノイズレベルが確立されます。例として、カーネル密度推定、カーネルサポートベクターマシン、およびRKHSの関数について考えます。
Bayesian Nonparametric Hidden Semi-Markov Models
ベイズノンパラメトリック隠れセミマルコフモデル
There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM’s strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markov modeling, which has been developed mainly in the parametric non-Bayesian setting, to allow construction of highly interpretable models that admit natural prior information on state durations. In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semi-Markov Model (HDP-HSMM) and develop sampling algorithms for efficient posterior inference. The methods we introduce also provide new methods for sampling inference in the finite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments.
階層的ディリクレ過程隠れマルコフモデル(HDP-HMM)は、時系列データや時系列データから学習するための、広く普及している隠れマルコフモデルの自然なベイジアン非パラメトリック拡張として、大きな関心を集めています。しかし、多くの設定では、特に非幾何学的な状態持続時間を学習またはエンコードしたい場合には、HDP-HMMの厳格なマルコフ制約は望ましくありません。主にパラメトリック非ベイジアン設定で開発されてきた明示的持続時間半マルコフモデリングを利用することで、HDP-HMMを拡張してそのような構造を捉えることができ、状態持続時間に関する自然な事前情報を許容する高度に解釈可能なモデルの構築が可能になります。この論文では、明示的持続時間階層的ディリクレ過程隠れマルコフモデル(HDP-HSMM)を紹介し、効率的な事後推論のためのサンプリングアルゴリズムを開発します。紹介する方法は、有限ベイジアンHSMMでのサンプリング推論のための新しい方法も提供します。私たちのモジュール式ギブス サンプリング法は、より大規模な階層型ベイズ モデルのサンプラーに組み込むことができ、ベイズ推論ツールボックスの別のツールとしてセミマルコフ連鎖モデリングを追加できます。合成実験と実際の実験の両方で、HDP-HSMMと推論法の有用性を実証します。
CODA: High Dimensional Copula Discriminant Analysis
CODA: 高次元コピュラ判別分析
We propose a high dimensional classification method, named the Copula Discriminant Analysis (CODA). The CODA generalizes the normal-based linear discriminant analysis to the larger Gaussian Copula models (or the nonparanormal) as proposed by Liu et al. (2009). To simultaneously achieve estimation efficiency and robustness, the nonparametric rank-based methods including the Spearman’s rho and Kendall’s tau are exploited in estimating the covariance matrix. In high dimensional settings, we prove that the sparsity pattern of the discriminant features can be consistently recovered with the parametric rate, and the expected misclassification error is consistent to the Bayes risk. Our theory is backed up by careful numerical experiments, which show that the extra flexibility gained by the CODA method incurs little efficiency loss even when the data are truly Gaussian. These results suggest that the CODA method can be an alternative choice besides the normal-based high dimensional linear discriminant analysis.
私たちは、コピュラ判別分析(CODA)という高次元分類法を提案します。CODAは、Liuら(2009)が提案したように、正規ベースの線形判別分析をより大きなガウス コピュラ モデル(または非パラノーマル)に一般化します。推定効率と堅牢性を同時に達成するために、共分散行列の推定には、スピアマンのローやケンドールのタウなどのノンパラメトリック ランク ベースの方法を利用します。高次元設定では、判別特徴のスパース パターンをパラメトリック レートで一貫して回復できること、および予測される誤分類エラーがベイズ リスクと一貫していることを証明しています。我々の理論は、慎重な数値実験によって裏付けられており、CODA法によって得られる追加の柔軟性は、データが真にガウス分布である場合でも、効率の低下をほとんど引き起こさないことがわかっています。これらの結果は、CODA法が正規ベースの高次元線形判別分析の代替選択肢になり得ることを示唆しています。
A C++ Template-Based Reinforcement Learning Library: Fitting the Code to the Mathematics
C++ テンプレートベースの強化学習ライブラリ: コードを数学に適合させる
This paper introduces the rllib as an original C++ template-based library oriented toward value function estimation. Generic programming is promoted here as a way of having a good fit between the mathematics of reinforcement learning and their implementation in a library. The main concepts of rllib are presented, as well as a short example.
この論文では、値関数推定を目的としたC++テンプレートベースのオリジナルライブラリとしてrllibについて紹介します。ここでは、ジェネリック プログラミングは、強化学習の数学とライブラリでの実装との間にうまく適合する方法として推進されています。rllibの主な概念と、短い例を示します。
Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality
確率論的専門家のアドバイスによる最適発見:有限時間解析と巨視的最適性
We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an algorithm based on the optimistic paradigm and on the Good-Turing missing mass estimator. We prove two different regret bounds on the performance of this algorithm under weak assumptions on the probabilistic experts. Under more restrictive hypotheses, we also prove a macroscopic optimality result, comparing the algorithm both with an oracle strategy and with uniform sampling. Finally, we provide numerical experiments illustrating these theoretical findings.
私たちは、電力システムのセキュリティ分析の問題から生じる元の問題を検討し、確率論的な専門家のアドバイスで最適な発見と名付けます。楽観的なパラダイムとグッドチューリングの欠落質量推定量に基づくアルゴリズムでこれに対処します。このアルゴリズムのパフォーマンスについて、確率論的専門家の弱い仮定の下で、2つの異なる後悔の範囲を証明します。より限定的な仮説の下では、アルゴリズムをオラクル戦略と一様サンプリングの両方と比較することで、巨視的な最適性の結果も証明します。最後に、これらの理論的知見を示す数値実験を提供します。
Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
正則化損失最小化のための確率的双座標上昇法
Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications.
確率的勾配降下法(SGD)は、その強力な理論的保証により、SVMなどの大規模な教師あり機械学習最適化問題を解決するために人気を博しています。密接に関連するDual Coordinate Ascent (DCA)法は、さまざまなソフトウェア パッケージに実装されていますが、これまでのところ、優れた収束解析が欠けていました。この論文では、ストキャスティック二重座標上昇法(SDCA)の新しい分析を提示し、このクラスの方法がSGDと同等またはそれ以上の強力な理論的保証を享受していることを示しています。この分析は、SDCAの実用化に対する有効性を正当化するものです。
Algorithms for Discovery of Multiple Markov Boundaries
複数のマルコフ境界を発見するためのアルゴリズム
Algorithms for Markov boundary discovery from data constitute an important recent development in machine learning, primarily because they offer a principled solution to the variable/feature selection problem and give insight on local causal structure. Over the last decade many sound algorithms have been proposed to identify a single Markov boundary of the response variable. Even though faithful distributions and, more broadly, distributions that satisfy the intersection property always have a single Markov boundary, other distributions/data sets may have multiple Markov boundaries of the response variable. The latter distributions/data sets are common in practical data-analytic applications, and there are several reasons why it is important to induce multiple Markov boundaries from such data. However, there are currently no sound and efficient algorithms that can accomplish this task. This paper describes a family of algorithms TIE* that can discover all Markov boundaries in a distribution. The broad applicability as well as efficiency of the new algorithmic family is demonstrated in an extensive benchmarking study that involved comparison with 26 state-of-the-art algorithms/variants in 15 data sets from a diversity of application domains.
データからマルコフ境界を発見するアルゴリズムは、主に変数/特徴選択問題に原理的な解決策を提供し、局所的な因果構造に関する洞察を与えることから、機械学習における最近の重要な開発です。過去10年間で、応答変数の単一のマルコフ境界を識別するための健全なアルゴリズムが多数提案されてきました。忠実な分布、およびより広義には交差特性を満たす分布は常に単一のマルコフ境界を持ちますが、他の分布/データ セットは応答変数の複数のマルコフ境界を持つ場合があります。後者の分布/データ セットは実際のデータ分析アプリケーションで一般的であり、そのようなデータから複数のマルコフ境界を誘導することが重要である理由はいくつかあります。ただし、現在、このタスクを実行できる健全で効率的なアルゴリズムはありません。この論文では、分布内のすべてのマルコフ境界を発見できるアルゴリズム ファミリTIE*について説明します。新しいアルゴリズム ファミリの幅広い適用性と効率性は、さまざまなアプリケーション ドメインの15のデータ セットにおける26の最先端のアルゴリズム/バリアントとの比較を含む広範なベンチマーク調査で実証されています。
A Theory of Multiclass Boosting
多クラスブースティングの理論
Boosting combines weak classifiers to form highly accurate predictors. Although the case of binary classification is well understood, in the multiclass setting, the “correct” requirements on the weak classifier, or the notion of the most efficient boosting algorithms are missing. In this paper, we create a broad and general framework, within which we make precise and identify the optimal requirements on the weak-classifier, as well as design the most effective, in a certain sense, boosting algorithms that assume such requirements.
ブースティングは、弱い分類子を組み合わせて、非常に正確な予測子を形成します。二項分類のケースはよく理解されていますが、多クラス設定では、弱い分類器の”正しい”要件、または最も効率的なブースティング アルゴリズムの概念が欠落しています。この論文では、弱分類器の最適な要件を正確に特定し、そのような要件を仮定するある意味で最も効果的なブースティングアルゴリズムを設計する、広範で一般的なフレームワークを作成します。
Ranked Bandits in Metric Spaces: Learning Diverse Rankings over Large Document Collections
メートル法空間のランク付けされたバンディット:大規模なドキュメントコレクションに対する多様なランキングの学習
Most learning to rank research has assumed that the utility of different documents is independent, which results in learned ranking functions that return redundant results. The few approaches that avoid this have rather unsatisfyingly lacked theoretical foundations, or do not scale. We present a learning-to-rank formulation that optimizes the fraction of satisfied users, with several scalable algorithms that explicitly takes document similarity and ranking context into account. Our formulation is a non-trivial common generalization of two multi-armed bandit models from the literature: ranked bandits (Radlinski et al., 2008) and Lipschitz bandits (Kleinberg et al., 2008b). We present theoretical justifications for this approach, as well as a near-optimal algorithm. Our evaluation adds optimizations that improve empirical performance, and shows that our algorithms learn orders of magnitude more quickly than previous approaches.
研究のランク付け学習のほとんどは、異なるドキュメントの有用性が独立していると想定しており、その結果、冗長な結果を返す学習されたランキング関数が発生します。これを回避する数少ないアプローチは、理論的な基盤が欠けていたり、スケールがなかったりします。満足しているユーザーの割合を最適化するlearning-to-rank定式化と、ドキュメントの類似性とランキング コンテキストを明示的に考慮したいくつかのスケーラブルなアルゴリズムを紹介します。私たちの定式化は、文献からの2つの多腕バンディットモデルの自明ではない共通の一般化です:ランク付けされたバンディット(Radlinskiら, 2008)とリプシッツバンディット(Kleinbergら, 2008b)。このアプローチの理論的な正当性と、最適に近いアルゴリズムを示します。私たちの評価では、経験的パフォーマンスを向上させる最適化が追加され、アルゴリズムが以前のアプローチよりも桁違いに速く学習することが示されています。
Fast Generalized Subset Scan for Anomalous Pattern Detection
異常パターン検出のための高速一般化サブセットスキャン
We propose Fast Generalized Subset Scan (FGSS), a new method for detecting anomalous patterns in general categorical data sets. We frame the pattern detection problem as a search over subsets of data records and attributes, maximizing a nonparametric scan statistic over all such subsets. We prove that the nonparametric scan statistics possess a novel property that allows for efficient optimization over the exponentially many subsets of the data without an exhaustive search, enabling FGSS to scale to massive and high-dimensional data sets. We evaluate the performance of FGSS in three real-world application domains (customs monitoring, disease surveillance, and network intrusion detection), and demonstrate that FGSS can successfully detect and characterize relevant patterns in each domain. As compared to three other recently proposed detection algorithms, FGSS substantially decreased run time and improved detection power for massive multivariate data sets.
私たちは、一般的なカテゴリデータセットの異常なパターンを検出するための新しい方法である高速一般化サブセットスキャン(FGSS)を提案します。パターン検出の問題は、データ レコードと属性のサブセットに対する検索として組み立てられ、そのようなすべてのサブセットでノンパラメトリック スキャン統計を最大化します。私たちは、ノンパラメトリックスキャン統計が、徹底的な検索を行わずにデータの指数関数的多数のサブセットに対して効率的な最適化を可能にする新しい特性を持っていることを証明し、FGSSを大規模で高次元のデータセットに拡張できることを証明します。3つの実際のアプリケーションドメイン(税関監視、疾病監視、ネットワーク侵入検出)でFGSSのパフォーマンスを評価し、FGSSが各ドメインの関連パターンを正常に検出して特徴付けることができることを実証します。最近提案された他の3つの検出アルゴリズムと比較して、FGSSは実行時間を大幅に短縮し、大規模な多変量データセットの検出能力を向上させました。
On the Learnability of Shuffle Ideals
シャッフルの理想の学習可能性について
PAC learning of unrestricted regular languages is long known to be a difficult problem. The class of shuffle ideals is a very restricted subclass of regular languages, where the shuffle ideal generated by a string $u$ is the collection of all strings containing $u$ as a subsequence. This fundamental language family is of theoretical interest in its own right and provides the building blocks for other important language families. Despite its apparent simplicity, the class of shuffle ideals appears quite difficult to learn. In particular, just as for unrestricted regular languages, the class is not properly PAC learnable in polynomial time if RP $\neq$ NP, and PAC learning the class improperly in polynomial time would imply polynomial time algorithms for certain fundamental problems in cryptography. In the positive direction, we give an efficient algorithm for properly learning shuffle ideals in the statistical query (and therefore also PAC) model under the uniform distribution.
PACによる制限のない正規言語の学習は、難しい問題であることが長い間知られています。シャッフル理想のクラスは、文字列$u$によって生成されるシャッフル理想が、サブシーケンスとして$u$を含むすべての文字列のコレクションである、通常の言語の非常に制限されたサブクラスです。この基本的な言語ファミリーは、それ自体が理論的な関心事であり、他の重要な言語ファミリーの構成要素を提供します。その見かけの単純さにもかかわらず、シャッフルの理想のクラスは学ぶのが非常に難しいように見えます。特に、制限のない正規言語と同様に、RP $neq$ NPの場合、クラスは多項式時間で適切にPAC学習可能ではなく、PACが多項式時間でクラスを不適切に学習すると、暗号学の特定の基本的な問題に対する多項式時間アルゴリズムが暗示されます。正の方向には、一様分布の下で統計クエリ(したがってPAC)モデルでシャッフル理想を適切に学習するための効率的なアルゴリズムを提供します。
A Framework for Evaluating Approximation Methods for Gaussian Process Regression
ガウス過程回帰の近似法評価フレームワーク
Gaussian process (GP) predictors are an important component of many Bayesian approaches to machine learning. However, even a straightforward implementation of Gaussian process regression (GPR) requires O(n2) space and O(n3) time for a data set of n examples. Several approximation methods have been proposed, but there is a lack of understanding of the relative merits of the different approximations, and in what situations they are most useful. We recommend assessing the quality of the predictions obtained as a function of the compute time taken, and comparing to standard baselines (e.g., Subset of Data and FITC). We empirically investigate four different approximation algorithms on four different prediction problems, and make our code available to encourage future comparisons.
ガウス過程(GP)予測子は、機械学習に対する多くのベイズアプローチの重要な要素です。ただし、ガウス過程回帰(GPR)の単純な実装でも、n個の例のデータセットにはO(n2)スペースとO(n3)時間が必要です。いくつかの近似方法が提案されていますが、さまざまな近似の相対的なメリットと、それらが最も役立つ状況についての理解が不足しています。得られた予測の品質は、計算にかかった時間の関数として評価し、標準的なベースライン(データのサブセットやFITCなど)と比較することをお勧めします。4つの異なる予測問題に対して4つの異なる近似アルゴリズムを経験的に調査し、将来の比較を促進するためにコードを利用できるようにします。
Using Symmetry and Evolutionary Search to Minimize Sorting Networks
対称性と進化的探索を使用してソートネットワークを最小化する
Sorting networks are an interesting class of parallel sorting algorithms with applications in multiprocessor computers and switching networks. They are built by cascading a series of comparison-exchange units called comparators. Minimizing the number of comparators for a given number of inputs is a challenging optimization problem. This paper presents a two-pronged approach called Symmetry and Evolution based Network Sort Optimization (SENSO) that makes it possible to scale the solutions to networks with a larger number of inputs than previously possible. First, it uses the symmetry of the problem to decompose the minimization goal into subgoals that are easier to solve. Second, it minimizes the resulting greedy solutions further by using an evolutionary algorithm to learn the statistical distribution of comparators in minimal networks. The final solutions improve upon half-century of results published in patents, books, and peer-reviewed literature, demonstrating the potential of the SENSO approach for solving difficult combinatorial problems.
ソーティング ネットワークは、マルチプロセッサ コンピュータやスイッチング ネットワークに応用される、興味深い並列ソーティング アルゴリズムのクラスです。これらは、コンパレータと呼ばれる一連の比較交換ユニットをカスケード接続することで構築されます。与えられた入力数に対するコンパレータの数を最小化することは、困難な最適化問題です。この論文では、対称性と進化に基づくネットワーク ソート最適化(SENSO)と呼ばれる2本柱のアプローチを紹介します。このアプローチにより、従来よりも多くの入力を持つネットワークにソリューションを拡張できます。まず、問題の対称性を使用して、最小化目標を解決しやすいサブ目標に分解します。次に、進化的アルゴリズムを使用して最小ネットワーク内のコンパレータの統計的分布を学習することにより、結果として得られる貪欲なソリューションをさらに最小化します。最終的なソリューションは、特許、書籍、査読済み文献で公開された半世紀にわたる結果を改善し、困難な組み合わせの問題を解決するためのSENSOアプローチの可能性を示しています。
Sparse Single-Index Model
スパース シングル インデックス モデル
Let (X, Y) be a random pair taking values in ℝp × ℝ. In the so-called single-index model, one has Y=f*(θ* TX)+W, where f* is an unknown univariate measurable function, θ* is an unknown vector in ℝd, and W denotes a random noise satisfying E[W|X]=0. The single-index model is known to offer a flexible way to model a variety of high-dimensional real-world phenomena. However, despite its relative simplicity, this dimension reduction scheme is faced with severe complications as soon as the underlying dimension becomes larger than the number of observations (‘p larger than n’ paradigm). To circumvent this difficulty, we consider the single-index model estimation problem from a sparsity perspective using a PAC-Bayesian approach. On the theoretical side, we offer a sharp oracle inequality, which is more powerful than the best known oracle inequalities for other common procedures of single-index recovery. The proposed method is implemented by means of the reversible jump Markov chain Monte Carlo technique and its performance is compared with that of standard procedures.
(X, Y)を ℝp× ℝ の値を取るランダムなペアとします。いわゆるシングルインデックスモデルでは、Y=f*(θ* TX)+Wとなります。ここで、f*は未知の一変量測定可能関数、θ*は ℝdの未知のベクトル、WはE[W|X]=0を満たすランダムノイズを表します。シングルインデックスモデルは、さまざまな高次元の現実世界の現象をモデル化する柔軟な方法を提供することが知られています。ただし、比較的単純であるにもかかわらず、この次元削減スキームは、基礎となる次元が観測数よりも大きくなるとすぐに深刻な複雑さに直面します(「pがnより大きい」パラダイム)。この困難を回避するために、PACベイズアプローチを使用して、スパース性の観点からシングルインデックスモデルの推定問題を考察します。理論面では、他の一般的なシングルインデックス回復手順の最もよく知られているオラクル不等式よりも強力なシャープなオラクル不等式を提供します。提案された方法は、可逆ジャンプ マルコフ連鎖モンテ カルロ法によって実装され、そのパフォーマンスが標準的な手順のパフォーマンスと比較されます。
MAGIC Summoning: Towards Automatic Suggesting and Testing of Gestures With Low Probability of False Positives During Use
MAGIC召喚:使用中の誤検知の可能性が低いジェスチャーの自動提案とテストに向けて
Gestures for interfaces should be short, pleasing, intuitive, and easily recognized by a computer. However, it is a challenge for interface designers to create gestures easily distinguishable from users’ normal movements. Our tool MAGIC Summoning addresses this problem. Given a specific platform and task, we gather a large database of unlabeled sensor data captured in the environments in which the system will be used (an ‘Everyday Gesture Library’ or EGL). The EGL is quantized and indexed via multi-dimensional Symbolic Aggregate approXimation (SAX) to enable quick searching. MAGIC exploits the SAX representation of the EGL to suggest gestures with a low likelihood of false triggering. Suggested gestures are ordered according to brevity and simplicity, freeing the interface designer to focus on the user experience. Once a gesture is selected, MAGIC can output synthetic examples of the gesture to train a chosen classifier (for example, with a hidden Markov model). If the interface designer suggests his own gesture and provides several examples, MAGIC estimates how accurately that gesture can be recognized and estimates its false positive rate by comparing it against the natural movements in the EGL. We demonstrate MAGIC’s effectiveness in gesture selection and helpfulness in creating accurate gesture recognizers.
インターフェースのジェスチャは、短く、心地よく、直感的で、コンピュータに簡単に認識されるものでなければなりません。しかし、インターフェース設計者にとって、ユーザーの通常の動作と簡単に区別できるジェスチャを作成することは困難です。弊社のツールMAGIC Summoningは、この問題に対処します。特定のプラットフォームとタスクが与えられた場合、システムが使用される環境でキャプチャされたラベルなしのセンサー データの大規模なデータベース(「Everyday Gesture Library」またはEGL)を収集します。EGLは、多次元Symbolic Aggregate approXimation (SAX)によって量子化およびインデックス付けされ、迅速な検索が可能になります。MAGICは、EGLのSAX表現を利用して、誤トリガーの可能性が低いジェスチャを提案します。提案されたジェスチャは、簡潔さと単純さに従って順序付けられるため、インターフェース設計者はユーザー エクスペリエンスに集中できます。ジェスチャが選択されると、MAGICは、選択された分類器(たとえば、隠れマルコフ モデルを使用)をトレーニングするために、ジェスチャの合成例を出力できます。インターフェイス デザイナーが独自のジェスチャを提案し、いくつかの例を提供すると、MAGICはそのジェスチャがどの程度正確に認識されるかを推定し、EGLの自然な動きと比較して誤検出率を推定します。MAGICがジェスチャの選択に効果的であること、および正確なジェスチャ認識機能を作成する上で役立つことを実証します。
Lower Bounds and Selectivity of Weak-Consistent Policies in Stochastic Multi-Armed Bandit Problem
確率的多腕バンディット問題における弱無矛盾方策の下限と選択性
This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistency, and exhibit a generalisation of the bound. We also study the existence of logarithmic bounds in general and in the case of Hannan consistency. Moreover, we prove that it is impossible to design an adaptive policy that would select the best of two algorithms by taking advantage of the properties of the environment. To get these results, we study variants of popular Upper Confidence Bounds (UCB) policies.
この論文では、確率的多腕バンディットの古典モデルにおける後悔の下限に専念しています。ライとロビンズのよく知られた結果は、その後バーネタスとカテハキスによって拡張され、すべての一貫した政策に対する対数的な境界の存在を確立しました。私たちは一貫性の概念を緩和し、境界の一般化を示します。また、一般に対数境界の存在と、ハナン整合性の場合についても研究します。さらに、環境の特性を利用して、2つのアルゴリズムのうち最良のものを選択する適応型ポリシーを設計することは不可能であることを証明します。これらの結果を得るために、一般的な信頼上限(UCB)ポリシーのバリアントを調査します。
Universal Consistency of Localized Versions of Regularized Kernel Methods
正規化されたカーネルメソッドのローカライズされたバージョンのユニバーサル一貫性
In supervised learning problems, global and local learning algorithms are used. In contrast to global learning algorithms, the prediction of a local learning algorithm in a testing point is only based on training data which are close to the testing point. Every global algorithm such as support vector machines (SVM) can be localized in the following way: in every testing point, the (global) learning algorithm is not applied to the whole training data but only to the k nearest neighbors (kNN) of the testing point. In case of support vector machines, the success of such mixtures of SVM and kNN (called SVM-KNN) has been shown in extensive simulation studies and also for real data sets but only little has been known on theoretical properties so far. In the present article, it is shown how a large class of regularized kernel methods (including SVM) can be localized in order to get a universally consistent learning algorithm.
教師あり学習問題では、グローバル学習アルゴリズムとローカル学習アルゴリズムが使用されます。グローバル学習アルゴリズムとは対照的に、テストポイントでのローカル学習アルゴリズムの予測は、テストポイントに近いトレーニングデータのみに基づいています。サポートベクターマシン(SVM)などのすべてのグローバルアルゴリズムは、次の方法でローカライズできます:すべてのテストポイントで、(グローバル)学習アルゴリズムはトレーニングデータ全体に適用されるのではなく、テストポイントのk最近傍(kNN)にのみ適用されます。サポートベクターマシンの場合、このようなSVMとkNN(SVM-KNN)の混合物の成功は、広範なシミュレーション研究や実際のデータセットでも示されていますが、理論的な特性についてはこれまでほとんど知られていませんでした。この記事では、汎用的に一貫性のある学習アルゴリズムを得るために、正規化されたカーネルメソッド(SVMを含む)の大規模なクラスをローカライズする方法を示します。
Pairwise Likelihood Ratios for Estimation of Non-Gaussian Structural Equation Models
非ガウス構造方程式モデルの推定のためのペアワイズ尤度比
We present new measures of the causal direction, or direction of effect, between two non-Gaussian random variables. They are based on the likelihood ratio under the linear non-Gaussian acyclic model (LiNGAM). We also develop simple first-order approximations of the likelihood ratio and analyze them based on related cumulant-based measures, which can be shown to find the correct causal directions. We show how to apply these measures to estimate LiNGAM for more than two variables, and even in the case of more variables than observations. We further extend the method to cyclic and nonlinear models. The proposed framework is statistically at least as good as existing ones in the cases of few data points or noisy data, and it is computationally and conceptually very simple. Results on simulated fMRI data indicate that the method may be useful in neuroimaging where the number of time points is typically quite small.
私たちは、2つの非ガウス確率変数間の因果方向、または効果の方向の新しい尺度を提示します。これらは、線形非ガウス非巡回モデル(LiNGAM)の下での尤度比に基づいています。また、尤度比の単純な1次近似を作成し、関連する累積ベースの測定に基づいてそれらを分析します。これにより、正しい因果関係の方向を見つけることを示すことができます。これらの尺度を適用して、2つ以上の変数についてLiNGAMを推定する方法、さらには観測値よりも多くの変数の場合でもLiNGAMを推定する方法を示します。この手法をさらに、周期モデルと非線形モデルに拡張します。提案されたフレームワークは、データポイントが少ないかノイズの多いデータの場合、統計的には少なくとも既存のフレームワークと同程度に優れており、計算的にも概念的にも非常に単純です。シミュレートされたfMRIデータの結果は、この方法が、通常、時点の数が非常に少ないニューロイメージングに役立つ可能性があることを示しています。
Nested Expectation Propagation for Gaussian Process Classification with a Multinomial Probit Likelihood
多項プロビット尤度を持つガウス過程分類のための枝分かれ期待伝播
This paper considers probabilistic multinomial probit classification using Gaussian process (GP) priors. Challenges with multiclass GP classification are the integration over the non-Gaussian posterior distribution, and the increase of the number of unknown latent variables as the number of target classes grows. Expectation propagation (EP) has proven to be a very accurate method for approximate inference but the existing EP approaches for the multinomial probit GP classification rely on numerical quadratures, or independence assumptions between the latent values associated with different classes, to facilitate the computations. In this paper we propose a novel nested EP approach which does not require numerical quadratures, and approximates accurately all between-class posterior dependencies of the latent values, but still scales linearly in the number of classes. The predictive accuracy of the nested EP approach is compared to Laplace, variational Bayes, and Markov chain Monte Carlo (MCMC) approximations with various benchmark data sets. In the experiments nested EP was the most consistent method compared to MCMC sampling, but in terms of classification accuracy the differences between all the methods were small from a practical point of view.
この論文では、ガウス過程(GP)事前分布を使用した確率的多項プロビット分類について検討します。多クラスGP分類の課題は、非ガウス事後分布の積分と、対象クラスの数が増えるにつれて未知の潜在変数の数が増えることです。期待値伝播(EP)は近似推論の非常に正確な方法であることが証明されていますが、多項プロビットGP分類の既存のEPアプローチは、計算を容易にするために、数値求積法、または異なるクラスに関連付けられた潜在値間の独立仮定に依存しています。この論文では、数値求積法を必要とせず、潜在値のクラス間事後依存性をすべて正確に近似しながらも、クラス数に比例してスケールする、新しいネストされたEPアプローチを提案します。ネストされたEPアプローチの予測精度を、さまざまなベンチマーク データ セットを使用して、ラプラス、変分ベイズ、およびマルコフ連鎖モンテカルロ(MCMC)近似と比較します。実験では、ネストされたEPはMCMCサンプリングと比較して最も一貫性のある方法でしたが、分類精度の点では、実用的な観点からはすべての方法間の違いは小さいものでした。
Ranking Forests
森林のランキング
The present paper examines how the aggregation and feature randomization principles underlying the algorithm RANDOM FOREST (Breiman, 2001) can be adapted to bipartite ranking. The approach taken here is based on nonparametric scoring and ROC curve optimization in the sense of the AUC criterion. In this problem, aggregation is used to increase the performance of scoring rules produced by ranking trees, as those developed in Clémençon and Vayatis (2009c). The present work describes the principles for building median scoring rules based on concepts from rank aggregation. Consistency results are derived for these aggregated scoring rules and an algorithm called RANKING FOREST is presented. Furthermore, various strategies for feature randomization are explored through a series of numerical experiments on artificial data sets.
この論文では、アルゴリズムRANDOM FOREST(Breiman、2001)の基礎となる集約と特徴のランダム化の原理を二者ランキングにどのように適応できるかを検討します。ここで採用するアプローチは、ノンパラメトリック スコアリングとAUC基準の意味でのROC曲線最適化に基づいています。この問題では、Clémençon and Vayatis(2009c)で開発されたものと同様に、ツリーのランク付けによって生成されたスコアリングルールのパフォーマンスを向上させるために集計が使用されます。この研究では、ランク集計の概念に基づいて中央値のスコアリングルールを構築するための原則について説明します。これらの集約されたスコアリング ルールの一貫性の結果が導き出され、RANKING FORESTと呼ばれるアルゴリズムが表示されます。さらに、特徴量のランダム化のためのさまざまな戦略が、人工データセットに対する一連の数値実験を通じて探求されています。
Global Analytic Solution of Fully-observed Variational Bayesian Matrix Factorization
全観測変分ベイジアン行列因数分解の全球解析解
The variational Bayesian (VB) approximation is known to be a promising approach to Bayesian estimation, when the rigorous calculation of the Bayes posterior is intractable. The VB approximation has been successfully applied to matrix factorization (MF), offering automatic dimensionality selection for principal component analysis. Generally, finding the VB solution is a non-convex problem, and most methods rely on a local search algorithm derived through a standard procedure for the VB approximation. In this paper, we show that a better option is available for fully-observed VBMF—the global solution can be analytically computed. More specifically, the global solution is a reweighted SVD of the observed matrix, and each weight can be obtained by solving a quartic equation with its coefficients being functions of the observed singular value. We further show that the global optimal solution of empirical VBMF (where hyperparameters are also learned from data) can also be analytically computed. We illustrate the usefulness of our results through experiments in multi-variate analysis.
変分ベイズ(VB)近似は、ベイズ事後分布の厳密な計算が困難な場合にベイズ推定を行う有望な手法として知られています。VB近似は行列因子分解(MF)にうまく適用されており、主成分分析の次元の自動選択を提供しています。一般に、VB解を見つけることは非凸問題であり、ほとんどの方法はVB近似の標準手順から導出される局所探索アルゴリズムに依存しています。この論文では、完全観測VBMFに、より優れたオプション、つまりグローバル解を解析的に計算できることを示します。より具体的には、グローバル解は観測行列の再重み付けされたSVDであり、各重みは、係数が観測された特異値の関数である4次方程式を解くことで取得できます。さらに、経験的VBMF (ハイパーパラメータもデータから学習される)のグローバル最適解も解析的に計算できることを示します。私たちは多変量解析の実験を通じて私たちの結果の有用性を示します。
