partykit: A Modular Toolkit for Recursive Partytioning in R
partykit: R での再帰的なパーティションのためのモジュール式ツールキット
The R package partykit provides a flexible toolkit for learning, representing, summarizing, and visualizing a wide range of tree- structured regression and classification models. The functionality encompasses: (a) basic infrastructure for representing trees (inferred by any algorithm) so that unified print/plot/predict methods are available; (b) dedicated methods for trees with constant fits in the leaves (or terminal nodes) along with suitable coercion functions to create such trees (e.g., by rpart, RWeka, PMML); (c) a reimplementation of conditional inference trees (ctree, originally provided in the party package); (d) an extended reimplementation of model-based recursive partitioning (mob, also originally in party) along with dedicated methods for trees with parametric models in the leaves. Here, a brief overview of the package and its design is given while more detailed discussions of items (a)—(d) are available in vignettes accompanying the package.
Rパッケージpartykitは、さまざまなツリー構造回帰モデルと分類モデルを学習、表現、要約、視覚化するための柔軟なツールキットを提供します。機能には以下が含まれます:(a)統一された印刷/プロット/予測方法が利用可能になるように、ツリーを表現するための基本的なインフラストラクチャ(任意のアルゴリズムによって推論されます)。(b)葉(または末端ノード)に一定のフィットを持つ樹木のための専用の方法と、そのような樹木を作成するための適切な強制関数(例えば、rpart、RWeka、PMMLによる)と、(c)条件付き推論ツリー(CTree、元々はPartyパッケージで提供されていたもの)の再実装。(d)モデルベースの再帰的分割(MOB、元々はパーティーに含まれていた)の拡張再実装と、葉にパラメトリック モデルを持つ樹木の専用メソッド。ここでは、パッケージとそのデザインの概要を簡単に説明し、(a)〜(d)のアイテムの詳細については、パッケージに付属のビネットで説明します。
PAC Optimal MDP Planning with Application to Invasive Species Management
PAC最適MDP計画と侵入種管理への応用
In a simulator-defined MDP, the Markovian dynamics and rewards are provided in the form of a simulator from which samples can be drawn. This paper studies MDP planning algorithms that attempt to minimize the number of simulator calls before terminating and outputting a policy that is approximately optimal with high probability. The paper introduces two heuristics for efficient exploration and an improved confidence interval that enables earlier termination with probabilistic guarantees. We prove that the heuristics and the confidence interval are sound and produce with high probability an approximately optimal policy in polynomial time. Experiments on two benchmark problems and two instances of an invasive species management problem show that the improved confidence intervals and the new search heuristics yield reductions of between 8% and 47% in the number of simulator calls required to reach near- optimal policies.
シミュレータ定義のMDPでは、マルコフのダイナミクスと報酬がシミュレータの形で提供され、そこからサンプルを抽出できます。この論文では、シミュレータ呼び出しの数を最小限に抑えてから終了し、ほぼ最適なポリシーを高い確率で出力しようとするMDP計画アルゴリズムについて学習します。この論文では、効率的な探索のための2つのヒューリスティックと、確率的保証による早期終了を可能にする信頼区間の改善について紹介しています。ヒューリスティックと信頼区間が健全であり、多項式時間でほぼ最適な方策を高い確率で生成することを証明します。2つのベンチマーク問題と侵入種管理問題の2つのインスタンスに関する実験では、改善された信頼区間と新しい探索ヒューリスティックにより、最適に近い方策に到達するために必要なシミュレータ呼び出しの数が8%から47%減少することが示されています。
Marginalizing Stacked Linear Denoising Autoencoders
マージナライジング、スタック型リニア、デナイジングオートエンコーダ
Stacked denoising autoencoders (SDAs) have been successfully used to learn new representations for domain adaptation. They have attained record accuracy on standard benchmark tasks of sentiment analysis across different text domains. SDAs learn robust data representations by reconstruction, recovering original features from data that are artificially corrupted with noise. In this paper, we propose marginalized Stacked Linear Denoising Autoencoder (mSLDA) that addresses two crucial limitations of SDAs: high computational cost and lack of scalability to high-dimensional features. In contrast to SDAs, our approach of mSLDA marginalizes noise and thus does not require stochastic gradient descent or other optimization algorithms to learn parameters — in fact, the linear formulation gives rise to a closed-form solution. Consequently, mSLDA, which can be implemented in only 20 lines of MATLAB, is about two orders of magnitude faster than a corresponding SDA. Furthermore, the representations learnt by mSLDA are as effective as the traditional SDAs, attaining almost identical accuracies in benchmark tasks.
スタック型ノイズ除去オートエンコーダ(SDA)は、ドメイン適応のための新しい表現の学習に効果的に使用されており、さまざまなテキスト ドメインにわたる感情分析の標準ベンチマーク タスクで記録的な精度を達成しています。SDAは、再構築によって堅牢なデータ表現を学習し、ノイズによって人工的に破損したデータから元の特徴を回復します。この論文では、計算コストの高さと高次元の特徴へのスケーラビリティの欠如という、SDAの2つの重要な制限に対処する、マージナライズド スタック型線形ノイズ除去オートエンコーダ(mSLDA)を提案します。SDAとは対照的に、mSLDAのアプローチはノイズをマージナライズするため、パラメータを学習するために確率的勾配降下法やその他の最適化アルゴリズムを必要としません。実際、線形定式化により、閉じた形式のソリューションが生成されます。その結果、MATLABのわずか20行で実装できるmSLDAは、対応するSDAよりも約2桁高速です。さらに、mSLDAによって学習された表現は従来のSDAと同様に効果的であり、ベンチマーク タスクでほぼ同じ精度を達成します。
Graphical Models via Univariate Exponential Family Distributions
単変量指数族分布によるグラフィカルモデル
Undirected graphical models, or Markov networks, are a popular class of statistical models, used in a wide variety of applications. Popular instances of this class include Gaussian graphical models and Ising models. In many settings, however, it might not be clear which subclass of graphical models to use, particularly for non-Gaussian and non-categorical data. In this paper, we consider a general sub-class of graphical models where the node-wise conditional distributions arise from exponential families. This allows us to derive multivariate graphical model distributions from univariate exponential family distributions, such as the Poisson, negative binomial, and exponential distributions. Our key contributions include a class of M-estimators to fit these graphical model distributions; and rigorous statistical analysis showing that these M-estimators recover the true graphical model structure exactly, with high probability. We provide examples of genomic and proteomic networks learned via instances of our class of graphical models derived from Poisson and exponential distributions.
無向グラフィカル モデル、またはマルコフ ネットワークは、統計モデルの一般的なクラスであり、さまざまなアプリケーションで使用されています。このクラスの一般的な例としては、ガウス グラフィカル モデルやイジング モデルがあります。ただし、多くの場合、特に非ガウスおよび非カテゴリ データの場合は、どのグラフィカル モデルのサブクラスを使用するかが明確でない場合があります。この論文では、ノードごとの条件付き分布が指数族から生じるグラフィカル モデルの一般的なサブクラスを検討します。これにより、ポアソン分布、負の二項分布、指数分布などの単変量指数族分布から多変量グラフィカル モデル分布を導出できます。私たちの主な貢献には、これらのグラフィカル モデル分布に適合するM推定量のクラスと、これらのM推定量が真のグラフィカル モデル構造を高い確率で正確に復元することを示す厳密な統計分析が含まれます。ポアソン分布と指数分布から導出されたグラフィカル モデルのクラスのインスタンスを介して学習されたゲノム ネットワークとプロテオーム ネットワークの例を示します。
Condition for Perfect Dimensionality Recovery by Variational Bayesian PCA
変分ベイジアンPCAによる完全次元回復の条件
Having shown its good performance in many applications, variational Bayesian (VB) learning is known to be one of the best tractable approximations to Bayesian learning. However, its performance was not well understood theoretically. In this paper, we clarify the behavior of VB learning in probabilistic PCA (or fully-observed matrix factorization). More specifically, we establish a necessary and sufficient condition for perfect dimensionality (or rank) recovery in the large-scale limit when the matrix size goes to infinity. Our result theoretically guarantees the performance of VB-PCA. At the same time, it also reveals the conservative nature of VB learning— it offers a low false positive rate at the expense of low sensitivity. By contrasting with an alternative dimensionality selection method, we characterize VB learning in PCA. In our analysis, we obtain bounds of the noise variance estimator, and a new and simple analytic-form solution for the other parameters, which themselves are useful for implementation of VB-PCA.
多くのアプリケーションで優れたパフォーマンスを示している変分ベイズ(VB)学習は、ベイズ学習の最も扱いやすい近似法の1つとして知られています。しかし、そのパフォーマンスは理論的には十分に理解されていませんでした。この論文では、確率的PCA (または完全観測行列分解)におけるVB学習の動作を明らかにします。より具体的には、行列サイズが無限大になる大規模限界で完全な次元(またはランク)回復のための必要十分条件を確立します。私たちの結果は、理論的にVB-PCAのパフォーマンスを保証します。同時に、VB学習の保守的な性質も明らかにします。つまり、感度が低い代わりに、偽陽性率が低いということです。別の次元選択方法と対比することで、PCAにおけるVB学習を特徴付けます。私たちの分析では、ノイズ分散推定量の範囲と、VB-PCAの実装に役立つ他のパラメーターの新しい単純な解析形式のソリューションを取得します。
Non-Asymptotic Analysis of a New Bandit Algorithm for Semi-Bounded Rewards
半有界報酬のための新しいバンディットアルゴリズムの非漸近解析
In this paper we consider a stochastic multiarmed bandit problem. It is known in this problem that Deterministic Minimum Empirical Divergence (DMED) policy achieves the asymptotic theoretical bound for the model where each reward distribution is supported in a known bounded interval, say $[0,1]$. However, the regret bound of DMED is described in an asymptotic form and the performance in finite time has been unknown. We modify this policy and derive a finite-time regret bound for the new policy, Indexed Minimum Empirical Divergence (IMED), by refining large deviation probabilities to a simple non-asymptotic form. Further, the refined analysis reveals that the finite-time regret bound is valid even in the case that the reward is not bounded from below. Therefore, our finite-time result applies to the case that the minimum reward (that is, the maximum loss) is unknown or unbounded. We also present some simulation results which shows that IMED much improves DMED and performs competitively to other state-of-the-art policies.
この論文では、確率的多腕バンディット問題を考察します。この問題では、決定論的最小経験的ダイバージェンス(DMED)ポリシーが、各報酬分布が既知の有界区間、たとえば$[0,1]$でサポートされているモデルの漸近理論的境界を達成することが知られています。しかし、DMEDの後悔境界は漸近形式で記述され、有限時間でのパフォーマンスは不明であった。このポリシーを修正し、大偏差確率を単純な非漸近形式に改良することで、新しいポリシーであるインデックス付き最小経験的ダイバージェンス(IMED)の有限時間後悔境界を導出します。さらに、改良された分析により、報酬が下から制限されていない場合でも有限時間の後悔境界が有効であることが明らかになった。したがって、有限時間の結果は、最小報酬(つまり、最大損失)が不明または無制限の場合にも適用されます。また、IMEDがDMEDを大幅に改善し、他の最先端のポリシーと競争力のあるパフォーマンスを発揮することを示すシミュレーション結果もいくつか示します。
Learning to Identify Concise Regular Expressions that Describe Email Campaigns
メールキャンペーンを説明する簡潔な正規表現を特定する方法を学ぶ
This paper addresses the problem of inferring a regular expression from a given set of strings that resembles, as closely as possible, the regular expression that a human expert would have written to identify the language. This is motivated by our goal of automating the task of postmasters who use regular expressions to describe and blacklist email spam campaigns. Training data contains batches of messages and corresponding regular expressions that an expert postmaster feels confident to blacklist. We model this task as a two-stage learning problem with structured output spaces and appropriate loss functions. We derive decoders and the resulting optimization problems which can be solved using standard cutting plane methods. We report on a case study conducted with an email service provider.
この論文では、特定の文字列セットから、人間の専門家が言語を識別するために記述した正規表現にできるだけ近い正規表現を推論する問題に取り組んでいます。これは、正規表現を使用して電子メールスパムキャンペーンを説明およびブラックリストに登録するポストマスターのタスクを自動化するという私たちの目標によって動機付けられています。トレーニングデータには、専門のポストマスターが自信を持ってブラックリストに登録できると感じるメッセージのバッチと対応する正規表現が含まれています。この課題は、構造化された出力空間と適切な損失関数を持つ2段階の学習問題としてモデル化します。デコーダとその結果として得られる最適化問題を導き出し、標準的な切断面法を使用して解くことができます。メールサービスプロバイダーと共同で実施したケーススタディについて報告します。
Supervised Learning via Euler’s Elastica Models
オイラーのエラスティカモデルによる教師あり学習
This paper investigates the Euler’s elastica (EE) model for high-dimensional supervised learning problems in a function approximation framework. In 1744 Euler introduced the elastica energy for a 2D curve on modeling torsion-free thin elastic rods. Together with its degenerate form of total variation (TV), Euler’s elastica has been successfully applied to low- dimensional data processing such as image denoising and image inpainting in the last two decades. Our motivation is to apply Euler’s elastica to high-dimensional supervised learning problems. To this end, a supervised learning problem is modeled as an energy functional minimization under a new geometric regularization scheme, where the energy is composed of a squared loss and an elastica penalty. The elastica penalty aims at regularizing the approximated function by heavily penalizing large gradients and high curvature values on all level curves. We take a computational PDE approach to minimize the energy functional. By using variational principles, the energy minimization problem is transformed into an Euler-Lagrange PDE. However, this PDE is usually high-dimensional and can not be directly handled by common low-dimensional solvers. To circumvent this difficulty, we use radial basis functions (RBF) to approximate the target function, which reduces the optimization problem to finding the linear coefficients of these basis functions. Some theoretical properties of this new model, including the existence and uniqueness of solutions and universal consistency, are analyzed. Extensive experiments have demonstrated the effectiveness of the proposed model for binary classification, multi-class classification, and regression tasks.
この論文では、関数近似フレームワークにおける高次元教師あり学習問題に対するオイラーのエラスティカ(EE)モデルについて検討します。1744年にオイラーは、ねじれのない細い弾性棒のモデリングにおいて、2D曲線のエラスティカ エネルギーを導入した。オイラーのエラスティカは、その退化した全変動(TV)形式とともに、過去20年間で画像のノイズ除去や画像修復などの低次元データ処理にうまく適用されてきた。本稿の目的は、オイラーのエラスティカを高次元教師あり学習問題に適用することです。この目的のため、教師あり学習問題は、エネルギーが損失の二乗とエラスティカ ペナルティで構成される新しい幾何学的正則化スキームの下でのエネルギー関数最小化としてモデル化されます。エラスティカ ペナルティは、すべてのレベルの曲線で大きな勾配と高い曲率値に重いペナルティを課すことによって、近似関数を正則化することを目的としています。この論文では、エネルギー関数を最小化するために計算PDEアプローチを採用します。変分原理を使用することで、エネルギー最小化問題はオイラー・ラグランジュ偏微分方程式に変換されます。ただし、この偏微分方程式は通常高次元であり、一般的な低次元ソルバーでは直接処理できません。この困難を回避するために、ラジアル基底関数(RBF)を使用してターゲット関数を近似します。これにより、最適化の問題はこれらの基底関数の線形係数を見つけることに簡略化されます。この新しいモデルのいくつかの理論的特性(ソリューションの存在と一意性、普遍的な一貫性など)が分析されます。広範な実験により、バイナリ分類、マルチクラス分類、および回帰タスクに対する提案モデルの有効性が実証されています。
Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis
トポロジカルデータ解析におけるパーシステンス図推定の収束率
Computational topology has recently seen an important development toward data analysis, giving birth to the field of topological data analysis. Topological persistence, or persistent homology, appears as a fundamental tool in this field. In this paper, we study topological persistence in general metric spaces, with a statistical approach. We show that the use of persistent homology can be naturally considered in general statistical frameworks and that persistence diagrams can be used as statistics with interesting convergence properties. Some numerical experiments are performed in various contexts to illustrate our results.
近年、計算トポロジーはデータ解析に向けて重要な発展を遂げており、トポロジカルデータ解析の分野が誕生しています。トポロジカル永続性、または永続ホモロジーは、この分野の基本的なツールとして現れます。この論文では、一般的な計量空間におけるトポロジカル永続性を統計的アプローチで研究します。パーシステントホモロジーの使用は、一般的な統計フレームワークで自然に考慮でき、パーシステンス図は興味深い収束特性を持つ統計として使用できることを示します。いくつかの数値実験は、結果を説明するためにさまざまなコンテキストで実行されます。
Minimax Analysis of Active Learning
アクティブラーニングのミニマックス分析
This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active learning with a VC class is always asymptotically smaller than that of passive learning, and is typically significantly smaller than the best previously-published upper bounds in the active learning literature. In high-noise regimes, it turns out that all active learning problems of a given VC dimension have roughly the same minimax label complexity, which contrasts with well-known results for bounded noise. In low-noise regimes, we find that the label complexity is well-characterized by a simple combinatorial complexity measure we call the star number. Interestingly, we find that almost all of the complexity measures previously explored in the active learning literature have worst-case values exactly equal to the star number. We also propose new active learning strategies that nearly achieve these minimax label complexities.
この研究では、さまざまなノイズ モデルのもとで、一般仮説クラスによる能動学習のミニマックス ラベル複雑度の分布フリーの上限と下限を確立します。その結果、いくつかの驚くべき事実が明らかになりました。特に、Tsybakov (2004)のノイズ モデルのもとでは、VCクラスによる能動学習のミニマックス ラベル複雑度は常に受動学習のそれよりも漸近的に小さく、能動学習の文献でこれまでに発表された最良の上限よりも大幅に小さくなります。ノイズが多い状況では、特定のVC次元のすべての能動学習問題がほぼ同じミニマックス ラベル複雑度を持つことがわかります。これは、境界付きノイズのよく知られた結果とは対照的です。ノイズが少ない状況では、ラベル複雑度は、スター ナンバーと呼ばれる単純な組み合わせ複雑度尺度によってよく特徴付けられることがわかります。興味深いことに、能動学習の文献でこれまでに検討された複雑度尺度のほとんどすべてが、最悪の場合の値がスター ナンバーとまったく同じであることがわかりました。また、これらのミニマックス ラベル複雑度をほぼ達成する新しい能動学習戦略も提案します。
The Sample Complexity of Learning Linear Predictors with the Squared Loss
二乗損失による線形予測子の学習におけるサンプルの複雑さ
We provide a tight sample complexity bound for learning bounded- norm linear predictors with respect to the squared loss. Our focus is on an agnostic PAC-style setting, where no assumptions are made on the data distribution beyond boundedness. This contrasts with existing results in the literature, which rely on other distributional assumptions, refer to specific parameter settings, or use other performance measures.
私たちは、二乗損失に関して有界ノルム線形予測子を学習するための厳密なサンプル複雑性限界を提供します。私たちの焦点は、制限を超えたデータ分布について仮定がなされない、不可知論的なPACスタイルの設定にあります。これは、他の分布の仮定に依存したり、特定のパラメータ設定を参照したり、他のパフォーマンス指標を使用したりする文献の既存の結果とは対照的です。
SnFFT: A Julia Toolkit for Fourier Analysis of Functions over Permutations
SnFFT:順列上の関数のフーリエ解析のためのJuliaツールキット
$\mathbb{S}_n$FFT is an easy to use software library written in the Julia language to facilitate Fourier analysis on the symmetric group (set of permutations) of degree $n$, denoted $\mathbb{S}_n$ and make it more easily deployable within statistical machine learning algorithms. Our implementation internally creates the irreducible matrix representations of $\mathbb{S}_n$, and efficiently computes fast Fourier transforms (FFTs) and inverse fast Fourier transforms (iFFTs). Advanced users can achieve scalability and promising practical performance by exploiting various other forms of sparsity. Further, the library also supports the partial inverse Fourier transforms which utilizes the smoothness properties of functions by maintaining only the first few Fourier coefficients. Out of the box, $\mathbb{S}_n$FFT currently offers two non-trivial operations for functions defined on $\mathbb{S}_n$, namely convolution and correlation. While the potential applicability of $\mathbb{S}_n$FFT is fairly broad, as an example, we show how it can be used for clustering ranked data, where each ranking is modeled as a distribution on $\mathbb{S}_n$.
$\mathbb{S}_n$FFTはJulia言語で書かれた使いやすいソフトウェア ライブラリで、次数$n$の対称群(順列の集合) ($\mathbb{S}_n$と表記)のフーリエ解析を容易にし、統計的機械学習アルゴリズム内でより簡単に展開できるようにします。実装では、内部的に$\mathbb{S}_n$の既約行列表現を作成し、高速フーリエ変換(FFT)と逆高速フーリエ変換(iFFT)を効率的に計算します。上級ユーザーは、他のさまざまな形式のスパース性を利用することで、スケーラビリティと有望な実用的なパフォーマンスを実現できます。さらに、ライブラリは、最初のいくつかのフーリエ係数のみを維持することで関数の滑らかさの特性を利用する部分逆フーリエ変換もサポートしています。すぐに使用できる$\mathbb{S}_n$FFTは現在、$\mathbb{S}_n$で定義された関数に対して、畳み込みと相関という2つの重要な操作を提供します。$\mathbb{S}_n$FFTの潜在的な適用範囲はかなり広いですが、例として、各ランキングが$\mathbb{S}_n$上の分布としてモデル化されるランク付けされたデータのクラスタリングにそれをどのように使用できるかを示します。
Agnostic Learning of Disjunctions on Symmetric Distributions
対称分布上の選言の不可知論的学習
We consider the problem of approximating and learning disjunctions (or equivalently, conjunctions) on symmetric distributions over $\{0,1\}^n$. Symmetric distributions are distributions whose PDF is invariant under any permutation of the variables. We prove that for every symmetric distribution $\mathcal{D}$, there exists a set of $n^{O(\log{(1/\epsilon)})}$ functions $\mathbb{S}$, such that for every disjunction $c$, there is function $p$, expressible as a linear combination of functions in $\mathbb{S}$, such that $p$ $\epsilon$-approximates $c$ in $\ell_1$ distance on $\mathcal{D}$ or $\mathbf{E}_{x \sim \mathcal{D}}[ |c(x)-p(x)|] \leq \epsilon$. This implies an agnostic learning algorithm for disjunctions on symmetric distributions that runs in time $n^{O( \log{(1/\epsilon)})}$. The best known previous bound is $n^{O(1/\epsilon^4)}$ and follows from approximation of the more general class of halfspaces (Wimmer, 2010). We also show that there exists a symmetric distribution $\mathcal{D}$, such that the minimum degree of a polynomial that $1/3$-approximates the disjunction of all $n$ variables in $\ell_1$ distance on $\mathcal{D}$ is $\Omega(\sqrt{n})$. Therefore the learning result above cannot be achieved via $\ell_1$-regression with a polynomial basis used in most other agnostic learning algorithms. Our technique also gives a simple proof that for any product distribution $\mathcal{D}$ and every disjunction $c$, there exists a polynomial $p$ of degree $O(\log{(1/\epsilon)})$ such that $p$ $\epsilon$-approximates $c$ in $\ell_1$ distance on $\mathcal{D}$. This was first proved by Blais et al. (2008) via a more involved argument.
私たちは、$\{0,1\}^n$上の対称分布上の選言(または同等の連言)を近似して学習する問題を考察します。対称分布とは、変数の任意の順列に対してPDFが不変である分布です。すべての対称分布$\mathcal{D}$に対して、$n^{O(\log{(1/\epsilon)})}$関数の集合$\mathbb{S}$が存在し、すべての選言$c$に対して、$\mathbb{S}$内の関数の線形結合として表現可能な関数$p$が存在し、$p$が$\mathcal{D}$上の$\ell_1$距離で$c$を$\epsilon$近似するか、$\mathbf{E}_{x \sim \mathcal{D}}[ |c(x)-p(x)|] \leq \epsilon$であることを証明します。これは、対称分布上の選言に対する、実行時間$n^{O( \log{(1/\epsilon)})}$の不可知論的学習アルゴリズムを意味します。これまで知られている最良の境界は$n^{O(1/\epsilon^4)}$であり、より一般的なクラスの半空間の近似から得られます(Wimmer、2010)。また、対称分布$\mathcal{D}$が存在し、$\mathcal{D}$上の$\ell_1$距離にあるすべての$n$変数の選言を$1/3$近似する多項式の最小次数が$\Omega(\sqrt{n})$であることも示しています。したがって、上記の学習結果は、他のほとんどの不可知論的学習アルゴリズムで使用される多項式基底による$\ell_1$回帰では達成できません。私たちの手法では、任意の積分布$\mathcal{D}$と任意の選言$c$に対して、次数$O(\log{(1/\epsilon)})$の多項式$p$が存在し、$p$が$\mathcal{D}$上の$\ell_1$距離で$c$を$\epsilon$近似するという簡単な証明も得られます。これは、より複雑な議論を経てBlaisら(2008)によって初めて証明されました。
On the Inductive Bias of Dropout
ドロップアウトの帰納的バイアスについて
Dropout is a simple but effective technique for learning in neural networks and other settings. A sound theoretical understanding of dropout is needed to determine when dropout should be applied and how to use it most effectively. In this paper we continue the exploration of dropout as a regularizer pioneered by Wager et al. We focus on linear classification where a convex proxy to the misclassification loss (i.e. the logistic loss used in logistic regression) is minimized. We show:
ドロップアウトは、ニューラルネットワークやその他の環境で学習するためのシンプルですが効果的な手法です。ドロップアウトをいつ適用すべきか、そしてそれを最も効果的に使用する方法を決定するには、ドロップアウトの健全な理論的理解が必要です。この論文では、Wagerらによって開拓された正則化器としてのドロップアウトの調査を続けます。ここでは、誤分類損失(つまり、ロジスティック回帰で使用されるロジスティック損失)に対する凸型プロキシが最小化される線形分類に焦点を当てます。私たちは示します:
Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
高速交互最小二乗法による行列補完と低ランクSVD
The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Netflix competition. Two popular approaches for solving the problem are nuclear-norm- regularized matrix approximation (Candes and Tao, 2009; Mazumder et al., 2010), and maximum-margin matrix factorization (Srebro et al., 2005). These two procedures are in some cases solving equivalent problems, but with quite different algorithms. In this article we bring the two approaches together, leading to an efficient algorithm for large matrix factorization and completion that outperforms both of these. We develop a software package softImpute in R for implementing our approaches, and a distributed version for very large matrices using the Spark cluster programming environment
行列完成問題は、主に有名なNetflixの競争の結果として、多くの注目を集めています。この問題を解決するための2つの一般的なアプローチは、核規範正則行列近似です(Candes and Tao, 2009;Mazumderら, 2010)、最大マージン行列因数分解(Srebroら, 2005)など、さまざまな要素が使用されています。これらの2つの手順は、場合によっては同等の問題を解決しますが、アルゴリズムはまったく異なります。この記事では、2つのアプローチを組み合わせ、これらの両方を凌駕する大規模な行列の因数分解と完了のための効率的なアルゴリズムを導き出します。私たちは、アプローチを実装するためのソフトウェアパッケージをRで開発し、Sparkクラスタープログラミング環境を使用して非常に大きな行列用の分散バージョンを開発します
Learning Theory of Randomized Kaczmarz Algorithm
ランダム化カツマルツ・アルゴリズムの学習理論
A relaxed randomized Kaczmarz algorithm is investigated in a least squares regression setting by a learning theory approach. When the sampling values are accurate and the regression function (conditional means) is linear, such an algorithm has been well studied in the community of non-uniform sampling. In this paper, we are mainly interested in the different case of either noisy random measurements or a nonlinear regression function. In this case, we show that relaxation is needed. A necessary and sufficient condition on the sequence of relaxation parameters or step sizes for the convergence of the algorithm in expectation is presented. Moreover, polynomial rates of convergence, both in expectation and in probability, are provided explicitly. As a result, the almost sure convergence of the algorithm is proved by applying the Borel-Cantelli Lemma.
緩和されたランダム化Kaczmarzアルゴリズムは、学習理論アプローチによって最小二乗回帰設定で調査されます。サンプリング値が正確で、回帰関数(条件付き平均)が線形である場合、そのようなアルゴリズムは不均一なサンプリングのコミュニティで十分に研究されています。この論文では、主にノイズの多いランダム測定または非線形回帰関数の異なるケースに関心があります。この場合、リラクゼーションが必要であることを示します。アルゴリズムの期待値への収束のための緩和パラメータまたはステップサイズのシーケンスに関する必要十分な条件が提示されます。さらに、期待値と確率の両方における多項式収束率が明示的に提供されます。その結果、アルゴリズムのほぼ確実な収束は、Borel-Cantelli補題を適用することによって証明されます。
Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
分割統治カーネルリッジ回帰:ミニマックス最適レートを持つ分散アルゴリズム
We study a decomposition-based scalable approach to kernel ridge regression, and show that it achieves minimax optimal convergence rates under relatively mild conditions. The method is simple to describe: it randomly partitions a dataset of size $N$ into $m$ subsets of equal size, computes an independent kernel ridge regression estimator for each subset using a careful choice of the regularization parameter, then averages the local solutions into a global predictor. This partitioning leads to a substantial reduction in computation time versus the standard approach of performing kernel ridge regression on all $N$ samples. Our two main theorems establish that despite the computational speed-up, statistical optimality is retained: as long as $m$ is not too large, the partition-based estimator achieves the statistical minimax rate over all estimators using the set of $N$ samples. As concrete examples, our theory guarantees that the number of subsets $m$ may grow nearly linearly for finite-rank or Gaussian kernels and polynomially in $N$ for Sobolev spaces, which in turn allows for substantial reductions in computational cost. We conclude with experiments on both simulated data and a music-prediction task that complement our theoretical results, exhibiting the computational and statistical benefits of our approach.
私たちは、カーネルリッジ回帰に対する分解ベースのスケーラブルなアプローチを研究し、比較的穏やかな条件下でミニマックス最適収束率を達成することを示します。この方法は説明が簡単です。サイズ$N$のデータセットをランダムに等しいサイズの$m$個のサブセットに分割し、正則化パラメータを慎重に選択して各サブセットの独立したカーネルリッジ回帰推定量を計算し、次にローカルソリューションを平均してグローバル予測子にします。この分割により、すべての$N$個のサンプルに対してカーネルリッジ回帰を実行する標準的なアプローチと比較して、計算時間が大幅に短縮されます。私たちの2つの主要な定理は、計算の高速化にもかかわらず、統計的最適性が保持されることを確立します。つまり、$m$が大きすぎない限り、パーティションベースの推定量は、$N$個のサンプルのセットを使用してすべての推定量に対して統計的ミニマックス率を達成します。具体的な例として、我々の理論は、部分集合の数$m$が有限ランクまたはガウスカーネルの場合はほぼ線形に増加し、ソボレフ空間の場合は$N$の多項式に増加することを保証し、これにより計算コストを大幅に削減できます。最後に、シミュレーションデータと音楽予測タスクの両方で実験を行い、理論的結果を補完し、我々のアプローチの計算上および統計上の利点を示します。
Plug-and-Play Dual-Tree Algorithm Runtime Analysis
プラグアンドプレイデュアルツリーアルゴリズムランタイム解析
Numerous machine learning algorithms contain pairwise statistical problems at their core—that is, tasks that require computations over all pairs of input points if implemented naively. Often, tree structures are used to solve these problems efficiently. Dual-tree algorithms can efficiently solve or approximate many of these problems. Using cover trees, rigorous worst-case runtime guarantees have been proven for some of these algorithms. In this paper, we present a problem- independent runtime guarantee for any dual-tree algorithm using the cover tree, separating out the problem- dependent and the problem-independent elements. This allows us to just plug in bounds for the problem-dependent elements to get runtime guarantees for dual-tree algorithms for any pairwise statistical problem without re-deriving the entire proof. We demonstrate this plug-and-play procedure for nearest-neighbor search and approximate kernel density estimation to get improved runtime guarantees. Under mild assumptions, we also present the first linear runtime guarantee for dual-tree based range search.
多くの機械学習アルゴリズムは、その中核にペアワイズ統計問題、つまり単純に実装するとすべての入力ポイントのペアに対する計算を必要とするタスクを含んでいます。多くの場合、ツリー構造を使用してこれらの問題を効率的に解決します。デュアルツリー アルゴリズムは、これらの問題の多くを効率的に解決または近似できます。カバー ツリーを使用すると、これらのアルゴリズムの一部で厳密な最悪ケースの実行時間保証が証明されています。この論文では、問題に依存する要素と問題に依存しない要素を分離して、カバー ツリーを使用する任意のデュアルツリー アルゴリズムの問題に依存しない実行時間保証を示します。これにより、問題に依存する要素の境界を挿入するだけで、証明全体を再導出することなく、任意のペアワイズ統計問題に対するデュアルツリー アルゴリズムの実行時間保証を得ることができます。このプラグ アンド プレイ手順を最近傍検索と近似カーネル密度推定に使用して、実行時間保証を改善します。また、軽度の仮定の下で、デュアルツリー ベースの範囲検索に対する最初の線形実行時間保証も示します。
Ultra-Scalable and Efficient Methods for Hybrid Observational and Experimental Local Causal Pathway Discovery
ハイブリッド観察および実験的局所因経路探索のための超スケーラブルで効率的な方法
Discovery of causal relations from data is a fundamental objective of several scientific disciplines. Most causal discovery algorithms that use observational data can infer causality only up to a statistical equivalency class, thus leaving many causal relations undetermined. In general, complete identification of causal relations requires experimentation to augment discoveries from observational data. This has led to the recent development of several methods for active learning of causal networks that utilize both observational and experimental data in order to discover causal networks. In this work, we focus on the problem of discovering local causal pathways that contain only direct causes and direct effects of the target variable of interest and propose new discovery methods that aim to minimize the number of required experiments, relax common sufficient discovery assumptions in order to increase discovery accuracy, and scale to high-dimensional data with thousands of variables. We conduct a comprehensive evaluation of new and existing methods with data of dimensionality up to 1,000,000 variables. We use both artificially simulated networks and in-silico gene transcriptional networks that model the characteristics of real gene expression data.
データから因果関係を発見することは、いくつかの科学分野の基本的な目標です。観測データを使用する因果関係発見アルゴリズムのほとんどは、統計的同値クラスまでの因果関係しか推測できないため、多くの因果関係が未確定のままになります。一般に、因果関係を完全に特定するには、観測データからの発見を補強するための実験が必要です。このため、因果ネットワークを発見するために観測データと実験データの両方を利用する因果ネットワークのアクティブラーニングのいくつかの方法が最近開発されました。この研究では、対象変数の直接的な原因と直接的な影響のみを含むローカル因果経路を発見するという問題に焦点を当て、必要な実験の数を最小限に抑え、発見の精度を高めるために共通の十分な発見の仮定を緩和し、数千の変数を含む高次元データに拡張することを目的とした新しい発見方法を提案します。最大1,000,000の変数の次元のデータを使用して、新しい方法と既存の方法を包括的に評価します。私たちは、人工的にシミュレートされたネットワークと、実際の遺伝子発現データの特性をモデル化するインシリコ遺伝子転写ネットワークの両方を使用します。
On Semi-Supervised Linear Regression in Covariate Shift Problems
共変量シフト問題における半教師付き線形回帰について
Semi-supervised learning approaches are trained using the full training (labeled) data and available testing (unlabeled) data. Demonstrations of the value of training with unlabeled data typically depend on a smoothness assumption relating the conditional expectation to high density regions of the marginal distribution and an inherent missing completely at random assumption for the labeling. So-called covariate shift poses a challenge for many existing semi-supervised or supervised learning techniques. Covariate shift models allow the marginal distributions of the labeled and unlabeled feature data to differ, but the conditional distribution of the response given the feature data is the same. An example of this occurs when a complete labeled data sample and then an unlabeled sample are obtained sequentially, as it would likely follow that the distributions of the feature data are quite different between samples. The value of using unlabeled data during training for the elastic net is justified geometrically in such practical covariate shift problems. The approach works by obtaining adjusted coefficients for unlabeled prediction which recalibrate the supervised elastic net to compromise: (i) maintaining elastic net predictions on the labeled data with (ii) shrinking unlabeled predictions to zero. Our approach is shown to dominate linear supervised alternatives on unlabeled response predictions when the unlabeled feature data are concentrated on a low dimensional manifold away from the labeled data and the true coefficient vector emphasizes directions away from this manifold. Large variance of the supervised predictions on the unlabeled set is reduced more than the increase in squared bias when the unlabeled responses are expected to be small, so an improved compromise within the bias-variance tradeoff is the rationale for this performance improvement. Performance is validated on simulated and real data.
半教師あり学習アプローチは、完全なトレーニング(ラベル付き)データと利用可能なテスト(ラベルなし)データを使用してトレーニングされます。ラベルなしデータを使用したトレーニングの価値の実証は、通常、条件付き期待値を周辺分布の高密度領域に関連付ける平滑性仮定と、ラベル付けに対する完全にランダムな仮定が本質的に欠落していることに依存します。いわゆる共変量シフトは、多くの既存の半教師あり学習または教師あり学習手法にとって課題となります。共変量シフト モデルでは、ラベル付きおよびラベルなしの特徴データの周辺分布は異なりますが、特徴データが与えられた場合の応答の条件付き分布は同じです。この例は、完全なラベル付きデータ サンプルとラベルなしサンプルが順番に取得される場合に発生します。これは、特徴データの分布がサンプル間でかなり異なる可能性が高いためです。エラスティック ネットのトレーニング中にラベルなしデータを使用することの価値は、このような実用的な共変量シフト問題において幾何学的に正当化されます。このアプローチは、ラベルなし予測の調整係数を取得することで機能します。この調整係数は、教師あり弾性ネットを再調整して、(i)ラベル付きデータに対する弾性ネット予測を維持しながら、(ii)ラベルなし予測をゼロに縮小します。ラベルなし特徴データがラベル付きデータから離れた低次元多様体に集中し、真の係数ベクトルがこの多様体から離れる方向を強調する場合、ラベルなし応答予測に関して、線形教師あり代替案よりもこのアプローチの方が優れていることが示されています。ラベルなしセットに対する教師あり予測の大きな分散は、ラベルなし応答が小さいと予想される場合のバイアスの二乗の増加よりも減少するため、バイアスと分散のトレードオフ内での妥協点の改善が、このパフォーマンス向上の根拠となります。パフォーマンスは、シミュレートされたデータと実際のデータで検証されます。
Global Convergence of Online Limited Memory BFGS
オンライン限定メモリBFGSのグローバル収束
Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi- Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Experimental evaluation on a search engine advertising problem showcase reductions in convergence time relative to stochastic gradient descent algorithms.
大規模な機械学習で発生する確率的目的を持つ最適化問題を解くための、Broyden-Fletcher-Goldfarb-Shanno (BFGS)準ニュートン法のオンライン(確率的)制限メモリ バージョンのグローバル収束が確立されます。サンプル関数のヘッセ固有値の下限と上限は、曲率近似行列が有界行列式とトレースを持つことを保証するのに十分であることが示されており、これにより、確率1の最適な引数への収束を確立できます。検索エンジン広告問題に関する実験的評価は、確率的勾配降下アルゴリズムと比較して収束時間の短縮を示しています。
A Direct Estimation of High Dimensional Stationary Vector Autoregressions
高次元定常ベクトル自己回帰の直接推定
The vector autoregressive (VAR) model is a powerful tool in learning complex time series and has been exploited in many fields. The VAR model poses some unique challenges to researchers: On one hand, the dimensionality, introduced by incorporating multiple numbers of time series and adding the order of the vector autoregression, is usually much higher than the time series length; On the other hand, the temporal dependence structure naturally present in the VAR model gives rise to extra difficulties in data analysis. The regular way in cracking the VAR model is via “least squares” and usually involves adding different penalty terms (e.g., ridge or lasso penalty) in handling high dimensionality. In this manuscript, we propose an alternative way in estimating the VAR model. The main idea is, via exploiting the temporal dependence structure, formulating the estimating problem to a linear program. There is instant advantage of the proposed approach over the lasso-type estimators: The estimation equation can be decomposed to multiple sub-equations and accordingly can be solved efficiently using parallel computing. Besides that, we also bring new theoretical insights into the VAR model analysis. So far the theoretical results developed in high dimensions (e.g., Song and Bickel, 2011 and Kock and Callot, 2015) are based on stringent assumptions that are not transparent. Our results, on the other hand, show that the spectral norms of the transition matrices play an important role in estimation accuracy and build estimation and prediction consistency accordingly. Moreover, we provide some experiments on both synthetic and real-world equity data. We show that there are empirical advantages of our method over the lasso-type estimators in parameter estimation and forecasting.
ベクトル自己回帰(VAR)モデルは、複雑な時系列を学習するための強力なツールであり、多くの分野で活用されてきました。VARモデルは、研究者にいくつかの独特の課題を提起します。一方では、複数の時系列を組み込み、ベクトル自己回帰の順序を追加することによって導入される次元は、通常、時系列の長さよりもはるかに高くなります。他方では、VARモデルに自然に存在する時間依存構造により、データ分析にさらなる困難が生じます。VARモデルを解読する通常の方法は「最小二乗法」によるもので、通常、高次元を処理する際にさまざまなペナルティ項(リッジ ペナルティやラッソ ペナルティなど)を追加します。この原稿では、VARモデルを推定する別の方法を提案します。主なアイデアは、時間依存構造を利用して、推定問題を線形計画に定式化することです。提案されたアプローチには、Lassoタイプの推定量よりも優れた利点があります。推定方程式を複数の部分方程式に分解できるため、並列コンピューティングを使用して効率的に解くことができます。それに加えて、VARモデル分析に新しい理論的洞察ももたらします。これまで、高次元で開発された理論的結果(例: Song and Bickel、2011年、Kock and Callot、2015年)は、透明性のない厳格な仮定に基づいています。一方、私たちの結果は、遷移行列のスペクトル ノルムが推定精度に重要な役割を果たし、それに応じて推定と予測の一貫性を構築することを示しています。さらに、合成株式データと実際の株式データの両方でいくつかの実験を提供します。パラメーター推定と予測において、Lassoタイプの推定量よりも私たちの方法に経験的な利点があることを示します。
Discrete Reproducing Kernel Hilbert Spaces: Sampling and Distribution of Dirac-masses
離散再現カーネルヒルベルト空間:ディラック質量のサンプリングと分布
We study reproducing kernels, and associated reproducing kernel Hilbert spaces (RKHSs) $\mathscr{H}$ over infinite, discrete and countable sets $V$. In this setting we analyze in detail the distributions of the corresponding Dirac point-masses of $V$. Illustrations include certain models from neural networks: An Extreme Learning Machine (ELM) is a neural network-configuration in which a hidden layer of weights are randomly sampled, and where the object is then to compute resulting output. For RKHSs $\mathscr{H}$ of functions defined on a prescribed countable infinite discrete set $V$, we characterize those which contain the Dirac masses $\delta_{x}$ for all points $x$ in $V$. Further examples and applications where this question plays an important role are: (i) discrete Brownian motion-Hilbert spaces, i.e., discrete versions of the Cameron-Martin Hilbert space; (ii) energy-Hilbert spaces corresponding to graph-Laplacians where the set $V$ of vertices is then equipped with a resistance metric; and finally (iii) the study of Gaussian free fields.
私たちは、無限、離散、可算集合$V$上の再生核および関連する再生核ヒルベルト空間(RKHS) $\mathscr{H}$を研究します。この設定で、$V$の対応するディラック質点の分布を詳細に分析します。例示には、ニューラル ネットワークからの特定のモデルが含まれます。エクストリーム ラーニング マシン(ELM)は、隠れた重みの層がランダムにサンプリングされ、結果の出力を計算するニューラル ネットワーク構成です。所定の可算無限離散集合$V$上で定義された関数のRKHS $\mathscr{H}$について、$V$内のすべての点$x$のディラック質点$\delta_{x}$を含むものを特徴付ける。この問題が重要な役割を果たすその他の例とアプリケーションには、(i)離散ブラウン運動ヒルベルト空間、つまりCameron-Martinヒルベルト空間の離散バージョンがあります。(ii)グラフラプラシアンに対応するエネルギーヒルベルト空間（頂点集合$V$に抵抗計量が備わっている場合）；そして最後に(iii)ガウス自由場の研究。
Eigenwords: Spectral Word Embeddings
固有語:スペクトルワードの埋め込み
Spectral learning algorithms have recently become popular in data-rich domains, driven in part by recent advances in large scale randomized SVD, and in spectral estimation of Hidden Markov Models. Extensions of these methods lead to statistical estimation algorithms which are not only fast, scalable, and useful on real data sets, but are also provably correct. Following this line of research, we propose four fast and scalable spectral algorithms for learning word embeddings — low dimensional real vectors (called Eigenwords) that capture the “meaning” of words from their context. All the proposed algorithms harness the multi-view nature of text data i.e. the left and right context of each word, are fast to train and have strong theoretical properties. Some of the variants also have lower sample complexity and hence higher statistical power for rare words. We provide theory which establishes relationships between these algorithms and optimality criteria for the estimates they provide. We also perform thorough qualitative and quantitative evaluation of Eigenwords showing that simple linear approaches give performance comparable to or superior than the state-of-the-art non-linear deep learning based methods.
スペクトル学習アルゴリズムは、大規模なランダム化SVDや隠れマルコフ モデルのスペクトル推定の最近の進歩に一部起因して、最近、データの多い領域で人気が高まっています。これらの方法の拡張により、高速でスケーラブルで、実際のデータ セットで役立つだけでなく、証明可能な正確性も備えた統計推定アルゴリズムが実現します。この研究の流れに沿って、単語の埋め込み(単語の「意味」をそのコンテキストから取得する低次元の実数ベクトル(固有語と呼ばれる))を学習するための高速でスケーラブルな4つのスペクトル アルゴリズムを提案します。提案されたアルゴリズムはすべて、テキスト データのマルチビューの性質、つまり各単語の左と右のコンテキストを利用し、トレーニングが高速で、強力な理論的特性を備えています。また、一部のバリアントではサンプルの複雑さが低く、したがってまれな単語の統計的検出力が高くなります。これらのアルゴリズムと、それらが提供する推定値の最適性基準との関係を確立する理論を提供します。また、Eigenwordsの徹底的な定性的および定量的評価も実行し、単純な線形アプローチが最先端の非線形ディープラーニングベースの方法と同等かそれ以上のパフォーマンスを発揮することを示しています。
Completing Any Low-rank Matrix, Provably
低ランクの行列を証明可能な形で完成させる
Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint—known as incoherence—on its row and column spaces. In these cases, the subset of elements is assumed to be sampled uniformly at random. In this paper, we show that any rank-$ r $ $ n$-by-$ n $ matrix can be exactly recovered from as few as $O(nr \log^2 n)$ randomly chosen elements, provided this random choice is made according to a specific biased distribution suitably dependent on the coherence structure of the matrix: the probability of any element being sampled should be at least a constant times the sum of the leverage scores of the corresponding row and column. Moreover, we prove that this specific form of sampling is nearly necessary, in a natural precise sense; this implies that many other perhaps more intuitive sampling schemes fail. We further establish three ways to use the above result for the setting when leverage scores are not known a priori. (a) We describe a provably-correct sampling strategy for the case when only the column space is incoherent and no assumption or knowledge of the row space is required. (b) We propose a two-phase sampling procedure for general matrices that first samples to estimate leverage scores followed by sampling for exact recovery. These two approaches assume control over the sampling procedure. (c) By using our main theorem in a reverse direction, we provide an analysis showing the advantages of the (empirically successful) weighted nuclear/trace-norm minimization approach over the vanilla un- weighted formulation given non-uniformly distributed observed elements. This approach does not require controlled sampling or knowledge of the leverage scores.
行列の完全化、すなわち、低ランク行列をその要素の小さなサブセットから正確かつ証明可能な形で復元することは、現在のところ、行列が行と列の空間で制約的な構造的制約（非一貫性として知られる）を満たす場合にのみ可能であることがわかっています。このような場合、要素のサブセットは一様にランダムにサンプリングされると想定されます。この論文では、ランダム選択が行列の一貫性構造に適切に依存する特定の偏りのある分布に従って行われる場合、ランク$ r $ $ n$行$ n $列の行列は、ランダムに選択された$O(nr \log^2 n)$個の要素から正確に復元できることを示す。つまり、サンプリングされる要素の確率は、対応する行と列のてこ比スコアの合計の定数倍以上でなければならない。さらに、この特定のサンプリング形式は、自然で正確な意味でほぼ必要であることを証明しています。これは、他の多くの、おそらくより直感的なサンプリング方式が失敗することを意味します。さらに、てこ比スコアが事前にわからない場合の設定に上記の結果を使用する3つの方法を確立します。(a)列空間のみがインコヒーレントであり、行空間に関する仮定や知識が不要な場合の、証明可能な正しいサンプリング戦略について説明します。(b)一般的な行列に対して、最初にてこ比スコアを推定するためのサンプリングを行い、次に正確な回復のためのサンプリングを行う2段階のサンプリング手順を提案します。これら2つのアプローチは、サンプリング手順の制御を前提としています。(c)主定理を逆方向に使用して、非均一に分布した観測要素を前提とした、(経験的に成功した)重み付き核/トレースノルム最小化アプローチが、重みなしのバニラ定式化よりも優れていることを示す分析を提供します。このアプローチでは、制御されたサンプリングやてこ比スコアの知識は必要ありません。
Comparing Hard and Overlapping Clusterings
ハードクラスタリングとオーバーラップクラスタリングの比較
Similarity measures for comparing clusterings is an important component, e.g., of evaluating clustering algorithms, for consensus clustering, and for clustering stability assessment. These measures have been studied for over 40 years in the domain of exclusive hard clusterings (exhaustive and mutually exclusive object sets). In the past years, the literature has proposed measures to handle more general clusterings (e.g., fuzzy/probabilistic clusterings). This paper provides an overview of these new measures and discusses their drawbacks. We ultimately develop a corrected-for-chance measure (13AGRI) capable of comparing exclusive hard, fuzzy/probabilistic, non- exclusive hard, and possibilistic clusterings. We prove that 13AGRI and the adjusted Rand index (ARI, by Hubert and Arabie) are equivalent in the exclusive hard domain. The reported experiments show that only 13AGRI could provide both a fine- grained evaluation across clusterings with different numbers of clusters and a constant evaluation between random clusterings, showing all the four desirable properties considered here. We identified a high correlation between 13AGRI applied to fuzzy clusterings and ARI applied to hard exclusive clusterings over 14 real data sets from the UCI repository, which corroborates the validity of 13AGRI fuzzy clustering evaluation. 13AGRI also showed good results as a clustering stability statistic for solutions produced by the expectation maximization algorithm for Gaussian mixture. Implementation and supplementary figures can be found at sn.im/25a9h8u.
クラスタリングを比較するための類似性尺度は、クラスタリング アルゴリズムの評価、コンセンサス クラスタリング、クラスタリング安定性評価などの重要な要素です。これらの尺度は、排他的ハード クラスタリング(網羅的かつ相互に排他的なオブジェクト セット)の領域で40年以上研究されてきました。過去数年間、文献では、より一般的なクラスタリング(ファジー/確率的クラスタリングなど)を処理する尺度が提案されています。この論文では、これらの新しい尺度の概要を示し、その欠点について説明します。最終的には、排他的ハード、ファジー/確率的、非排他的ハード、および可能性的クラスタリングを比較できる、偶然性補正尺度(13AGRI)を開発します。13AGRIと調整済みRand指数(ARI、HubertおよびArabieによる)が排他的ハード領域で同等であることを証明します。報告された実験は、13AGRIのみが、異なる数のクラスターを持つクラスタリング全体にわたるきめ細かい評価と、ランダム クラスタリング間の一定の評価の両方を提供できることを示しており、ここで検討されている4つの望ましい特性のすべてを示しています。UCIリポジトリからの14の実際のデータ セットで、ファジー クラスタリングに適用された13AGRIと、ハード排他的クラスタリングに適用されたARIの間に高い相関関係があることを確認しました。これは、13AGRIファジー クラスタリング評価の妥当性を裏付けるものです。13AGRIは、ガウス混合の期待値最大化アルゴリズムによって生成されたソリューションのクラスタリング安定性統計としても優れた結果を示しました。実装と補足図はsn.im/25a9h8uにあります。
Combination of Feature Engineering and Ranking Models for Paper-Author Identification in KDD Cup 2013
KDD Cup 2013における論文著者同定のための特徴エンジニアリングモデルとランキングモデルの組み合わせ
This paper describes the winning solution of team National Taiwan University for track 1 of KDD Cup 2013. The track 1 in KDD Cup 2013 considers the paper-author identification problem, which is to identify whether a paper is truly written by an author. First, we conduct feature engineering to transform the various types of provided text information into 97 features. Second, we train classification and ranking models using these features. Last, we combine our individual models to boost the performance by using results on the internal validation set and the official Valid set. Some effective post-processing techniques have also been proposed. Our solution achieves 0.98259 MAP score and ranks the first place on the private leaderboard of the Test set.
この論文では、KDD Cup 2013のトラック1で優勝したチームNational Taiwan Universityの解答について説明します。KDD Cup 2013のトラック1では、論文が本当に著者によって書かれたものかどうかを特定するという、論文と著者の識別問題について考察しています。まず、提供される様々な種類のテキスト情報を97の特徴に変換する特徴量エンジニアリングを行います。次に、これらの機能を使用して分類モデルとランク付けモデルをトレーニングします。最後に、個々のモデルを組み合わせて、内部検証セットと公式の有効セットの結果を使用してパフォーマンスを向上させます。いくつかの効果的な後処理技術も提案されています。私たちのソリューションは0.98259のMAPスコアを達成し、テストセットのプライベートリーダーボードで1位にランクインします。
Optimality of Poisson Processes Intensity Learning with Gaussian Processes
ポアソン過程の最適性 ガウス過程による強度学習
In this paper we provide theoretical support for the so-called “Sigmoidal Gaussian Cox Process” approach to learning the intensity of an inhomogeneous Poisson process on a $d$-dimensional domain. This method was proposed by Adams, Murray and MacKay (ICML, 2009), who developed a tractable computational approach and showed in simulation and real data experiments that it can work quite satisfactorily. The results presented in the present paper provide theoretical underpinning of the method. In particular, we show how to tune the priors on the hyper parameters of the model in order for the procedure to automatically adapt to the degree of smoothness of the unknown intensity, and to achieve optimal convergence rates.
この論文では、$d$次元領域上の不均質なポアソン過程の強度を学習するための、いわゆる「シグモイダルガウスコックス過程」アプローチを理論的にサポートします。この方法は、Adams、Murray、MacKay(ICML、2009)によって提案され、扱いやすい計算アプローチを開発し、シミュレーションと実際のデータ実験で非常に満足のいく動作を示すことを示しました。本論文で提示された結果は、この方法の理論的基盤を提供します。特に、未知強度の滑らかさの程度に手順が自動的に適応し、最適な収束率を達成するために、モデルのハイパーパラメータの事前確率を調整する方法を示します。
The Randomized Causation Coefficient
ランダム化された因果係数
We are interested in learning causal relationships between pairs of random variables, purely from observational data. To effectively address this task, the state-of-the-art relies on strong assumptions on the mechanisms mapping causes to effects, such as invertibility or the existence of additive noise, which only hold in limited situations. On the contrary, this short paper proposes to learn how to perform causal inference directly from data, without the need of feature engineering. In particular, we pose causality as a kernel mean embedding classification problem, where inputs are samples from arbitrary probability distributions on pairs of random variables, and labels are types of causal relationships. We validate the performance of our method on synthetic and real-world data against the state-of-the-art. Moreover, we submitted our algorithm to the ChaLearn’s “Fast Causation Coefficient Challenge” competition, with which we won the fastest code prize and ranked third in the overall leaderboard.
私たちは、純粋に観測データからランダム変数のペア間の因果関係を学習することに興味があります。このタスクに効果的に対処するため、最先端の技術は、可逆性や加法性ノイズの存在など、原因を結果にマッピングするメカニズムに関する強力な仮定に依存していますが、これらは限られた状況でのみ当てはまります。それとは対照的に、この短い論文では、特徴エンジニアリングを必要とせずに、データから直接因果推論を実行する方法を学習することを提案しています。特に、因果関係をカーネル平均埋め込み分類問題として提示します。ここで、入力はランダム変数のペアの任意の確率分布からのサンプルであり、ラベルは因果関係のタイプです。私たちは、合成データと実世界のデータに対する私たちの方法のパフォーマンスを最先端の技術と比較して検証します。さらに、私たちは私たちのアルゴリズムをChaLearnの「Fast Causation Coefficient Challenge」コンテストに提出し、最速コード賞を受賞し、総合リーダーボードで3位にランクされました。
Linear Dimensionality Reduction: Survey, Insights, and Generalizations
線形次元削減: 調査、洞察、一般化
Linear dimensionality reduction methods are a cornerstone of analyzing high dimensional data, due to their simple geometric interpretations and typically attractive computational properties. These methods capture many data features of interest, such as covariance, dynamical structure, correlation between data sets, input-output relationships, and margin between data classes. Methods have been developed with a variety of names and motivations in many fields, and perhaps as a result the connections between all these methods have not been highlighted. Here we survey methods from this disparate literature as optimization programs over matrix manifolds. We discuss principal component analysis, factor analysis, linear multidimensional scaling, Fisher’s linear discriminant analysis, canonical correlations analysis, maximum autocorrelation factors, slow feature analysis, sufficient dimensionality reduction, undercomplete independent component analysis, linear regression, distance metric learning, and more. This optimization framework gives insight to some rarely discussed shortcomings of well-known methods, such as the suboptimality of certain eigenvector solutions. Modern techniques for optimization over matrix manifolds enable a generic linear dimensionality reduction solver, which accepts as input data and an objective to be optimized, and returns, as output, an optimal low-dimensional projection of the data. This simple optimization framework further allows straightforward generalizations and novel variants of classical methods, which we demonstrate here by creating an orthogonal-projection canonical correlations analysis. More broadly, this survey and generic solver suggest that linear dimensionality reduction can move toward becoming a blackbox, objective-agnostic numerical technology.
線形次元削減法は、その単純な幾何学的解釈と魅力的な計算特性により、高次元データの分析の基礎となっています。これらの方法は、共分散、動的構造、データセット間の相関、入出力関係、データクラス間のマージンなど、多くのデータの特徴を捉えます。多くの分野でさまざまな名前と動機で方法が開発されてきましたが、その結果、これらすべての方法間のつながりが強調されてこなかったのかもしれません。ここでは、このさまざまな文献から、行列多様体上の最適化プログラムとしての方法を調査します。主成分分析、因子分析、線形多次元尺度法、フィッシャーの線形判別分析、正準相関分析、最大自己相関因子、低速特徴分析、十分な次元削減、不完全独立成分分析、線形回帰、距離測定学習などについて説明します。この最適化フレームワークは、特定の固有ベクトル解の準最適性など、よく知られた方法のあまり議論されていない欠点についての洞察を提供します。行列多様体に対する最適化の最新技術により、汎用線形次元削減ソルバーが可能になります。このソルバーは、入力データと最適化する目的を受け取り、出力としてデータの最適な低次元投影を返します。このシンプルな最適化フレームワークにより、従来の方法の簡単な一般化と新しいバリエーションが可能になります。ここでは、直交投影正準相関分析を作成することでこれを実証します。より広い意味では、この調査と汎用ソルバーは、線形次元削減がブラックボックスで目的に依存しない数値技術になる可能性があることを示唆しています。
CEKA: A Tool for Mining the Wisdom of Crowds
CEKA:群衆の知恵を掘り起こすためのツール
CEKA is a software package for developers and researchers to mine the wisdom of crowds. It makes the entire knowledge discovery procedure much easier, including analyzing qualities of workers, simulating labeling behaviors, inferring true class labels of instances, filtering and correcting mislabeled instances (noise), building learning models and evaluating them. It integrates a set of state-of-the-art inference algorithms, a set of general noise handling algorithms, and abundant functions for model training and evaluation. CEKA is written in Java with core classes being compatible with the well-known machine learning tool WEKA, which makes the utilization of the functions in WEKA much easier.
CEKAは、開発者や研究者が群衆の知恵を掘り起こすためのソフトウェアパッケージです。これにより、ワーカーの品質の分析、ラベリング動作のシミュレーション、インスタンスの真のクラスラベルの推測、誤ってラベル付けされたインスタンス(ノイズ)のフィルタリングと修正、学習モデルの構築と評価など、ナレッジディスカバリーの手順全体がはるかに簡単になります。最先端の推論アルゴリズムのセット、一般的なノイズ処理アルゴリズムのセット、およびモデルのトレーニングと評価のための豊富な関数を統合しています。CEKAはJavaで記述されており、コアクラスは有名な機械学習ツールWEKAと互換性があるため、WEKAの機能の利用がはるかに容易になります。
Optimal Bayesian Estimation in Random Covariate Design with a Rescaled Gaussian Process Prior
再スケーリングされたガウス過程事前分布を持つランダム共変量計画における最適ベイズ推定
In Bayesian nonparametric models, Gaussian processes provide a popular prior choice for regression function estimation. Existing literature on the theoretical investigation of the resulting posterior distribution almost exclusively assume a fixed design for covariates. The only random design result we are aware of (van der Vaart and van Zanten, 2011) assumes the assigned Gaussian process to be supported on the smoothness class specified by the true function with probability one. This is a fairly restrictive assumption as it essentially rules out the Gaussian process prior with a squared exponential kernel when modeling rougher functions. In this article, we show that an appropriate rescaling of the above Gaussian process leads to a rate-optimal posterior distribution even when the covariates are independently realized from a known density on a compact set. The proofs are based on deriving sharp concentration inequalities for frequentist kernel estimators; the results might be of independent interest.
ベイジアン ノンパラメトリック モデルでは、回帰関数推定の事前分布としてガウス過程がよく使用されます。結果として得られる事後分布の理論的調査に関する既存の文献は、共変量に対してほぼ例外なく固定設計を前提としています。私たちが知っている唯一のランダム設計結果(van der Vaartおよびvan Zanten、2011)は、割り当てられたガウス過程が、確率1で真の関数によって指定された平滑性クラスでサポートされていると想定しています。これは、より粗い関数をモデル化するときに、2乗指数カーネルを持つガウス過程事前分布を実質的に排除するため、かなり制限的な想定です。この記事では、上記のガウス過程を適切に再スケーリングすると、共変量がコンパクト セット上の既知の密度から独立して実現される場合でも、速度が最適な事後分布が得られることを示します。証明は、頻度主義カーネル推定量に対する鋭い集中不等式を導出することに基づいています。結果は独立して興味深いものとなる可能性があります。
Online Tensor Methods for Learning Latent Variable Models
潜在変数モデルを学習するためのオンラインテンソル法
We introduce an online tensor decomposition based approach for two latent variable modeling problems namely, (1) community detection, in which we learn the latent communities that the social actors in social networks belong to, and (2) topic modeling, in which we infer hidden topics of text articles. We consider decomposition of moment tensors using stochastic gradient descent. We conduct optimization of multilinear operations in SGD and avoid directly forming the tensors, to save computational and storage costs. We present optimized algorithm in two platforms. Our GPU-based implementation exploits the parallelism of SIMD architectures to allow for maximum speed-up by a careful optimization of storage and data transfer, whereas our CPU-based implementation uses efficient sparse matrix computations and is suitable for large sparse data sets. For the community detection problem, we demonstrate accuracy and computational efficiency on Facebook, Yelp and DBLP data sets, and for the topic modeling problem, we also demonstrate good performance on the New York Times data set. We compare our results to the state-of-the-art algorithms such as the variational method, and report a gain of accuracy and a gain of several orders of magnitude in the execution time.
私たちは、潜在変数モデリング問題2つ、すなわち(1)コミュニティ検出(ソーシャル ネットワークのソーシャル アクターが属する潜在コミュニティを学習)、および(2)トピック モデリング(テキスト記事の隠れたトピックを推測)に対するオンライン テンソル分解ベースのアプローチを紹介します。確率的勾配降下法を使用したモーメント テンソルの分解を検討します。SGDで多重線形演算を最適化し、テンソルを直接形成しないようにすることで、計算コストとストレージ コストを節約します。2つのプラットフォームで最適化されたアルゴリズムを紹介します。GPUベースの実装では、SIMDアーキテクチャの並列処理を利用して、ストレージとデータ転送を慎重に最適化することで最大限の速度向上を実現します。一方、CPUベースの実装では、効率的なスパース マトリックス計算を使用し、大規模なスパース データ セットに適しています。コミュニティ検出問題では、Facebook、Yelp、DBLPデータ セットで精度と計算効率を実証し、トピック モデリング問題では、New York Timesデータ セットで優れたパフォーマンスを実証します。私たちは、変分法などの最先端のアルゴリズムと私たちの結果を比較し、精度の向上と実行時間の数桁の短縮を報告します。
A View of Margin Losses as Regularizers of Probability Estimates
確率推定の正則化器としての証拠金損失の見方
Regularization is commonly used in classifier design, to assure good generalization. Classical regularization enforces a cost on classifier complexity, by constraining parameters. This is usually combined with a margin loss, which favors large-margin decision rules. A novel and unified view of this architecture is proposed, by showing that margin losses act as regularizers of posterior class probabilities, in a way that amplifies classical parameter regularization. The problem of controlling the regularization strength of a margin loss is considered, using a decomposition of the loss in terms of a link and a binding function. The link function is shown to be responsible for the regularization strength of the loss, while the binding function determines its outlier robustness. A large class of losses is then categorized into equivalence classes of identical regularization strength or outlier robustness. It is shown that losses in the same regularization class can be parameterized so as to have tunable regularization strength. This parameterization is finally used to derive boosting algorithms with loss regularization (BoostLR). Three classes of tunable regularization losses are considered in detail. Canonical losses can implement all regularization behaviors but have no flexibility in terms of outlier modeling. Shrinkage losses support equally parameterized link and binding functions, leading to boosting algorithms that implement the popular shrinkage procedure. This offers a new explanation for shrinkage as a special case of loss-based regularization. Finally, $\alpha$-tunable losses enable the independent parameterization of link and binding functions, leading to boosting algorithms of great flexibility. This is illustrated by the derivation of an algorithm that generalizes both AdaBoost and LogitBoost, behaving as either one when that best suits the data to classify. Various experiments provide evidence of the benefits of probability regularization for both classification and estimation of posterior class probabilities.
分類器の設計では、一般化を確実にするために、正則化が一般的に使用されます。古典的な正則化では、パラメータを制約することで、分類器の複雑さにコストがかかります。これは通常、マージン損失と組み合わされ、マージンが大きい決定ルールが優先されます。このアーキテクチャの新しい統一されたビューが提案され、マージン損失が事後クラス確率の正則化子として機能し、古典的なパラメータ正則化を増幅することを示しています。マージン損失の正則化強度を制御する問題は、リンクと結合関数の観点から損失を分解して検討します。リンク関数は損失の正則化強度に関与し、結合関数は外れ値堅牢性を決定することが示されています。次に、損失の大きなクラスが、同一の正則化強度または外れ値堅牢性の同等クラスに分類されます。同じ正則化クラスの損失は、調整可能な正則化強度を持つようにパラメータ化できることが示されています。このパラメータ化は、最終的に損失正則化(BoostLR)を使用したブースティング アルゴリズムを導出するために使用されます。調整可能な正則化損失の3つのクラスについて詳しく検討します。標準損失はすべての正則化動作を実装できますが、外れ値モデリングに関しては柔軟性がありません。収縮損失は、同様にパラメーター化されたリンク関数とバインディング関数をサポートし、一般的な収縮手順を実装するブースティング アルゴリズムにつながります。これにより、損失ベースの正則化の特殊なケースとしての収縮の新しい説明が提供されます。最後に、$\alpha$調整可能な損失により、リンク関数とバインディング関数の独立したパラメーター化が可能になり、柔軟性の高いブースティング アルゴリズムにつながります。これは、AdaBoostとLogitBoostの両方を一般化し、分類するデータに最適な場合にどちらか一方として動作するアルゴリズムの導出によって示されます。さまざまな実験により、分類と事後クラス確率の推定の両方に対する確率正則化の利点が証明されています。
Decision Boundary for Discrete Bayesian Network Classifiers
離散ベイジアン ネットワーク分類器の決定境界
Bayesian network classifiers are a powerful machine learning tool. In order to evaluate the expressive power of these models, we compute families of polynomials that sign-represent decision functions induced by Bayesian network classifiers. We prove that those families are linear combinations of products of Lagrange basis polynomials. In absence of $V$-structures in the predictor sub-graph, we are also able to prove that this family of polynomials does indeed characterize the specific classifier considered. We then use this representation to bound the number of decision functions representable by Bayesian network classifiers with a given structure.
ベイジアン ネットワーク分類器は、強力な機械学習ツールです。これらのモデルの表現力を評価するために、ベイジアンネットワーク分類器によって誘導される決定関数を符号で表す多項式の族を計算します。これらの族がラグランジュ基底多項式の積の線形結合であることを証明します。予測子サブグラフに$V$-構造がない場合、この多項式のファミリーが実際に考慮された特定の分類器を特徴付けることを証明することもできます。次に、この表現を使用して、ベイジアン ネットワーク分類器で表現可能な決定関数の数を特定の構造で制限します。
Absent Data Generating Classifier for Imbalanced Class Sizes
不均衡なクラス・サイズのデータ生成分類子の不在
We propose an algorithm for two-class classification problems when the training data are imbalanced. This means the number of training instances in one of the classes is so low that the conventional classification algorithms become ineffective in detecting the minority class. We present a modification of the kernel Fisher discriminant analysis such that the imbalanced nature of the problem is explicitly addressed in the new algorithm formulation. The new algorithm exploits the properties of the existing minority points to learn the effects of other minority data points, had they actually existed. The algorithm proceeds iteratively by employing the learned properties and conditional sampling in such a way that it generates sufficient artificial data points for the minority set, thus enhancing the detection probability of the minority class. Implementing the proposed method on a number of simulated and real data sets, we show that our proposed method performs competitively compared to a set of alternative state-of-the-art imbalanced classification algorithms.
私たちは、トレーニング データが不均衡な場合の2クラス分類問題に対するアルゴリズムを提案します。これは、クラスの1つにおけるトレーニング インスタンスの数が非常に少ないため、従来の分類アルゴリズムでは少数クラスの検出が無効になることを意味します。カーネル フィッシャー判別分析の修正を提示し、問題の不均衡な性質が新しいアルゴリズム定式化で明示的に対処されるようにします。新しいアルゴリズムは、既存の少数ポイントの特性を利用して、他の少数データ ポイントが実際に存在した場合の効果を学習します。アルゴリズムは、学習した特性と条件付きサンプリングを使用して反復的に進行し、少数セットに十分な人工データ ポイントを生成するようにすることで、少数クラスの検出確率を高めます。提案された方法を多数のシミュレートされたデータ セットと実際のデータ セットに実装し、提案された方法が、一連の他の最先端の不均衡な分類アルゴリズムと比較して競争力のあるパフォーマンスを発揮することを示します。
When Are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
オーバーコンプリートなトピックモデルはどのような場合に識別可能になりますか?構造化スパース性を持つTensor Tucker分解の一意性
Overcomplete latent representations have been very popular for unsupervised feature learning in recent years. In this paper, we specify which overcomplete models can be identified given observable moments of a certain order. We consider probabilistic admixture or topic models in the overcomplete regime, where the number of latent topics can greatly exceed the size of the observed word vocabulary. While general overcomplete topic models are not identifiable, we establish generic identifiability under a constraint, referred to as topic persistence. Our sufficient conditions for identifiability involve a novel set of “higher order” expansion conditions on the topic-word matrix or the population structure of the model. This set of higher-order expansion conditions allow for overcomplete models, and require the existence of a perfect matching from latent topics to higher order observed words. We establish that random structured topic models are identifiable w.h.p. in the overcomplete regime. Our identifiability results allows for general (non-degenerate) distributions for modeling the topic proportions, and thus, we can handle arbitrarily correlated topics in our framework. Our identifiability results imply uniqueness of a class of tensor decompositions with structured sparsity which is contained in the class of Tucker decompositions, but is more general than the Candecomp/Parafac (CP) decomposition.
近年、教師なし特徴学習では、過剰完全潜在表現が大変人気があります。この論文では、特定の順序の観測可能な瞬間が与えられた場合に、どの過剰完全モデルを識別できるかを指定します。過剰完全領域では、潜在トピックの数が観測された単語語彙のサイズを大幅に超える可能性がある確率的混合モデルまたはトピック モデルを検討します。一般的な過剰完全トピック モデルは識別できませんが、トピック持続性と呼ばれる制約の下で、一般的な識別可能性を確立します。識別可能性の十分な条件には、トピック単語マトリックスまたはモデルの母集団構造に対する新しい一連の「高次」拡張条件が含まれます。この一連の高次拡張条件により、過剰完全モデルが可能になり、潜在トピックからより高次の観測単語への完全な一致の存在が必要になります。過剰完全領域では、ランダム構造化トピック モデルがw.h.p.で識別可能であることを確立します。識別可能性の結果は、トピックの割合をモデル化するための一般的な（非退化）分布を可能にするため、フレームワークで任意の相関トピックを処理できます。識別可能性の結果は、構造化されたスパース性を持つテンソル分解のクラスの一意性を暗示しています。このクラスはTucker分解のクラスに含まれますが、Candecomp/Parafac (CP)分解よりも一般的です。
Derivative Estimation Based on Difference Sequence via Locally Weighted Least Squares Regression
局所加重最小二乗回帰による差分シーケンスに基づく微分推定
A new method is proposed for estimating derivatives of a nonparametric regression function. By applying Taylor expansion technique to a derived symmetric difference sequence, we obtain a sequence of approximate linear regression representation in which the derivative is just the intercept term. Using locally weighted least squares, we estimate the derivative in the linear regression model. The estimator has less bias in both valleys and peaks of the true derivative function. For the special case of a domain with equispaced design points, the asymptotic bias and variance are derived; consistency and asymptotic normality are established. In simulations our estimators have less bias and mean square error than its main competitors, especially second order derivative estimator.
ノンパラメトリック回帰関数の導関数を推定するための新しい方法が提案されています。導出された対称差分シーケンスにテイラー展開手法を適用することにより、導関数が切片項のみである近似線形回帰表現のシーケンスが得られます。局所的に重み付けされた最小二乗法を使用して、線形回帰モデルの導関数を推定します。推定量は、真の導関数の谷と山の両方でバイアスが少なくなります。等間隔の設計点を持つ領域の特殊なケースでは、漸近バイアスと分散が導出されます。一貫性と漸近正規性が確立されます。シミュレーションでは、当社の推定量は、主要な競合他社、特に二次微分推定量よりもバイアスと平均二乗誤差が小さくなっています。
pyGPs — A Python Library for Gaussian Process Regression and Classification
pyGPs — ガウス過程の回帰と分類のためのPythonライブラリ
We introduce pyGPs, an object-oriented implementation of Gaussian processes (gps) for machine learning. The library provides a wide range of functionalities reaching from simple gp specification via mean and covariance and gp inference to more complex implementations of hyperparameter optimization, sparse approximations, and graph based learning. Using Python we focus on usability for both “users” and “researchers”. Our main goal is to offer a user- friendly and flexible implementation of gps for machine learning.
私たちは、機械学習のためのガウス過程(gps)のオブジェクト指向実装であるpyGPsを紹介します。このライブラリは、平均と共分散、gp推論による単純なgp指定から、ハイパーパラメーター最適化、スパース近似、グラフベースの学習のより複雑な実装まで、幅広い機能を提供します。Pythonでは、「ユーザー」と「研究者」の双方にとってのユーザビリティを重視しています。私たちの主な目標は、機械学習用のGPSのユーザーフレンドリーで柔軟な実装を提供することです。
Counting and Exploring Sizes of Markov Equivalence Classes of Directed Acyclic Graphs
有向非巡回グラフのマルコフ同値クラスのサイズのカウントと探索
When learning a directed acyclic graph (DAG) model via observational data, one generally cannot identify the underlying DAG, but can potentially obtain a Markov equivalence class. The size (the number of DAGs) of a Markov equivalence class is crucial to infer causal effects or to learn the exact causal DAG via further interventions. Given a set of Markov equivalence classes, the distribution of their sizes is a key consideration in developing learning methods. However, counting the size of an equivalence class with many vertices is usually computationally infeasible, and the existing literature reports the size distributions only for equivalence classes with ten or fewer vertices. In this paper, we develop a method to compute the size of a Markov equivalence class. We first show that there are five types of Markov equivalence classes whose sizes can be formulated as five functions of the number of vertices respectively. Then we introduce a new concept of a rooted sub- class. The graph representations of rooted subclasses of a Markov equivalence class are used to partition this class recursively until the sizes of all rooted sub-classes can be computed via the five functions. The proposed size counting is efficient for Markov equivalence classes of sparse DAGs with hundreds of vertices. Finally, we explore the size and edge distributions of Markov equivalence classes and find experimentally that, in general, (1) most Markov equivalence classes are half completed and their average sizes are small, and (2) the sizes of sparse classes grow approximately exponentially with the numbers of vertices.
観測データを介して有向非巡回グラフ(DAG)モデルを学習する場合、一般に基礎となるDAGを識別することはできませんが、マルコフ同値クラスを取得できる可能性があります。マルコフ同値クラスのサイズ(DAGの数)は、因果効果を推測したり、さらなる介入を介して正確な因果DAGを学習したりするために重要です。マルコフ同値クラスのセットが与えられた場合、それらのサイズの分布は学習方法の開発において重要な考慮事項です。ただし、多数の頂点を持つ同値クラスのサイズを数えることは通常、計算上不可能であり、既存の文献では10個以下の頂点を持つ同値クラスのサイズ分布のみが報告されています。この論文では、マルコフ同値クラスのサイズを計算する方法を開発します。まず、サイズがそれぞれ頂点数の5つの関数として定式化できる5種類のマルコフ同値クラスがあることを示します。次に、ルート付きサブクラスという新しい概念を紹介します。マルコフ同値類のルート付きサブクラスのグラフ表現は、5つの関数によってすべてのルート付きサブクラスのサイズを計算できるようになるまで、このクラスを再帰的に分割するために使用されます。提案されたサイズ カウントは、数百の頂点を持つスパースDAGのマルコフ同値類に効率的です。最後に、マルコフ同値類のサイズとエッジの分布を調査し、一般に、(1)ほとんどのマルコフ同値類は半分完成しており、平均サイズは小さいこと、(2)スパース クラスのサイズは頂点の数とともにほぼ指数関数的に増加することが実験的にわかりました。
A General Framework for Fast Stagewise Algorithms
高速ステージワイズアルゴリズムの一般的なフレームワーク
Forward stagewise regression follows a very simple strategy for constructing a sequence of sparse regression estimates: it starts with all coefficients equal to zero, and iteratively updates the coefficient (by a small amount $\epsilon$) of the variable that achieves the maximal absolute inner product with the current residual. This procedure has an interesting connection to the lasso: under some conditions, it is known that the sequence of forward stagewise estimates exactly coincides with the lasso path, as the step size $\epsilon$ goes to zero. Furthermore, essentially the same equivalence holds outside of least squares regression, with the minimization of a differentiable convex loss function subject to an $\ell_1$ norm constraint (the stagewise algorithm now updates the coefficient corresponding to the maximal absolute component of the gradient). Even when they do not match their $\ell_1$-constrained analogues, stagewise estimates provide a useful approximation, and are computationally appealing. Their success in sparse modeling motivates the question: can a simple, effective strategy like forward stagewise be applied more broadly in other regularization settings, beyond the $\ell_1$ norm and sparsity? The current paper is an attempt to do just this. We present a general framework for stagewise estimation, which yields fast algorithms for problems such as group- structured learning, matrix completion, image denoising, and more.
フォワード段階的回帰は、一連のスパース回帰推定値を構築するための非常に単純な戦略に従います。すべての係数がゼロである状態から開始し、現在の残差との絶対内積が最大となる変数の係数を(小さな量$\epsilon$だけ)繰り返し更新します。この手順はLassoと興味深い関係があります。ある条件下では、ステップ サイズ$\epsilon$がゼロになるにつれて、フォワード段階的推定値のシーケンスがLassoパスと正確に一致することがわかっています。さらに、最小二乗回帰以外でも、$\ell_1$ノルム制約に従う微分可能な凸損失関数の最小化で、基本的に同じ同等性が保持されます(段階的アルゴリズムは、勾配の最大絶対成分に対応する係数を更新します)。$\ell_1$制約の類似物と一致しない場合でも、段階的推定値は有用な近似値を提供し、計算上魅力的です。スパースモデリングにおける彼らの成功は、次のような疑問を生じさせます。フォワードステージワイズのようなシンプルで効果的な戦略は、$\ell_1$ノルムとスパース性を超えて、他の正則化設定に広く適用できるのでしょうか?現在の論文は、まさにこれを実現するための試みです。私たちは、グループ構造化学習、行列補完、画像ノイズ除去などの問題に対する高速アルゴリズムを生み出す、ステージワイズ推定の一般的なフレームワークを提示します。
Bayesian Nonparametric Covariance Regression
ベイズノンパラメトリック共分散回帰
Capturing predictor-dependent correlations amongst the elements of a multivariate response vector is fundamental to numerous applied domains, including neuroscience, epidemiology, and finance. Although there is a rich literature on methods for allowing the variance in a univariate regression model to vary with predictors, relatively little has been done in the multivariate case. As a motivating example, we consider the Google Flu Trends data set, which provides indirect measurements of influenza incidence at a large set of locations over time (our predictor). To accurately characterize temporally evolving influenza incidence across regions, it is important to develop statistical methods for a time-varying covariance matrix. Importantly, the locations provide a redundant set of measurements and do not yield a sparse nor static spatial dependence structure. We propose to reduce dimensionality and induce a flexible Bayesian nonparametric covariance regression model by relating these location-specific trajectories to a lower-dimensional subspace through a latent factor model with predictor-dependent factor loadings. These loadings are in terms of a collection of basis functions that vary nonparametrically over the predictor space. Such low-rank approximations are in contrast to sparse precision assumptions, and are appropriate in a wide range of applications. Our formulation aims to address three challenges: scaling to large $p$ domains, coping with missing values, and allowing an irregular grid of observations. The model is shown to be highly flexible, while leading to a computationally feasible implementation via Gibbs sampling. The ability to scale to large $p$ domains and cope with missing values is fundamental in analyzing the Google Flu Trends data.
多変量応答ベクトルの要素間の予測子依存の相関関係を捉えることは、神経科学、疫学、金融など、数多くの応用分野の基礎となります。単変量回帰モデルの分散を予測子によって変化させる方法については豊富な文献がありますが、多変量の場合ではほとんど研究されていません。動機となる例として、Google Flu Trendsデータ セットを検討します。このデータ セットは、時間の経過に伴う大規模な場所のセットでのインフルエンザ発生率の間接的な測定値を提供します(予測子)。地域間で時間的に変化するインフルエンザ発生率を正確に特徴付けるには、時間とともに変化する共分散行列の統計的手法を開発することが重要です。重要なのは、場所によって測定値のセットが冗長になり、スパースでも静的でもない空間依存構造が生成されないことです。私たちは、予測子に依存する因子負荷を持つ潜在因子モデルを通じて、これらの場所固有の軌跡をより低次元のサブスペースに関連付けることで、次元を削減し、柔軟なベイジアン ノンパラメトリック共分散回帰モデルを誘導することを提案します。これらの負荷は、予測子空間上でノンパラメトリックに変化する基底関数のコレクションに関するものです。このような低ランク近似は、スパース精度の仮定とは対照的であり、幅広いアプリケーションに適しています。私たちの定式化は、大規模な$p$ドメインへのスケーリング、欠損値への対処、および不規則な観測グリッドの許可という3つの課題に対処することを目的としています。このモデルは非常に柔軟であることが示されており、ギブス サンプリングによる計算上実行可能な実装につながります。大規模な$p$ドメインへのスケーリングと欠損値への対処能力は、Google Flu Trendsデータの分析において不可欠です。
Complexity of Equivalence and Learning for Multiplicity Tree Automata
多重度木オートマトンにおける等価性と学習の複雑さ
We consider the query and computational complexity of learning multiplicity tree automata in Angluin’s exact learning model. In this model, there is an oracle, called the Teacher, that can answer membership and equivalence queries posed by the Learner. Motivated by this feature, we first characterise the complexity of the equivalence problem for multiplicity tree automata, showing that it is logspace equivalent to polynomial identity testing. We then move to query complexity, deriving lower bounds on the number of queries needed to learn multiplicity tree automata over both fixed and arbitrary fields. In the latter case, the bound is linear in the size of the target automaton. The best known upper bound on the query complexity over arbitrary fields derives from an algorithm of Habrard and Oncina (2006), in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, a smallest counterexample tree may already be exponential in the size of the target automaton. Thus the above algorithm has query complexity exponentially larger than our lower bound, and does not run in time polynomial in the size of the target automaton. We give a new learning algorithm for multiplicity tree automata in which counterexamples to equivalence queries are represented as DAGs. The query complexity of this algorithm is quadratic in the target automaton size and linear in the size of a largest counterexample. In particular, if the Teacher always returns DAG counterexamples of minimal size then the query complexity is quadratic in the target automaton size—almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.
私たちは、Angluinの正確な学習モデルで多重木オートマトンを学習する際のクエリと計算の複雑さについて検討します。このモデルには、学習者によって提示されたメンバーシップと同値性のクエリに答えることができる教師と呼ばれるオラクルがあります。この特徴に着目して、まず多重木オートマトンに対する同値性の問題の複雑さを特徴付け、それが多項式恒等テストと対数空間で等価であることを示します。次にクエリの複雑さに移り、固定フィールドと任意フィールドの両方で多重木オートマトンを学習するために必要なクエリ数の下限を導きます。後者の場合、下限はターゲット オートマトンのサイズに比例します。任意のフィールドでのクエリの複雑さの最もよく知られている上限は、HabrardとOncina (2006)のアルゴリズムから導き出されます。このアルゴリズムでは、クエリの数はターゲット オートマトンのサイズと、教師によって返されるツリーとして表される最大の反例のサイズに比例します。しかし、最小の反例ツリーは、ターゲット オートマトンのサイズに対して既に指数関数的になっている可能性があります。したがって、上記のアルゴリズムのクエリ複雑度は下限よりも指数関数的に大きくなり、ターゲット オートマトンのサイズの多項式時間で実行されません。同値クエリに対する反例がDAGとして表現される多重木オートマトンの新しい学習アルゴリズムを示します。このアルゴリズムのクエリ複雑度は、ターゲット オートマトンのサイズに対して2次で、最大反例のサイズに対して線形です。特に、教師が常に最小サイズのDAG反例を返す場合、クエリ複雑度はターゲット オートマトンのサイズに対して2次になります。これは下限とほぼ一致し、これまで知られている最良のアルゴリズムを指数関数的に改善します。
The Libra Toolkit for Probabilistic Models
確率モデルのためのLibraツールキット
The Libra Toolkit is a collection of algorithms for learning and inference with discrete probabilistic models, including Bayesian networks, Markov networks, dependency networks, and sum-product networks. Compared to other toolkits, Libra places a greater emphasis on learning the structure of tractable models in which exact inference is efficient. It also includes a variety of algorithms for learning graphical models in which inference is potentially intractable, and for performing exact and approximate inference. Libra is released under a 2-clause BSD license to encourage broad use in academia and industry.
Libraツールキットは、ベイジアンネットワーク、マルコフネットワーク、依存関係ネットワーク、和積ネットワークなどの離散確率モデルを使用した学習と推論のためのアルゴリズムのコレクションです。他のツールキットと比較して、Libraは、正確な推論が効率的である扱いやすいモデルの構造の学習に重点を置いています。また、推論が難解な可能性のあるグラフィカルモデルを学習したり、正確な推論と近似推論を実行したりするためのさまざまなアルゴリズムも含まれています。Libraは、学界や産業界での幅広い使用を促進するために、2条項BSDライセンスの下でリリースされています。
From Dependency to Causality: A Machine Learning Approach
依存性から因果関係へ:機械学習アプローチ
The relationship between statistical dependency and causality lies at the heart of all statistical approaches to causal inference. Recent results in the ChaLearn cause-effect pair challenge have shown that causal directionality can be inferred with good accuracy also in Markov indistinguishable configurations thanks to data driven approaches. This paper proposes a supervised machine learning approach to infer the existence of a directed causal link between two variables in multivariate settings with $n>2$ variables. The approach relies on the asymmetry of some conditional (in)dependence relations between the members of the Markov blankets of two variables causally connected. Our results show that supervised learning methods may be successfully used to extract causal information on the basis of asymmetric statistical descriptors also for $n>2$ variate distributions.
統計的依存性と因果関係の関係は、因果推論に対するすべての統計的アプローチの中心にあります。ChaLearnの因果関係ペアチャレンジの最近の結果では、データ駆動型のアプローチにより、マルコフの区別がつかない構成でも因果関係の方向性を高い精度で推測できることが示されています。この論文では、$n>2$変数を持つ多変量設定の2つの変数間に有向因果関係が存在すると推論するための教師あり機械学習アプローチを提案しています。このアプローチは、因果的に接続された2つの変数のマルコフブランケットのメンバー間の条件付き(非)依存関係の非対称性に依存しています。私たちの結果は、教師あり学習法が、非対称統計記述子に基づいて因果情報を抽出するためにうまく使用できることを示しています。また、$n>2$の変量分布についても。
Geometry and Expressive Power of Conditional Restricted Boltzmann Machines
条件付き制限付きボルツマンマシンの幾何学と表現力
Conditional restricted Boltzmann machines are undirected stochastic neural networks with a layer of input and output units connected bipartitely to a layer of hidden units. These networks define models of conditional probability distributions on the states of the output units given the states of the input units, parameterized by interaction weights and biases. We address the representational power of these models, proving results on their ability to represent conditional Markov random fields and conditional distributions with restricted supports, the minimal size of universal approximators, the maximal model approximation errors, and on the dimension of the set of representable conditional distributions. We contribute new tools for investigating conditional probability models, which allow us to improve the results that can be derived from existing work on restricted Boltzmann machine probability models.
条件付き制限ボルツマンマシンは、入力ユニットと出力ユニットの層が隠れユニットの層に二分的に接続された無向確率ニューラルネットワークです。これらのネットワークは、入力ユニットの状態を前提として、交互作用の重みとバイアスによってパラメーター化された、出力ユニットの状態に関する条件付き確率分布のモデルを定義します。これらのモデルの表現力に取り組み、条件付きマルコフ確率場と制限されたサポートを持つ条件付き分布を表現する能力、ユニバーサル近似器の最小サイズ、最大モデル近似誤差、および表現可能な条件付き分布のセットの次元に関する結果を証明します。私たちは、条件付き確率モデルを調査するための新しいツールを提供し、制限付きボルツマンマシン確率モデルに関する既存の研究から導き出される結果を改善することができます。
Multiclass Learnability and the ERM Principle
多クラス学習可能性とERMの原則
We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning symmetric multiclass hypothesis classes—classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone’s dimension.
私たちは、いくつかの学習環境におけるマルチクラス予測のサンプルの複雑さを研究します。PACの設定について、私たちの分析は驚くべき現象を明らかにします:二項分類とは対照的に、一部の経験的リスク最小化者(ERM学習者)が他のものよりもサンプルの複雑さが低いマルチクラス仮説クラスが存在することを示しています。さらに、一部のERM学習者が学習できるクラスもあれば、他のERM学習者が学習できないクラスもあります。優れたERM学習器を設計するための原則を提案し、この原則を使用して、ラベル名の順列の下で不変である対称多クラス仮説クラス—クラスを学習するサンプルの複雑さの厳密な境界を証明します。さらに、リトルストーンの次元の新しい一般化を使用して、オンライン設定とバンディット設定でのマルチクラス学習の間違いと後悔の境界の特徴付けを提供します。
Achievability of Asymptotic Minimax Regret by Horizon-Dependent and Horizon-Independent Strategies
地平線依存戦略と地平線非依存戦略による漸近的ミニマックス後悔の達成可能性
The normalized maximum likelihood distribution achieves minimax coding (log-loss) regret given a fixed sample size, or horizon, $n$. It generally requires that $n$ be known in advance. Furthermore, extracting the sequential predictions from the normalized maximum likelihood distribution is computationally infeasible for most statistical models. Several computationally feasible alternative strategies have been devised. We characterize the achievability of asymptotic minimaxity by horizon-dependent and horizon-independent strategies. We prove that no horizon-independent strategy can be asymptotically minimax in the multinomial case. A weaker result is given in the general case subject to a condition on the horizon-dependence of the normalized maximum likelihood. Motivated by these negative results, we demonstrate that an easily implementable Bayes mixture based on a conjugate Dirichlet prior with a simple dependency on $n$ achieves asymptotic minimaxity for all sequences, simplifying earlier similar proposals. Our numerical experiments for the Bernoulli model demonstrate improved finite- sample performance by a number of novel horizon-dependent and horizon-independent algorithms.
正規化最大尤度分布は、固定サンプルサイズ、つまりホライズン$n$が与えられた場合に、ミニマックスコーディング(対数損失)後悔を実現します。通常、$n$が事前にわかっている必要があります。さらに、正規化最大尤度分布からシーケンシャル予測を抽出することは、ほとんどの統計モデルでは計算上不可能です。計算上実行可能な代替戦略がいくつか考案されています。漸近的ミニマキシの達成可能性を、ホライズン依存戦略とホライズン非依存戦略によって特徴付けます。多項式の場合、ホライズン非依存戦略は漸近的にミニマックスにはならないことを証明します。正規化最大尤度のホライズン依存性に関する条件に従う一般的なケースでは、より弱い結果が得られます。これらの否定的な結果に動機付けられて、$n$に単純に依存する共役ディリクレ事前分布に基づく、簡単に実装可能なベイズ混合がすべてのシーケンスに対して漸近的ミニマキシを達成し、以前の同様の提案を簡素化することを実証します。ベルヌーイ モデルに関する私たちの数値実験では、いくつかの新しい地平線依存型および地平線非依存型アルゴリズムによって有限サンプルのパフォーマンスが向上することが実証されています。
Agnostic Insurability of Model Classes
モデルクラスの不可知性保険
Motivated by problems in insurance, our task is to predict finite upper bounds on a future draw from an unknown distribution $p$ over natural numbers. We can only use past observations generated independently and identically distributed according to $p$. While $p$ is unknown, it is known to belong to a given collection $\mathcal{P}$ of probability distributions on the natural numbers. The support of the distributions $p \in \mathcal{P}$ may be unbounded, and the prediction game goes on for infinitely many draws. We are allowed to make observations without predicting upper bounds for some time. But we must, with probability $1$, start and then continue to predict upper bounds after a finite time irrespective of which $p \in \mathcal{P}$ governs the data. If it is possible, without knowledge of $p$ and for any prescribed confidence however close to $1$, to come up with a sequence of upper bounds that is never violated over an infinite time window with confidence at least as big as prescribed, we say the model class $\mathcal{P}$ is insurable. We completely characterize the insurability of any class $\mathcal{P}$ of distributions over natural numbers by means of a condition on how the neighborhoods of distributions in $\mathcal{P}$ should be, one that is both necessary and sufficient.
保険の問題に動機付けられた私たちの仕事は、自然数に対する未知の分布$p$からの将来の抽選の有限の上限を予測することです。独立に生成され、$p$に従って同一に分布する過去の観測値のみを使用できます。$p$は未知ですが、自然数に関する確率分布の特定のコレクション$\mathcal{P}$に属することがわかっています。分布$p \in \mathcal{P}$のサポートは無制限である可能性があり、予測ゲームは無限回の抽選で続きます。しばらくの間、上限を予測せずに観測を行うことができます。しかし、どの$p \in \mathcal{P}$がデータを支配するかに関係なく、有限時間後には確率$1$で上限の予測を開始し、その後継続する必要があります。$p$を知らなくても、また、どんなに$1$に近い規定の信頼度でも、規定された信頼度以上で無限の時間枠にわたって決して破られることのない上限のシーケンスを導き出すことができる場合、モデルクラス$\mathcal{P}$は保険可能であるといいます。自然数上の分布の任意のクラス$\mathcal{P}$の保険可能性は、$\mathcal{P}$内の分布の近傍がどのようになるべきかという必要かつ十分な条件によって完全に特徴付けられます。
Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
スパースガウスベイジアンネットワークの凹型ペナルティ評価
We develop a penalized likelihood estimation framework to learn the structure of Gaussian Bayesian networks from observational data. In contrast to recent methods which accelerate the learning problem by restricting the search space, our main contribution is a fast algorithm for score-based structure learning which does not restrict the search space in any way and works on high-dimensional data sets with thousands of variables. Our use of concave regularization, as opposed to the more popular $\ell_0$ (e.g. BIC) penalty, is new. Moreover, we provide theoretical guarantees which generalize existing asymptotic results when the underlying distribution is Gaussian. Most notably, our framework does not require the existence of a so-called faithful DAG representation, and as a result, the theory must handle the inherent nonidentifiability of the estimation problem in a novel way. Finally, as a matter of independent interest, we provide a comprehensive comparison of our approach to several standard structure learning methods using open-source packages developed for the R language. Based on these experiments, we show that our algorithm obtains higher sensitivity with comparable false discovery rates for high- dimensional data and scales efficiently as the number of nodes increases. In particular, the total runtime for our method to generate a solution path of 20 estimates for DAGs with 8000 nodes is around one hour.
私たちは、観測データからガウスベイジアンネットワークの構造を学習するためのペナルティ付き尤度推定フレームワークを開発しました。探索空間を制限することで学習問題を加速する最近の方法とは対照的に、我々の主な貢献は、探索空間をまったく制限せず、数千の変数を持つ高次元データセットで機能するスコアベースの構造学習の高速アルゴリズムです。より一般的な$\ell_0$ (例: BIC)ペナルティではなく、凹正則化を使用するのは新しいことです。さらに、基礎となる分布がガウス分布である場合に、既存の漸近結果を一般化する理論的な保証を提供します。最も注目すべきは、我々のフレームワークはいわゆる忠実なDAG表現の存在を必要とせず、その結果、理論は推定問題に固有の識別不可能性を新しい方法で処理する必要があることです。最後に、独立した関心事項として、R言語用に開発されたオープンソースパッケージを使用したいくつかの標準的な構造学習方法と我々のアプローチの包括的な比較を示します。これらの実験に基づいて、私たちのアルゴリズムは、高次元データに対して同等の誤検出率でより高い感度を獲得し、ノード数の増加に応じて効率的に拡張できることを示しています。特に、8000ノードのDAGに対して20の推定値のソリューション パスを生成するための私たちの方法の合計実行時間は約1時間です。
Adaptive Strategy for Stratified Monte Carlo Sampling
層別モンテカルロサンプリングの適応戦略
We consider the problem of stratified sampling for Monte Carlo integration of a random variable. We model this problem in a $K$-armed bandit, where the arms represent the $K$ strata. The goal is to estimate the integral mean, that is a weighted average of the mean values of the arms. The learner is allowed to sample the variable $n$ times, but it can decide on-line which stratum to sample next. We propose an UCB-type strategy that samples the arms according to an upper bound on their estimated standard deviations. We compare its performance to an ideal sample allocation that knows the standard deviations of the arms. For sub-Gaussian arm distributions, we provide bounds on the total regret: a distribution-dependent bound of order $\text{poly}(\lambda_{\min}^{-1})\tilde{O}(n^{-3/2})$ (The notation $a_n=\text{poly}(b_n)$ means that there exist $C$,$\alpha>0$ such that $a_n\le Cb_n^\alpha$ for $n$ large enough. Moreover, $a_n=\tilde{O}(b_n)$ means that $a_n/b_n=\text{poly}(\log n)$ for $n$ large enough.) that depends on a measure of the disparity $\lambda_{\min}$ of the per stratum variances and a distribution-free bound $\text{poly}(K)\tilde{O}(n^{-7/6})$ that does not. We give similar, but somewhat sharper bounds on a proxy of the regret. The problem- independent bound for this proxy matches its recent minimax lower bound in terms of $n$ up to a $\log n$ factor.
私たちは、ランダム変数のモンテカルロ積分のための層別サンプリングの問題を検討します。この問題を、Kアーム バンディットでモデル化します。アームはK層を表します。目標は、積分平均、つまりアームの平均値の加重平均を推定することです。学習者は変数をn回サンプリングできますが、次にどの層をサンプリングするかはオンラインで決定できます。推定された標準偏差の上限に従ってアームをサンプリングするUCBタイプの戦略を提案します。そのパフォーマンスを、アームの標準偏差がわかっている理想的なサンプル割り当てと比較します。サブガウス分布のアーム分布の場合、総後悔の境界値を提供します。これは、層ごとの分散の不一致の尺度$\lambda_{\min}$に依存する分布依存の境界値$\text{poly}(\lambda_{\min}^{-1})\tilde{O}(n^{-3/2})$です(表記$a_n=\text{poly}(b_n)$は、十分に大きい$n$に対して$a_n\le Cb_n^\alpha$となる$C$,$\alpha>0$が存在することを意味します。さらに、$a_n=\tilde{O}(b_n)$は、十分に大きい$n$に対して$a_n/b_n=\text{poly}(\log n)$であることを意味します)。また、分布に依存しない境界値$\text{poly}(K)\tilde{O}(n^{-7/6})$は、この境界値に依存しません。後悔の代理変数についても、同様だがやや厳しい境界を与える。この代理変数の問題に依存しない境界は、$\log n$係数までの$n$に関して最近のミニマックス下限に一致します。
Existence and Uniqueness of Proper Scoring Rules
適切な採点ルールの存在と独自性
To discuss the existence and uniqueness of proper scoring rules one needs to extend the associated entropy functions as sublinear functions to the conic hull of the prediction set. In some natural function spaces, such as the Lebesgue $L^p$-spaces over $\mathbb{R}^d$, the positive cones have empty interior. Entropy functions defined on such cones have directional derivatives only, which typically exist on large subspaces and behave similarly to gradients. Certain entropies may be further extended continuously to open cones in normed spaces containing signed densities. The extended densities are Gateaux differentiable except on a negligible set and have everywhere continuous subgradients due to the supporting hyperplane theorem. We introduce the necessary framework from analysis and algebra that allows us to give an affirmative answer to the titular question of the paper. As a result of this, we give a formal sense in which entropy functions have uniquely associated proper scoring rules. We illustrate our framework by studying the derivatives and subgradients of the following three prototypical entropies: Shannon entropy, Hyvarinen entropy, and quadratic entropy.
適切なスコアリング規則の存在と一意性を議論するには、関連するエントロピー関数をサブ線形関数として予測セットの円錐包に拡張する必要があります。$\mathbb{R}^d$上のルベーグ$L^p$空間などの一部の自然関数空間では、正の円錐は空の内部を持ちます。このような円錐上で定義されたエントロピー関数は方向微分のみを持ち、通常は大きな部分空間上に存在し、勾配と同様に動作します。特定のエントロピーは、符号付き密度を含むノルム空間内の開円錐に連続的にさらに拡張できます。拡張された密度は、無視できる集合を除いてガトー微分可能であり、サポートする超平面定理により、どこでも連続的なサブ勾配を持ちます。解析と代数から必要なフレームワークを導入し、論文のタイトルの質問に肯定的な回答を与えることができます。この結果、エントロピー関数が一意に関連する適切なスコアリング規則を持つという形式的な意味を与えます。私たちは、シャノン エントロピー、ヒヴァリネン エントロピー、および2次エントロピーという3つの典型的なエントロピーの導関数とサブ勾配を調べることで、このフレームワークを説明します。
Constraint-based Causal Discovery from Multiple Interventions over Overlapping Variable Sets
重複する変数セットに対する複数の介入からの制約に基づく因果関係の発見
Scientific practice typically involves repeatedly studying a system, each time trying to unravel a different perspective. In each study, the scientist may take measurements under different experimental conditions (interventions, manipulations, perturbations) and measure different sets of quantities (variables). The result is a collection of heterogeneous data sets coming from different data distributions. In this work, we present algorithm COmbINE, which accepts a collection of data sets over overlapping variable sets under different experimental conditions; COmbINE then outputs a summary of all causal models indicating the invariant and variant structural characteristics of all models that simultaneously fit all of the input data sets. COmbINE converts estimated dependencies and independencies in the data into path constraints on the data- generating causal model and encodes them as a SAT instance. The algorithm is sound and complete in the sample limit. To account for conflicting constraints arising from statistical errors, we introduce a general method for sorting constraints in order of confidence, computed as a function of their corresponding p-values. In our empirical evaluation, COmbINE outperforms in terms of efficiency the only pre-existing similar algorithm; the latter additionally admits feedback cycles, but does not admit conflicting constraints which hinders the applicability on real data. As a proof-of-concept, COmbINE is employed to co- analyze 4 real, mass-cytometry data sets measuring phosphorylated protein concentrations of overlapping protein sets under 3 different interventions.
科学の実践には通常、システムを繰り返し研究することが含まれており、そのたびに異なる視点を解明しようとします。各研究で、科学者は異なる実験条件(介入、操作、摂動)で測定を行い、異なる量(変数)のセットを測定します。その結果、異なるデータ分布からの異種データ セットのコレクションが生まれます。この研究では、異なる実験条件の下で重複する変数セットのデータ セットのコレクションを受け入れるアルゴリズムCOmbINEを紹介します。次に、COmbINEは、すべての入力データ セットに同時に適合するすべてのモデルの不変および可変の構造特性を示すすべての因果モデルの要約を出力します。COmbINEは、データ内の推定された依存関係と独立性を、データを生成する因果モデルのパス制約に変換し、SATインスタンスとしてエンコードします。このアルゴリズムは、サンプル制限内で健全かつ完全です。統計エラーから生じる矛盾する制約を考慮するために、対応するp値の関数として計算された信頼度の順に制約を並べ替える一般的な方法を紹介します。私たちの経験的評価では、COmbINEは、効率の点で唯一の既存の類似アルゴリズムよりも優れています。後者はフィードバック サイクルも許容しますが、実際のデータへの適用を妨げる矛盾する制約は許容しません。概念実証として、COmbINEは、3つの異なる介入下で重複するタンパク質セットのリン酸化タンパク質濃度を測定する4つの実際の質量サイトメトリー データ セットを共同分析するために使用されます。
On Linearly Constrained Minimum Variance Beamforming
線形制約付き最小分散ビームフォーミング上
Beamforming is a widely used technique for source localization in signal processing and neuroimaging. A number of vector- beamformers have been introduced to localize neuronal activity by using magnetoencephalography (MEG) data in the literature. However, the existing theoretical analyses on these beamformers have been limited to simple cases, where no more than two sources are allowed in the associated model and the theoretical sensor covariance is also assumed known. The information about the effects of the MEG spatial and temporal dimensions on the consistency of vector-beamforming is incomplete. In the present study, we consider a class of vector-beamformers defined by thresholding the sensor covariance matrix, which include the standard vector-beamformer as a special case. A general asymptotic theory is developed for these vector-beamformers, which shows the extent of effects to which the MEG spatial and temporal dimensions on estimating the neuronal activity index. The performances of the proposed beamformers are assessed by simulation studies. Superior performances of the proposed beamformers are obtained when the signal-to-noise ratio is low. We apply the proposed procedure to real MEG data sets derived from five sessions of a human face-perception experiment, finding several highly active areas in the brain. A good agreement between these findings and the known neurophysiology of the MEG response to human face perception is shown.
ビームフォーミングは、信号処理および神経イメージングにおける音源定位に広く使用されている技術です。文献では、脳磁図(MEG)データを使用して神経活動の定位を行うベクトル ビームフォーマーが数多く紹介されています。しかし、これらのビームフォーマーに関する既存の理論分析は、関連モデルで2つ以上の音源が許可されず、理論的なセンサー共分散も既知であると想定される単純なケースに限られています。MEGの空間的および時間的次元がベクトル ビームフォーミングの一貫性に与える影響に関する情報は不完全です。この研究では、センサー共分散行列をしきい値処理することによって定義されるベクトル ビームフォーマーのクラスを検討します。これには、標準ベクトル ビームフォーマーが特殊なケースとして含まれています。これらのベクトル ビームフォーマーの一般的な漸近理論が開発され、MEGの空間的および時間的次元が神経活動指数の推定に与える影響の程度が示されています。提案されたビームフォーマーの性能は、シミュレーション研究によって評価されます。提案されたビームフォーマーは、信号対雑音比が低い場合に優れた性能を発揮します。提案された手順を、人間の顔認識実験の5セッションから得られた実際のMEGデータ セットに適用し、脳内のいくつかの非常に活発な領域を発見しました。これらの発見と、人間の顔認識に対するMEG応答の既知の神経生理学との間には良好な一致が見られました。
Photonic Delay Systems as Machine Learning Implementations
機械学習実装としてのフォトニック遅延システム
Nonlinear photonic delay systems present interesting implementation platforms for machine learning models. They can be extremely fast, offer great degrees of parallelism and potentially consume far less power than digital processors. So far they have been successfully employed for signal processing using the Reservoir Computing paradigm. In this paper we show that their range of applicability can be greatly extended if we use gradient descent with backpropagation through time on a model of the system to optimize the input encoding of such systems. We perform physical experiments that demonstrate that the obtained input encodings work well in reality, and we show that optimized systems perform significantly better than the common Reservoir Computing approach. The results presented here demonstrate that common gradient descent techniques from machine learning may well be applicable on physical neuro-inspired analog computers.
非線形フォトニック遅延システムは、機械学習モデルのための興味深い実装プラットフォームを提供します。これらは非常に高速で、並列処理が非常に高く、デジタルプロセッサよりもはるかに少ない電力を消費する可能性があります。これまでのところ、Reservoir Computingパラダイムを使用した信号処理にうまく採用されています。この論文では、システムのモデルで時間の経過に伴う逆伝播を伴う勾配降下法を使用して、そのようなシステムの入力エンコーディングを最適化すると、それらの適用範囲が大幅に拡張できることを示します。得られた入力エンコーディングが実際にうまく機能することを実証する物理実験を行い、最適化されたシステムが一般的なリザーバーコンピューティングアプローチよりも大幅に優れたパフォーマンスを発揮することを示しています。ここで紹介した結果は、機械学習による一般的な勾配降下法が、物理的な神経に触発されたアナログコンピュータに適用できる可能性があることを示しています。
Alexey Chervonenkis’s Bibliography
Alexey Chervonenkisの参考文献
Alexey Chervonenkis’s Bibliography: Introductory Comments
Alexey Chervonenkisの参考文献:紹介コメント
Learning Using Privileged Information: Similarity Control and Knowledge Transfer
特権情報を用いた学習:類似性制御と知識移転
This paper describes a new paradigm of machine learning, in which Intelligent Teacher is involved. During training stage, Intelligent Teacher provides Student with information that contains, along with classification of each example, additional privileged information (for example, explanation) of this example. The paper describes two mechanisms that can be used for significantly accelerating the speed of Student’s learning using privileged information: (1) correction of Student’s concepts of similarity between examples, and (2) direct Teacher-Student knowledge transfer.
この論文では、Intelligent Teacherが関与する機械学習の新しいパラダイムについて説明します。トレーニング・ステージでは、Intelligent Teacherは、各例の分類とともに、この例の追加の特権情報(例えば、説明)を含む情報をStudentに提供します。この論文では、特権情報を使用して生徒の学習速度を大幅に加速するために使用できる2つのメカニズム、すなわち、(1)例間の類似性に関する生徒の概念の修正、および(2)教師と生徒の直接的な知識の伝達について説明します。
Predicting a Switching Sequence of Graph Labelings
グラフラベリングのスイッチングシーケンスの予測
We study the problem of predicting online the labeling of a graph. We consider a novel setting for this problem in which, in addition to observing vertices and labels on the graph, we also observe a sequence of just vertices on a second graph. A latent labeling of the second graph selects one of $K$ labelings to be active on the first graph. We propose a polynomial time algorithm for online prediction in this setting and derive a mistake bound for the algorithm. The bound is controlled by the geometric cut of the observed and latent labelings, as well as the resistance diameters of the graphs. When specialized to multitask prediction and online switching problems the bound gives new and sharper results under certain conditions.
私たちは、グラフのラベリングをオンラインで予測する問題を研究します。この問題に対しては、グラフ上の頂点とラベルを観察するだけでなく、2番目のグラフ上の頂点だけのシーケンスも観察するという新しい設定を検討します。2番目のグラフの潜在的なラベル付けでは、最初のグラフでアクティブにする$K$ラベルの1つが選択されます。この設定でオンライン予測用の多項式時間アルゴリズムを提案し、アルゴリズムの誤りの範囲を導き出します。境界は、観測された標識と潜在的な標識の幾何学的カット、およびグラフの抵抗直径によって制御されます。マルチタスク予測とオンラインスイッチングの問題に特化すると、境界は特定の条件下で新しくより鮮明な結果をもたらします。
Towards an Axiomatic Approach to Hierarchical Clustering of Measures
測度の階層的クラスタリングへの公理的アプローチに向けて
We propose some axioms for hierarchical clustering of probability measures and investigate their ramifications. The basic idea is to let the user stipulate the clusters for some elementary measures. This is done without the need of any notion of metric, similarity or dissimilarity. Our main results then show that for each suitable choice of user-defined clustering on elementary measures we obtain a unique notion of clustering on a large set of distributions satisfying a set of additivity and continuity axioms. We illustrate the developed theory by numerous examples including some with and some without a density.
私たちは、確率測度の階層的クラスタリングのためのいくつかの公理を提案し、それらの影響を調査します。基本的な考え方は、ユーザーがいくつかの基本的な対策のためにクラスターを規定できるようにすることです。これは、メートル法、類似性、または非類似性の概念を必要とせずに行われます。次に、私たちの主な結果は、基本測度上のユーザー定義クラスタリングの適切な選択ごとに、一連の加法性と連続性の公理を満たす大規模な分布セットでのクラスタリングのユニークな概念が得られることを示しています。開発された理論を、密度のあるものとないものを含む多数の例で説明します。
Semi-Supervised Interpolation in an Anticausal Learning Scenario
反因果学習シナリオにおける半教師あり補間
According to a recently stated ‘independence postulate’, the distribution $P_{\rm cause}$ contains no information about the conditional $P_{\rm effect | cause}$ while $P_{\rm effect}$ may contain information about $P_{\rm cause | effect}$. Since semi- supervised learning (SSL) attempts to exploit information from $P_X$ to assist in predicting $Y$ from $X$, it should only work in anticausal direction, i.e., when $Y$ is the cause and $X$ is the effect. In causal direction, when $X$ is the cause and $Y$ the effect, unlabelled $x$-values should be useless. To shed light on this asymmetry, we study a deterministic causal relation $Y=f(X)$ as recently assayed in Information-Geometric Causal Inference (IGCI). Within this model, we discuss two options to formalize the independence of $P_X$ and $f$ as an orthogonality of vectors in appropriate inner product spaces. We prove that unlabelled data help for the problem of interpolating a monotonically increasing function if and only if the orthogonality conditions are violated — which we only expect for the anticausal direction. Here, performance of SSL and its supervised baseline analogue is measured in terms of two different loss functions: first, the mean squared error and second the surprise in a Bayesian prediction scenario.
最近発表された「独立公理」によれば、分布$P_{\rm cause}$には条件付き$P_{\rm effect | cause}$に関する情報は含まれませんが、$P_{\rm effect}$には$P_{\rm cause | effect}$に関する情報が含まれる場合があります。半教師あり学習(SSL)は$P_X$からの情報を利用して$X$から$Y$を予測しようとするため、反因果方向、つまり$Y$が原因で$X$が結果である場合にのみ機能します。因果方向では、$X$が原因で$Y$が結果である場合、ラベルのない$x$値は役に立たないはずです。この非対称性を明らかにするために、情報幾何学的因果推論(IGCI)で最近評価された決定論的因果関係$Y=f(X)$を研究します。このモデルでは、適切な内積空間のベクトルの直交性として$P_X$と$f$の独立性を形式化する2つのオプションについて説明します。ラベルなしのデータは、直交性条件に違反する場合に限り、単調増加関数の補間問題に役立つことを証明します。これは、反因果方向に対してのみ予想されます。ここでは、SSLとその監視ベースライン類似体のパフォーマンスは、2つの異なる損失関数、つまり1つ目は平均二乗誤差、2つ目はベイズ予測シナリオにおけるサプライズで測定されます。
Exceptional Rotations of Random Graphs: A VC Theory
ランダムグラフの例外的な回転:VC理論
In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogous questions to those of Vapnik and Chervonenkis for deviations of averages: how “rich” does the process have to be so that one sees atypical behavior. In particular, we study a natural process of ErdÅs-Rényi random graphs indexed by unit vectors in $\R^d$. We investigate the deviations of the process with respect to three fundamental properties: clique number, chromatic number, and connectivity. In all cases we establish upper and lower bounds for the minimal dimension $d$ that guarantees the existence of “exceptional directions” in which the random graph behaves atypically with respect to the property. For each of the three properties, four theorems are established, to describe upper and lower bounds for the threshold dimension in the subcritical and supercritical regimes.
この論文では、大きなランダム構造の典型的な振る舞いからの最大偏差を探ります。高次元ランダムグラフプロセスのモデルを導入し、平均の偏差についてVapnikとChervonenkisのモデルと同様の質問をします:プロセスが非定型の動作を見るためにどれだけ「豊か」でなければならないか。特に、$R^d$の単位ベクトルによってインデックス付けされたErdÅs-RÃNYI©ランダムグラフの自然なプロセスを研究します。私たちは、クリーク数、色数、および接続性という3つの基本的な特性に関して、プロセスの偏差を調査します。すべての場合において、ランダムグラフがプロパティに対して非定型的に動作する「例外的な方向」の存在を保証する最小次元$d$の上限と下限を設定します。3つの特性のそれぞれについて、亜臨界領域と超臨界領域のしきい値次元の上限と下限を記述するために、4つの定理が確立されます。
Sharp Oracle Bounds for Monotone and Convex Regression Through Aggregation
集約による単調回帰と凸回帰のシャープオラクル境界
We derive oracle inequalities for the problems of isotonic and convex regression using the combination of $Q$-aggregation procedure and sparsity pattern aggregation. This improves upon the previous results including the oracle inequalities for the constrained least squares estimator. One of the improvements is that our oracle inequalities are sharp, i.e., with leading constant 1. It allows us to obtain bounds for the minimax regret thus accounting for model misspecification, which was not possible based on the previous results. Another improvement is that we obtain oracle inequalities both with high probability and in expectation.
私たちは、等張回帰と凸回帰の問題に対して、$Q$-aggregationプロシージャとスパース パターン アグリゲーションの組み合わせを使用して、オラクル不等式を導出します。これにより、制約付き最小二乗推定量のオラクル不等式を含む以前の結果が改善されます。改善点の1つは、オラクルの不等式が鋭い、つまり先行定数1を持つことです。これにより、ミニマックスの後悔の範囲を取得することができ、以前の結果に基づいて不可能だったモデルの誤指定を説明することができます。もう1つの改善点は、オラクルの不等式を高い確率と期待値の両方で取得できることです。
On the Asymptotic Normality of an Estimate of a Regression Functional
回帰汎関数の推定値の漸近正規性について
An estimate of the second moment of the regression function is introduced. Its asymptotic normality is proved such that the asymptotic variance depends neither on the dimension of the observation vector, nor on the smoothness properties of the regression function. The asymptotic variance is given explicitly.
回帰関数の2番目のモーメントの推定が導入されます。その漸近正規性は、漸近分散が観測ベクトルの次元にも回帰関数の平滑性特性にも依存しないことが証明されています。漸近分散は明示的に与えられます。
Fast Rates in Statistical and Online Learning
統計学習とオンライン学習の高速レート
The speed with which a learning algorithm converges as it is presented with more data is a central problem in machine learning — a fast rate of convergence means less data is needed for the same level of performance. The pursuit of fast rates in online and statistical learning has led to the discovery of many conditions in learning theory under which fast learning is possible. We show that most of these conditions are special cases of a single, unifying condition, that comes in two forms: the central condition for `proper’ learning algorithms that always output a hypothesis in the given model, and stochastic mixability for online algorithms that may make predictions outside of the model. We show that under surprisingly weak assumptions both conditions are, in a certain sense, equivalent. The central condition has a re-interpretation in terms of convexity of a set of pseudoprobabilities, linking it to density estimation under misspecification. For bounded losses, we show how the central condition enables a direct proof of fast rates and we prove its equivalence to the Bernstein condition, itself a generalization of the Tsybakov margin condition, both of which have played a central role in obtaining fast rates in statistical learning. Yet, while the Bernstein condition is two-sided, the central condition is one-sided, making it more suitable to deal with unbounded losses. In its stochastic mixability form, our condition generalizes both a stochastic exp-concavity condition identified by Juditsky, Rigollet and Tsybakov and Vovk’s notion of mixability. Our unifying conditions thus provide a substantial step towards a characterization of fast rates in statistical learning, similar to how classical mixability characterizes constant regret in the sequential prediction with expert advice setting.
学習アルゴリズムに多くのデータが与えられたときに収束する速度は、機械学習の中心的な問題です。収束速度が速いということは、同じレベルのパフォーマンスを得るために必要なデータが少なくなることを意味します。オンライン学習と統計学習における高速化の追求により、学習理論において高速学習が可能な条件が数多く発見されました。これらの条件のほとんどが、単一の統一条件の特殊なケースであり、2つの形式があることを示します。つまり、常に特定のモデルで仮説を出力する「適切な」学習アルゴリズムの中心条件と、モデル外で予測を行う可能性のあるオンライン アルゴリズムの確率的混合可能性です。驚くほど弱い仮定の下では、両方の条件がある意味で同等であることを示します。中心条件は、疑似確率セットの凸性の観点から再解釈され、誤指定下での密度推定にリンクされます。制限された損失の場合、中心条件によって高速レートの直接的な証明が可能になることを示し、統計学習で高速レートを得る上で中心的な役割を果たしてきた、ツィバコフ マージン条件の一般化であるベルンシュタイン条件との等価性を証明します。ただし、ベルンシュタイン条件は両側であるのに対し、中心条件は片側であるため、無制限の損失を処理するのに適しています。確率的混合可能性形式では、私たちの条件は、Juditsky、Rigollet、およびツィバコフによって特定された確率的exp-凹条件と、Vovkの混合可能性の概念の両方を一般化します。したがって、私たちの統一条件は、統計学習における高速レートの特徴付けに向けて大きな一歩を踏み出します。これは、専門家のアドバイスによる逐次予測の設定で、古典的な混合可能性が一定の後悔を特徴付けるのと似ています。
Optimal Estimation of Low Rank Density Matrices
低ランク密度行列の最適推定
The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten $p$-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.
密度行列は、量子システムの状態を記述する単位トレースの正の半定値エルミート行列です。この論文の目標は、量子状態トモグラフィーで使用されるトレース回帰モデル(特にパウリ測定の場合)における低ランク密度行列の推定誤差率の最小最大下限を開発することです。このような境界は、Kullback-Leibler発散(相対エントロピー距離)やヘリンガー距離(いわゆるBures距離)、Schatten $p$-norm距離の量子バージョンなど、統計的に関連性のあるいくつかの距離に対して確立されます。フォン・ノイマン・エントロピー・ペナルティによる最小二乗推定量の鋭い上限とオラクル不等式が得られ、これらの距離に対してミニマックス下限が(対数係数まで)達成されることを示しています。
Batch Learning from Logged Bandit Feedback through Counterfactual Risk Minimization
反事実的リスク最小化によるログ記録バンディットフィードバックからのバッチ学習
We develop a learning principle and an efficient algorithm for batch learning from logged bandit feedback. This learning setting is ubiquitous in online systems (e.g., ad placement, web search, recommendation), where an algorithm makes a prediction (e.g., ad ranking) for a given input (e.g., query) and observes bandit feedback (e.g., user clicks on presented ads). We first address the counterfactual nature of the learning problem (Bottou et al., 2013) through propensity scoring. Next, we prove generalization error bounds that account for the variance of the propensity-weighted empirical risk estimator. In analogy to the Structural Risk Minimization principle of Wapnik and Tscherwonenkis (1979), these constructive bounds give rise to the Counterfactual Risk Minimization (CRM) principle. We show how CRM can be used to derive a new learning method— called Policy Optimizer for Exponential Models (POEM)—for learning stochastic linear rules for structured output prediction. We present a decomposition of the POEM objective that enables efficient stochastic gradient optimization. The effectiveness and efficiency of POEM is evaluated on several simulated multi- label classification problems, as well as on a real-world information retrieval problem. The empirical results show that the CRM objective implemented in POEM provides improved robustness and generalization performance compared to the state- of-the-art.
私たちは、記録されたバンディットフィードバックからバッチ学習を行うための学習原理と効率的なアルゴリズムを開発しました。この学習設定は、オンラインシステム（広告配置、ウェブ検索、推奨など）に広く普及しており、アルゴリズムは特定の入力（クエリなど）に対して予測（広告ランキングなど）を行い、バンディットフィードバック（提示された広告をユーザーがクリックするなど）を観察します。我々はまず、傾向スコアリングを通じて学習問題（Bottouら, 2013）の反事実的性質に対処します。次に、傾向加重経験的リスク推定値の分散を考慮した一般化誤差境界を証明します。WapnikとTscherwonenkis（1979）の構造的リスク最小化原理と同様に、これらの建設的境界から反事実的リスク最小化（CRM）原理が生まれます。CRMを使用して、構造化された出力予測の確率的線形ルールを学習するための新しい学習方法(POEM (指数モデル用ポリシー オプティマイザー)と呼ばれる)を導き出す方法を示します。効率的な確率的勾配最適化を可能にするPOEM目的の分解を示します。POEMの有効性と効率性は、シミュレートされた複数のラベル分類問題と、実際の情報検索問題で評価されます。実験結果から、POEMに実装されたCRM目的により、最先端のものと比較して堅牢性と一般化パフォーマンスが向上することがわかります。
V-Matrix Method of Solving Statistical Inference Problems
統計的推論問題を解くためのV行列法
This paper presents direct settings and rigorous solutions of the main Statistical Inference problems. It shows that rigorous solutions require solving multidimensional Fredholm integral equations of the first kind in the situation where not only the right-hand side of the equation is an approximation, but the operator in the equation is also defined approximately. Using Stefanuyk-Vapnik theory for solving such ill-posed operator equations, constructive methods of empirical inference are introduced. These methods are based on a new concept called $V$-matrix. This matrix captures geometric properties of the observation data that are ignored by classical statistical methods.
この論文では、主要な統計的推論問題の直接的な設定と厳密な解決策を示します。これは、厳密な解法では、方程式の右辺が近似であるだけでなく、方程式の演算子も近似的に定義される状況で、最初の種類の多次元フレドホルム積分方程式を解く必要があることを示しています。このような不利な作用素方程式を解くためにStefanuyk-Vapnik理論を使用して、経験的推論の構成的方法を紹介します。これらの方法は、$V$-matrixと呼ばれる新しい概念に基づいています。この行列は、従来の統計手法では無視される観測データの幾何学的特性をキャプチャします。
Preface to this Special Issue
本特集号の巻頭言
Approximate Modified Policy Iteration and its Application to the Game of Tetris
近似修正ポリシーの反復とテトリスゲームへの適用
Modified policy iteration (MPI) is a dynamic programming (DP) algorithm that contains the two celebrated policy and value iteration methods. Despite its generality, MPI has not been thoroughly studied, especially its approximation form which is used when the state and/or action spaces are large or infinite. In this paper, we propose three implementations of approximate MPI (AMPI) that are extensions of the well-known approximate DP algorithms: fitted-value iteration, fitted-Q iteration, and classification-based policy iteration. We provide error propagation analysis that unify those for approximate policy and value iteration. We develop the finite-sample analysis of these algorithms, which highlights the influence of their parameters. In the classification-based version of the algorithm (CBMPI), the analysis shows that MPI’s main parameter controls the balance between the estimation error of the classifier and the overall value function approximation. We illustrate and evaluate the behavior of these new algorithms in the Mountain Car and Tetris problems. Remarkably, in Tetris, CBMPI outperforms the existing DP approaches by a large margin, and competes with the current state-of-the-art methods while using fewer samples.
修正ポリシー反復(MPI)は、2つの有名なポリシー反復法と値反復法を含む動的計画法(DP)アルゴリズムです。その汎用性にもかかわらず、MPIは、特に状態空間やアクション空間が大きいか無限である場合に使用される近似形式については、十分に研究されていません。この論文では、よく知られている近似DPアルゴリズムの拡張である近似MPI (AMPI)の3つの実装を提案します。近似ポリシー反復法と値反復法を統合したエラー伝播分析を提供します。これらのアルゴリズムの有限サンプル分析を開発し、そのパラメータの影響を強調します。分類ベースのアルゴリズム バージョン(CBMPI)では、分析により、MPIの主なパラメータが分類器の推定エラーと全体的な値関数近似の間のバランスを制御することが示されています。Mountain Car問題とTetris問題でこれらの新しいアルゴリズムの動作を説明し、評価します。驚くべきことに、テトリスでは、CBMPIは既存のDPアプローチを大幅に上回り、より少ないサンプル数で現在の最先端の方法と競合します。
Bayesian Nonparametric Crowdsourcing
ベイズノンパラメトリッククラウドソーシング
Crowdsourcing has been proven to be an effective and efficient tool to annotate large data-sets. User annotations are often noisy, so methods to combine the annotations to produce reliable estimates of the ground truth are necessary. We claim that considering the existence of clusters of users in this combination step can improve the performance. This is especially important in early stages of crowdsourcing implementations, where the number of annotations is low. At this stage there is not enough information to accurately estimate the bias introduced by each annotator separately, so we have to resort to models that consider the statistical links among them. In addition, finding these clusters is interesting in itself as knowing the behavior of the pool of annotators allows implementing efficient active learning strategies. Based on this, we propose in this paper two new fully unsupervised models based on a Chinese restaurant process (CRP) prior and a hierarchical structure that allows inferring these groups jointly with the ground truth and the properties of the users. Efficient inference algorithms based on Gibbs sampling with auxiliary variables are proposed. Finally, we perform experiments, both on synthetic and real databases, to show the advantages of our models over state-of-the-art algorithms.
クラウドソーシングは、大規模なデータセットに注釈を付ける効果的かつ効率的なツールであることが証明されています。ユーザーの注釈はノイズが多いことが多いため、注釈を組み合わせて信頼性の高い真実の推定値を生成する方法が必要です。この組み合わせステップでユーザーのクラスターの存在を考慮すると、パフォーマンスが向上すると主張します。これは、注釈の数が少ないクラウドソーシング実装の初期段階では特に重要です。この段階では、各注釈者が個別に導入したバイアスを正確に推定するための情報が不足しているため、注釈者間の統計的リンクを考慮したモデルに頼る必要があります。さらに、これらのクラスターを見つけること自体が興味深いものです。注釈者のプールの行動を知ることで、効率的なアクティブラーニング戦略を実装できるためです。これに基づいて、この論文では、中国料理レストランプロセス(CRP)の事前分布と、真実とユーザーのプロパティを使用してこれらのグループを共同で推論できる階層構造に基づく2つの新しい完全教師なしモデルを提案します。補助変数を使用したギブスサンプリングに基づく効率的な推論アルゴリズムを提案します。最後に、合成データベースと実際のデータベースの両方で実験を行い、最先端のアルゴリズムに対する当社のモデルの利点を示します。
Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
ニューラルセマンティック基底発見への応用による較正多変量回帰
We propose a calibrated multivariate regression method named CMR for fitting high dimensional multivariate regression models. Compared with existing methods, CMR calibrates regularization for each regression task with respect to its noise level so that it simultaneously attains improved finite-sample performance and tuning insensitiveness. Theoretically, we provide sufficient conditions under which CMR achieves the optimal rate of convergence in parameter estimation. Computationally, we propose an efficient smoothed proximal gradient algorithm with a worst- case numerical rate of convergence $\cO(1/\epsilon)$, where $\epsilon$ is a pre-specified accuracy of the objective function value. We conduct thorough numerical simulations to illustrate that CMR consistently outperforms other high dimensional multivariate regression methods. We also apply CMR to solve a brain activity prediction problem and find that it is as competitive as a handcrafted model created by human experts. The R package camel implementing the proposed method is available on the Comprehensive R Archive Network cran.r-project.org/web/ packages/camel.
私たちは、高次元多変量回帰モデルをフィッティングするための、較正された多変量回帰法CMRを提案します。既存の方法と比較して、CMRは各回帰タスクの正則化をノイズ レベルに関して較正するため、有限サンプルのパフォーマンスとチューニングの鈍感さを同時に向上させることができます。理論的には、CMRがパラメータ推定において最適な収束率を達成するための十分な条件を提供します。計算的には、最悪の数値収束率$\cO(1/\epsilon)$を持つ効率的な平滑化近似勾配アルゴリズムを提案します。ここで、$\epsilon$は目的関数値の事前指定された精度です。徹底的な数値シミュレーションを実施して、CMRが他の高次元多変量回帰法よりも一貫して優れていることを示す。また、CMRを脳活動予測問題の解決に適用し、人間の専門家が作成した手作りモデルと同等の競争力があることを発見した。提案された方法を実装するRパッケージcamelは、Comprehensive R Archive Network cran.r-project.org/web/packages/camelで入手できます。
RLPy: A Value-Function-Based Reinforcement Learning Framework for Education and Research
RLPy:教育と研究のための価値関数ベースの強化学習フレームワーク
RLPy is an object-oriented reinforcement learning software package with a focus on value-function-based methods using linear function approximation and discrete actions. The framework was designed for both educational and research purposes. It provides a rich library of fine-grained, easily exchangeable components for learning agents (e.g., policies or representations of value functions), facilitating recently increased specialization in reinforcement learning. RLPy is written in Python to allow fast prototyping, but is also suitable for large-scale experiments through its built-in support for optimized numerical libraries and parallelization. Code profiling, domain visualizations, and data analysis are integrated in a self-contained package available under the Modified BSD License at github.com/rlpy/rlpy. All of these properties allow users to compare various reinforcement learning algorithms with little effort.
RLPyは、線形関数近似と離散アクションを使用した価値関数ベースの手法に焦点を当てたオブジェクト指向の強化学習ソフトウェアパッケージです。このフレームワークは、教育目的と研究目的の両方で設計されました。学習エージェント用のきめ細かく、簡単に交換できるコンポーネントの豊富なライブラリ(たとえば、値関数の方策や表現)を提供し、最近増加している強化学習の専門化を促進します。RLPyはPythonで書かれているため、迅速なプロトタイピングが可能ですが、最適化された数値ライブラリと並列化のサポートが組み込まれているため、大規模な実験にも適しています。コードプロファイリング、ドメインの可視化、およびデータ分析は、github.com/rlpy/rlpyのModified BSDライセンスの下で利用可能な自己完結型パッケージに統合されています。これらの特性により、ユーザーはさまざまな強化学習アルゴリズムを少しの労力で比較できます。
Flexible High-Dimensional Classification Machines and Their Asymptotic Properties
柔軟な高次元分級機とその漸近特性
Classification is an important topic in statistics and machine learning with great potential in many real applications. In this paper, we investigate two popular large-margin classification methods, Support Vector Machine (SVM) and Distance Weighted Discrimination (DWD), under two contexts: the high-dimensional, low-sample size data and the imbalanced data. A unified family of classification machines, the FLexible Assortment MachinE (FLAME) is proposed, within which DWD and SVM are special cases. The FLAME family helps to identify the similarities and differences between SVM and DWD. It is well known that many classifiers overfit the data in the high-dimensional setting; and others are sensitive to the imbalanced data, that is, the class with a larger sample size overly influences the classifier and pushes the decision boundary towards the minority class. SVM is resistant to the imbalanced data issue, but it overfits high- dimensional data sets by showing the undesired data-piling phenomenon. The DWD method was proposed to improve SVM in the high-dimensional setting, but its decision boundary is sensitive to the imbalanced ratio of sample sizes. Our FLAME family helps to understand an intrinsic connection between SVM and DWD, and provides a trade-off between sensitivity to the imbalanced data and overfitting the high-dimensional data. Several asymptotic properties of the FLAME classifiers are studied. Simulations and real data applications are investigated to illustrate theoretical findings.
分類は、統計と機械学習における重要なトピックであり、多くの実際のアプリケーションで大きな可能性を秘めています。この論文では、高次元でサンプルサイズの小さいデータと不均衡なデータという2つのコンテキストで、2つの一般的な大マージン分類方法であるサポートベクターマシン(SVM)と距離加重判別(DWD)を調査します。分類マシンの統合ファミリであるFLexible Assortment MachinE (FLAME)が提案されており、その中ではDWDとSVMが特殊なケースです。FLAMEファミリは、SVMとDWDの類似点と相違点を識別するのに役立ちます。多くの分類器が高次元設定でデータに過剰適合することはよく知られています。また、不均衡なデータに敏感な分類器もあります。つまり、サンプルサイズの大きいクラスは分類器に過度に影響を及ぼし、決定境界を少数クラスに押しやります。SVMは不均衡なデータの問題には耐性がありますが、望ましくないデータパイリング現象を示すことで、高次元データセットに過剰適合します。DWD法は高次元設定でSVMを改善するために提案されましたが、その決定境界はサンプル サイズの不均衡な比率に敏感です。当社のFLAMEファミリーは、SVMとDWDの本質的なつながりを理解するのに役立ち、不均衡なデータに対する感度と高次元データのオーバーフィッティングとの間のトレードオフを提供します。FLAME分類器のいくつかの漸近特性が研究されています。シミュレーションと実際のデータ アプリケーションが調査され、理論的発見が説明されています。
A Finite Sample Analysis of the Naive Bayes Classifier
単純ベイズ分類器の有限サンプル解析
We revisit, from a statistical learning perspective, the classical decision-theoretic problem of weighted expert voting. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Naive Bayes weighted majority and related rules. In the case of known expert competence levels, we give sharp error estimates for the optimal rule. We derive optimality results for our estimates and also establish some structural characterizations. When the competence levels are unknown, they must be empirically estimated. We provide frequentist and Bayesian analyses for this situation. Some of our proof techniques are non-standard and may be of independent interest. Several challenging open problems are posed, and experimental results are provided to illustrate the theory.
私たちは、統計学習の観点から、加重専門家投票の古典的な決定理論問題を再検討します。特に、最適な単純ベイズ加重多数決ルールと関連ルールの一貫性(漸近的および有限的)を調べます。既知の専門家の能力レベルの場合、最適なルールに対して鋭い誤差推定値を与えます。推定値の最適性結果を導き出し、いくつかの構造特性も確立します。コンピテンシーレベルが不明な場合は、経験的に推定する必要があります。この状況に対して、頻度論的分析とベイズ分析を提供します。私たちの証明技術の一部は非標準であり、独立した関心事となる可能性があります。いくつかの挑戦的な未解決の問題が提起され、理論を説明するために実験結果が提供されます。
Second-Order Non-Stationary Online Learning for Regression
回帰のための二次非定常オンライン学習
The goal of a learner in standard online learning, is to have the cumulative loss not much larger compared with the best- performing function from some fixed class. Numerous algorithms were shown to have this gap arbitrarily close to zero, compared with the best function that is chosen off-line. Nevertheless, many real-world applications, such as adaptive filtering, are non-stationary in nature, and the best prediction function may drift over time. We introduce two novel algorithms for online regression, designed to work well in non-stationary environment. Our first algorithm performs adaptive resets to forget the history, while the second is last-step min-max optimal in context of a drift. We analyze both algorithms in the worst-case regret framework and show that they maintain an average loss close to that of the best slowly changing sequence of linear functions, as long as the cumulative drift is sublinear. In addition, in the stationary case, when no drift occurs, our algorithms suffer logarithmic regret, as for previous algorithms. Our bounds improve over existing ones, and simulations demonstrate the usefulness of these algorithms compared with other state-of-the-art approaches.
標準的なオンライン学習における学習者の目標は、ある固定クラスから最もパフォーマンスの高い関数と比較して、累積損失がそれほど大きくならないようにすることです。オフラインで選択された最良の関数と比較して、このギャップがゼロに任意に近いことが多数のアルゴリズムで示されています。しかし、適応フィルタリングなどの多くの実際のアプリケーションは本質的に非定常であり、最良の予測関数は時間の経過とともにドリフトする可能性があります。ここでは、非定常環境で適切に機能するように設計された、オンライン回帰の新しいアルゴリズムを2つ紹介します。最初のアルゴリズムは、履歴を忘れるために適応リセットを実行し、2つ目のアルゴリズムはドリフトのコンテキストで最後のステップの最小最大最適化を実行します。両方のアルゴリズムを最悪のケースの後悔フレームワークで分析し、累積ドリフトが線形以下である限り、両方のアルゴリズムが平均損失を、最も緩やかに変化する線形関数のシーケンスの平均損失に近い値に維持することを示します。さらに、ドリフトが発生しない定常ケースでは、以前のアルゴリズムと同様に、私たちのアルゴリズムは対数的な後悔に悩まされます。私たちの境界は既存のものよりも改善されており、シミュレーションでは他の最先端のアプローチと比較してこれらのアルゴリズムの有用性が実証されています。
A Comprehensive Survey on Safe Reinforcement Learning
安全な強化学習に関する総合的調査
Safe Reinforcement Learning can be defined as the process of learning policies that maximize the expectation of the return in problems in which it is important to ensure reasonable system performance and/or respect safety constraints during the learning and/or deployment processes. We categorize and analyze two approaches of Safe Reinforcement Learning. The first is based on the modification of the optimality criterion, the classic discounted finite/infinite horizon, with a safety factor. The second is based on the modification of the exploration process through the incorporation of external knowledge or the guidance of a risk metric. We use the proposed classification to survey the existing literature, as well as suggesting future directions for Safe Reinforcement Learning.
安全な強化学習とは、学習および/または展開プロセス中に合理的なシステムパフォーマンスを確保したり、安全上の制約を尊重したりすることが重要な問題において、リターンの期待を最大化する学習ポリシーの学習プロセスとして定義できます。この研究では、Safe Reinforcement Learningの2つのアプローチを分類し、分析します。1つ目は、最適性基準、つまり古典的な割引有限/無限地平線の変更に基づいており、安全率があります。2つ目は、外部知識の組み込みまたはリスク指標のガイダンスによる探索プロセスの変更に基づいています。提案された分類を使用して、既存の文献を調査するとともに、安全な強化学習の将来の方向性を提案します。
The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
低ランク行列補完のための代数的組み合わせ的アプローチ
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More specifically, apart from introducing an algebraic combinatorial theory of low-rank matrix completion, we present probability-one algorithms to decide whether a particular entry of the matrix can be completed. We also describe methods to complete that entry from a few others, and to estimate the error which is incurred by any method completing that entry. Furthermore, we show how known results on matrix completion and their sampling assumptions can be related to our new perspective and interpreted in terms of a completability phase transition.
私たちは、代数幾何学とマトロイド理論のツールを用いて、いくつかのエントリ間の関係を研究することに基づく、低ランク行列補完に関する新しい代数的組み合わせ論的見解を提示します。このアプローチの本質的な局所性により、閉じた理論的および実践的なフレームワークで単一のエントリを扱うことができます。より具体的には、低ランク行列補完の代数的組み合わせ理論を導入するだけでなく、行列の特定のエントリが完了できるかどうかを決定するための確率1アルゴリズムを提示します。また、他のいくつかのエントリからそのエントリを完了する方法と、そのエントリを完了するメソッドによって発生するエラーを見積もる方法についても説明します。さらに、行列の完成に関する既知の結果とそのサンプリングの仮定が、新しい視点にどのように関連し、補完性相転移の観点から解釈できるかを示します。
Rationality, Optimism and Guarantees in General Reinforcement Learning
一般強化学習における合理性・楽観主義・保証
In this article, we present a top-down theoretical study of general reinforcement learning agents. We begin with rational agents with unlimited resources and then move to a setting where an agent can only maintain a limited number of hypotheses and optimizes plans over a horizon much shorter than what the agent designer actually wants. We axiomatize what is rational in such a setting in a manner that enables optimism, which is important to achieve systematic explorative behavior. Then, within the class of agents deemed rational, we achieve convergence and finite-error bounds. Such results are desirable since they imply that the agent learns well from its experiences, but the bounds do not directly guarantee good performance and can be achieved by agents doing things one should obviously not. Good performance cannot in fact be guaranteed for any agent in fully general settings. Our approach is to design agents that learn well from experience and act rationally. We introduce a framework for general reinforcement learning agents based on rationality axioms for a decision function and an hypothesis- generating function designed so as to achieve guarantees on the number errors. We will consistently use an optimistic decision function but the hypothesis-generating function needs to change depending on what is known/assumed. We investigate a number of natural situations having either a frequentist or Bayesian flavor, deterministic or stochastic environments and either finite or countable hypothesis class. Further, to achieve sufficiently good bounds as to hold promise for practical success we introduce a notion of a class of environments being generated by a set of laws. None of the above has previously been done for fully general reinforcement learning environments.
この記事では、一般的な強化学習エージェントのトップダウン理論研究を紹介します。無制限のリソースを持つ合理的なエージェントから始め、エージェントが限られた数の仮説しか維持できず、エージェント設計者が実際に望むよりもはるかに短い期間で計画を最適化する設定に移ります。体系的な探索行動を実現するために重要な楽観主義を可能にする方法で、このような設定で何が合理的であるかを公理化します。次に、合理的と見なされるエージェントのクラス内で、収束と有限エラー境界を実現します。このような結果は、エージェントが経験から十分に学習することを意味しているため望ましいものですが、境界は優れたパフォーマンスを直接保証するものではなく、エージェントが明らかにすべきでないことをすることで達成できます。実際には、完全に一般的な設定では、どのエージェントでも優れたパフォーマンスを保証することはできません。私たちのアプローチは、経験から十分に学習し、合理的に行動するエージェントを設計することです。エラー数の保証を実現するように設計された決定関数と仮説生成関数の合理性公理に基づく、一般的な強化学習エージェントのフレームワークを紹介します。我々は一貫して楽観的な決定関数を使用しますが、仮説生成関数は既知/想定されるものに応じて変更する必要があります。私たちは、頻度主義またはベイジアン風味、決定論的または確率的環境、有限または可算仮説クラスのいずれかを持ついくつかの自然な状況を調査します。さらに、実用的な成功を約束する十分に良好な境界を達成するために、一連の法則によって生成される環境のクラスの概念を導入します。上記のいずれも、完全に一般的な強化学習環境に対してこれまで行われたことはありません。
Learning Equilibria of Games via Payoff Queries
ペイオフクエリによるゲームの均衡の学習
A recent body of experimental literature has studied {\em empirical game-theoretical analysis}, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for exact equilibria of bimatrix and graphical games. We then study the query complexity of approximate equilibria in bimatrix games. Finally, we study the query complexity of exact equilibria in symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.
最近の一連の実験的文献では、経験的ゲーム理論的分析を研究しており、純粋戦略プロファイルのサブセットの観察とそれに関連するプレーヤーへの報酬から成るゲームの部分的な知識があります。目的は、これらの観察に基づいて、ゲームの正確なまたは近似的なナッシュ均衡を見つけることです。通常、戦略プロファイルはアルゴリズムによってオンラインで選択されると想定されています。私たちは、対応する計算学習モデルと、さまざまなクラスのゲームについて均衡を学習するためのクエリの複雑さを研究します。バイマトリックス ゲームとグラフィカル ゲームの正確な均衡に関する基本的な結果を示します。次に、バイマトリックス ゲームにおける近似均衡のクエリの複雑さを研究します。最後に、対称ネットワーク輻輳ゲームにおける正確な均衡のクエリの複雑さを研究します。有向非巡回ネットワークの場合、純粋戦略プロファイルのごく一部をクエリするだけでコスト関数を学習できます(したがって均衡を計算できます)。並列リンクの特殊なケースでは、コスト値のごく一部だけを学習しながら均衡を特定できるというより強力な結果が得られます。
Learning Sparse Low-Threshold Linear Classifiers
スパース低しきい値線形分類器の学習
We consider the problem of learning a non-negative linear classifier with a $\ell_1$-norm of at most $k$, and a fixed threshold, under the hinge-loss. This problem generalizes the problem of learning a $k$-monotone disjunction. We prove that we can learn efficiently in this setting, at a rate which is linear in both $k$ and the size of the threshold, and that this is the best possible rate. We provide an efficient online learning algorithm that achieves the optimal rate, and show that in the batch case, empirical risk minimization achieves this rate as well. The rates we show are tighter than the uniform convergence rate, which grows with $k^2$.
私たちは、ヒンジ損失の下で、$ell_1$-normが最大$k$で、しきい値が固定されている非負の線形分類器を学習する問題を考えます。この問題は、$k$-単調な選言を学習する問題を一般化します。この設定では、$k$と閾値のサイズの両方で線形のレートで効率的に学習できること、そしてこれが可能な限り最高のレートであることを証明します。最適なレートを達成する効率的なオンライン学習アルゴリズムを提供し、バッチケースでは、経験的リスクの最小化もこのレートを達成することを示しています。私たちが示すレートは、$k^2$で増加する一様収束率よりもタイトです。
Perturbed Message Passing for Constraint Satisfaction Problems
制約充足問題に対する摂動メッセージの受け渡し
We introduce an efficient message passing scheme for solving Constraint Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief Propagation (BP) and Survey Propagation (SP) messages to bypass decimation and directly produce a single satisfying assignment. Our first CSP solver, called Perturbed Belief Propagation, smoothly interpolates two well-known inference procedures; it starts as BP and ends as a Gibbs sampler, which produces a single sample from the set of solutions. Moreover we apply a similar perturbation scheme to SP to produce another CSP solver, Perturbed Survey Propagation. Experimental results on random and real-world CSPs show that Perturbed BP is often more successful and at the same time tens to hundreds of times more efficient than standard BP guided decimation. Perturbed BP also compares favorably with state-of-the-art SP-guided decimation, which has a computational complexity that generally scales exponentially worse than our method (w.r.t. the cardinality of variable domains and constraints). Furthermore, our experiments with random satisfiability and coloring problems demonstrate that Perturbed SP can outperform SP-guided decimation, making it the best incomplete random CSP-solver in difficult regimes.
私たちは、制約充足問題(CSP)を解決するための効率的なメッセージ パッシング スキームを紹介します。これは、ビリーフ プロパゲーション(BP)とサーベイ プロパゲーション(SP)メッセージの確率的摂動を使用してデシメーションを回避し、単一の満足な割り当てを直接生成します。最初のCSPソルバーは、摂動ビリーフ プロパゲーションと呼ばれ、2つのよく知られた推論手順をスムーズに補間します。BPとして開始し、ソリューション セットから単一のサンプルを生成するギブス サンプラーとして終了します。さらに、同様の摂動スキームをSPに適用して、別のCSPソルバーである摂動サーベイ プロパゲーションを生成します。ランダムCSPと実世界のCSPに関する実験結果から、摂動BPは多くの場合、標準のBP誘導デシメーションよりも成功率が高く、同時に数十から数百倍効率的であることがわかります。摂動BPは、最先端のSPガイド デシメーションと比較しても遜色ありません。最先端のSPガイド デシメーションの計算複雑性は、一般的に(変数ドメインと制約のカーディナリティに関して)私たちの方法よりも指数関数的に悪化します。さらに、ランダムな充足可能性とカラーリングの問題に関する私たちの実験では、摂動SPがSPガイド デシメーションよりも優れていることが実証されており、困難な状況では不完全ランダムCSPソルバーとして最適です。
Encog: Library of Interchangeable Machine Learning Models for Java and C#
Encog: Java と C# の交換可能な機械学習モデルのライブラリ
This paper introduces the Encog library for Java and C#, a scalable, adaptable, multi-platform machine learning framework that was first released in 2008. Encog allows a variety of machine learning models to be applied to data sets using regression, classification, and clustering. Various supported machine learning models can be used interchangeably with minimal recoding. Encog uses efficient multithreaded code to reduce training time by exploiting modern multicore processors. The current version of Encog can be downloaded from www.encog.org.
この論文では、2008年に初めてリリースされた、スケーラブルで適応性の高いマルチプラットフォームの機械学習フレームワークであるJavaおよびC#用のEncogライブラリを紹介します。Encogを使用すると、回帰、分類、クラスタリングを使用して、さまざまな機械学習モデルをデータセットに適用できます。サポートされているさまざまな機械学習モデルを、最小限の再コーディングで交換可能に使用できます。Encogは、効率的なマルチスレッド コードを使用して、最新のマルチコア プロセッサを活用することでトレーニング時間を短縮します。Encogの現在のバージョンは、www.encog.orgからダウンロードできます。
Local Identification of Overcomplete Dictionaries
過完全辞書のローカル同定
This paper presents the first theoretical results showing that stable identification of overcomplete $\mu$-coherent dictionaries $\Phi \in \mathbb{R}^{d\times K}$ is locally possible from training signals with sparsity levels $S$ up to the order $O(\mu^{-2})$ and signal to noise ratios up to $O(\sqrt{d})$. In particular the dictionary is recoverable as the local maximum of a new maximization criterion that generalizes the K-means criterion. For this maximization criterion results for asymptotic exact recovery for sparsity levels up to $O(\mu^{-1})$ and stable recovery for sparsity levels up to $O(\mu^{-2})$ as well as signal to noise ratios up to $O(\sqrt{d})$ are provided. These asymptotic results translate to finite sample size recovery results with high probability as long as the sample size $N$ scales as $O(K^3dS \tilde \epsilon^{-2})$, where the recovery precision $\tilde{\epsilon}$ can go down to the asymptotically achievable precision. Further, to actually find the local maxima of the new criterion, a very simple Iterative Thresholding and K (signed) Means algorithm (ITKM), which has complexity $O(dKN)$ in each iteration, is presented and its local efficiency is demonstrated in several experiments.
この論文では、スパースレベルが最大でオーダー$O(\mu^{-2})$、信号対雑音比が最大で$O(\sqrt{d})$のトレーニング信号から、過剰完備$\mu$コヒーレント辞書$\Phi \in \mathbb{R}^{d\times K}$の安定識別が局所的に可能であることを示す最初の理論的結果を提示します。特に、辞書は、K平均基準を一般化する新しい最大化基準の局所的最大値として回復可能です。この最大化基準では、スパースレベルが最大$O(\mu^{-1})$の漸近的正確回復、スパースレベルが最大$O(\mu^{-2})$、信号対雑音比が最大$O(\sqrt{d})$の安定した回復の結果が提供されます。これらの漸近結果は、サンプルサイズ$N$が$O(K^3dS \tilde \epsilon^{-2})$に比例する限り、高い確率で有限サンプルサイズの回復結果につながります。回復精度$\tilde{\epsilon}$は、漸近的に達成可能な精度まで下がる可能性があります。さらに、新しい基準の局所的最大値を実際に見つけるために、各反復の複雑度が$O(dKN)$である非常に単純な反復しきい値設定およびK (符号付き)平均アルゴリズム(ITKM)が提示され、その局所的効率がいくつかの実験で実証されています。
Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
行動データからの大規模人口グラフィカルゲームの構造とパラメータの学習
We consider learning, from strictly behavioral data, the structure and parameters of linear influence games (LIGs), a class of parametric graphical games introduced by Irfan and Ortiz (2014). LIGs facilitate causal strategic inference (CSI): Making inferences from causal interventions on stable behavior in strategic settings. Applications include the identification of the most influential individuals in large (social) networks. Such tasks can also support policy-making analysis. Motivated by the computational work on LIGs, we cast the learning problem as maximum-likelihood estimation (MLE) of a generative model defined by pure-strategy Nash equilibria (PSNE). Our simple formulation uncovers the fundamental interplay between goodness-of-fit and model complexity: good models capture equilibrium behavior within the data while controlling the true number of equilibria, including those unobserved. We provide a generalization bound establishing the sample complexity for MLE in our framework. We propose several algorithms including convex loss minimization (CLM) and sigmoidal approximations. We prove that the number of exact PSNE in LIGs is small, with high probability; thus, CLM is sound. We illustrate our approach on synthetic data and real-world U.S. congressional voting records. We briefly discuss our learning framework’s generality and potential applicability to general graphical games.
私たちは、厳密に行動データから、IrfanとOrtiz (2014)によって導入されたパラメトリック グラフィカル ゲームの一種である線形影響ゲーム(LIG)の構造とパラメーターを学習することを検討します。LIGは因果戦略的推論(CSI)、つまり戦略的設定における安定した行動に対する因果的介入からの推論を促進します。アプリケーションには、大規模な(ソーシャル)ネットワークで最も影響力のある個人の特定が含まれます。このようなタスクは、政策立案分析をサポートすることもできます。LIGに関する計算作業に動機付けられて、我々は学習問題を、純粋戦略ナッシュ均衡(PSNE)によって定義される生成モデルの最大尤度推定(MLE)として定式化しました。我々のシンプルな定式化により、適合度とモデルの複雑さの間の基本的な相互作用が明らかになりました。つまり、優れたモデルは、データ内の均衡行動を捉えながら、観測されていない均衡も含めた真の均衡の数を制御します。私たちは、フレームワークにおけるMLEのサンプル複雑さを確立する一般化境界を提供します。凸損失最小化(CLM)やシグモイド近似など、いくつかのアルゴリズムを提案します。LIG内の正確なPSNEの数は少ないが、高い確率で存在することを証明します。したがって、CLMは妥当です。合成データと実際の米国議会の投票記録を使用して、このアプローチを説明します。学習フレームワークの一般性と、一般的なグラフィカル ゲームへの潜在的な適用性について簡単に説明します。
Fast Cross-Validation via Sequential Testing
シーケンシャルテストによる迅速なクロスバリデーション
With the increasing size of today’s data sets, finding the right parameter configuration in model selection via cross-validation can be an extremely time-consuming task. In this paper we propose an improved cross-validation procedure which uses nonparametric testing coupled with sequential analysis to determine the best parameter set on linearly increasing subsets of the data. By eliminating underperforming candidates quickly and keeping promising candidates as long as possible, the method speeds up the computation while preserving the power of the full cross-validation. Theoretical considerations underline the statistical power of our procedure. The experimental evaluation shows that our method reduces the computation time by a factor of up to 120 compared to a full cross-validation with a negligible impact on the accuracy.
今日のデータセットのサイズが大きくなるにつれ、クロスバリデーションによるモデル選択で適切なパラメーター構成を見つけることは、非常に時間のかかる作業になる可能性があります。この論文では、ノンパラメトリックテストとシーケンシャル分析を組み合わせて、データの線形に増加するサブセットに最適なパラメータセットを決定する、改善されたクロスバリデーション手順を提案します。パフォーマンスの低い候補を迅速に排除し、有望な候補をできるだけ長く保持することで、この手法は完全なクロスバリデーションの能力を維持しながら計算を高速化します。理論的な考察は、私たちの手順の統計的力を強調しています。実験的評価では、私たちの方法は、完全な交差検証と比較して計算時間を最大120倍短縮し、精度への影響は無視できることを示しています。
Lasso Screening Rules via Dual Polytope Projection
デュアルポリトープ投影によるラッソスクリーニングルール
Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large- scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have $0$ components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no exact screening rule for group Lasso. We have evaluated our screening rule using synthetic and real data sets. Results show that our rule is more effective in identifying inactive predictors than existing state-of-the-art screening rules for Lasso.
Lassoは、スパース表現を見つけるために広く使用されている回帰手法です。特徴空間の次元とサンプル数が非常に大きい場合、Lasso問題を解決することは依然として困難です。大規模なLasso問題を効率的に解決するために、El Ghaouiと彼の同僚は、非アクティブな予測子、つまりソリューション ベクトルに$0$コンポーネントを持つ予測子をすばやく識別できるSAFEルールを提案しました。次に、非アクティブな予測子または特徴を最適化問題から削除して、その規模を縮小できます。標準Lassoをデュアル形式に変換することにより、非アクティブな予測子には、最適なデュアル ソリューションに対する非アクティブな制約のセットが含まれていることが示されます。この論文では、デュアル ポリトープ射影(DPP)による効率的で効果的なスクリーニング ルールを提案します。これは主に、デュアル空間で実行可能なセットが凸型で閉じたポリトープであるという事実による、最適なデュアル ソリューションの一意性と非拡張性に基づいています。さらに、私たちのスクリーニング ルールは、グループLasso内の非アクティブなグループを識別するために拡張できることを示しています。私たちが知る限り、現在、グループLassoの正確なスクリーニング ルールはありません。私たちは、合成データ セットと実際のデータ セットを使用して、私たちのスクリーニング ルールを評価しました。結果は、私たちのルールが、Lassoの既存の最先端のスクリーニング ルールよりも非アクティブな予測子を識別するのに効果的であることを示しています。
Joint Estimation of Multiple Precision Matrices with Common Structures
共通の構造を持つ複数の精度行列の同時推定
Estimation of inverse covariance matrices, known as precision matrices, is important in various areas of statistical analysis. In this article, we consider estimation of multiple precision matrices sharing some common structures. In this setting, estimating each precision matrix separately can be suboptimal as it ignores potential common structures. This article proposes a new approach to parameterize each precision matrix as a sum of common and unique components and estimate multiple precision matrices in a constrained $l_1$ minimization framework. We establish both estimation and selection consistency of the proposed estimator in the high dimensional setting. The proposed estimator achieves a faster convergence rate for the common structure in certain cases. Our numerical examples demonstrate that our new estimator can perform better than several existing methods in terms of the entropy loss and Frobenius loss. An application to a glioblastoma cancer data set reveals some interesting gene networks across multiple cancer subtypes.
逆共分散行列（精度行列とも呼ばれる）の推定は、統計分析のさまざまな分野で重要です。この記事では、共通構造を共有する複数の精度行列の推定について検討します。この設定では、各精度行列を個別に推定すると、潜在的な共通構造が無視されるため、最適ではない可能性があります。この記事では、各精度行列を共通コンポーネントと一意コンポーネントの合計としてパラメーター化し、制約付き$l_1$最小化フレームワークで複数の精度行列を推定する新しいアプローチを提案します。高次元設定で、提案された推定量の推定と選択の一貫性を確立します。提案された推定量は、特定のケースで共通構造の収束速度が速くなります。数値例では、エントロピー損失とフロベニウス損失に関して、新しい推定量がいくつかの既存の方法よりも優れていることを示しています。神経膠芽腫癌データセットへの適用により、複数の癌サブタイプにわたるいくつかの興味深い遺伝子ネットワークが明らかになりました。
Learning with the Maximum Correntropy Criterion Induced Losses for Regression
回帰の最大コレントロピー基準による学習では損失がもたらされます
Within the statistical learning framework, this paper studies the regression model associated with the correntropy induced losses. The correntropy, as a similarity measure, has been frequently employed in signal processing and pattern recognition. Motivated by its empirical successes, this paper aims at presenting some theoretical understanding towards the maximum correntropy criterion in regression problems. Our focus in this paper is two-fold: first, we are concerned with the connections between the regression model associated with the correntropy induced loss and the least squares regression model. Second, we study its convergence property. A learning theory analysis which is centered around the above two aspects is conducted. From our analysis, we see that the scale parameter in the loss function balances the convergence rates of the regression model and its robustness. We then make some efforts to sketch a general view on robust loss functions when being applied into the learning for regression problems. Numerical experiments are also implemented to verify the effectiveness of the model.
この論文では、統計学習フレームワーク内で、コレントロピー誘導損失に関連する回帰モデルについて検討します。コレントロピーは、類似性尺度として、信号処理やパターン認識で頻繁に使用されています。その実証的な成功に動機づけられ、この論文では、回帰問題における最大コレントロピー基準に対する理論的理解を提示することを目的としています。本論文の焦点は2つあります。まず、コレントロピー誘導損失に関連する回帰モデルと最小二乗回帰モデルの関係について検討します。次に、その収束特性について検討します。上記の2つの側面を中心に学習理論分析を行います。分析から、損失関数のスケール パラメーターが、回帰モデルの収束率と堅牢性のバランスをとることがわかります。次に、回帰問題の学習に適用する場合の堅牢な損失関数に関する一般的な見解を概説します。モデルの有効性を検証するために、数値実験も実施します。
Combined l1 and Greedy l0 Penalized Least Squares for Linear Model Selection
線形モデル選択のためのl1とGreedy l0の組み合わせ最小二乗法のペナルティ
We introduce a computationally effective algorithm for a linear model selection consisting of three steps: screening–ordering– selection (SOS). Screening of predictors is based on the thresholded Lasso that is $\ell_1$ penalized least squares. The screened predictors are then fitted using least squares (LS) and ordered with respect to their $|t|$ statistics. Finally, a model is selected using greedy generalized information criterion (GIC) that is $\ell_0$ penalized LS in a nested family induced by the ordering. We give non-asymptotic upper bounds on error probability of each step of the SOS algorithm in terms of both penalties. Then we obtain selection consistency for different ($n$, $p$) scenarios under conditions which are needed for screening consistency of the Lasso. Our error bounds and numerical experiments show that SOS is worth considering alternative for multi-stage convex relaxation, the latest quasiconvex penalized LS. For the traditional setting ($n >p$) we give Sanov-type bounds on the error probabilities of the ordering–selection algorithm. It is surprising consequence of our bounds that the selection error of greedy GIC is asymptotically not larger than of exhaustive GIC.
私たちは、スクリーニング、順序付け、選択(SOS)の3つのステップから成る、計算効率の高い線形モデル選択アルゴリズムを紹介します。予測子のスクリーニングは、しきい値付きLasso ($\ell_1$ペナルティ付き最小二乗法)に基づきます。次に、スクリーニングされた予測子は最小二乗法(LS)を使用してフィッティングされ、その$|t|$統計量に関して順序付けされます。最後に、順序付けによって誘導されるネストされたファミリー内の$\ell_0$ペナルティ付きLSである貪欲一般化情報基準(GIC)を使用してモデルが選択されます。両方のペナルティに関して、SOSアルゴリズムの各ステップのエラー確率の非漸近的上限を示します。次に、Lassoのスクリーニングの一貫性に必要な条件下で、さまざまな($n$、$p$)シナリオの選択一貫性を取得します。我々の誤差境界と数値実験は、SOSが最新の準凸ペナルティ付きLSである多段凸緩和の代替として検討する価値があることを示しています。従来の設定($n >p$)では、順序付け-選択アルゴリズムのエラー確率にSanov型の境界を与えます。貪欲なGICの選択エラーが網羅的なGICの選択エラーよりも漸近的に大きくならないことは、この境界の驚くべき結果です。
Distributed Matrix Completion and Robust Factorization
分散行列補完とロバストな因数分解
If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the “divide” step and control their magnitude in the “conquer” step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.
学習方法を最新のデータセットの膨大なサイズに拡張するには、機械学習の分野に並列コンピューティングと分散コンピューティングを採用することが不可欠です。近年の行列因数分解法の開発に触発され、理論は豊富だが計算の複雑さが乏しいこと、および分散アーキテクチャへの行列のマッピングが比較的容易であることから、ノイズの多い行列分解のためのスケーラブルな分割統治フレームワークを導入します。このフレームワークの徹底的な理論的分析を提示し、「除算」ステップによってもたらされる統計的誤差を特徴付け、「征服」ステップでその大きさを制御することで、全体的なアルゴリズムが基本アルゴリズムと同等の高確率推定保証を享受できるようにします。また、このアプローチで達成可能なほぼ線形から超線形への高速化を実証する協調フィルタリングとビデオ背景モデリングの実験も紹介します。
A Statistical Perspective on Algorithmic Leveraging
アルゴリズム活用に関する統計的視点
One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method. In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance, both conditional and unconditional on the observed data. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling. Based on these theoretical results, we propose and analyze two new leveraging algorithms: one constructs a smaller least-squares problem with “shrinkage” leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical results indicate that our theory is a good predictor of practical performance of existing and new leverage- based algorithms and that the new algorithms achieve improved performance. For example, with the same computation reduction as in the original algorithmic leveraging approach, our proposed SLEV typically leads to improved biases and variances both unconditionally and conditionally (on the observed data), and our proposed LEVUNW typically yields improved unconditional biases and variances.
大規模なデータセットを扱う一般的な方法の1つはサンプリングです。たとえば、経験的統計レバレッジ スコアを重要度サンプリング分布として使用することにより、アルゴリズム レバレッジ法では、データ マトリックスの行/列をサンプリングして再スケールし、サブ問題の計算を実行する前にデータ サイズを削減します。この方法は、最小二乗近似、最小絶対偏差近似、低ランク マトリックス近似などのマトリックス問題に対するアルゴリズムの計算効率の向上に成功しています。既存の作業は、最悪の実行時間などのアルゴリズムの問題や、高品質の実装の提供に関連する数値の問題に焦点を当てていますが、この方法の統計的側面を扱ったものはありません。この論文では、固定数の予測子を持つ線形回帰モデルのパラメーターを推定するコンテキストで、アルゴリズム レバレッジの統計的特性を評価するためのシンプルでありながら効果的なフレームワークを提供します。特に、レバレッジ ベースのサンプリングのいくつかのバージョンについて、観測データに条件付きと条件なしの両方で、バイアスと分散の結果を導きます。統計的な観点から、バイアスと分散から、レバレッジベースのサンプリングも均一サンプリングも、他方を優位に立たせるものではないことが示されています。この結果は、ワーストケース分析のアルゴリズムの観点から、均一サンプリングと比較した場合、レバレッジベースのサンプリングはワーストケースのアルゴリズム結果が均一に優れているというよく知られた結果を考えると、特に印象的です。これらの理論的結果に基づいて、2つの新しいレバレッジ アルゴリズムを提案し、分析します。1つは「収縮」レバレッジ スコア(SLEV)を持つより小さな最小二乗問題を構築し、もう1つはより小さく重み付けされていない(またはバイアスされた)最小二乗問題を解きます(LEVUNW)。既存のレバレッジ ベースの方法とこれら2つの新しい方法の詳細な実証的評価が、合成データ セットと実際のデータ セットの両方で実行されます。実証的結果は、私たちの理論が既存および新しいレバレッジ ベースのアルゴリズムの実際のパフォーマンスの優れた予測因子であり、新しいアルゴリズムがパフォーマンスの向上を実現することを示しています。たとえば、元のアルゴリズム活用アプローチと同じ計算量の削減により、提案されたSLEVは通常、無条件および条件付き(観測データに対して)の両方でバイアスと分散の改善につながり、提案されたLEVUNWは通常、無条件のバイアスと分散の改善をもたらします。
Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm
多数決のリスク限界:PACベイズ解析から学習アルゴリズムへ
We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback- Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.
私たちは、バイナリ分類における多数決の挙動に関する広範な分析を提案します。特に、投票者の平均品質と平均不一致を考慮に入れた、多数決のリスク境界であるC境界を導入します。また、トレーニング データに含まれるさまざまな観測からC境界を推定する方法を示す広範なPACベイジアン分析も提案します。この分析は自己完結型であり、PACベイジアン統計学習理論の入門資料として使用できます。一般的なPACベイジアンの観点を出発点として、珍しいPACベイジアン境界で終わります。これらの境界の一部にはKullback-Leiblerダイバージェンスが含まれず、その他の境界ではカーネル関数を投票者として使用できます(サンプル圧縮設定経由)。最後に、この分析から、基本的にC境界を最小化するMinCq学習アルゴリズムを提案します。MinCqは単純な二次計画に簡略化されます。MinCqは理論的に根拠があるだけでなく、AdaBoostおよびサポート ベクター マシンとの広範な実験的比較で示されているように、最先端のパフォーマンスを実現します。
Strong Consistency of the Prototype Based Clustering in Probabilistic Space
確率空間におけるプロトタイプベースクラスタリングの強い一貫性
In this paper we formulate in general terms an approach to prove strong consistency of the Empirical Risk Minimisation inductive principle applied to the prototype or distance based clustering. This approach was motivated by the Divisive Information- Theoretic Feature Clustering model in probabilistic space with Kullback-Leibler divergence, which may be regarded as a special case within the Clustering Minimisation framework.
この論文では、プロトタイプまたは距離ベースのクラスタリングに適用される経験的リスク最小化帰納原理の強力な一貫性を証明するためのアプローチを一般的な用語で定式化します。このアプローチは、Kullback-Leibler発散を伴う確率空間におけるDivisive Information-Theoretic Feature Clusteringモデルによって動機付けられました。これは、クラスタリング最小化フレームワーク内の特別なケースと見なすことができます。
Response-Based Approachability with Applications to Generalized No-Regret Problems
一般化された後悔問題への応用による応答ベースの親しみやすさ
Blackwell’s theory of approachability provides fundamental results for repeated games with vector-valued payoffs, which have been usefully applied in the theory of learning in games, and in devising online learning algorithms in the adversarial setup. A target set $S$ is approachable by a player (the agent) in such a game if he can ensure that the average payoff vector converges to $S$, no matter what the opponent does. Blackwell provided two equivalent conditions for a convex set to be approachable. Standard approachability algorithms rely on the primal condition, which is a geometric separation condition, and essentially require to compute at each stage a projection direction from a certain point to $S$. Here we introduce an approachability algorithm that relies on Blackwell’s dual condition, which requires the agent to have a feasible response to each mixed action of the opponent, namely a mixed action such that the expected payoff vector belongs to $S$. Thus, rather than projections, the proposed algorithm relies on computing the response to a certain action of the opponent at each stage. We demonstrate the utility of the proposed approach by applying it to certain generalizations of the classical regret minimization problem, which incorporate side constraints, reward-to-cost criteria, and so-called global cost functions. In these extensions, computation of the projection is generally complex while the response is readily obtainable.
ブラックウェルの接近可能性理論は、ベクトル値のペイオフを伴う繰り返しゲームに基本的な結果をもたらし、ゲームにおける学習理論や、敵対的設定におけるオンライン学習アルゴリズムの考案に有効に適用されてきた。このようなゲームでは、対戦相手が何をしても平均ペイオフベクトルがSに収束することをプレイヤー(エージェント)が保証できれば、ターゲット セットSはプレイヤー(エージェント)にとって接近可能です。ブラックウェルは、凸集合が接近可能であるための2つの同等の条件を示した。標準的な接近可能性アルゴリズムは、幾何学的分離条件である主条件に依存しており、基本的に各段階で特定の点からSへの射影方向を計算する必要があります。ここでは、ブラックウェルの双対条件に依存する接近可能性アルゴリズムを紹介します。この条件では、エージェントが対戦相手の各混合アクションに対して実行可能な応答、つまり期待されるペイオフ ベクトルがSに属するような混合アクションを持つことが求められます。したがって、提案されたアルゴリズムは、射影ではなく、各段階での対戦相手の特定のアクションに対する応答を計算することに依存します。私たちは、サイド制約、報酬対コスト基準、いわゆるグローバルコスト関数を組み込んだ古典的な後悔最小化問題の特定の一般化に提案アプローチを適用することで、その有用性を実証します。これらの拡張では、投影の計算は一般に複雑ですが、応答は簡単に得られます。
A Compression Technique for Analyzing Disagreement-Based Active Learning
意見の相違に基づくアクティブラーニングの分析のための圧縮手法
We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.
私たちは、不一致ベースのアクティブラーニングのラベルの複雑さの新しく改善された特性付けを導入し、主要な量はバージョン空間圧縮セットサイズです。この量は、同じバージョン空間を誘発するトレーニングデータの最小サブセットのサイズとして定義されます。CALの厳密な分析や、ガウス分布と製品密度の軸に整列した長方形の混合下での線形セパレーターのラベル複雑性境界の精緻化など、新しい特性評価のさまざまなアプリケーションを示します。バージョン空間圧縮セットのサイズと、ラベルの複雑さの新しい特性付けは、自然に不可知論的学習問題に拡張でき、2つのよく知られたアクティブラーニングアルゴリズムの新しい高速化結果を示します。
Evolving GPU Machine Code
進化するGPUマシンコード
Parallel Graphics Processing Unit (GPU) implementations of GP have appeared in the literature using three main methodologies: (i) compilation, which generates the individuals in GPU code and requires compilation; (ii) pseudo-assembly, which generates the individuals in an intermediary assembly code and also requires compilation; and (iii) interpretation, which interprets the codes. This paper proposes a new methodology that uses the concepts of quantum computing and directly handles the GPU machine code instructions. Our methodology utilizes a probabilistic representation of an individual to improve the global search capability. In addition, the evolution in machine code eliminates both the overhead of compiling the code and the cost of parsing the program during evaluation. We obtained up to 2.74 trillion GP operations per second for the 20-bit Boolean Multiplexer benchmark. We also compared our approach with the other three GPU-based acceleration methodologies implemented for quantum-inspired linear GP. Significant gains in performance were obtained.
GPの並列GPU (Graphics Processing Unit)実装は、文献に3つの主な方法論を使用して登場しています。(i)コンパイル(個体をGPUコードで生成し、コンパイルが必要)、(ii)疑似アセンブリ(個体を中間アセンブリ コードで生成し、コンパイルが必要)、(iii)解釈(コードを解釈)です。この論文では、量子コンピューティングの概念を使用し、GPUマシン コード命令を直接処理する新しい方法論を提案します。この方法論では、個体の確率的表現を利用して、グローバル検索機能を向上させます。さらに、マシン コードの進化により、コードのコンパイルのオーバーヘッドと、評価中にプログラムを解析するコストの両方が排除されます。20ビット ブール マルチプレクサ ベンチマークでは、1秒あたり最大2.74兆回のGP操作が得られました。また、量子に着想を得た線形GP用に実装された他の3つのGPUベースのアクセラレーション方法論とこのアプローチを比較しました。
Discrete Restricted Boltzmann Machines
離散制限付きボルツマンマシン
We describe discrete restricted Boltzmann machines: probabilistic graphical models with bipartite interactions between visible and hidden discrete variables. Examples are binary restricted Boltzmann machines and discrete naïve Bayes models. We detail the inference functions and distributed representations arising in these models in terms of configurations of projected products of simplices and normal fans of products of simplices. We bound the number of hidden variables, depending on the cardinalities of their state spaces, for which these models can approximate any probability distribution on their visible states to any given accuracy. In addition, we use algebraic methods and coding theory to compute their dimension.
私たちは、離散制限ボルツマンマシンについて説明します:可視変数と隠れ離散変数の間の二部相互作用を持つ確率的グラフィカルモデル。例としては、バイナリ制限ボルツマンマシンや離散ナイブベイズモデルがあります。これらのモデルで生じる推論関数と分布表現を、シンプリスの投影積とシンプリスの積の正規ファンの構成の観点から詳しく説明します。隠れ変数の数を、その状態空間のカーディナリティに応じて制限し、これらのモデルが可視状態の任意の確率分布を任意の精度に近似できるようにします。さらに、代数的方法と符号化理論を使用して、それらの次元を計算します。
Generalized Hierarchical Kernel Learning
一般化階層カーネル学習
This paper generalizes the framework of Hierarchical Kernel Learning (HKL) and illustrates its utility in the domain of rule learning. HKL involves Multiple Kernel Learning over a set of given base kernels assumed to be embedded on a directed acyclic graph. This paper proposes a two-fold generalization of HKL: the first is employing a generic $\ell_1/\ell_\rho$ block-norm regularizer ($\rho\in(1,2]$) that alleviates a key limitation of the HKL formulation. The second is a generalization to the case of multi-class, multi-label and more generally, multi-task applications. The main technical contribution of this work is the derivation of a highly specialized partial dual of the proposed generalized HKL formulation and an efficient mirror descent based active set algorithm for solving it. Importantly, the generic regularizer enables the proposed formulation to be employed in the Rule Ensemble Learning (REL) where the goal is to construct an ensemble of conjunctive propositional rules. Experiments on benchmark REL data sets illustrate the efficacy of the proposed generalizations.
この論文では、階層的カーネル学習(HKL)のフレームワークを一般化し、ルール学習の分野でのその有用性について説明します。HKLは、有向非巡回グラフに埋め込まれていると想定される一連の基本カーネルに対する多重カーネル学習を伴います。この論文では、HKLの2つの一般化を提案しています。1つ目は、HKL定式化の主な制限を軽減する汎用$\ell_1/\ell_\rho$ブロックノルム正則化子($\rho\in(1,2]$)を使用することです。2つ目は、マルチクラス、マルチラベル、より一般的にはマルチタスク アプリケーションの場合への一般化です。この研究の主な技術的貢献は、提案された一般化HKL定式化の高度に特殊化された部分双対と、それを解決するための効率的なミラー降下ベースのアクティブ セット アルゴリズムの導出です。重要なことは、汎用正則化子によって、提案された定式化をルール アンサンブル学習(REL)で使用できることです。RELの目標は、連言命題ルールのアンサンブルを構築することです。ベンチマークRELデータ セットでの実験により、提案された一般化の有効性が実証されています。
Regularized M-estimators with Nonconvexity: Statistical and Algorithmic Theory for Local Optima
非凸性を持つ正則化M推定量:局所最適性のための統計的およびアルゴリズム理論
We provide novel theoretical results regarding local optima of regularized $M$-estimators, allowing for nonconvexity in both loss and penalty functions. Under restricted strong convexity on the loss and suitable regularity conditions on the penalty, we prove that any stationary point of the composite objective function will lie within statistical precision of the underlying parameter vector. Our theory covers many nonconvex objective functions of interest, including the corrected Lasso for errors-in-variables linear models; regression for generalized linear models with nonconvex penalties such as SCAD, MCP, and capped-$\ell_1$; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the $\ell_1$-, $\ell_2$-, and prediction error between stationary points and the population-level optimum. We also propose a simple modification of composite gradient descent that may be used to obtain a near-global optimum within statistical precision $\epsilon_{\text{stat}}$ in $\log(1/\epsilon_{\text{stat}})$ steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.
私たちは、損失関数とペナルティ関数の両方で非凸性を許容する、正規化された$M$推定量の局所最適値に関する新しい理論的結果を提供します。損失に関する制限された強い凸性とペナルティに関する適切な正規性条件の下で、複合目的関数の任意の定常点は、基礎となるパラメーター ベクトルの統計的精度内に存在することを証明します。我々の理論は、変数エラー線形モデルの修正Lasso、SCAD、MCP、キャップされた$\ell_1$などの非凸ペナルティを持つ一般化線形モデルの回帰、高次元グラフィカル モデル推定など、多くの興味深い非凸目的関数をカバーしています。定常点と集団レベルの最適値との間の$\ell_1$、$\ell_2$、および予測誤差の境界を提供することで、統計的精度を定量化します。また、複合勾配降下法の単純な修正法を提案します。この修正法は、統計精度$\epsilon_{\text{stat}}$内で$\log(1/\epsilon_{\text{stat}})$ステップでほぼグローバル最適値を取得するために使用できます。これは、あらゆる一次法の中で可能な限り最速の速度です。理論的結果の鮮明さを示すシミュレーション研究を提供します。
The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in R
Rでの高次元線形回帰と精度行列推定のためのフレアパッケージ
This paper describes an R package named flare, which implements a family of new high dimensional regression methods (LAD Lasso, SQRT Lasso, $\ell_q$ Lasso, and Dantzig selector) and their extensions to sparse precision matrix estimation (TIGER and CLIME). These methods exploit different nonsmooth loss functions to gain modeling flexibility, estimation robustness, and tuning insensitiveness. The developed solver is based on the alternating direction method of multipliers (ADMM). The package flare is coded in double precision C, and called from R by a user-friendly interface. The memory usage is optimized by using the sparse matrix output. The experiments show that flare is efficient and can scale up to large problems.
この論文では、新しい高次元回帰手法(LAD Lasso、SQRT Lasso、$ell_q$ Lasso、Dantzig selector)のファミリと、それらのスパース精度行列推定(TIGERおよびCLIME)への拡張を実装するflareという名前のRパッケージについて説明します。これらの手法では、さまざまな非平滑損失関数を利用して、モデリングの柔軟性、推定のロバスト性、および調整の鈍感性を獲得します。開発されたソルバーは、乗数交互方向法(ADMM)に基づいています。パッケージフレアは倍精度Cでコード化され、ユーザーフレンドリーなインターフェースによってRから呼び出されます。メモリ使用量は、スパース行列出力を使用して最適化されます。実験では、フレアが効率的であり、大きな問題にスケールアップできることが示されています。
Introducing CURRENNT: The Munich Open-Source CUDA RecurREnt Neural Network Toolkit
CURRENNTの紹介:ミュンヘンのオープンソースCUDA RecurREntニューラルネットワークツールキット
In this article, we introduce CURRENNT, an open-source parallel implementation of deep recurrent neural networks (RNNs) supporting graphics processing units (GPUs) through NVIDIA’s Computed Unified Device Architecture (CUDA). CURRENNT supports uni- and bidirectional RNNs with Long Short-Term Memory (LSTM) memory cells which overcome the vanishing gradient problem. To our knowledge, CURRENNT is the first publicly available parallel implementation of deep LSTM-RNNs. Benchmarks are given on a noisy speech recognition task from the 2013 2nd CHiME Speech Separation and Recognition Challenge, where LSTM-RNNs have been shown to deliver best performance. In the result, double digit speedups in bidirectional LSTM training are achieved with respect to a reference single-threaded CPU implementation. CURRENNT is available under the GNU General Public License from http://sourceforge.net/p/currennt.
この記事では、NVIDIAのComputed Unified Device Architecture (CUDA)を通じてグラフィックス プロセッシング ユニット(GPU)をサポートするディープ リカレント ニューラル ネットワーク(RNN)のオープンソースの並列実装であるCURRENNTを紹介します。CURRENNTは、長短命記憶(LSTM)メモリセルを備えた単方向および双方向のRNNをサポートし、勾配消失の問題を克服します。私たちの知る限り、CURRENNTはディープLSTM-RNNの公開された最初の並列実装であり、ベンチマークは、LSTM-RNNが最高のパフォーマンスを発揮することが示された2013年の第2回CHiME音声分離および認識チャレンジのノイズの多い音声認識タスクで提供されています。その結果、参照シングルスレッドCPUの実装に関して、双方向LSTMトレーニングの2桁の高速化が達成されます。CURRENNTは、http://sourceforge.net/p/currenntのGNU General Public Licenseの下で利用できます。
AD3: Alternating Directions Dual Decomposition for MAP Inference in Graphical Models
AD3:グラフィカルモデルにおけるMAP推論のための交互方向双対分解
We present AD$^3$, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs, based on the alternating directions method of multipliers. Like other dual decomposition algorithms, AD$^3$ has a modular architecture, where local subproblems are solved independently, and their solutions are gathered to compute a global update. The key characteristic of AD$^3$ is that each local subproblem has a quadratic regularizer, leading to faster convergence, both theoretically and in practice. We provide closed-form solutions for these AD$^3$ subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD$^3$ applicable to a wide range of problems. Experiments on synthetic and real-world problems show that AD$^3$ compares favorably with the state-of-the-art.
私たちは、乗数の交互方向法に基づいて、因子グラフ上の近似最大事後(MAP)推論のための新しいアルゴリズムであるAD$^3$を提示します。他の双対分解アルゴリズムと同様に、AD$^3$はモジュラー アーキテクチャを採用しており、ローカルなサブ問題を個別に解決し、その解を集めてグローバル更新を計算します。AD$^3$の主な特徴は、各局所部分問題が2次正則化器を持ち、理論的にも実践的にも収束が速くなることです。これらのAD$^3$サブ問題に対して、バイナリ ペアワイズ因子と1次論理制約を課す因子に対して閉形式のソリューションを提供します。任意の因子(大規模または組み合わせ)に対して、ローカルMAP構成を計算するためにオラクルのみを必要とするアクティブセット法を導入し、AD$^3$を幅広い問題に適用できるようにします。合成問題と実世界問題に関する実験では、AD$^3$が最先端のものと比較しても遜色ないことが示されています。
A Classification Module for Genetic Programming Algorithms in JCLEC
JCLECにおける遺伝的プログラミングアルゴリズムの分類モジュール
JCLEC-Classification is a usable and extensible open source library for genetic programming classification algorithms. It houses implementations of rule-based methods for classification based on genetic programming, supporting multiple model representations and providing to users the tools to implement any classifier easily. The software is written in Java and it is available from jclec.sourceforge.net/classification under the GPL license.
JCLEC-Classificationは、遺伝的プログラミング分類アルゴリズム用の使いやすく拡張可能なオープンソースライブラリです。これは、遺伝的プログラミングに基づく分類のためのルールベースの方法の実装を収容し、複数のモデル表現をサポートし、任意の分類器を簡単に実装するためのツールをユーザーに提供します。ソフトウェアはJavaで書かれており、GPLライセンスの下でjclec.sourceforge.net/classificationから入手できます。
Iterative and Active Graph Clustering Using Trace Norm Minimization Without Cluster Size Constraints
クラスタサイズ制約なしのトレースノルム最小化を使用した反復グラフクラスタリングとアクティブグラフクラスタリング
This paper investigates graph clustering under the planted partition model in the presence of small clusters. Traditional results dictate that for an algorithm to provably correctly recover the underlying clusters, all clusters must be sufficiently large—in particular, the cluster sizes need to be $\tilde{\Omega}(\sqrt{n})$, where $n$ is the number of nodes of the graph. We show that this is not really a restriction: by a refined analysis of a convex-optimization-based recovery approach, we prove that small clusters, under certain mild assumptions, do not hinder recovery of large ones. Based on this result, we further devise an iterative algorithm to provably recover almost all clusters via a âpeeling strategyâ: we recover large clusters first, leading to a reduced problem, and repeat this procedure. These results are extended to the partial observation setting, in which only a (chosen) part of the graph is observed. The peeling strategy gives rise to an active learning algorithm, in which edges adjacent to smaller clusters are queried more often after large clusters are learned (and removed). We expect that the idea of iterative peeling—that is, sequentially identifying a subset of the clusters and reducing the problem to a smaller one—is useful more broadly beyond the specific implementations (based on convex optimization) used in this paper.
この論文では、小さなクラスターが存在する場合のプランテッド パーティション モデルによるグラフ クラスタリングについて調査します。従来の結果では、アルゴリズムが基礎となるクラスターを正しく回復するには、すべてのクラスターが十分に大きくなければならないとされています。特に、クラスターのサイズは$\tilde{\Omega}(\sqrt{n})$である必要があります。ここで、$n$はグラフのノードの数です。これは実際には制約ではないことを示しています。凸最適化ベースの回復アプローチの詳細な分析により、小さなクラスターは、特定の緩い仮定の下で、大きなクラスターの回復を妨げないことを証明します。この結果に基づいて、さらに反復アルゴリズムを考案し、ほぼすべてのクラスターを「ピーリング戦略」によって回復できることを証明します。まず大きなクラスターを回復して問題を縮小し、この手順を繰り返します。これらの結果は、グラフの(選択された)部分のみが観測される部分観測設定に拡張されます。ピーリング戦略により、大きなクラスターが学習(および削除)された後、小さなクラスターに隣接するエッジがより頻繁に照会されるアクティブ ラーニング アルゴリズムが生まれます。反復ピーリング(つまり、クラスターのサブセットを順番に識別し、問題をより小さな問題に縮小する)というアイデアは、この論文で使用されている特定の実装(凸最適化に基づく)を超えて、より広範囲で役立つと期待しています。
Network Granger Causality with Inherent Grouping Structure
固有のグループ化構造を持つネットワークグレンジャーの因果関係
The problem of estimating high-dimensional network models arises naturally in the analysis of many biological and socio-economic systems. In this work, we aim to learn a network structure from temporal panel data, employing the framework of Granger causal models under the assumptions of sparsity of its edges and inherent grouping structure among its nodes. To that end, we introduce a group lasso regression regularization framework, and also examine a thresholded variant to address the issue of group misspecification. Further, the norm consistency and variable selection consistency of the estimates are established, the latter under the novel concept of direction consistency. The performance of the proposed methodology is assessed through an extensive set of simulation studies and comparisons with existing techniques. The study is illustrated on two motivating examples coming from functional genomics and financial econometrics.
高次元ネットワークモデルを推定する問題は、多くの生物学的および社会経済的システムの分析で自然に発生します。この研究では、グレンジャー因果モデルのフレームワークを用いて、そのエッジのスパース性とノード間の固有のグループ化構造を仮定して、時間パネルデータからネットワーク構造を学習することを目指します。そのために、グループLASSO回帰正則化フレームワークを導入し、グループの誤指定の問題に対処するためのしきい値バリアントも検討します。さらに、推定値のノルム一貫性と変数選択一貫性が確立され、後者は方向一貫性の新しい概念の下で確立されます。提案された方法論の性能は、広範な一連のシミュレーション研究と既存の手法との比較を通じて評価されます。この研究では、機能ゲノミクスと金融計量経済学から得られた2つの動機付けの例に示されています。
Composite Self-Concordant Minimization
複合自己一致最小化
We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function, endowed with an easily computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new set of analytic step-size selection and correction procedures based on the structure of the problem. We describe concrete algorithmic instances of our framework for several interesting applications and demonstrate them numerically on both synthetic and real data.
私たちは、自己一致関数と非平滑凸関数の合計を最小化するための変数計量フレームワークを提案し、簡単に計算可能な近位演算子を備えています。理論的には、滑らかな部分での通常のリプシッツ勾配の仮定に頼ることなく、フレームワークの収束を確立します。私たちの仕事の重要なハイライトは、問題の構造に基づく新しい解析的なステップサイズの選択と修正手順のセットです。いくつかの興味深いアプリケーションのためのフレームワークの具体的なアルゴリズムインスタンスを説明し、それらを合成データと実データの両方で数値で示します。
Geometric Intuition and Algorithms for Ev–SVM
Ev–SVMのための幾何学的直感とアルゴリズム
In this work we address the E$\nu$–SVM model proposed by Pérez –Cruz et al. as an extension of the traditional $\nu$ support vector classification model ($\nu$–SVM). Through an enhancement of the range of admissible values for the regularization parameter $\nu$, the E$\nu$–SVM has been shown to be able to produce a wider variety of decision functions, giving rise to a better adaptability to the data. However, while a clear and intuitive geometric interpretation can be given for the $\nu$–SVM model as a nearest–point problem in reduced convex hulls (RCH–NPP), no previous work has been made in developing such intuition for the E$\nu$–SVM model. In this paper we show how E$\nu$–SVM can be reformulated as a geometrical problem that generalizes RCH–NPP, providing new insights into this model. Under this novel point of view, we propose the rapminos algorithm, able to solve E$\nu$–SVM more efficiently than the current methods. Furthermore, we show how rapminos is able to address the E$\nu$–SVM model for any choice of regularization norm $\ell_{p \geq 1}$ seamlessly, which further extends the SVM model flexibility beyond the usual E$\nu$–SVM models.
この研究では、Pérez-Cruzらが従来の$\nu$サポートベクター分類モデル($\nu$–SVM)の拡張として提案したE$\nu$–SVMモデルを取り上げます。正規化パラメーター$\nu$の許容値の範囲を拡大することで、E$\nu$–SVMはより多様な決定関数を生成でき、データへの適応性が向上することが示されています。ただし、$\nu$–SVMモデルについては、縮小凸包(RCH–NPP)における最近点問題として明確かつ直感的な幾何学的解釈が可能ですが、E$\nu$–SVMモデルについてそのような直感を開発する研究はこれまで行われていません。この論文では、E$\nu$–SVMをRCH–NPPを一般化する幾何学的問題として再定式化する方法を示し、このモデルに対する新しい洞察を提供します。この新しい観点から、我々は現在の方法よりも効率的にE$\nu$–SVMを解くことができるrapminosアルゴリズムを提案します。さらに、我々はrapminosが正規化ノルム$\ell_{p \geq 1}$の任意の選択に対してE$\nu$–SVMモデルをシームレスに処理する方法を示し、これによりSVMモデルの柔軟性が通常のE$\nu$–SVMモデルを超えてさらに拡張されます。
An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
非同期並列確率的座標降下アルゴリズム
We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate ($1/K$) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is $O(n^{1/2})$ in unconstrained optimization and $O(n^{1/4})$ in the separable- constrained case, where $n$ is the number of variables. We describe results from implementation on 40-core processors.
私たちは、スムーズで制約のない関数、または分離可能な制約のある関数を最小化するための非同期並列確率的座標降下アルゴリズムについて説明します。この手法は、必須の強凸性特性を満たす関数では線形収束率を達成し、一般凸関数ではサブリニア率($1/K$)を達成します。マルチコア システムでは、プロセッサの数が制約なしの最適化で$O(n^{1/2})$、分離可能な制約付きの場合($n$は変数の数)で$O(n^{1/4})$の場合、マルチコア システムでのほぼ線形の高速化が期待できます。40コアプロセッサでの実装結果について説明します。
Multimodal Gesture Recognition via Multiple Hypotheses Rescoring
多重仮説再スコアリングによるマルチモーダルジェスチャー認識
We present a new framework for multimodal gesture recognition that is based on a multiple hypotheses rescoring fusion scheme. We specifically deal with a demanding Kinect-based multimodal data set, introduced in a recent gesture recognition challenge (ChaLearn 2013), where multiple subjects freely perform multimodal gestures. We employ multiple modalities, that is, visual cues, such as skeleton data, color and depth images, as well as audio, and we extract feature descriptors of the hands’ movement, handshape, and audio spectral properties. Using a common hidden Markov model framework we build single-stream gesture models based on which we can generate multiple single stream-based hypotheses for an unknown gesture sequence. By multimodally rescoring these hypotheses via constrained decoding and a weighted combination scheme, we end up with a multimodally-selected best hypothesis. This is further refined by means of parallel fusion of the monomodal gesture models applied at a segmental level. In this setup, accurate gesture modeling is proven to be critical and is facilitated by an activity detection system that is also presented. The overall approach achieves 93.3% gesture recognition accuracy in the ChaLearn Kinect-based multimodal data set, significantly outperforming all recently published approaches on the same challenging multimodal gesture recognition task, providing a relative error rate reduction of at least 47.6%.
私たちは、複数の仮説を再スコアリングする融合スキームに基づく、マルチモーダル ジェスチャ認識のための新しいフレームワークを紹介します。特に、最近のジェスチャ認識チャレンジ(ChaLearn 2013)で導入された、複数の被験者が自由にマルチモーダル ジェスチャを実行する、要求の厳しいKinectベースのマルチモーダル データ セットを扱います。私たちは、複数のモダリティ、つまりスケルトン データ、色と深度の画像、オーディオなどの視覚的な手がかりを使用し、手の動き、手形、オーディオのスペクトル特性の特徴記述子を抽出します。一般的な隠れマルコフ モデル フレームワークを使用して、未知のジェスチャ シーケンスに対して複数のシングル ストリーム ベースの仮説を生成できるシングル ストリーム ジェスチャ モデルを構築します。制約付きデコードと重み付けされた組み合わせスキームを介してこれらの仮説をマルチモーダルに再スコアリングすることで、マルチモーダルに選択された最良の仮説が得られます。これは、セグメント レベルで適用されるモノモーダル ジェスチャ モデルの並列融合によってさらに洗練されます。この設定では、正確なジェスチャ モデリングが重要であることが証明されており、これは、同じく提示されているアクティビティ検出システムによって促進されます。全体的なアプローチでは、ChaLearn Kinectベースのマルチモーダル データ セットで93.3%のジェスチャ認識精度を達成し、同じ困難なマルチモーダル ジェスチャ認識タスクで最近公開されたすべてのアプローチを大幅に上回り、相対エラー率が少なくとも47.6%削減されます。
Multi-layered Gesture Recognition with Kinect
キネクトによる多層ジェスチャ認識
This paper proposes a novel multi-layered gesture recognition method with Kinect. We explore the essential linguistic characters of gestures: the components concurrent character and the sequential organization character, in a multi-layered framework, which extracts features from both the segmented semantic units and the whole gesture sequence and then sequentially classifies the motion, location and shape components. In the first layer, an improved principle motion is applied to model the motion component. In the second layer, a particle-based descriptor and a weighted dynamic time warping are proposed for the location component classification. In the last layer, the spatial path warping is further proposed to classify the shape component represented by unclosed shape context. The proposed method can obtain relatively high performance for one-shot learning gesture recognition on the ChaLearn Gesture Dataset comprising more than 50, 000 gesture sequences recorded with Kinect.
この論文では、Kinectを用いた新しい多層ジェスチャー認識手法を提案します。ジェスチャーの本質的な言語的特徴、すなわち、構成要素の同時性文字と逐次的な組織化文字を、セグメント化された意味単位とジェスチャーシーケンス全体の両方から特徴を抽出し、運動、位置、形状の構成要素を逐次的に分類する多層的なフレームワークで探求します。最初のレイヤーでは、改良された原理運動が適用されて、運動成分がモデル化されます。2番目のレイヤーでは、粒子ベースの記述子と重み付けされた動的タイム ワープが位置コンポーネントの分類に提案されています。最後のレイヤーでは、閉じていないシェイプ コンテキストによって表されるシェイプ コンポーネントを分類するために、空間パス ワープがさらに提案されています。提案された方法は、Kinectで記録された50, 000以上のジェスチャーシーケンスを含むChaLearn Gesture Dataset上でのワンショット学習ジェスチャー認識に対して比較的高いパフォーマンスを得ることができます。
Learning Transformations for Clustering and Classification
クラスタリングと分類のための学習変換
A low-rank transformation learning framework for subspace clustering and classification is proposed here. Many high- dimensional data, such as face images and motion sequences, approximately lie in a union of low-dimensional subspaces. The corresponding subspace clustering problem has been extensively studied in the literature to partition such high-dimensional data into clusters corresponding to their underlying low- dimensional subspaces. Low-dimensional intrinsic structures are often violated for real-world observations, as they can be corrupted by errors or deviate from ideal models. We propose to address this by learning a linear transformation on subspaces using nuclear norm as the modeling and optimization criteria. The learned linear transformation restores a low-rank structure for data from the same subspace, and, at the same time, forces a maximally separated structure for data from different subspaces. In this way, we reduce variations within the subspaces, and increase separation between the subspaces for a more robust subspace clustering. This proposed learned robust subspace clustering framework significantly enhances the performance of existing subspace clustering methods. Basic theoretical results presented here help to further support the underlying framework. To exploit the low-rank structures of the transformed subspaces, we further introduce a fast subspace clustering technique, which efficiently combines robust PCA with sparse modeling. When class labels are present at the training stage, we show this low-rank transformation framework also significantly enhances classification performance. Extensive experiments using public data sets are presented, showing that the proposed approach significantly outperforms state-of-the-art methods for subspace clustering and classification. The learned low cost transform is also applicable to other classification frameworks.
ここでは、サブスペースのクラスタリングと分類のための低ランク変換学習フレームワークを提案します。顔画像やモーションシーケンスなどの多くの高次元データは、低次元サブスペースの和集合にほぼ存在します。このような高次元データを、その基礎となる低次元サブスペースに対応するクラスターに分割するための対応するサブスペースクラスタリング問題は、文献で広く研究されてきました。低次元の固有構造は、エラーによって破損したり、理想的なモデルから逸脱したりする可能性があるため、実際の観察ではしばしば違反されます。私たちは、モデリングと最適化の基準として核ノルムを使用してサブスペースの線形変換を学習することで、この問題に対処することを提案します。学習された線形変換は、同じサブスペースのデータに対して低ランク構造を復元し、同時に、異なるサブスペースのデータに対して最大限に分離された構造を強制します。このようにして、サブスペース内の変動を減らし、サブスペース間の分離を増やして、より堅牢なサブスペースクラスタリングを実現します。この提案された学習された堅牢なサブスペースクラスタリングフレームワークは、既存のサブスペースクラスタリング方法のパフォーマンスを大幅に向上させます。ここで提示された基本的な理論的結果は、基礎となるフレームワークをさらにサポートするのに役立ちます。変換されたサブスペースの低ランク構造を活用するために、堅牢なPCAとスパース モデリングを効率的に組み合わせた高速サブスペース クラスタリング手法をさらに導入します。クラス ラベルがトレーニング段階に存在する場合、この低ランク変換フレームワークによって分類パフォーマンスも大幅に向上することがわかります。公開データセットを使用した広範な実験が提示され、提案されたアプローチがサブスペース クラスタリングと分類の最先端の方法を大幅に上回ることを示しています。学習された低コストの変換は、他の分類フレームワークにも適用できます。
Online Learning via Sequential Complexities
逐次的な複雑さによるオンライン学習
We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to the sequential setting. The developed theory is shown to yield precise learning guarantees for the problem of sequential prediction. In particular, we show necessary and sufficient conditions for online learnability in the setting of supervised learning. Several examples show the utility of our framework: we can establish learnability without having to exhibit an explicit online learning algorithm.
私たちは、逐次予測の問題を検討し、関連するゲームのミニマックス値を研究するためのツールを提供します。古典的な統計的学習理論は、i.i.d.データを用いた学習を研究するためのいくつかの有用な複雑さの尺度を提供します。私たちが提案する逐次の複雑さは、これらの尺度を逐次設定に拡張したものと見なすことができます。開発された理論は、逐次予測の問題に対して正確な学習保証をもたらすことが示されています。特に、教師あり学習の場面におけるオンライン学習可能性のための必要十分条件を示す。いくつかの例は、私たちのフレームワークの有用性を示しています:明示的なオンライン学習アルゴリズムを示すことなく、学習可能性を確立できます。
SAMOA: Scalable Advanced Massive Online Analysis
サモア:スケーラブルで高度な大規模オンライン分析
SAMOA (Scalable Advanced Massive Online Analysis) is a platform for mining big data streams. It provides a collection of distributed streaming algorithms for the most common data mining and machine learning tasks such as classification, clustering, and regression, as well as programming abstractions to develop new algorithms. It features a pluggable architecture that allows it to run on several distributed stream processing engines such as Storm, S4, and Samza. SAMOA is written in Java, is open source, and is available at samoa-project.net under the Apache Software License version 2.0.
SAMOA(Scalable Advanced Massive Online Analysis)は、ビッグデータストリームをマイニングするためのプラットフォームです。これは、分類、クラスタリング、回帰などの最も一般的なデータ マイニングおよび機械学習タスクのための分散ストリーミング アルゴリズムのコレクションと、新しいアルゴリズムを開発するためのプログラミング抽象化を提供します。プラグ可能なアーキテクチャを備えているため、Storm、S4、Samzaなどの複数の分散ストリーム処理エンジンで実行できます。SAMOAはJavaで書かれており、オープンソースであり、samoa-project.netでApache Software Licenseバージョン2.0の下で入手できます。
Links Between Multiplicity Automata, Observable Operator Models and Predictive State Representations — a Unified Learning Framework
多重度オートマトン、観測可能な演算子モデル、および予測状態表現の間のリンク — 統一学習フレームワーク
Stochastic multiplicity automata (SMA) are weighted finite automata that generalize probabilistic automata. They have been used in the context of probabilistic grammatical inference. Observable operator models (OOMs) are a generalization of hidden Markov models, which in turn are models for discrete-valued stochastic processes and are used ubiquitously in the context of speech recognition and bio-sequence modeling. Predictive state representations (PSRs) extend OOMs to stochastic input-output systems and are employed in the context of agent modeling and planning. We present SMA, OOMs, and PSRs under the common framework of sequential systems, which are an algebraic characterization of multiplicity automata, and examine the precise relationships between them. Furthermore, we establish a unified approach to learning such models from data. Many of the learning algorithms that have been proposed can be understood as variations of this basic learning scheme, and several turn out to be closely related to each other, or even equivalent.
確率的多重オートマトン(SMA)は、確率的オートマトンを一般化する重み付き有限オートマトンです。確率的文法推論のコンテキストで使用されています。観測可能演算子モデル(OOM)は、隠れマルコフ モデルの一般化です。隠れマルコフ モデルは、離散値確率過程のモデルであり、音声認識やバイオシーケンス モデリングのコンテキストで広く使用されています。予測状態表現(PSR)は、OOMを確率的入出力システムに拡張し、エージェント モデリングとプランニングのコンテキストで使用されます。ここでは、多重オートマトンを代数的に特徴付けるシーケンシャル システムの共通フレームワークの下で、SMA、OOM、およびPSRを紹介し、それらの正確な関係を調べます。さらに、データからこのようなモデルを学習するための統一されたアプローチを確立します。提案されている学習アルゴリズムの多くは、この基本的な学習スキームのバリエーションとして理解することができ、いくつかは互いに密接に関連しているか、同等であることが判明しています。
Statistical Topological Data Analysis using Persistence Landscapes
パーシステンスランドスケープを用いた統計的トポロジカルデータ解析
We define a new topological summary for data that we call the persistence landscape. Since this summary lies in a vector space, it is easy to combine with tools from statistics and machine learning, in contrast to the standard topological summaries. Viewed as a random variable with values in a Banach space, this summary obeys a strong law of large numbers and a central limit theorem. We show how a number of standard statistical tests can be used for statistical inference using this summary. We also prove that this summary is stable and that it can be used to provide lower bounds for the bottleneck and Wasserstein distances.
私たちは、データの新しいトポロジ サマリーを定義し、これを永続化ランドスケープと呼びます。このサマリーはベクトル空間にあるため、標準のトポロジカルサマリーとは対照的に、統計学や機械学習のツールと簡単に組み合わせることができます。バナッハ空間に値を持つ確率変数として見ると、この要約は大数の強力な法則と中心極限定理に従います。この要約を使用して、いくつかの標準的な統計的検定を統計的推論にどのように使用できるかを示します。また、この要約が安定しており、ボトルネック距離とワッサーシュタイン距離の下限を提供するために使用できることも証明します。
Simultaneous Pursuit of Sparseness and Rank Structures for Matrix Decomposition
行列分解のためのスパース性とランク構造の同時追求
In multi-response regression, pursuit of two different types of structures is essential to battle the curse of dimensionality. In this paper, we seek a sparsest decomposition representation of a parameter matrix in terms of a sum of sparse and low rank matrices, among many overcomplete decompositions. On this basis, we propose a constrained method subject to two nonconvex constraints, respectively for sparseness and low-rank properties. Computationally, obtaining an exact global optimizer is rather challenging. To overcome the difficulty, we use an alternating directions method solving a low-rank subproblem and a sparseness subproblem alternatively, where we derive an exact solution to the low-rank subproblem, as well as an exact solution in a special case and an approximated solution generally through a surrogate of the $L_0$-constraint and difference convex programming, for the sparse subproblem. Theoretically, we establish convergence rates of a global minimizer in the Hellinger-distance, providing an insight into why pursuit of two different types of decomposed structures is expected to deliver higher estimation accuracy than its counterparts based on either sparseness alone or low-rank approximation alone. Numerical examples are given to illustrate these aspects, in addition to an application to facial imagine recognition and multiple time series analysis.
マルチレスポンス回帰では、次元の呪いと戦うために、2つの異なるタイプの構造を追求することが不可欠です。この論文では、多くの過剰完全分解の中から、スパース行列と低ランク行列の和によるパラメータ行列の最もスパースな分解表現を求めます。これに基づいて、スパース性と低ランク特性のそれぞれに対して2つの非凸制約を受ける制約付き方法を提案します。計算上、正確なグローバル最適化を得ることはかなり困難です。この困難を克服するために、低ランク部分問題とスパース性部分問題を交互に解く交互方向法を使用します。この方法では、低ランク部分問題の正確な解、特殊なケースでの正確な解、および一般にスパース部分問題に対する$L_0$制約と差分凸計画法の代理による近似解を導出します。理論的には、ヘリンガー距離におけるグローバル最小化器の収束率を確立し、2つの異なるタイプの分解構造の追求が、スパース性のみまたは低ランク近似のみに基づくものよりも高い推定精度を実現すると予想される理由についての洞察を提供します。顔画像認識と複数の時系列分析への応用に加えて、これらの側面を説明するために数値例が示されています。
Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
群衆ラベリングにおける最適な予算配分のための統計的意思決定
It has become increasingly popular to obtain machine learning labels through commercial crowdsourcing services. The crowdsourcing workers or annotators are paid for each label they provide, but the task requester usually has only a limited amount of the budget. Since the data instances have different levels of labeling difficulty and the workers have different reliability for the labeling task, it is desirable to wisely allocate the budget among all the instances and workers such that the overall labeling quality is maximized. In this paper, we formulate the budget allocation problem as a Bayesian Markov decision process (MDP), which simultaneously conducts learning and decision making. The optimal allocation policy can be obtained by using the dynamic programming (DP) recurrence. However, DP quickly becomes computationally intractable when the size of the problem increases. To solve this challenge, we propose a computationally efficient approximate policy which is called optimistic knowledge gradient. Our method applies to both pull crowdsourcing marketplaces with homogeneous workers and push marketplaces with heterogeneous workers. It can also incorporate the contextual information of instances when they are available. The experiments on both simulated and real data show that our policy achieves a higher labeling quality than other existing policies at the same budget level.
商用クラウドソーシング サービスを通じて機械学習ラベルを取得することがますます一般的になっています。クラウドソーシング ワーカーまたはアノテーターは、提供したラベルごとに報酬を受け取りますが、タスク要求者は通常、限られた予算しか持っていません。データ インスタンスにはラベル付けの難易度が異なり、ワーカーにはラベル付けタスクに対する信頼性が異なるため、全体的なラベル付け品質が最大化されるように、すべてのインスタンスとワーカーに予算を賢く割り当てることが望ましいです。この論文では、予算割り当て問題を、学習と意思決定を同時に実行するベイジアン マルコフ決定プロセス(MDP)として定式化します。最適な割り当てポリシーは、動的プログラミング(DP)再帰を使用して取得できます。ただし、問題のサイズが大きくなると、DPはすぐに計算上手に負えなくなります。この課題を解決するために、楽観的知識勾配と呼ばれる計算効率の高い近似ポリシーを提案します。この方法は、同質のワーカーがいるプル クラウドソーシング マーケットプレイスと異質のワーカーがいるプッシュ マーケットプレイスの両方に適用されます。インスタンスのコンテキスト情報が利用可能な場合は、それを組み込むこともできます。シミュレーションデータと実際のデータの両方での実験により、当社のポリシーは同じ予算レベルの他の既存のポリシーよりも高いラベル付け品質を実現することが示されました。
