The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins
AdaBoostのダイナミクス:周期的な動作とマージンの収束
In order to study the convergence properties of the AdaBoostalgorithm, we reduce AdaBoost to a nonlinear iterated map andstudy the evolution of its weight vectors. This dynamical systemsapproach allows us to understand AdaBoost’s convergence propertiescompletely in certain cases; for these cases we find stablecycles, allowing us to explicitly solve for AdaBoost’s output.Using this unusual technique, we are able to show that AdaBoostdoes not always converge to a maximum margin combined classifier,answering an open question. In addition, we show that”non-optimal” AdaBoost (where the weak learning algorithm doesnot necessarily choose the best weak classifier at each iteration)may fail to converge to a maximum margin classifier, even if”optimal” AdaBoost produces a maximum margin. Also, we show thatif AdaBoost cycles, it cycles among “support vectors”, i.e.,examples that achieve the same smallest margin.
AdaBoostアルゴリズムの収束特性を研究するために、AdaBoostを非線形反復マップに縮小し、その重みベクトルの進化を研究します。この動的システムアプローチにより、特定のケースでAdaBoostの収束特性を完全に理解することができます。これらのケースでは、安定サイクルが見つかり、AdaBoostの出力を明示的に解くことができます。この珍しい手法を使用すると、AdaBoostが常に最大マージン結合分類器に収束するとは限らないことを示すことができます。これは、未解決の質問に答えます。さらに、「最適でない」AdaBoost(弱学習アルゴリズムが各反復で最適な弱分類子を選択するとは限らない)は、「最適な」AdaBoostが最大マージンを生成した場合でも、最大マージン分類器に収束しない可能性があることを示します。また、AdaBoostがサイクルする場合、”サポート ベクトル”間、つまり同じ最小マージンを達成する例間を循環することを示します。
Fast Binary Feature Selection with Conditional Mutual Information
条件付き相互情報量による高速バイナリ機能選択
We propose in this paper a very fast feature selection technique basedon conditional mutual information. By picking features which maximizetheir mutual information with the class to predict conditional to anyfeature already picked, it ensures the selection of features which areboth individually informative and two-by-two weakly dependant. We showthat this feature selection method outperforms other classicalalgorithms, and that a naive Bayesian classifier built with featuresselected that way achieves error rates similar to those ofstate-of-the-art methods such as boosting or SVMs. The implementationwe propose selects 50 features among 40,000, based on a trainingset of 500 examples in a tenth of a second on a standard 1Ghz PC.
私たちは、この論文では、条件付き相互情報量に基づく非常に高速な特徴選択手法を提案します。クラスとの相互情報量を最大化する特徴を選択することで、既に選択された任意の特徴を条件付きで予測することにより、個別に情報を提供し、2×2の弱い依存性を持つ特徴の選択を保証します。この特徴選択方法が他の古典的なアルゴリズムよりも優れていること、およびそのように選択された特徴で構築された単純なベイズ分類器が、ブースティングやSVMなどの最先端の方法と同様のエラー率を達成することを示します。私たちが提案する実装は、標準の1Ghz PCで10分の1秒で500の例のトレーニングセットに基づいて、40,000の機能の中から50の機能を選択します。
Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning
強化学習における勾配推定のための分散縮小手法
Policy gradient methods for reinforcement learning avoid some of theundesirable properties of the value function approaches, such aspolicy degradation (Baxter and Bartlett, 2001). However, the variance of theperformance gradient estimates obtained from the simulation issometimes excessive. In this paper, we consider variance reductionmethods that were developed for Monte Carlo estimates of integrals.We study two commonly used policy gradient techniques, the baselineand actor-critic methods, from this perspective. Both can beinterpreted as additive control variate variance reduction methods.We consider the expected average reward performance measure, and wefocus on the GPOMDP algorithm for estimating performance gradients inpartially observable Markov decision processes controlled bystochastic reactive policies. We give bounds for the estimation errorof the gradient estimates for both baseline and actor-criticalgorithms, in terms of the sample size and mixing properties of thecontrolled system. For the baseline technique, we compute the optimalbaseline, and show that the popular approach of using the averagereward to define the baseline can be suboptimal. For actor-criticalgorithms, we show that using the true value function as the criticcan be suboptimal. We also discuss algorithms for estimating theoptimal baseline and approximate value function.
強化学習のポリシー勾配法は、ポリシー劣化(BaxterおよびBartlett、2001)などの価値関数アプローチの望ましくない特性の一部を回避します。ただし、シミュレーションから得られるパフォーマンス勾配推定値の分散は、場合によっては過剰になります。この論文では、積分のモンテ カルロ推定用に開発された分散削減法を検討します。この観点から、一般的に使用される2つのポリシー勾配手法、ベースライン法とアクター クリティック法を検討します。どちらも、加法的な制御変量分散削減法として解釈できます。期待される平均報酬パフォーマンス測定を検討し、確率的反応ポリシーによって制御される部分的に観測可能なマルコフ決定プロセスのパフォーマンス勾配を推定するためのGPOMDPアルゴリズムに焦点を当てます。制御対象システムのサンプル サイズと混合特性の観点から、ベースライン アルゴリズムとアクター クリティカル アルゴリズムの両方の勾配推定値の推定誤差の境界を示します。ベースライン手法では、最適なベースラインを計算し、平均報酬を使用してベースラインを定義する一般的なアプローチが最適ではない可能性があることを示します。アクター クリティカル アルゴリズムでは、真の値関数をクリティカルとして使用すると最適ではない可能性があることを示します。また、最適なベースラインと近似値関数を推定するアルゴリズムについても説明します。
Non-negative Matrix Factorization with Sparseness Constraints
スパース制約による非負の行列因数分解
Non-negative matrix factorization (NMF) is a recently developed technique for finding parts-based, linear representations of non-negative data. Although it has successfully been applied in several applications, it does not always result in parts-based representations. In this paper, we show how explicitly incorporating the notion of ‘sparseness’ improves the found decompositions. Additionally, we provide complete MATLAB code both for standard NMF and for our extension. Our hope is that this will further the application of these methods to solving novel data-analysis problems.
非負行列因数分解(NMF)は、非負データの部品ベースの線形表現を見つけるために最近開発された手法です。これはいくつかのアプリケーションで成功裏に適用されていますが、必ずしも部品ベースの表現になるわけではありません。この論文では、「スパース性」の概念を明示的に組み込むことで、発見された分解がどのように改善されるかを示します。さらに、標準のNMFと拡張機能の両方に対して完全なMATLABコードを提供しています。これにより、これらの手法が新たなデータ解析問題の解決にさらに応用されることが期待されます。
Fast String Kernels using Inexact Matching for Protein Sequences
タンパク質配列の不正確なマッチングを使用した高速ストリングカーネル
We describe several families of k-mer based string kernels related to the recently presented mismatch kernel and designedfor use with support vector machines (SVMs) for classificationof protein sequence data. These new kernels — restricted gappy kernels, substitution kernels, and wildcard kernels — are based on feature spaces indexed by k-length subsequences (“k-mers”) from the string alphabet Σ. However, for all kernels we define here, the kernel value K(x,y) can be computed in O(cK(|x|+|y|)) time, where the constant cK dependson the parameters of the kernel but is independent of the size |Σ| of the alphabet. Thus the computation of these kernels is linear in the length of the sequences, like the mismatch kernel, but we improve upon the parameter-dependent constant cK = km+1|Σ|m of the (k,m)-mismatch kernel.We compute the kernels efficiently using a trie data structure and relate our new kernels to the recently described transducer formalism. In protein classification experiments on two benchmark SCOP data sets, we show that our new faster kernels achieve SVM classification performance comparable to the mismatch kernel and the Fisher kernel derived from profile hidden Markov models, and we investigate the dependence of the kernels on parameter choice.
私たちは、最近発表されたミスマッチカーネルに関連し、タンパク質配列データの分類のためのサポートベクターマシン(SVM)で使用するために設計された、k-merベースの文字列カーネルのいくつかのファミリについて説明します。これらの新しいカーネル(制限付きギャップカーネル、置換カーネル、ワイルドカードカーネル)は、文字列アルファベット Σ からk長サブシーケンス(「k-mer」)でインデックス付けされた特徴空間に基づいています。ただし、ここで定義するすべてのカーネルについて、カーネル値K(x,y)はO(cK(|x|+|y|))時間で計算できます。ここで、定数cKはカーネルのパラメータに依存しますが、アルファベットのサイズ|Σ|には依存しません。したがって、これらのカーネルの計算は、ミスマッチカーネルのようにシーケンスの長さに比例しますが、(k,m)ミスマッチカーネルのパラメータ依存定数cK = km+1|Σ|mを改良します。トライデータ構造を使用してカーネルを効率的に計算し、新しいカーネルを最近説明したトランスデューサ形式に関連付けます。2つのベンチマークSCOPデータ セットでのタンパク質分類実験では、新しい高速カーネルが、プロファイル隠れマルコフ モデルから派生したミスマッチ カーネルおよびフィッシャー カーネルに匹敵するSVM分類パフォーマンスを実現することを示し、カーネルのパラメーター選択への依存性を調査します。
Second Order Cone Programming Formulations for Feature Selection
特徴選択のための 2 次コーン計画法の定式化
This paper addresses the issue of feature selection for linear classifiers given the moments of the class conditionaldensities. The problem is posed as finding a minimal set of features such that the resulting classifier has a low misclassification error. Using a bound on the misclassification error involving the mean and covariance of class conditional densities and minimizing an L1 norm as an approximate criterion for feature selection, a second order programming formulation is derived. To handle errors in estimation of mean and covariances, a tractable robust formulation is also discussed. In a slightly different setting the Fisher discriminant is derived. Feature selection for Fisher discriminant is also discussed. Experimental results on synthetic data sets and on real life microarray data show that the proposed formulations are competitive with the state of the art linear programming formulation.
この論文では、クラス条件密度のモーメントを前提とした線形分類器の特徴選択の問題を取り上げます。この問題は、結果として得られる分類器の誤分類誤差が小さくなるような最小限の特徴のセットを見つけることとして提起されます。クラスの条件付き密度の平均と共分散を含む誤分類誤差の範囲を使用し、特徴選択の近似基準としてL1ノルムを最小化すると、2次プログラミング定式化が導出されます。平均と共分散の推定における誤差を処理するために、扱いやすいロバストな定式化についても説明します。少し異なる設定では、フィッシャー判別式が導出されます。フィッシャー判別式の特徴選択についても説明します。合成データセットと実際のマイクロアレイデータでの実験結果は、提案された定式化が最先端の線形計画法の定式化と競争力があることを示しています。
The Entire Regularization Path for the Support Vector Machine
サポートベクターマシンの正則化パス全体
The support vector machine (SVM) is a widely used tool for classification.Many efficient implementations exist for fitting a two-class SVMmodel. The user has to supply values for the tuning parameters: theregularization cost parameter, and the kernel parameters. It seems acommon practice is to use a default value for the cost parameter,often leading to the least restrictive model. In this paper we arguethat the choice of the cost parameter can be critical. We thenderive an algorithm that can fit the entire path of SVM solutionsfor every value of the cost parameter, with essentially the samecomputational cost as fitting one SVM model. We illustrate ouralgorithm on some examples, and use our representation to givefurther insight into the range of SVM solutions.
サポートベクターマシン(SVM)は、分類に広く使用されているツールです。2クラスのSVMmodelを適合させるための効率的な実装は数多く存在します。ユーザーは、チューニング パラメーターの値(regularizationコスト パラメーターとカーネル パラメーター)を指定する必要があります。一般的な方法は、コストパラメータにデフォルト値を使用することのようで、多くの場合、最も制限の少ないモデルにつながります。この論文では、コストパラメータの選択が重要になる可能性があると主張します。次に、コスト パラメーターのすべての値に対してSVMソリューションの全パスを適合させることができるアルゴリズムを導き出します。これは、基本的に1つのSVMモデルを適合させるのと同じ計算コストです。いくつかの例でアルゴリズムを説明し、その表現を使用してSVMソリューションの範囲についてさらに洞察を提供します。
Some Properties of Regularized Kernel Methods
正則化カーネルメソッドの一部のプロパティ
In regularized kernel methods, the solution of a learning problemis found by minimizing functionals consisting of the sum of a dataand a complexity term. In this paper we investigate someproperties of a more general form of the above functionals inwhich the data term corresponds to the expected risk. First, weprove a quantitative version of the representer theorem holdingfor both regression and classification, for both differentiableand non-differentiable loss functions, and for arbitrary offsetterms. Second, we show that the case in which the offset space isnon trivial corresponds to solving a standard problem ofregularization in a Reproducing Kernel Hilbert Space in which thepenalty term is given by a seminorm. Finally, we discuss theissues of existence and uniqueness of the solution. From thespecialization of our analysis to the discrete setting it isimmediate to establish a connection between the solutionproperties of sparsity and coefficient boundedness and someproperties of the loss function. For the case of Support Vector Machines forclassification, we also obtain a complete characterization of thewhole method in terms of the Khun-Tucker conditions with no needto introduce the dual formulation.
正規化カーネル法では、学習問題の解は、データと複雑性項の合計で構成される関数を最小化することによって見つかります。この論文では、データ項が期待リスクに対応する上記の関数のより一般的な形式のいくつかの特性を調査します。まず、回帰と分類の両方、微分可能および微分不可能な損失関数の両方、および任意のオフセット項に対して成立する、表現定理の定量的バージョンを証明します。次に、オフセット空間が自明でないケースは、ペナルティ項が半ノルムで与えられる再生カーネル ヒルベルト空間における正規化の標準問題を解くことに対応することを示します。最後に、解の存在と一意性の問題について議論します。分析を離散設定に特化することで、スパース性と係数の有界性の解の特性と損失関数のいくつかの特性との間の関係をすぐに確立できます。分類用サポート ベクター マシンの場合、双対定式化を導入する必要なく、Khun-Tucker条件に関して方法全体の完全な特性も得られます。
Randomized Variable Elimination
ランダム化された変数の除去
Variable selection, the process of identifying input variables that are relevant to a particular learning problem, has received much attention in the learning community. Methods that employ a learningalgorithm as a part of the selection process (wrappers) have been shown to outperform methods that select variables independently from the learning algorithm (filters), but only at great computational expense. We present a randomized wrapper algorithm whose computational requirements are within a constant factor of simply learning in the presence of all input variables, provided that the number of relevant variables is small and known in advance. We then show how to remove the latter assumption, and demonstrate performance on several problems.
変数選択は、特定の学習問題に関連する入力変数を特定するプロセスであり、学習コミュニティで大きな注目を集めています。選択プロセスの一部として学習アルゴリズムを使用する方法(ラッパー)は、学習アルゴリズム(フィルター)とは独立して変数を選択する方法よりも優れていることが示されていますが、それは大きな計算コストがかかるだけです。関連する変数の数が少なく、事前にわかっている場合、計算要件がすべての入力変数の存在下で単に学習する一定の要因内にあるランダム化されたラッパーアルゴリズムを示します。次に、後者の仮定を削除する方法を示し、いくつかの問題でパフォーマンスを示します。
Large-Sample Learning of Bayesian Networks is NP-Hard
ベイジアンネットワークの大規模サンプル学習はNP困難
In this paper, we provide new complexity results for algorithms thatlearn discrete-variable Bayesian networks from data. Our resultsapply whenever the learning algorithm uses a scoring criterion thatfavors the simplest structure for which the model is able to representthe generative distribution exactly. Our results therefore holdwhenever the learning algorithm uses a consistent scoring criterionand is applied to a sufficiently large dataset. We show thatidentifying high-scoring structures is NP-hard, even when anycombination of one or more of the following hold: the generativedistribution is perfect with respect to some DAG containing hiddenvariables; we are given an independence oracle; we are given aninference oracle; we are given an information oracle; we restrictpotential solutions to structures in which each node has at most kparents, for all k>=3. Our proof relies on a new technical result that we establish in theappendices. In particular, we provide a method for constructing thelocal distributions in a Bayesian network such that the resultingjoint distribution is provably perfect with respect to the structureof the network.
この論文では、データから離散変数ベイジアンネットワークを学習するアルゴリズムの新しい複雑性の結果を示します。学習アルゴリズムが、モデルが生成分布を正確に表現できる最も単純な構造を優先するスコアリング基準を使用する場合、結果は適用されます。したがって、学習アルゴリズムが一貫したスコアリング基準を使用し、十分に大きなデータセットに適用される場合、結果は適用されます。次の1つ以上の組み合わせが当てはまる場合でも、高スコア構造の識別はNP困難であることを示します。生成分布は、隠れた変数を含むいくつかのDAGに関して完璧です。独立オラクルが与えられています。推論オラクルが与えられています。情報オラクルが与えられています。私たちは、各ノードが最大でk個の親を持つ構造に潜在的なソリューションを制限します(すべてのk>=3について)。我々の証明は、付録で確立する新しい技術的結果に依存しています。特に、ベイジアン ネットワークのローカル分布を構築するための方法を提供し、その結果生じる結合分布がネットワークの構造に関して証明可能な完全性を持つようにします。
The Minimum Error Minimax Probability Machine
最小誤差ミニマックス確率マシン
We construct a distribution-free Bayes optimal classifier called the MinimumError Minimax Probability Machine (MEMPM) in a worst-case setting, i.e., underall possible choices of class-conditional densities with a given mean andcovariance matrix. By assuming no specific distributions for the data, ourmodel is thus distinguished from traditional Bayes optimal approaches, where anassumption on the data distribution is a must. This model is extended from theMinimax Probability Machine (MPM), a recently-proposed novel classifier, and isdemonstrated to be the general case of MPM. Moreover, it includes anotherspecial case named the Biased Minimax Probability Machine, which is appropriate for handling biased classification. One appealing feature of MEMPM is that itcontains an explicit performance indicator, i.e., a lower bound on theworst-case accuracy, which is shown to be tighter than that of MPM. We provideconditions under which the worst-case Bayes optimal classifier converges to theBayes optimal classifier. We demonstrate how to apply a more generalstatistical framework to estimate model input parameters robustly. We alsoshow how to extend our model to nonlinear classification by exploitingkernelization techniques. A series of experiments on both synthetic data setsand real world benchmark data sets validates our proposition and demonstratesthe effectiveness of our model.
私たちは、最悪ケースの設定、すなわち、与えられた平均と共分散行列を持つクラス条件付き密度の可能なすべての選択肢の下で、分布のないベイズ最適分類器、MinimumError Minimax Probability Machine (MEMPM)を構築します。データに特定の分布を仮定しないことで、我々のモデルは、データ分布の仮定が必須である従来のベイズ最適アプローチとは区別されます。このモデルは、最近提案された新しい分類器であるMinimax Probability Machine (MPM)から拡張され、MPMの一般的なケースであることが実証されています。さらに、バイアス付き分類の処理に適した、バイアス付きMinimax Probability Machineという別の特殊なケースも含まれています。MEMPMの魅力的な機能の1つは、明示的なパフォーマンス指標、すなわち、最悪ケースの精度の下限値が含まれていることです。これは、MPMの下限値よりも厳密であることが示されています。私たちは、最悪ケースのベイズ最適分類器がベイズ最適分類器に収束する条件を提供します。より一般的な統計フレームワークを適用して、モデル入力パラメータを堅牢に推定する方法を示します。また、カーネル化技術を利用してモデルを非線形分類に拡張する方法も示します。合成データセットと実際のベンチマークデータセットの両方での一連の実験により、提案が検証され、モデルの有効性が実証されます。
Statistical Analysis of Some Multi-Category Large Margin Classification Methods
いくつかのマルチカテゴリ大マージン分類法の統計分析
The purpose of this paper is to investigate statistical properties ofrisk minimization based multi-category classification methods. These methods can be considered as natural extensions of binary large margin classification. We establish conditions that guarantee the consistency of classifiers obtained in the risk minimization frameworkwith respect to the classification error. Examples are provided for four specific forms of the general formulation, which extend a number of known methods.Using these examples, we show that some risk minimization formulations can also be used to obtain conditional probability estimatesfor the underlying problem. Such conditional probability informationcan be useful for statistical inferencing tasks beyond classification.
この論文の目的は、リスク最小化に基づくマルチカテゴリ分類法の統計的特性を調査することです。これらの方法は、バイナリの大きなマージン分類の自然な拡張と見なすことができます。リスク最小化フレームワークで得られた分類器の分類誤差に対する一貫性を保証する条件を確立します。一般的な定式化の4つの特定の形態について例が示されており、これらは多くの既知の方法を拡張しています。これらの例を使用して、一部のリスク最小化定式化を使用して、根本的な問題の条件付き確率推定値を取得することもできることを示します。このような条件付き確率情報は、分類を超えた統計的推論タスクに役立ちます。
Efficient Feature Selection via Analysis of Relevance and Redundancy
関連性と冗長性の分析による効率的な機能選択
Feature selection is applied to reduce the number offeatures in many applications where data has hundreds or thousandsof features. Existing feature selection methods mainly focus onfinding relevant features. In this paper, we show that featurerelevance alone is insufficient for efficient feature selection ofhigh-dimensional data. We define feature redundancy and propose toperform explicit redundancy analysis in feature selection. A newframework is introduced that decouples relevance analysis andredundancy analysis. We develop a correlation-based method forrelevance and redundancy analysis, and conduct an empirical studyof its efficiency and effectiveness comparing with representativemethods.
特徴選択は、データに数百または数千の特徴がある多くのアプリケーションで、特徴の数を減らすために適用されます。既存の機能選択方法は、主に関連する機能を見つけることに焦点を当てています。この論文では、高次元データの特徴選択を効率的に行うには、特徴関連性だけでは不十分であることを示します。特徴の冗長性を定義し、特徴選択において明示的な冗長性分析を行うことを提案します。関連性分析と冗長性分析を分離する新しいフレームワークが導入されました。この研究では、関連性分析と冗長性分析のための相関ベースの手法を開発し、その効率性と有効性について代表的な手法と比較した実証研究を行う。
Model Averaging for Prediction with Discrete Bayesian Networks
離散ベイジアンネットワークによる予測のためのモデル平均化
In this paper we consider the problem ofperforming Bayesian model-averaging over a class of discreteBayesian network structures consistent with a partial ordering andwith bounded in-degree k. We show that for N nodes this classcontains in the worst-case at least distinct network structures, and yet model averagingover these structures can be performed using operations. Furthermore we show that there exists asingle Bayesian network that defines a joint distribution over thevariables that is equivalent to model averaging over thesestructures. Although constructing this network is computationallyprohibitive, we show that it can be approximated by a tractablenetwork, allowing approximate model-averaged probabilitycalculations to be performed in O(N) time. Our result alsoleads to an exact and linear-time solution to the problem ofaveraging over the 2N possible feature sets in a naive Bayesmodel, providing an exact Bayesian solution to the troublesomefeature-selection problem for naive Bayes classifiers. Wedemonstrate the utility of these techniques in the context ofsupervised classification, showing empirically that modelaveraging consistently beats other generativeBayesian-network-based models, even when the generating model isnot guaranteed to be a member of the class being averaged over. Wecharacterize the performance over several parameters on simulatedand real-world data.
この論文では、部分順序と制限された入次数kと一致する離散ベイジアン ネットワーク構造のクラスに対してベイジアン モデル平均化を実行する問題を考察します。N個のノードに対して、最悪の場合でもこのクラスには少なくとも1つの異なるネットワーク構造が含まれますが、これらの構造に対するモデル平均化は操作を使用して実行できることを示します。さらに、これらの構造のモデル平均化と同等の変数の結合分布を定義する単一のベイジアン ネットワークが存在することを示します。このネットワークの構築は計算上法外ですが、扱いやすいネットワークで近似でき、近似モデル平均確率計算をO(N)時間で実行できることを示します。また、この結果は、ナイーブ ベイズ モデルで2N個の可能な特徴セットを平均化する問題に対する正確で線形時間のソリューションにつながり、ナイーブ ベイズ分類器の厄介な特徴選択問題に対する正確なベイジアン ソリューションを提供します。教師あり分類のコンテキストでこれらの手法の有用性を実証し、モデル平均化が他の生成ベイジアン ネットワーク ベースのモデルよりも一貫して優れていることを経験的に示します。これは、生成モデルが平均化されるクラスのメンバーであることが保証されていない場合でも同様です。シミュレーション データと実際のデータで、いくつかのパラメーターのパフォーマンスを特徴付けます。
Support Vector Machine Soft Margin Classifiers: Error Analysis
サポート ベクター マシン ソフト マージン分類器: エラー分析
The purpose of this paper is to provide a PAC error analysis forthe q-norm soft margin classifier, a support vector machineclassification algorithm. It consists of two parts:regularization error and sample error. While many techniquesare available for treating the sample error, much less is knownfor the regularization error and the correspondingapproximation error for reproducingkernel Hilbert spaces. We are mainly concerned about theregularization error. It is estimated for general distributionsby a K-functional in weighted Lq spaces. For weaklyseparable distributions (i.e., the margin may be zero)satisfactory convergence rates are provided by means of separating functions.A projection operator is introduced, which leads tobetter sample error estimates especially for small complexity kernels.The misclassification error is boundedby the V-risk associated with a general class ofloss functions V. The difficulty of bounding the offset is overcome.Polynomial kernels and Gaussian kernels are used todemonstrate the main results.The choice of the regularization parameterplays an important role in our analysis.
この論文の目的は、サポートベクターマシン分類アルゴリズムであるqノルムソフトマージン分類器のPAC誤差分析を提供することです。これは、正則化誤差とサンプル誤差の2つの部分で構成されています。サンプル誤差の処理には多くの手法がありますが、正則化誤差と、カーネルヒルベルト空間を再現するための対応する近似誤差についてはあまり知られていません。我々は主に正則化誤差に関心があります。これは、重み付きLq空間のK関数によって一般的な分布に対して推定されます。弱く分離可能な分布（つまり、マージンがゼロになる可能性がある）の場合、分離関数によって十分な収束率が提供されます。射影演算子が導入され、特に複雑度の低いカーネルでサンプル誤差の推定値が向上します。誤分類誤差は、損失関数Vの一般的なクラスに関連付けられたVリスクによって制限されます。オフセットを制限することの難しさは克服されています。多項式カーネルとガウスカーネルを使用して、主な結果を示します。正則化パラメーターの選択は、分析で重要な役割を果たします。
Knowledge-Based Kernel Approximation
知識ベースのカーネル近似
Prior knowledge, in the form of linear inequalities that need to besatisfied over multiple polyhedral sets, is incorporated into afunction approximation generated by a linear combination of linear ornonlinear kernels. In addition, the approximation needs to satisfyconventional conditions such as having given exact or inexact functionvalues at certain points. Determining such an approximation leads toa linear programming formulation. By using nonlinear kernels andmapping the prior polyhedral knowledge in the input space to onedefined by the kernels, the prior knowledge translates into nonlinearinequalities in the original input space. Through a number ofcomputational examples, including a real world breast cancer prognosisdataset, it is shown that prior knowledge can significantly improvefunction approximation.
事前知識は、複数の多面体集合で満たす必要のある線形不等式の形で、線形または非線形カーネルの線形結合によって生成される関数近似に組み込まれます。さらに、近似は、特定の点で正確な関数値または不正確な関数値を指定したなど、従来の条件を満たす必要があります。このような近似を決定すると、線形計画法の定式化につながります。非線形カーネルを使用し、入力空間の事前多面体知識をカーネルによって定義された知識にマッピングすることにより、事前知識は元の入力空間の非線形不等式に変換されます。実際の乳がん予後データセットを含む多くの計算例を通じて、事前知識が関数近似を大幅に改善できることが示されています。
Selective Rademacher Penalization and Reduced Error Pruning of Decision Trees
選択的なRademacherペナルティと決定木のエラープルーニングの削減
Rademacher penalization is a modern technique for obtainingdata-dependent bounds on the generalization error of classifiers. Itappears to be limited to relatively simple hypothesis classes because ofcomputational complexity issues. In this paper we, nevertheless, applyRademacher penalization to the in practice important hypothesis class ofunrestricted decision trees by considering the prunings of a givendecision tree rather than the tree growing phase. This studyconstitutes the first application of Rademacher penalization to hypothesis classes that have practical significance. We present two variations of the approach, one in which the hypothesis class consists of all prunings of the initial tree and another in which only the prunings that are accurate on growing data are taken into account. Moreover, we generalize the error-bounding approach from binary classification to multi-class situations. Our empirical experiments indicate that the proposed new bounds outperform distribution-independent bounds for decision tree prunings and provide non-trivial error estimates on real-world data sets.
ラデマッハー ペナルティは、分類器の一般化エラーに関するデータ依存の境界を取得するための最新の手法です。計算の複雑さの問題により、比較的単純な仮説クラスに限定されているようです。しかし、この論文では、ツリーの成長段階ではなく、特定の決定木の枝刈りを考慮することで、ラデマッハー ペナルティを、実際に重要な仮説クラスである無制限の決定木に適用します。この研究では、実用的な重要性を持つ仮説クラスへのラデマッハー ペナルティの初めての適用となります。このアプローチの2つのバリエーションを紹介します。1つは仮説クラスが初期ツリーのすべての枝刈りで構成されるもので、もう1つは成長するデータで正確な枝刈りのみを考慮するものです。さらに、エラー境界アプローチをバイナリ分類からマルチクラスの状況に一般化します。我々の実験では、提案された新しい境界は、決定木の剪定に対する分布に依存しない境界よりも優れており、現実世界のデータセットに対して重要な誤差推定値を提供することを示しています。
No Unbiased Estimator of the Variance of K-Fold Cross-Validation
Kフォールド交差検証の分散の不偏推定量なし
Most machine learning researchers perform quantitative experiments to estimate generalization error and compare the performance of different algorithms (in particular, their proposed algorithm). In order to be able to draw statistically convincing conclusions, it is important to estimate the uncertainty of such estimates.This paper studies the very commonly used K-fold cross-validation estimator of generalization performance. The main theorem shows that there exists no universal (valid under all distributions) unbiased estimator of the variance of K-fold cross-validation. The analysis that accompanies this result is based on the eigen-decomposition of the covariance matrix of errors, which has only three different eigenvalues corresponding to three degrees of freedom of the matrix and three components of the total variance. This analysis helps to better understand the nature of the problem and how it can make naive estimators (that don’t take into account the error correlations due to the overlap between training and test sets) grossly underestimate variance. This is confirmed by numerical experiments in which the three components of the variance are compared when the difficulty of the learning problem and the number of folds are varied.
機械学習の研究者の多くは、一般化誤差を推定し、さまざまなアルゴリズム（特に、提案されたアルゴリズム）のパフォーマンスを比較するために定量的な実験を行っています。統計的に説得力のある結論を導き出すためには、そのような推定値の不確実性を推定することが重要です。この論文では、一般化パフォーマンスの非常に一般的に使用されているK分割交差検証推定値について検討します。主な定理は、K分割交差検証の分散の普遍的な（すべての分布で有効な）不偏推定値は存在しないことを示しています。この結果に伴う分析は、誤差の共分散行列の固有分解に基づいています。この行列には、行列の3つの自由度と合計分散の3つの成分に対応する3つの異なる固有値しかありません。この分析は、問題の性質と、それがどのようにして単純な推定値（トレーニング セットとテスト セットの重複による誤差の相関を考慮しない）が分散を大幅に過小評価する原因になるのかを理解するのに役立ちます。これは、学習問題の難易度とフォールド数を変えた場合の分散の3つの要素を比較する数値実験によって確認されています。
Reinforcement Learning with Factored States and Actions
因子分解された状態と行動による強化学習
A novel approximation method is presented for approximating the value function and selecting good actions for Markov decision processes with large state and action spaces. The method approximates state-action values as negative free energies in an undirected graphical model called a product of experts. The model parameters can be learned efficiently because values and derivatives can be efficientlycomputed for a product of experts. Actions can be found even in large factored action spaces by the use of Markovchain Monte Carlo sampling. Simulation results show that the product of experts approximation can be used to solve large problems. In one simulation it is used to find actions in action spaces of size 240.
価値関数を近似し、大きな状態空間と行動空間を持つマルコフ決定過程に対して適切な行動を選択するための新しい近似方法が提示されます。この方法は、専門家の積と呼ばれる無向グラフィカルモデルで、状態作用値を負の自由エネルギーとして近似します。専門家の製品の値と導関数を効率的に計算できるため、モデルパラメータを効率的に学習できます。アクションは、マルコフチェーンモンテカルロサンプリングを使用することにより、大きな因数分解されたアクションスペースでも見つけることができます。シミュレーション結果は、専門家の近似の積を使用して大きな問題を解決できることを示しています。1つのシミュレーションでは、サイズ240のアクション空間でアクションを見つけるために使用されます。
Rational Kernels: Theory and Algorithms (Special Topic on Learning Theory)
Rational Kernels: Theory and Algorithms (学習理論に関する特別トピック)
Many classification algorithms were originally designed for fixed-sizevectors. Recent applications in text and speech processing andcomputational biology require however the analysis of variable-lengthsequences and more generally weighted automata. An approach widelyused in statistical learning techniques such as Support VectorMachines (SVMs) is that of kernel methods, due to their computationalefficiency in high-dimensional feature spaces. We introduce a generalfamily of kernels based on weighted transducers or rational relations, rational kernels , that extend kernel methods to the analysis ofvariable-length sequences or more generally weighted automata. Weshow that rational kernels can be computed efficiently using a generalalgorithm of composition of weighted transducers and a generalsingle-source shortest-distance algorithm.Not all rational kernels are positive definite and symmetric (PDS), or equivalently verify the Mercer condition, a condition thatguarantees the convergence of training for discriminant classificationalgorithms such as SVMs. We present several theoretical resultsrelated to PDS rational kernels. We show that under some generalconditions these kernels are closed under sum, product, orKleene-closure and give a general method for constructing a PDSrational kernel from an arbitrary transducer defined on somenon-idempotent semirings. We give the proof of severalcharacterization results that can be used to guide the design of PDSrational kernels. We also show that some commonly used string kernelsor similarity measures such as the edit-distance, the convolutionkernels of Haussler, and some string kernels used in the context ofcomputational biology are specific instances of rational kernels. Ourresults include the proof that the edit-distance over a non-trivialalphabet is not negative definite, which, to the best of ourknowledge, was never stated or proved before.Rational kernels can be combined with SVMs to form efficient andpowerful techniques for a variety of classification tasks in text andspeech processing, or computational biology. We describe examples ofgeneral families of PDS rational kernels that are useful in many ofthese applications and report the result of our experimentsillustrating the use of rational kernels in several difficultlarge-vocabulary spoken-dialog classification tasks based on deployedspoken-dialog systems. Our results show that rational kernels are easyto design and implement and lead to substantial improvements of theclassification accuracy.
多くの分類アルゴリズムは、もともと固定サイズのベクトル用に設計されました。しかし、テキストおよび音声処理や計算生物学における最近のアプリケーションでは、可変長シーケンスや、より一般的には重み付きオートマトンを解析する必要があります。サポートベクターマシン(SVM)などの統計学習技術では、高次元の特徴空間での計算効率が高いことから、カーネル法が広く使用されています。ここでは、重み付きトランスデューサーまたは有理関係に基づくカーネルの一般的なファミリである有理カーネルを紹介します。これは、カーネル法を可変長シーケンスや、より一般的には重み付きオートマトンを解析するように拡張します。重み付きトランスデューサーの一般的な合成アルゴリズムと、一般的な単一ソース最短距離アルゴリズムを使用して、有理カーネルを効率的に計算できることを示します。すべての有理カーネルが正定値対称(PDS)であるわけではありません。つまり、SVMなどの判別分類アルゴリズムのトレーニングの収束を保証する条件であるMercer条件を検証するわけではありません。PDS有理カーネルに関連するいくつかの理論的結果を示します。いくつかの一般的な条件下では、これらのカーネルは和、積、またはクリーネ閉包に対して閉じていることを示し、非冪等半環上で定義された任意のトランスデューサからPDS有理カーネルを構築する一般的な方法を示します。PDS有理カーネルの設計のガイドとして使用できるいくつかの特性評価結果の証明を示します。また、編集距離、ハウスラーの畳み込みカーネル、計算生物学のコンテキストで使用されるいくつかの文字列カーネルなど、一般的に使用される文字列カーネルまたは類似性測定が有理カーネルの特定のインスタンスであることを示します。私たちの結果には、非自明なアルファベット上の編集距離が負定値ではないことの証明が含まれていますが、これは私たちの知る限り、これまで述べられたことも証明されたこともありません。有理カーネルをSVMと組み合わせると、テキストおよび音声処理、または計算生物学におけるさまざまな分類タスクのための効率的で強力な手法を形成できます。これらのアプリケーションの多くで役立つPDS有理カーネルの一般的なファミリーの例を説明し、展開された音声対話システムに基づくいくつかの困難な大語彙音声対話分類タスクでの有理カーネルの使用を示す実験の結果を報告します。結果は、有理カーネルは設計と実装が容易であり、分類精度の大幅な向上につながることを示しています。
On Robustness Properties of Convex Risk Minimization Methods for Pattern Recognition
パターン認識のための凸リスク最小化法のロバスト性について
The paper brings together methods from two disciplines: machine learning theory and robust statistics.We argue that robustness is an important aspect andwe show that many existing machine learning methodsbased on the convex risk minimization principle have- besides other good properties – also the advantage of being robust. Robustness properties of machine learning methods based on convex risk minimization are investigated for the problem of pattern recognition. Assumptions are given for the existence of the influence function of the classifiers and for bounds on the influence function. Kernel logistic regression, support vector machines, least squares and the AdaBoost loss function are treated asspecial cases. Some results on the robustness of such methods are also obtained for the sensitivity curve and the maxbias, which are two other robustness criteria. A sensitivity analysis of the support vector machine is given.
この論文では、機械学習理論とロバスト統計学という2つの分野の手法をまとめています。私たちは、ロバスト性が重要な側面であると主張し、凸リスク最小化の原則に基づく多くの既存の機械学習方法には、他の優れた特性に加えて、ロバストであるという利点もあることを示しています。パターン認識の問題について、凸リスク最小化に基づく機械学習手法のロバスト性について検討します。分類器の影響関数の存在と影響関数の範囲について仮定が与えられます。カーネル ロジスティック回帰、サポート ベクター マシン、最小二乗法、およびAdaBoost損失関数は、特殊なケースとして扱われます。このような方法のロバスト性に関するいくつかの結果は、他の2つのロバスト性基準である感度曲線と最大バイアスについても得られます。サポートベクターマシンの感度分析を行います。
Probability Estimates for Multi-class Classification by Pairwise Coupling
ペアワイズ結合による多クラス分類の確率推定
Pairwise coupling is a popular multi-class classification method that combines all comparisons for each pair of classes. This paper presents two approaches for obtainingclass probabilities. Both methods can be reduced to linear systems andare easy to implement. We show conceptually and experimentally thatthe proposed approaches aremore stable than the two existing popular methods: votingand the method by Hastie and Tibshirani (1998).
ペアワイズ結合は、クラスの各ペアのすべての比較を組み合わせる一般的な多クラス分類方法です。この論文では、クラス確率を取得するための2つのアプローチを紹介します。どちらの方法も線形システムに縮小でき、実装も簡単です。提案されたアプローチは、既存の2つの一般的な方法、投票とHastieとTibshirani(1998)による方法よりも安定していることを概念的および実験的に示します。
Boosting as a Regularized Path to a Maximum Margin Classifier
最大マージン分類器への正則化パスとしてのブースティング
In this paper we study boosting methods from a new perspective. Webuild on recent work by Efron et al. to show that boostingapproximately (and in some cases exactly) minimizes its losscriterion with an l1 constraint on the coefficient vector. Thishelps understand the success of boosting with early stopping asregularized fitting of the loss criterion. For the two mostcommonly used criteria (exponential and binomial log-likelihood),we further show that as the constraint is relaxed—orequivalently as the boosting iterations proceed—the solutionconverges (in the separable case) to an “l1-optimal”separating hyper-plane. We prove that this l1-optimalseparating hyper-plane has the property of maximizing the minimall1-margin of the training data, as defined in the boostingliterature. An interesting fundamental similarity between boostingand kernel support vector machines emerges, as both can bedescribed as methods for regularized optimization inhigh-dimensional predictor space, using a computational trick tomake the calculation practical, and converging tomargin-maximizing solutions. While this statement describes SVMsexactly, it applies to boosting only approximately.
この論文では、ブースティング法を新しい観点から研究します。Efronらによる最近の研究を基に、ブースティングは係数ベクトルにl1制約を課すことで損失基準をほぼ(場合によっては正確に)最小化することを示します。これにより、損失基準の正規化されたフィッティングとして早期停止を行うブースティングの成功を理解するのに役立ちます。最も一般的に使用される2つの基準(指数および二項対数尤度)について、制約が緩和されるにつれて(つまり、ブースティングの反復が進むにつれて)、ソリューションが(分離可能なケースでは)「l1最適」分離超平面に収束することを示します。このl1最適分離超平面は、ブースティングの文献で定義されているように、トレーニング データの最小l1マージンを最大化する特性があることを証明します。ブースティングとカーネル サポート ベクター マシンの間には、興味深い基本的な類似点があります。どちらも、計算を実用的なものにするための計算トリックを使用し、マージンを最大化するソリューションに収束する、高次元の予測子空間での正規化された最適化の方法として説明できます。この記述はSVMを正確に説明していますが、ブースティングには近似的にしか適用されません。
Image Categorization by Learning and Reasoning with Regions
領域を用いた学習と推論によるイメージ分類
Designing computer programs to automatically categorize images using low-level features is a challenging research topic in computer vision. In this paper, we present a new learning technique, which extends Multiple-Instance Learning (MIL), and its application to the problem of region-based image categorization. Images are viewed as bags, each of which contains a number of instances corresponding to regions obtained from image segmentation. The standard MIL problem assumes that a bag is labeled positive if at least one of its instances is positive; otherwise, the bag is negative. In the proposed MIL framework, DD-SVM, a bag label is determined by some number of instances satisfying various properties. DD-SVM first learns a collection of instance prototypes according to a Diverse Density (DD) function. Each instance prototype represents a class of instances that is more likely to appear in bags with the specific label than in the other bags. A nonlinear mapping is then defined using the instance prototypes and maps every bag to a point in a new feature space, named the bag feature space. Finally, standard support vector machines are trained in the bag feature space. We provide experimental results on an image categorization problem and a drug activity prediction problem.
低レベルの特徴を使用して画像を自動的に分類するコンピュータ プログラムを設計することは、コンピュータ ビジョンにおける難しい研究テーマです。この論文では、マルチインスタンス学習(MIL)を拡張した新しい学習手法と、領域ベースの画像分類の問題へのその応用を紹介します。画像はバッグと見なされ、各バッグには、画像セグメンテーションから取得された領域に対応するインスタンスが多数含まれています。標準的なMIL問題では、少なくとも1つのインスタンスが正の場合、バッグは正とラベル付けされ、それ以外の場合はバッグは負とラベル付けされると想定されています。提案されたMILフレームワークであるDD-SVMでは、さまざまなプロパティを満たすインスタンスの数によってバッグ ラベルが決定されます。DD-SVMは、まず、多様性密度(DD)関数に従ってインスタンス プロトタイプのコレクションを学習します。各インスタンス プロトタイプは、特定のラベルの付いたバッグに他のバッグよりも出現する可能性が高いインスタンスのクラスを表します。次に、インスタンス プロトタイプを使用して非線形マッピングが定義され、すべてのバッグがバッグ特徴空間と呼ばれる新しい特徴空間内の点にマッピングされます。最後に、標準的なサポート ベクター マシンがバッグ特徴空間でトレーニングされます。画像分類問題と薬物活性予測問題に関する実験結果を示します。
Some Dichotomy Theorems for Neural Learning Problems
神経学習問題に対するいくつかの二分法定理
The computational complexity of learning from binary examples isinvestigated for linear threshold neurons. We introducecombinatorial measures that create classes of infinitely manylearning problems with sample restrictions. We analyze how thecomplexity of these problems depends on the values for the measures.The results are established as dichotomy theorems showing that eachproblem is either NP-complete or solvable in polynomial time. Inparticular, we consider consistency and maximum consistency problemsfor neurons with binary weights, and maximum consistency problemsfor neurons with arbitrary weights. We determine for each problemclass the dividing line between the NP-complete and polynomial-timesolvable problems. Moreover, all efficiently solvable problems areshown to have constructive algorithms that require no more thanlinear time on a random access machine model. Similar dichotomiesare exhibited for neurons with bounded threshold. The resultsdemonstrate on the one hand that the consideration of sampleconstraints can lead to the discovery of new efficient algorithmsfor non-trivial learning problems. On the other hand, hard learningproblems may remain intractable even for severely restrictedsamples.
線形しきい値ニューロンについて、バイナリ例からの学習の計算複雑性を調査します。サンプル制限のある無限の学習問題のクラスを作成する組み合わせ測定を導入します。これらの問題の複雑さが測定の値にどのように依存するかを分析します。結果は、各問題がNP完全であるか、多項式時間で解決可能であることを示す二分法定理として確立されます。特に、バイナリ重みを持つニューロンの一貫性と最大一貫性の問題、および任意の重みを持つニューロンの最大一貫性の問題を考慮します。各問題クラスについて、NP完全問題と多項式時間で解決可能な問題の境界線を決定します。さらに、効率的に解決可能なすべての問題には、ランダム アクセス マシン モデルで線形時間しか必要としない構成的アルゴリズムがあることが示されています。同様の二分法は、しきい値が制限されたニューロンにも見られます。結果は、一方では、サンプル制約を考慮することで、非自明な学習問題に対する新しい効率的なアルゴリズムを発見できることを示しています。他方では、厳しい制限のあるサンプルであっても、難しい学習問題は解決困難なままである可能性があります。
Feature Selection for Unsupervised Learning
教師なし学習のための機能選択
In this paper, we identify two issues involved in developing an automated feature subset selection algorithm for unlabeled data:the need for finding the number of clusters in conjunction with feature selection, and the need for normalizing the bias of feature selection criteria with respect to dimension. We explore the feature selection problem and these issues through FSSEM(Feature Subset Selection using Expectation-Maximization (EM) clustering) and through two different performance criteria for evaluating candidatefeature subsets: scatter separability and maximum likelihood. We present proofs on the dimensionality biases of these feature criteria, and present a cross-projection normalization scheme that can be applied to any criterion to ameliorate these biases.Our experiments show the need for feature selection, the need for addressingthese two issues, and the effectiveness of our proposed solutions.
この論文では、ラベル付けされていないデータの自動特徴サブセット選択アルゴリズムの開発に関連する2つの問題、つまり、特徴選択と組み合わせたクラスター数を見つける必要性と、次元に関する特徴選択基準のバイアスを正規化する必要性を特定します。特徴選択の問題とこれらの問題を、FSSEM(Feature Subset Selection using Expectation-Maximization (EM) clustering)と、候補特徴サブセットを評価するための2つの異なるパフォーマンス基準(散乱分離可能性と最大尤法)を通じて調査します。これらの特徴基準の次元バイアスに関する証明を提示し、これらのバイアスを改善するための任意の基準に適用できるクロスプロジェクション正規化スキームを提示します。私たちの実験は、機能選択の必要性、これら2つの問題に対処する必要性、および提案されたソリューションの有効性を示しています。
Probability Product Kernels (Special Topic on Learning Theory)
確率積カーネル(学習理論に関する特別トピック)
The advantages of discriminative learning algorithms and kernelmachines are combined with generative modeling using a novel kernelbetween distributions. In the probability product kernel, data pointsin the input space are mapped to distributions over the sample spaceand a general inner product is then evaluated as the integral of theproduct of pairs of distributions. The kernel is straightforward toevaluate for all exponential family models such as multinomials andGaussians and yields interesting nonlinear kernels. Furthermore, thekernel is computable in closed form for latent distributions such asmixture models, hidden Markov models and linear dynamical systems. Forintractable models, such as switching linear dynamical systems,structured mean-field approximations can be brought to bear on thekernel evaluation. For general distributions, even if an analyticexpression for the kernel is not feasible, we show a straightforwardsampling method to evaluate it. Thus, the kernel permitsdiscriminative learning methods, including support vector machines, toexploit the properties, metrics and invariances of the generativemodels we infer from each datum. Experiments are shown usingmultinomial models for text, hidden Markov models for biologicaldata sets and linear dynamical systems for time series data.
判別学習アルゴリズムとカーネルマシンの利点は、分布間の新しいカーネルを使用した生成モデリングと組み合わされています。確率積カーネルでは、入力空間のデータポイントがサンプル空間上の分布にマッピングされ、次に分布のペアの積の積分として一般的な内積が評価されます。カーネルは、多項式やガウス分布などのすべての指数族モデルに対して簡単に評価でき、興味深い非線形カーネルを生成します。さらに、カーネルは、混合モデル、隠れマルコフモデル、線形動的システムなどの潜在分布に対して閉じた形式で計算できます。スイッチング線形動的システムなどの扱いにくいモデルの場合、構造化平均場近似をカーネル評価に適用できます。一般的な分布の場合、カーネルの解析式が実行可能でなくても、それを評価するための簡単なサンプリング方法を示します。したがって、カーネルは、サポートベクターマシンを含む識別学習法が、各データから推測する生成モデルの特性、メトリック、および不変性を活用できるようにします。実験は、テキストの多項式モデル、生物学的データセットの隠れマルコフモデル、および時系列データの線形動的システムを使用して示されます。
Feature Discovery in Non-Metric Pairwise Data
非メトリックペアワイズデータでの特徴発見
Pairwise proximity data, given as similarity or dissimilarity matrix, can violate metricity. This occurs either due tonoise, fallible estimates, or due to intrinsic non-metric featuressuch as they arise from human judgments. So far the problem of non-metric pairwise data has been tackled by essentially omitting the negative eigenvalues or shifting the spectrum of the associated (pseudo-)covariance matrix for a subsequent embedding. However, little attention has been paid to the negative part of the spectrum itself. In particular no answer was given to whether the directions associated to the negative eigenvalues would at all code variance other than noise related. We show by a simple, exploratory analysis that the negative eigenvalues can code forrelevant structure in the data, thus leading to the discovery of newfeatures, which were lost by conventional data analysis techniques.The information hidden in the negative eigenvalue part of thespectrum is illustrated and discussed for three data sets, namely USPShandwritten digits, text-mining and data from cognitive psychology.
類似度または非類似度マトリックスとして与えられたペアワイズ近接データは、メトリック性を侵害する可能性があります。これは、ノイズ、誤りのある推定値、または人間の判断から生じるような固有の非メトリック機能が原因で発生します。これまで、非計量ペアワイズ データの問題は、基本的に負の固有値を省略するか、後続の埋め込みのために関連する(疑似)共分散行列のスペクトルをシフトすることによって対処されてきました。しかし、スペクトル自体の負の部分にはほとんど注意が払われてきませんでした。特に、負の固有値に関連付けられた方向が、ノイズ関連以外の分散をコード化するかどうかについては、答えが与えられていませんでした。私たちは、単純な探索的分析によって、負の固有値がデータ内の関連構造をコード化できることを示し、それによって従来のデータ分析手法では見落とされていた新しい特徴の発見につながります。スペクトルの負の固有値部分に隠された情報は、USPS手書き数字、テキストマイニング、認知心理学のデータという3つのデータ セットについて図示され、説明されています。
A Fast Algorithm for Joint Diagonalization with Non-orthogonal Transformations and its Application to Blind Source Separation
非直交変換によるジョイント対角化のための高速アルゴリズムとブラインドソース分離への応用
A new efficient algorithm is presented for joint diagonalization of several matrices. The algorithm is based on the Frobenius-normformulation of the joint diagonalization problem, and addressesdiagonalization with a general, non-orthogonal transformation. Theiterative scheme of the algorithm is based on a multiplicativeupdate which ensures the invertibility of the diagonalizer. Thealgorithm’s efficiency stems from the special approximation of thecost function resulting in a sparse, block-diagonal Hessian to beused in the computation of the quasi-Newton update step. Extensivenumerical simulations illustrate the performance of the algorithmand provide a comparison to other leading diagonalization methods.The results of such comparison demonstrate that the proposedalgorithm is a viable alternative to existing state-of-the-art jointdiagonalization algorithms. The practical use of our algorithm isshown for blind source separation problems.
いくつかの行列の結合対角化のための新しい効率的なアルゴリズムが提示されます。このアルゴリズムは、同時対角化問題のフロベニウスノルム定式化に基づいており、一般的な非直交変換で対角化に対処します。アルゴリズムの反復スキームは、対角器の可逆性を保証する乗算更新に基づいています。このアルゴリズムの効率は、コスト関数の特殊な近似により、準ニュートン更新ステップの計算に使用されるスパースなブロック対角ヘッセ分布が得られることに起因します。広範な数値シミュレーションは、アルゴリズムのパフォーマンスを示し、他の主要な対角化手法との比較を提供します。このような比較の結果は、提案されたアルゴリズムが既存の最先端の関節対角化アルゴリズムの実行可能な代替手段であることを示しています。私たちのアルゴリズムの実用化は、ブラインドソース分離問題で示されています。
Bias-Variance Analysis of Support Vector Machines for the Development of SVM-Based Ensemble Methods
SVMベースアンサンブル法の開発のためのサポートベクターマシンのバイアス分散分析
Bias-variance analysis provides a tool to study learning algorithms and can be used to properly design ensemble methods well tuned to the properties of a specific base learner. Indeed the effectiveness of ensemble methods critically depends on accuracy, diversity and learning characteristics of base learners. We present an extended experimental analysis of bias-variance decomposition of the error in Support Vector Machines (SVMs), considering Gaussian, polynomial and dot product kernels. A characterization of the error decomposition is provided, by means of the analysis of the relationships between bias, variance, kernel type and its parameters, offering insights into the way SVMs learn. The results show that the expected trade-off between bias and variance is sometimes observed, but more complex relationships can be detected, especially in Gaussian and polynomial kernels. We show that the bias-variance decomposition offers a rationale to develop ensemble methods using SVMs as base learners, and we outline two directions for developing SVM ensembles, exploiting the SVM bias characteristics and the bias-variance dependence on the kernel parameters.
バイアス分散分析は、学習アルゴリズムを研究するためのツールを提供し、特定のベース学習器の特性に合わせて適切に調整されたアンサンブル メソッドを適切に設計するために使用できます。実際、アンサンブル メソッドの有効性は、ベース学習器の精度、多様性、および学習特性に大きく依存します。私たちは、ガウス、多項式、およびドット積カーネルを考慮した、サポート ベクター マシン(SVM)のエラーのバイアス分散分解の拡張された実験分析を示します。バイアス、分散、カーネル タイプとそのパラメーターの関係を分析することによって、エラー分解の特性が示され、SVMの学習方法に関する洞察が提供されます。結果は、バイアスと分散の間に予想されるトレードオフが時々観察されるが、特にガウス カーネルと多項式カーネルではより複雑な関係が検出される可能性があることを示しています。バイアス分散分解は、SVMを基本学習者として使用するアンサンブル メソッドを開発する根拠となることを示し、SVMバイアス特性とカーネル パラメーターに対するバイアス分散の依存性を利用して、SVMアンサンブルを開発するための2つの方向性を概説します。
Hierarchical Latent Class Models for Cluster Analysis
クラスタ分析のための階層的潜在クラスモデル
Latent class models are used for cluster analysis of categorical data. Underlying such a model is the assumptionthat the observed variables are mutually independent given the class variable.A serious problem with the use of latent classmodels, known as local dependence, is that this assumption is oftenuntrue. In this paper we propose hierarchicallatent class models as a framework where the local dependenceproblem can be addressed in a principled manner.We develop a search-based algorithm forlearning hierarchical latent class models from data.The algorithm is evaluated using both synthetic and real-world data.
潜在クラスモデルは、カテゴリデータのクラスター分析に使用されます。このようなモデルの根底にあるのは、クラス変数が与えられた場合、観測された変数は相互に独立しているという仮定です。潜在クラスモデルの使用に関する深刻な問題(局所依存性)は、この仮定がしばしば真実ではないということです。この論文では、局所依存性の問題を原則的に解決できるフレームワークとして、階層的クラスモデルを提案します。データから階層的な潜在クラスモデルを学習するための探索型アルゴリズムを開発します。このアルゴリズムは、合成データと実世界のデータの両方を使用して評価されます。
Distance-Based Classification with Lipschitz Functions (Special Topic on Learning Theory)
リプシッツ関数による距離ベースの分類(学習理論に関する特別トピック)
The goal of this article is to develop a framework for large margin classification in metric spaces. We want to find a generalization of linear decision functions for metric spaces and define a corresponding notion of margin such that the decision function separates the training points with a large margin. It will turn out that using Lipschitz functions as decision functions, the inverse of the Lipschitz constant can be interpreted as the size of a margin. In order to construct a clean mathematical setup we isometrically embed the given metric space into a Banach space and the space of Lipschitz functions into its dual space. To analyze the resulting algorithm, we prove several representer theorems. They state that there always exist solutions of the Lipschitz classifier which can be expressed in terms of distance functions to training points. We provide generalization bounds for Lipschitz classifiers in terms of the Rademacher complexities of some Lipschitz function classes. The generality of our approach can be seen from the fact that several well-known algorithms are special cases of the Lipschitz classifier, among them the support vector machine, the linear programming machine, and the 1-nearest neighbor classifier.
この記事の目的は、メトリック空間で大きなマージンを分類するためのフレームワークを開発することです。メトリック空間の線形決定関数の一般化を見つけ、決定関数がトレーニング ポイントを大きなマージンで分離するように、対応するマージンの概念を定義します。リプシッツ関数を決定関数として使用すると、リプシッツ定数の逆数をマージンのサイズとして解釈できることがわかります。明確な数学的設定を構築するために、指定されたメトリック空間をバナッハ空間に等尺的に埋め込み、リプシッツ関数の空間をそのデュアル空間に埋め込みます。結果として得られるアルゴリズムを分析するために、いくつかの表現定理を証明します。彼らは、トレーニング ポイントまでの距離関数で表現できるLipschitz分類器の解が常に存在すると述べています。私たちは、いくつかのLipschitz関数クラスのRademacher複雑度の観点からLipschitz分類器の一般化境界を提供します。私たちのアプローチの一般性は、サポート ベクター マシン、線形計画マシン、および1近傍分類器など、いくつかのよく知られているアルゴリズムがLipschitz分類器の特殊なケースであるという事実からわかります。
Preference Elicitation and Query Learning (Special Topic on Learning Theory)
選好誘発とクエリ学習(学習理論に関する特別トピック)
In this paper we explore the relationship between “preference elicitation”, a learning-style problem that arises in combinatorial auctions, and the problem of learning via queries studied in computational learning theory. Preference elicitation is the process of asking questions about the preferences of bidders so as to best divide some set of goods. As a learning problem, it can be thought of as a setting in which there are multiple target concepts that can each be queried separately, but where the goal is not so much to learn each concept as it is to produce an “optimal example”. In this work, we prove a number of similarities and differences between two-bidder preference elicitation and query learning, giving both separation results and proving some connections between these problems.
この論文では、組み合わせオークションで発生する学習型の問題である「選好誘発」と、計算学習理論で研究されたクエリによる学習問題との関係を探ります。選好誘発とは、一部の商品のセットを最適に分割するために、入札者の選好について質問するプロセスです。学習問題としては、複数のターゲット概念があり、それぞれを個別にクエリできる設定と考えることができますが、各概念を学習することよりも「最適な例」を作成することが目標です。この研究では、2ビッダー選好の誘発とクエリ学習の間の多くの類似点と相違点を証明し、分離結果とこれらの問題間のいくつかの関連性を証明します。
The Sample Complexity of Exploration in the Multi-Armed Bandit Problem (Special Topic on Learning Theory)
多腕バンディット問題における探索のサンプル複雑性(学習理論に関する特別トピック)
We consider the multi-armed bandit problem under the PAC (“probably approximately correct”) model. It was shown by Even-Dar et al. (2002) that given n arms, a total of O((n/ε2)log(1/δ)) trials suffices in order to find an ε-optimal arm with probability at least 1-δ. We establish a matching lower bound on the expected number of trials under any sampling policy. We furthermore generalize the lower bound, and show an explicit dependence on the (unknown) statistics of the arms. We also provide a similar bound within a Bayesian setting. The case where the statistics of the arms are known but the identities of the arms are not, is also discussed. For this case, we provide a lower bound of Θ((1/ε2)(n+log(1/δ))) on the expected number of trials, as well as a sampling policy with a matching upper bound. If instead of the expected number of trials, we consider the maximum (over all sample paths) number of trials, we establish a matching upper and lower bound of the form Θ((n/ε2)log(1/δ)). Finally, we derive lower bounds on the expected regret, in the spirit of Lai and Robbins.
私たちは、PAC (「おそらくほぼ正しい」)モデルのもとで、多腕バンディット問題を考察します。Even-Darら(2002)は、n本のアームが与えられた場合、少なくとも1-δ の確率で ε 最適アームを見つけるには、合計O((n/ε2)log(1/δ))回の試行で十分であることを示しています。任意のサンプリング ポリシーのもとで、期待される試行回数に一致する下限を確立します。さらに、下限を一般化し、アームの(未知の)統計値への明示的な依存性を示します。ベイズ設定内でも同様の上限も示します。アームの統計値はわかっているが、アームのIDがわからない場合についても説明します。この場合は、期待される試行回数に Θ((1/ε2)(n+log(1/δ)))の下限と、一致する上限を持つサンプリング ポリシーを示します。予想される試行回数の代わりに、最大試行回数（すべてのサンプルパスにわたって）を考慮すると、Θ((n/ε2)log(1/δ))の形式で一致する上限と下限が確立されます。最後に、LaiとRobbinsの精神に則り、予想される後悔の下限を導出します。
New Techniques for Disambiguation in Natural Language and Their Application to Biological Text
自然言語における曖昧性解消のための新技術とその生物学的テキストへの応用
We study the problems of disambiguation in natural language, focusing on the problem of gene vs. protein name disambiguation in biological text and also considering the problem of context-sensitive spelling error correction. We introduce a new family of classifiers based on ordering and weighting the feature vectors obtained from word counts and word co-occurrence in the text, and inspect several concrete classifiers from this family. We obtain the most accurate prediction when weighting by positions of the words in the context. On the gene/protein name disambiguation problem, this classifier outperforms both the Naive Bayes and SNoW baseline classifiers. We also study the effect of the smoothing techniques with the Naive Bayes classifier, the collocation features, and the context length on the classification accuracy and show that correct setting of the context length is important and also problem-dependent.
私たちは、生物学的テキストにおける遺伝子名とタンパク質名の曖昧さ回避の問題に焦点を当て、文脈依存のスペルミス修正の問題も考慮して、自然言語における曖昧さ回避の問題を研究しています。テキスト内の単語数と単語の共起から得られる特徴ベクトルの順序付けと重み付けに基づく新しい分類子ファミリを導入し、このファミリからいくつかの具体的な分類子を検査します。コンテキスト内の単語の位置で重み付けすると、最も正確な予測が得られます。遺伝子/タンパク質名の曖昧さ解消問題では、この分類器はナイーブベイズとSNoWの両方のベースライン分類器よりも優れています。また、単純ベイズ分類器を使用した平滑化手法、コロケーション機能、およびコンテキスト長が分類精度に及ぼす影響についても研究し、コンテキスト長の正しい設定が重要であり、問題にも依存することを示します。
A Universal Well-Calibrated Algorithm for On-line Classification (Special Topic on Learning Theory)
オンライン分類のためのユニバーサルで十分に較正されたアルゴリズム (学習理論に関する特別トピック)
We study the problem of on-line classification in which the prediction algorithm, for each “significance level” δ, is required to output as its prediction a range of labels (intuitively, those labels deemed compatible with the available data at the level δ) rather than just one label; as usual, the examples are assumed to be generated independently from the same probability distribution P. The prediction algorithm is said to be “well-calibrated” for P and δ if the long-run relative frequency of errors does not exceed δ almost surely w.r. to P. For well-calibrated algorithms we take the number of “uncertain” predictions (i.e., those containing more than one label) as the principal measure of predictive performance. The main result of this paper is the construction of a prediction algorithm which, for any (unknown) P and any δ: (a) makes errors independently and with probability δ at every trial (in particular, is well-calibrated for P and δ); (b) makes in the long run no more uncertain predictions than any other prediction algorithm that is well-calibrated for P and δ; (c) processes example n in time O(log n).
私たちは、オンライン分類の問題を調査します。この問題では、予測アルゴリズムは、各「有意水準」δ に対して、予測として1つのラベルだけでなく、一連のラベル(直感的には、レベル δ で利用可能なデータと互換性があると見なされるラベル)を出力する必要があります。通常どおり、例は同じ確率分布Pから独立して生成されるものと想定されます。予測アルゴリズムは、Pと δ に対して「適切に調整されている」と言われます。これは、長期的なエラーの相対頻度がほぼ確実に δ を超えない場合です。Pに。適切に調整されたアルゴリズムの場合、予測パフォーマンスの主な尺度として「不確実な」予測(つまり、複数のラベルを含む予測)の数を使用します。この論文の主な結果は、任意の(未知の) Pと任意の δ に対して、(a)試行ごとに独立して確率 δ でエラーを起こす(特に、Pと δ に対して適切に調整されている)、(b)長期的にはPと δ に対して適切に調整された他のどの予測アルゴリズムよりも不確実な予測を行わない、(c)例nを時間O(log n)で処理する予測アルゴリズムの構築です。
Exact Bayesian Structure Discovery in Bayesian Networks
ベイジアンネットワークにおける正確なベイジアン構造の発見
Learning a Bayesian network structure from data is a well-motivated but computationally hard task. We present an algorithm that computes the exact posterior probability of a subnetwork, e.g., a directed edge; a modified version of the algorithm finds one of the most probable network structures. This algorithm runs in time O(n 2n + nk+1C(m)), where n is the number of network variables, k is a constant maximum in-degree, and C(m) is the cost of computing a single local marginal conditional likelihood for m data instances. This is the first algorithm with less than super-exponential complexity with respect to n. Exact computation allows us to tackle complex cases where existing Monte Carlo methods and local search procedures potentially fail. We show that also in domains with a large number of variables, exact computation is feasible, given suitable a priori restrictions on the structures; combining exact and inexact methods is also possible. We demonstrate the applicability of the presented algorithm on four synthetic data sets with 17, 22, 37, and 100 variables.
データからベイジアン ネットワーク構造を学習することは、十分に意図されていますが、計算上困難なタスクです。サブネットワーク(有向エッジなど)の正確な事後確率を計算するアルゴリズムを紹介します。アルゴリズムの修正バージョンでは、最も可能性の高いネットワーク構造の1つを見つけます。このアルゴリズムは、O(n 2n + nk+1C(m))の時間で実行されます。ここで、nはネットワーク変数の数、kは定数の最大入次数、C(m)はm個のデータ インスタンスの単一のローカル周辺条件付き尤度を計算するコストです。これは、nに関して超指数的複雑度未満の最初のアルゴリズムです。正確な計算により、既存のモンテ カルロ法やローカル検索手順が失敗する可能性のある複雑なケースに取り組むことができます。多数の変数を持つドメインでも、構造に適切な事前制約があれば正確な計算が実行可能であることを示します。正確な方法と不正確な方法を組み合わせることもできます。17、22、37、および100の変数を持つ4つの合成データ セットで、提示されたアルゴリズムの適用可能性を示します。
Computable Shell Decomposition Bounds
計算可能シェル分解境界
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase transitions. Here we use a variant of their ideas to derive an upper bound on the generalization error of a hypothesis computable from its training error and the histogram of training errors for the hypotheses in the class. In most cases this new bound is significantly tighter than traditional bounds computed from the training error and the cardinality of the class. Our results can also be viewed as providing a rigorous foundation for a model selection algorithm proposed by Scheffer and Joachims.
Haussler、Kearns、Seung、Tishbyは、位相遷移などの学習曲線における特定の経験的現象を理解する手段として、結合結合のシェル分解の概念を導入しました。ここでは、彼らのアイデアの変形を使用して、その学習誤差とクラス内の仮説の訓練誤差のヒストグラムから計算可能な仮説の一般化誤差の上限を導き出します。ほとんどの場合、この新しい境界は、学習誤差とクラスのカーディナリティから計算される従来の境界よりも大幅に狭くなります。私たちの結果は、SchefferとJoachimsによって提案されたモデル選択アルゴリズムの厳密な基盤を提供すると見なすこともできます。
Sources of Success for Boosted Wrapper Induction
ブーストラッパーインダクションの成功の源泉
In this paper, we examine an important recent rule-based information extraction (IE) technique named Boosted Wrapper Induction (BWI) by conducting experiments on a wider variety of tasks than previously studied, including tasks using several collections of natural text documents. We investigate systematically how each algorithmic component of BWI, in particular boosting, contributes to its success. We show that the benefit of boosting arises from the ability to reweight examples to learn specific rules (resulting in high precision) combined with the ability to continue learning rules after all positive examples have been covered (resulting in high recall). As a quantitative indicator of the regularity of an extraction task, we propose a new measure that we call the SWI ratio. We show that this measure is a good predictor of IE success and a useful tool for analyzing IE tasks. Based on these results, we analyze the strengths and limitations of BWI. Specifically, we explain limitations in the information made available, and in the representations used. We also investigate the consequences of the fact that confidence values returned during extraction are not true probabilities. Next, we investigate the benefits of including grammatical and semantic information for natural text documents, as well as parse tree and attribute-value information for XML and HTML documents. We show experimentally that incorporating even limited grammatical information can increase the regularity of natural text extraction tasks, resulting in improved performance. We conclude with proposals for enriching the representational power of BWI and other IE methods to exploit these and other types of regularities. [abs][pdf][ps.gz][ps
この論文では、Boosted Wrapper Induction (BWI)と呼ばれる最近の重要なルールベースの情報抽出(IE)手法について、これまで研究されたよりも幅広いタスク(複数の自然テキスト ドキュメント コレクションを使用するタスクを含む)で実験を行い、検証します。BWIの各アルゴリズム コンポーネント、特にブースティングが、その成功にどのように貢献しているかを体系的に調査します。ブースティングの利点は、特定のルールを学習するために例を再重み付けする機能(高い精度をもたらす)と、すべての正の例をカバーした後もルールの学習を継続する機能(高い再現率をもたらす)の組み合わせから生じることを示します。抽出タスクの規則性の定量的指標として、SWI比と呼ぶ新しい尺度を提案します。この尺度はIEの成功の優れた予測子であり、IEタスクを分析するための便利なツールであることを示します。これらの結果に基づいて、BWIの長所と限界を分析します。具体的には、利用可能な情報と使用される表現の限界について説明します。また、抽出中に返される信頼度値が真の確率ではないという事実の結果も調査します。次に、自然テキスト ドキュメントの文法および意味情報、およびXMLおよびHTMLドキュメントの解析ツリーと属性値情報を含めることの利点を調査します。限られた文法情報を組み込むだけでも、自然テキスト抽出タスクの規則性が向上し、パフォーマンスが向上することを実験的に示します。最後に、これらの規則性やその他の規則性を活用するために、BWIおよびその他のIE手法の表現力を強化するための提案を示します。[abs][pdf][ps.gz][ps
PAC-learnability of Probabilistic Deterministic Finite State Automata
確率的決定論的有限状態オートマトンのPAC学習可能性
We study the learnability of Probabilistic Deterministic Finite State Automata under a modified PAC-learning criterion. We argue that it is necessary to add additional parameters to the sample complexity polynomial, namely a bound on the expected length of strings generated from any state, and a bound on the distinguishability between states. With this, we demonstrate that the class of PDFAs is PAC-learnable using a variant of a standard state-merging algorithm and the Kullback-Leibler divergence as error function. [abs][pdf][ps.gz][ps
私たちは、確率的決定論的有限状態オートマトンの学習可能性を、修正されたPAC学習基準の下で研究します。サンプル複雑度多項式に追加のパラメータ、つまり、任意の状態から生成される文字列の予想される長さの境界と、状態間の識別可能性の境界を追加する必要があると主張します。これにより、PDFAのクラスが、標準状態マージアルゴリズムの変形とエラー関数としてのKullback-Leibler発散を使用してPAC学習可能であることを実証します。[ABS][PDFファイル][ps.gz][追伸
Robust Principal Component Analysis with Adaptive Selection for Tuning Parameters
調整パラメーターの適応選択によるロバストな主成分分析
The present paper discusses robustness against outliers in a principal component analysis (PCA). We propose a class of procedures for PCA based on the minimum psi principle, which unifies various approaches, including the classical procedure and recently proposed procedures. The reweighted matrix algorithm for off-line data and the gradient algorithm for on-line data are both investigated with respect to robustness. The reweighted matrix algorithm is shown to satisfy a desirable property with local convergence, and the on-line gradient algorithm is shown to satisfy an asymptotical stability of convergence. Some procedures in the class involve tuning parameters, which control sensitivity to outliers. We propose a shape-adaptive selection rule for tuning parameters using K-fold cross validation. [abs][pdf][ps.gz][ps
この論文では、主成分分析(PCA)における外れ値に対するロバスト性について論じる。私たちは、古典的な手順と最近提案された手順を含むさまざまなアプローチを統合する最小psiの原則に基づくPCAの手順のクラスを提案します。オフラインデータの再加重行列アルゴリズムとオンラインデータ用の勾配アルゴリズムは、どちらもロバスト性に関して調査されます。再重み付けされた行列アルゴリズムは、局所的な収束を伴う望ましい特性を満たすことが示され、オンライン勾配アルゴリズムは収束の漸近的安定性を満たすことが示されています。クラス内の一部のプロシージャには、外れ値に対する感度を制御するチューニング パラメーターが含まれます。Kフォールド交差検証を使用してパラメーターを調整するための形状適応選択ルールを提案します。
Learning Ensembles from Bites: A Scalable and Accurate Approach
Bitesからアンサンブルを学ぶ:スケーラブルで正確なアプローチ
Bagging and boosting are two popular ensemble methods that typically achieve better accuracy than a single classifier. These techniques have limitations on massive data sets, because the size of the data set can be a bottleneck. Voting many classifiers built on small subsets of data (“pasting small votes”) is a promising approach for learning from massive data sets, one that can utilize the power of boosting and bagging. We propose a framework for building hundreds or thousands of such classifiers on small subsets of data in a distributed environment. Experiments show this approach is fast, accurate, and scalable.
バギングとブースティングは、通常、単一の分類器よりも優れた精度を達成する2つの一般的なアンサンブル手法です。これらの手法では、データ セットのサイズがボトルネックになる可能性があるため、大規模なデータ セットには制限があります。データの小さなサブセットに基づいて構築された多くの分類子に投票する(“小さな票を貼り付ける”)ことは、大量のデータ セットから学習するための有望なアプローチであり、ブースティングとバギングの力を利用できるアプローチです。分散環境の小さなデータのサブセットに対して、数百または数千のそのような分類子を構築するためのフレームワークを提案します。実験によると、このアプローチは高速、正確、スケーラブルであることが示されています。
Distributional Scaling: An Algorithm for Structure-Preserving Embedding of Metric and Nonmetric Spaces
Distributional Scaling:計量空間と非計量空間の構造保存埋め込みのためのアルゴリズム
We present a novel approach for embedding general metric and nonmetric spaces into low-dimensional Euclidean spaces. As opposed to traditional multidimensional scaling techniques, which minimize the distortion of pairwise distances, our embedding algorithm seeks a low-dimensional representation of the data that preserves the structure (geometry) of the original data. The algorithm uses a hybrid criterion function that combines the pairwise distortion with what we call the geometric distortion. To assess the geometric distortion, we explore functions that reflect geometric properties. Our approach is different from the Isomap and LLE algorithms in that the discrepancy in distributional information is used to guide the embedding. We use clustering algorithms in conjunction with our embedding algorithm to direct the embedding process and improve its convergence properties. We test our method on metric and nonmetric data sets, and in the presence of noise. We demonstrate that our method preserves the structural properties of embedded data better than traditional MDS, and that its performance is robust with respect to clustering errors in the original data. Other results of the paper include accelerated algorithms for optimizing the standard MDS objective functions, and two methods for finding the most appropriate dimension in which to embed a given set of data.
私たちは、一般的な計量空間と非計量空間を低次元ユークリッド空間に埋め込むための新しいアプローチを提示します。ペアワイズ距離の歪みを最小化する従来の多次元尺度法とは対照的に、我々の埋め込みアルゴリズムは、元のデータの構造(形状)を保持するデータの低次元表現を求めます。このアルゴリズムは、ペアワイズ歪みと我々が幾何学的歪みと呼ぶものを組み合わせたハイブリッド基準関数を使用します。幾何学的歪みを評価するために、我々は幾何学的特性を反映する関数を探ります。我々のアプローチは、分布情報の不一致が埋め込みを導くために使用されるという点で、IsomapアルゴリズムやLLEアルゴリズムとは異なります。私たちは、埋め込みプロセスを指示し、その収束特性を改善するために、クラスタリング アルゴリズムを埋め込みアルゴリズムと組み合わせて使用します。私たちは、我々の方法を、計量データ セットと非計量データ セット、およびノイズの存在下でテストします。私たちは、我々の方法が従来のMDSよりも埋め込まれたデータの構造特性をより適切に保持し、そのパフォーマンスが元のデータのクラスタリング エラーに関して堅牢であることを示します。この論文のその他の結果には、標準のMDS目的関数を最適化するための高速アルゴリズムと、特定のデータセットを埋め込む最も適切な次元を見つけるための2つの方法が含まれています。
RCV1: A New Benchmark Collection for Text Categorization Research
RCV1: テキスト分類研究のための新しいベンチマークコレクション
Reuters Corpus Volume I (RCV1) is an archive of over 800,000 manually categorized newswire stories recently made available by Reuters, Ltd. for research purposes. Use of this data for research on text categorization requires a detailed understanding of the real world constraints under which the data was produced. Drawing on interviews with Reuters personnel and access to Reuters documentation, we describe the coding policy and quality control procedures used in producing the RCV1 data, the intended semantics of the hierarchical category taxonomies, and the corrections necessary to remove errorful data. We refer to the original data as RCV1-v1, and the corrected data as RCV1-v2. We benchmark several widely used supervised learning methods on RCV1-v2, illustrating the collection’s properties, suggesting new directions for research, and providing baseline results for future studies. We make available detailed, per-category experimental results, as well as corrected versions of the category assignments and taxonomy structures, via online appendices. [abs][pdf][ps.gz][ps][appendices
ロイター コーパス第1巻(RCV1)は、ロイター社が研究目的で最近公開した、手動で分類された80万件以上のニュースワイヤー記事のアーカイブです。テキスト分類の研究にこのデータを使用するには、データが作成された現実世界の制約を詳細に理解する必要があります。ロイターの担当者へのインタビューとロイターのドキュメントへのアクセスを利用して、RCV1データの作成に使用されたコーディング ポリシーと品質管理手順、階層カテゴリ分類の意図された意味、およびエラーのあるデータを削除するために必要な修正について説明します。元のデータをRCV1-v1、修正されたデータをRCV1-v2と呼びます。RCV1-v2で広く使用されているいくつかの教師あり学習方法をベンチマークし、コレクションの特性を示し、研究の新しい方向性を提案し、将来の研究のベースライン結果を提供します。詳細なカテゴリごとの実験結果、およびカテゴリの割り当てと分類構造の修正バージョンをオンライン付録で提供します。[abs][pdf][ps.gz][ps][付録
A Geometric Approach to Multi-Criterion Reinforcement Learning
多基準強化学習への幾何学的アプローチ
We consider the problem of reinforcement learning in a controlled Markov environment with multiple objective functions of the long-term average reward type. The environment is initially unknown, and furthermore may be affected by the actions of other agents, actions that are observed but cannot be predicted beforehand. We capture this situation using a stochastic game model, where the learning agent is facing an adversary whose policy is arbitrary and unknown, and where the reward function is vector-valued. State recurrence conditions are imposed throughout. In our basic problem formulation, a desired target set is specified in the vector reward space, and the objective of the learning agent is to approach the target set, in the sense that the long-term average reward vector will belong to this set. We devise appropriate learning algorithms, that essentially use multiple reinforcement learning algorithms for the standard scalar reward problem, which are combined using the geometric insight from the theory of approachability for vector-valued stochastic games. We then address the more general and optimization-related problem, where a nested class of possible target sets is prescribed, and the goal of the learning agent is to approach the smallest possible target set (which will generally depend on the unknown system parameters). A particular case which falls into this framework is that of stochastic games with average reward constraints, and further specialization provides a reinforcement learning algorithm for constrained Markov decision processes. Some basic examples are provided to illustrate these results. [abs][pdf][ps.gz][ps
私たちは、長期平均報酬型の複数の目的関数を持つ制御されたマルコフ環境における強化学習の問題を考察します。環境は最初は未知であり、さらに他のエージェントの行動、観察はされるが事前に予測できない行動の影響を受ける可能性があります。我々はこの状況を確率ゲーム モデルを使用して捉える。このモデルでは、学習エージェントは、そのポリシーが任意で未知であり、報酬関数がベクトル値である敵に直面しています。状態再帰条件は全体にわたって課されます。我々の基本的な問題定式化では、望ましいターゲット セットがベクトル報酬空間で指定され、学習エージェントの目的は、長期平均報酬ベクトルがこのセットに属するという意味で、ターゲット セットに近づくことです。私たちは、標準的なスカラー報酬問題に対して本質的に複数の強化学習アルゴリズムを使用する適切な学習アルゴリズムを考案し、ベクトル値確率ゲームの接近可能性の理論からの幾何学的洞察を使用してこれらを組み合わせる。次に、より一般的で最適化に関連した問題に取り組みます。この問題では、可能なターゲット セットのネストされたクラスが規定され、学習エージェントの目標は、可能な限り小さなターゲット セット(一般に、未知のシステム パラメータに依存します)に近づくことです。このフレームワークに該当する特定のケースは、平均報酬制約のある確率ゲームであり、さらに特化することで、制約付きマルコフ決定プロセス用の強化学習アルゴリズムが提供されます。これらの結果を説明するために、いくつかの基本的な例が提供されています。[abs][pdf][ps.gz][ps
A Compression Approach to Support Vector Model Selection
ベクトルモデルの選択をサポートするための圧縮アプローチ
In this paper we investigate connections between statistical learning theory and data compression on the basis of support vector machine (SVM) model selection. Inspired by several generalization bounds we construct “compression coefficients” for SVMs which measure the amount by which the training labels can be compressed by a code built from the separating hyperplane. The main idea is to relate the coding precision to geometrical concepts such as the width of the margin or the shape of the data in the feature space. The so derived compression coefficients combine well known quantities such as the radius-margin term R2/ρ2, the eigenvalues of the kernel matrix, and the number of support vectors. To test whether they are useful in practice we ran model selection experiments on benchmark data sets. As a result we found that compression coefficients can fairly accurately predict the parameters for which the test error is minimized. [abs][pdf][ps.gz][ps
この論文では、サポートベクターマシン(SVM)モデルの選択に基づいて、統計的学習理論とデータ圧縮の関係を調査します。いくつかの一般化境界に触発されて、分離超平面から構築されたコードによってトレーニングラベルを圧縮できる量を測定するSVMの「圧縮係数」を構築します。主な考え方は、コーディング精度を、マージンの幅や特徴空間内のデータの形状などの幾何学的概念に関連付けることです。そのように導出された圧縮係数は、半径-マージン項R2/ρ2、カーネル行列の固有値、サポート ベクトルの数など、よく知られている量を組み合わせたものです。それらが実際に有用かどうかをテストするために、ベンチマークデータセットでモデル選択実験を実行しました。その結果、圧縮係数は、テストエラーが最小化されるパラメータをかなり正確に予測できることがわかりました。[ABS][PDFファイル][ps.gz][追伸
Online Choice of Active Learning Algorithms
アクティブラーニングアルゴリズムのオンライン選択
This work is concerned with the question of how to combine online an ensemble of active learners so as to expedite the learning progress in pool-based active learning. We develop an active-learning master algorithm, based on a known competitive algorithm for the multi-armed bandit problem. A major challenge in successfully choosing top performing active learners online is to reliably estimate their progress during the learning session. To this end we propose a simple maximum entropy criterion that provides effective estimates in realistic settings. We study the performance of the proposed master algorithm using an ensemble containing two of the best known active-learning algorithms as well as a new algorithm. The resulting active-learning master algorithm is empirically shown to consistently perform almost as well as and sometimes outperform the best algorithm in the ensemble on a range of classification problems. [abs][pdf][ps.gz][ps
この研究では、プールベースのアクティブラーニングの学習進行を促進するために、アクティブ学習者のアンサンブルをオンラインでどのように組み合わせるかという問題に関係しています。私たちは、マルチアームバンディット問題に対する既知の競合アルゴリズムに基づいて、アクティブラーニングマスターアルゴリズムを開発します。オンラインでトップパフォーマンスのアクティブ学習者をうまく選択するための大きな課題は、学習セッション中の彼らの進歩を確実に推定することです。この目的のために、現実的な設定で効果的な推定を提供する単純な最大エントロピー基準を提案します。提案されたマスターアルゴリズムの性能を、最もよく知られているアクティブラーニングアルゴリズムの2つと新しいアルゴリズムを含むアンサンブルを使用して研究します。結果として得られるアクティブラーニングマスターアルゴリズムは、さまざまな分類問題でアンサンブル内の最良のアルゴリズムとほぼ同等に一貫して実行し、場合によってはそれを上回るパフォーマンスを発揮することが経験的に示されています。[ABS][PDFファイル][ps.gz][追伸
Weather Data Mining Using Independent Component Analysis
独立成分分析を使用した気象データマイニング
In this article, we apply the independent component analysis technique for mining spatio-temporal data. The technique has been applied to mine for patterns in weather data using the North Atlantic Oscillation (NAO) as a specific example. We find that the strongest independent components match the observed synoptic weather patterns corresponding to the NAO. We also validate our results by matching the independent component activities with the NAO index. [abs][pdf][ps.gz][ps
この記事では、時空間データのマイニングに独立成分分析手法を適用します。この手法は、北大西洋振動(NAO)を具体例として使用して、気象データのパターンの採掘に適用されています。最も強い独立成分は、NAOに対応する観測された総観気象パターンと一致することがわかりました。また、独立したコンポーネント活動をNAOインデックスと照合することにより、結果を検証します。
On the Importance of Small Coordinate Projections
小座標投影法の重要性について
It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is “small” in the sense that the Rademacher averages of this function class are small. We show that a new more general principle guarantees good generalization bounds. The new principle requires that random coordinate projections of the function class evaluated on random samples are “small” with high probability and that the random class of functions allows symmetrization. As an example, we prove that this geometric property of the function class is exactly the reason why the two lately proposed frameworks, the luckiness (Shawe-Taylor et al., 1998) and the algorithmic luckiness (Herbrich and Williamson, 2002), can be used to establish generalization bounds. [abs][pdf][ps.gz][ps
最近、アルゴリズムが仮説を選択する関数クラスが、この関数クラスのRademacher平均が小さいという意味で”小さい”場合に、シャープな一般化境界を取得できることが示されています。新しいより一般的な原理が良好な一般化境界を保証することを示します。新しい原則では、ランダム サンプルで評価された関数クラスのランダム座標投影が高確率で”小さく”、関数のランダム クラスが対称性を可能にすることが必要です。一例として、関数クラスのこの幾何学的特性が、最近提案された2つのフレームワーク、ラッキーネス(Shawe-Taylorら, 1998)とアルゴリズムのラッキーネス(Herbrich and Williamson, 2002)が一般化の境界を確立するために使用できる理由であることを証明します。[ABS][PDFファイル][ps.gz][追伸
Generalization Error Bounds for Threshold Decision Lists
しきい値決定リストの一般化誤差範囲
In this paper we consider the generalizationaccuracy of classification methods based on the iterative use oflinear classifiers. The resulting classifiers, which we call threshold decision lists act as follows. Some points of the dataset to be classified are given a particular classificationaccording to a linear threshold function (or hyperplane). Theseare then removed from consideration, and the procedure is iterateduntil all points are classified. Geometrically, we can imaginethat at each stage, points of the same classification aresuccessively chopped off from the data set by a hyperplane. We analyse theoretically the generalization properties of data classification techniques that are based on the use of threshold decision lists and on the special subclass of multilevel threshold functions. We present bounds on the generalization error in a standard probabilistic learning framework. The primary focus in this paper is on obtaining generalization error bounds that depend on the levels of separation—or margins—achieved by the successive linear classifiers. We also improve and extend previously published theoretical bounds on the generalization ability of perceptron decision trees.
この論文では、線形分類器の反復使用に基づく分類方法の一般化精度について検討します。結果として得られる分類器(ここでは閾値決定リストと呼びます)は、次のように動作します。分類するデータセットの一部のポイントに、線形閾値関数(または超平面)に従って特定の分類が与えられます。次に、これらのポイントは考慮から除外され、すべてのポイントが分類されるまでこの手順が繰り返されます。幾何学的には、各段階で、同じ分類のポイントが超平面によってデータセットから連続的に切り離されていると想像できます。閾値決定リストの使用と、マルチレベル閾値関数の特別なサブクラスに基づくデータ分類手法の一般化特性を理論的に分析します。標準的な確率学習フレームワークにおける一般化誤差の境界を示します。この論文の主な焦点は、連続する線形分類器によって達成される分離レベル(またはマージン)に依存する一般化誤差境界を取得することです。また、パーセプトロン決定木の一般化能力に関する、以前に発表された理論的限界を改善し、拡張します。
Subgroup Discovery with CN2-SD
CN2-SDによるサブグループディスカバリー
This paper investigates how to adapt standard classification rule learning approaches to subgroup discovery. The goal of subgroup discovery is to find rules describing subsets of the population that are sufficiently large and statistically unusual. The paper presents a subgroup discovery algorithm, CN2-SD, developed by modifying parts of the CN2 classification rule learner: its covering algorithm, search heuristic, probabilistic classification of instances, and evaluation measures. Experimental evaluation of CN2-SD on 23 UCI data sets shows substantial reduction of the number of induced rules, increased rule coverage and rule significance, as well as slight improvements in terms of the area under ROC curve, when compared with the CN2 algorithm. Application of CN2-SD to a large traffic accident data set confirms these findings.
この論文では、標準的な分類ルール学習アプローチをサブグループディスカバリーにどのように適応させるかを検討します。サブグループ探索の目標は、十分に大きく、統計的に異常である母集団のサブセットを記述するルールを見つけることです。この論文では、CN2分類ルール学習器の一部(カバーリング アルゴリズム、探索ヒューリスティック、インスタンスの確率的分類、評価手段)を変更して開発されたサブグループ探索アルゴリズムCN2-SDを紹介します。23のUCIデータセットに対するCN2-SDの実験的評価では、CN2アルゴリズムと比較した場合、誘導されたルールの数が大幅に減少し、ルールカバレッジとルールの意義が増加し、ROC曲線下面積がわずかに改善されたことが示されています。大規模な交通事故データセットへのCN2-SDの適用は、これらの発見を裏付けています。
Lossless Online Bayesian Bagging
ロスレスオンラインベイジアンバギング
Bagging frequently improves the predictive performance of a model. An online version has recently been introduced, which attempts to gain the benefits of an online algorithm while approximating regular bagging. However, regular online bagging is an approximation to its batch counterpart and so is not lossless with respect to the bagging operation. By operating under the Bayesian paradigm, we introduce an online Bayesian version of bagging which is exactly equivalent to the batch Bayesian version, and thus when combined with a lossless learning algorithm gives a completely lossless online bagging algorithm. We also note that the Bayesian formulation resolves a theoretical problem with bagging, produces less variability in its estimates, and can improve predictive performance for smaller data sets.
バギングは、モデルの予測パフォーマンスを頻繁に向上させます。最近、オンラインバージョンが導入され、通常のバギングに近似しながらオンラインアルゴリズムの利点を得ようとしています。ただし、通常のオンラインバギングは、対応するバッチの近似値であるため、バギング操作に関してロスレスではありません。ベイジアンパラダイムの下で操作することにより、バッチベイジアンバージョンとまったく同じオンラインベイジアンバージョンのバギングを導入し、したがって、ロスレス学習アルゴリズムと組み合わせると、完全にロスレスなオンラインバギングアルゴリズムが得られます。また、ベイズ定式化は、バギングに関する理論的な問題を解決し、推定値のばらつきを減らし、より小さなデータセットの予測パフォーマンスを向上させることができることにも注意してください。
In Defense of One-Vs-All Classification
One-Vs-All分類の擁護
We consider the problem of multiclass classification. Our main thesis is that a simple “one-vs-all” scheme is as accurate as any other approach, assuming that the underlying binary classifiers are well-tuned regularized classifiers such as support vector machines. This thesis is interesting in that it disagrees with a large body of recent published work on multiclass classification. We support our position by means of a critical review of the existing literature, a substantial collection of carefully controlled experimental work, and theoretical arguments.
私たちは、多クラス分類の問題を考えます。私たちの主な論文は、単純な「1対すべて」のスキームは、基礎となるバイナリ分類器がサポートベクターマシンなどの適切に調整された正規化分類器であると仮定して、他のアプローチと同じくらい正確であるということです。この論文では、最近発表された多クラス分類に関する多くの研究と一致しないという点で興味深いものです。私たちは、既存の文献の批判的レビュー、慎重に制御された実験研究の実質的なコレクション、および理論的な議論を通じて、私たちの立場を支持します。
Dimensionality Reduction for Supervised Learning with Reproducing Kernel Hilbert Spaces
カーネルヒルベルト空間の再現による教師あり学習のための次元削減
We propose a novel method of dimensionality reduction for supervised learning problems. Given a regression or classification problem in which we wish to predict a response variable Y from an explanatory variable X, we treat the problem of dimensionality reduction as that of finding a low-dimensional “effective subspace” for X which retains the statistical relationship between X and Y. We show that this problem can be formulated in terms of conditional independence. To turn this formulation into an optimization problem we establish a general nonparametric characterization of conditional independence using covariance operators on reproducing kernel Hilbert spaces. This characterization allows us to derive a contrast function for estimation of the effective subspace. Unlike many conventional methods for dimensionality reduction in supervised learning, the proposed method requires neither assumptions on the marginal distribution of X, nor a parametric model of the conditional distribution of Y. We present experiments that compare the performance of the method with conventional methods.
私たちは、教師あり学習問題のための次元削減の新しい方法を提案します。説明変数Xから応答変数Yを予測する回帰問題または分類問題が与えられた場合、次元削減の問題を、XとYの間の統計的関係を保持するXの低次元「有効部分空間」を見つける問題として扱う。私たちは、この問題が条件付き独立性の観点から定式化できることを示す。この定式化を最適化問題に変換するために、再生カーネル ヒルベルト空間上の共分散演算子を使用して、条件付き独立性の一般的なノンパラメトリック特性を確立します。この特性により、有効部分空間の推定のためのコントラスト関数を導出できます。教師あり学習における次元削減の多くの従来の方法とは異なり、提案された方法では、Xの周辺分布に関する仮定も、Yの条件付き分布のパラメトリック モデルも必要ありません。私たちは、この方法と従来の方法のパフォーマンスを比較する実験を提示します。
Learning the Kernel Matrix with Semidefinite Programming
半定値プログラミングによるカーネル行列の学習
Kernel-based learning algorithms work by embedding the data into a Euclidean space, and then searching for linear relations among the embedded data points. The embedding is performed implicitly, by specifying the inner products between each pair of points in the embedding space. This information is contained in the so-called kernel matrix, a symmetric and positive semidefinite matrix that encodes the relative positions of all points. Specifying this matrix amounts to specifying the geometry of the embedding space and inducing a notion of similarity in the input space—classical model selection problems in machine learning. In this paper we show how the kernel matrix can be learned from data via semidefinite programming (SDP) techniques. When applied to a kernel matrix associated with both training and test data this gives a powerful transductive algorithm—using the labeled part of the data one can learn an embedding also for the unlabeled part. The similarity between test points is inferred from training points and their labels. Importantly, these learning problems are convex, so we obtain a method for learning both the model class and the function without local minima. Furthermore, this approach leads directly to a convex method for learning the 2-norm soft margin parameter in support vector machines, solving an important open problem.
カーネルベースの学習アルゴリズムは、データをユークリッド空間に埋め込み、埋め込まれたデータ ポイント間の線形関係を検索することで機能します。埋め込みは、埋め込み空間内の各ポイントのペア間の内積を指定することによって暗黙的に実行されます。この情報は、すべてのポイントの相対位置をエンコードする対称で正の半正定値行列である、いわゆるカーネル マトリックスに含まれています。このマトリックスを指定することは、埋め込み空間のジオメトリを指定し、入力空間に類似性の概念を誘導することと同じです。これは、機械学習における古典的なモデル選択問題です。この論文では、半正定値計画(SDP)手法を使用して、データからカーネル マトリックスを学習する方法を示します。トレーニング データとテスト データの両方に関連付けられたカーネル マトリックスに適用すると、強力なトランスダクティブ アルゴリズムが得られます。つまり、データのラベル付き部分を使用して、ラベルなし部分の埋め込みも学習できます。テスト ポイント間の類似性は、トレーニング ポイントとそのラベルから推測されます。重要なのは、これらの学習問題は凸型であるため、モデル クラスと関数の両方を局所最小値なしで学習する方法が得られることです。さらに、このアプローチは、サポートベクターマシンの2ノルムソフトマージンパラメータを学習するための凸法に直接つながり、重要な未解決の問題を解決します。
Learning Rates for Q-learning
Qラーニングの学習率
In this paper we derive convergence rates for Q-learning.We show an interesting relationship between the convergence rate andthe learning rate used in Q-learning.For a polynomial learning rate,one which is 1/tω at time t where ω∈(1/2,1),we show that the convergence rate is polynomial in 1/(1-γ),where γ is the discount factor.In contrast we show thatfor a linear learning rate, one which is 1/t at time t,the convergence rate has an exponential dependence on 1/(1-γ).In addition we show a simple example that proves this exponential behavioris inherent for linear learning rates.
この論文では、Q学習の収束率を導き出します。収束率とQ学習で使用される学習率との間に興味深い関係を示します。多項式学習率の場合、時間tでω∈(1/2,1)の場合、収束率は1/(1-γ)で多項式であり、γは割引係数であることを示します。対照的に、線形学習率(時間tで1/t)の場合、収束率は1/(1-γ)に指数関数的に依存することを示します。さらに、この指数関数的な振る舞いが線形学習率に固有のものであることを証明する簡単な例を示します。
