Use of the Zero-Norm with Linear Models and Kernel Methods
線形モデルとカーネル法でのゼロノルムの使用
We explore the use of the so-called zero-norm of theparameters of linear models in learning. Minimization of such aquantity has many uses in a machine learning context: forvariable or feature selection, minimizing training error andensuring sparsity in solutions. We derive a simple but practicalmethod for achieving these goals and discuss its relationship toexisting techniques of minimizing the zero-norm.The method boils down to implementinga simple modification of vanilla SVM, namely viaan iterative multiplicative rescaling of the training data.Applications we investigate which aid our discussion includevariable and feature selection on biological microarray data,and multicategory classification.
私たちは、学習における線形モデルのパラメータのいわゆるゼロノルムの使用を探ります。このような量の最小化は、機械学習のコンテキストで多くの用途があります:変数または特徴の選択、トレーニングエラーの最小化、ソリューションのスパース性の確保。これらの目標を達成するためのシンプルだが実用的な方法を導き出し、ゼロノルムを最小化する既存の手法との関係について議論します。この方法は、バニラSVMの単純な変更、つまりトレーニングデータの反復乗算再スケーリングを介して実装することに要約されます。私たちが調査するアプリケーションには、生物学的マイクロアレイデータの変数と特徴の選択、およびマルチカテゴリ分類が含まれます。
Feature Extraction by Non-Parametric Mutual Information Maximization
ノンパラメトリック相互情報量最大化による特徴抽出
We present a method for learning discriminative feature transformsusing as criterion the mutual information between class labels andtransformed features. Instead of a commonly used mutualinformation measure based on Kullback-Leibler divergence, we use aquadratic divergence measure, which allows us to make an efficientnon-parametric implementation and requires no prior assumptionsabout class densities. In addition to linear transforms, we alsodiscuss nonlinear transforms that are implemented as radial basisfunction networks. Extensions to reduce the computationalcomplexity are also presented, and a comparison to greedy featureselection is made.
私たちは、クラスラベルと変換された特徴との間の相互情報を基準として使用して、識別的特徴変換を学習する方法を提示します。Kullback-Leibler発散に基づく一般的に使用される相互情報測度の代わりに、水生発散測度を使用するため、効率的なノンパラメトリック実装を行うことができ、クラス密度についての事前の仮定は必要ありません。線形変換に加えて、放射基底関数ネットワークとして実装される非線形変換についても説明します。計算の複雑さを軽減するための拡張も提示され、貪欲な特徴選択との比較が行われます。
Ranking a Random Feature for Variable and Feature Selection
変数と特徴選択のためのランダム特徴のランク付け
We describe a feature selection method that can be applied directly tomodels that are linear with respect to their parameters, and indirectly toothers. It is independent of the target machine. It is closely related toclassical statistical hypothesis tests, but it is more intuitive, hence moresuitable for use by engineers who are not statistics experts. Furthermore,some assumptions of classical tests are relaxed. The method has been usedsuccessfully in a number of applications that are briefly described.
私たちは、パラメータに対して線形のモデルに直接適用でき、他のモデルに間接的に適用できる機能選択方法について説明します。これは、ターゲットマシンから独立しています。これは古典的な統計仮説検定と密接に関連していますが、より直感的であるため、統計の専門家ではないエンジニアによる使用に適しています。さらに、古典的なテストの一部の仮定は緩和されています。この方法は、簡単に説明されている多くのアプリケーションで成功裏に使用されています。
MLPs (Mono-Layer Polynomials and Multi-Layer Perceptrons) for Nonlinear Modeling
非線形モデリングのためのMLP(単層多項式および多層パーセプトロン)
This paper presents a model selection procedure which stresses the importance of the classic polynomial models as tools for evaluating the complexity of a given modeling problem, and for removing non-significant input variables. If the complexity of the problem makes a neural network necessary, the selection among neural candidates can be performed in two phases. In an additive phase, the most important one, candidate neural networks with an increasing number of hidden neurons are trained. The addition of hidden neurons is stopped when the effect of the round-off errors becomes significant, so that, for instance, confidence intervals cannot be accurately estimated. This phase leads to a set of approved candidate networks. In a subsequent subtractive phase, a selection among approved networks is performed using statistical Fisher tests. The series of tests starts from a possibly too large unbiased network (the full network), and ends with the smallest unbiased network whose input variables and hidden neurons all have a significant contribution to the regression estimate. This method was successfully tested against the real-world regression problems proposed at the NIPS2000 Unlabeled Data Supervised Learning Competition; two of them are included here as illustrative examples.
この論文では、モデル選択手順を紹介し、与えられたモデリング問題の複雑さを評価し、重要でない入力変数を除去するツールとして、古典的な多項式モデルの重要性を強調しています。問題の複雑さによりニューラル ネットワークが必要な場合、ニューラル候補の選択は2つのフェーズで実行できます。最も重要な追加フェーズでは、隠れニューロンの数を増やしながら候補ニューラル ネットワークをトレーニングします。丸め誤差の影響が大きくなり、たとえば信頼区間を正確に推定できなくなると、隠れニューロンの追加は停止されます。このフェーズにより、承認された候補ネットワークのセットが作成されます。次の減算フェーズでは、統計的フィッシャー テストを使用して、承認されたネットワークの選択が実行されます。一連のテストは、大きすぎる可能性のある不偏ネットワーク(完全なネットワーク)から開始され、入力変数と隠れニューロンがすべて回帰推定に大きく寄与する最小の不偏ネットワークで終了します。この方法は、NIPS2000ラベルなしデータ教師あり学習コンペティションで提案された実際の回帰問題に対してテストされ、成功しました。ここではそのうちの2つを例として挙げます。
Overfitting in Making Comparisons Between Variable Selection Methods
変数選択方法間の比較における過適合
This paper addresses a common methodological flaw in the comparison ofvariable selection methods. A practical approach to guide the searchor the selection process is to compute cross-validation performanceestimates of the different variable subsets. Used with computationallyintensive search algorithms, these estimates may overfit and yieldbiased predictions. Therefore, they cannot be used reliably to comparetwo selection methods, as is shown by the empirical results of thispaper. Instead, like in other instances of the model selectionproblem, independent test sets should be used for determining thefinal performance. The claims made in the literature about thesuperiority of more exhaustive search algorithms over simpler ones arealso revisited, and some of them infirmed.
この論文では、変数選択方法の比較における一般的な方法論的欠陥について説明します。検索者の選択プロセスをガイドする実用的なアプローチは、さまざまな変数サブセットの交差検証パフォーマンス推定値を計算することです。計算負荷の高い検索アルゴリズムと併用すると、これらの推定値は過剰適合し、予測が偏る可能性があります。したがって、この論文の経験的結果が示すように、2つの選択方法を確実に比較するために使用することはできません。代わりに、モデル選択問題の他のインスタンスと同様に、最終的なパフォーマンスを決定するために独立したテスト セットを使用する必要があります。より網羅的な検索アルゴリズムが単純なアルゴリズムよりも優れているという文献での主張も再検討され、それらのいくつかは弱体化しています。
Variable Selection Using SVM-based Criteria
SVM ベースの基準を使用した変数選択
We propose new methods to evaluate variable subset relevance witha view to variable selection. Relevance criteria are derived fromSupport Vector Machines and are based on weight vector||w||2 or generalization error bounds sensitivity withrespect to a variable. Experiments on linear and non-linear toyproblems and real-world datasets have been carried out to assessthe effectiveness of these criteria. Results show that thecriterion based on weight vector derivative achieves good resultsand performs consistently well over the datasets we used.
私たちは、変数選択を視野に入れた変数サブセットの関連性を評価する新しい方法を提案します。関連性基準は、Support Vector Machinesから導き出され、重みベクトルに基づいています||w||2または汎化誤差は、変数に関する感度を制限します。これらの基準の有効性を評価するために、線形および非線形の玩具問題と実世界のデータセットに関する実験が行われました。結果は、重みベクトル導関数に基づく基準が良好な結果を達成し、使用したデータセットに対して一貫して良好なパフォーマンスを発揮することを示しています。
Grafting: Fast, Incremental Feature Selection by Gradient Descent in Function Space
グラフト:関数空間における勾配降下法による高速増分特徴選択
We present a novel and flexible approach to the problem of featureselection, called grafting. Rather than considering featureselection as separate from learning, grafting treats the selection ofsuitable features as an integral part of learning a predictor in aregularized learning framework. To make this regularized learningprocess sufficiently fast for large scale problems, grafting operatesin an incremental iterative fashion, gradually building up a featureset while training a predictor model using gradient descent. At eachiteration, a fast gradient-based heuristic is used to quickly assesswhich feature is most likely to improve the existing model, thatfeature is then added to the model, and the model is incrementallyoptimized using gradient descent. The algorithm scales linearly withthe number of data points and at most quadratically with the number offeatures. Grafting can be used with a variety of predictor modelclasses, both linear and non-linear, and can be used for bothclassification and regression. Experiments are reported here on avariant of grafting for classification, using both linear andnon-linear models, and using a logistic regression-inspired lossfunction. Results on a variety of synthetic and real world data setsare presented. Finally the relationship between grafting, stagewiseadditive modelling, and boosting is explored.
私たちは、グラフティングと呼ばれる、特徴選択の問題に対する新しい柔軟なアプローチを提示します。グラフティングは、特徴選択を学習とは別のものとして考えるのではなく、適切な特徴の選択を、正規化学習フレームワークにおける予測子の学習の不可欠な部分として扱います。この正規化学習プロセスを大規模な問題に対して十分に高速にするために、グラフティングは増分反復方式で動作し、勾配降下法を使用して予測子モデルをトレーニングしながら、徐々に特徴セットを構築します。各反復では、高速勾配ベースのヒューリスティックを使用して、どの特徴が既存のモデルを改善する可能性が最も高いかを迅速に評価し、その特徴をモデルに追加して、勾配降下法を使用してモデルを増分的に最適化します。アルゴリズムは、データ ポイントの数に比例して、最大で特徴の数の2乗でスケーリングされます。グラフティングは、線形と非線形の両方のさまざまな予測子モデル クラスで使用でき、分類と回帰の両方に使用できます。ここでは、線形モデルと非線形モデルの両方を使用し、ロジスティック回帰にヒントを得た損失関数を使用して、分類のためのグラフティングのさまざまなバリエーションに関する実験が報告されています。さまざまな合成データ セットと実際のデータ セットの結果が提示されています。最後に、グラフティング、段階的な加法モデリング、およびブースティングの関係が検討されています。
Sufficient Dimensionality Reduction
十分な次元削減
Dimensionality reduction of empirical co-occurrence data is a fundamental problem in unsupervised learning. It is also a well studied problem in statistics known as the analysis of cross-classified data. One principled approach to this problem is to represent the data in low dimension with minimal loss of (mutual) information contained in the original data. In this paper we introduce an information theoretic nonlinear method for finding such a most informative dimension reduction. In contrast with previously introduced clustering based approaches, here we extract continuous feature functions directly from the co-occurrence matrix. In a sense, we automatically extract functions of the variables that serve as approximate sufficient statistics for a sample of one variable about the other one. Our method is different from dimensionality reduction methods which are based on a specific, sometimes arbitrary, metric or embedding. Another interpretation of our method is as generalized – multi-dimensional – non-linear regression, where rather than fitting one regression function through two dimensional data, we extract d-regression functions whose expectation values capture the information among the variables. It thus presents a new learning paradigm that unifies aspects from both supervised and unsupervised learning. The resulting dimension reduction can be described by two conjugate d-dimensional differential manifolds that are coupled through Maximum Entropy I-projections. The Riemannian metrics of these manifolds are determined by the observed expectation values of our extracted features.Following this geometric interpretation we present an iterativeinformation projection algorithm for finding such featuresand prove its convergence. Our algorithm is similar to the method of”association analysis” in statistics, though the feature extractioncontext as well as the information theoretic and geometricinterpretation are new.The algorithm is illustrated byvarious synthetic co-occurrence data. It is then demonstrated fortext categorization and information retrieval and proves effectivein selecting a small set of features, often improving performance over the original feature set.
経験的共起データの次元削減は、教師なし学習の基本的な問題です。また、クロス分類データの分析として知られる統計学でよく研究されている問題でもあります。この問題に対する1つの原則的なアプローチは、元のデータに含まれる(相互)情報の損失を最小限に抑えながら、データを低次元で表現することです。この論文では、このような最も有益な次元削減を見つけるための情報理論的非線形法を紹介します。以前に紹介したクラスタリング ベースのアプローチとは対照的に、ここでは共起行列から連続的な特徴関数を直接抽出します。ある意味では、ある変数のサンプルが他の変数について十分な近似統計量として機能する変数の関数を自動的に抽出します。この方法は、特定の、場合によっては任意のメトリックまたは埋め込みに基づく次元削減方法とは異なります。この方法の別の解釈は、一般化された多次元非線形回帰であり、2次元データに1つの回帰関数を当てはめるのではなく、期待値が変数間の情報を捕捉するd回帰関数を抽出します。したがって、これは教師あり学習と教師なし学習の両方の側面を統合する新しい学習パラダイムを提示します。結果として得られる次元削減は、最大エントロピーI射影を介して結合された2つの共役d次元微分多様体によって記述できます。これらの多様体のリーマン計量は、抽出された特徴の観測期待値によって決定されます。この幾何学的解釈に従って、このような特徴を見つけるための反復情報射影アルゴリズムを提示し、その収束を証明します。このアルゴリズムは、統計における「関連分析」の方法に似ていますが、特徴抽出コンテキスト、および情報理論的および幾何学的解釈は新しいものです。このアルゴリズムは、さまざまな合成共起データによって説明されます。次に、テキスト分類と情報検索について実証され、小さな特徴セットを選択するのに効果的であることが証明され、多くの場合、元の特徴セットよりもパフォーマンスが向上します。
An Extensive Empirical Study of Feature Selection Metrics for Text Classification
テキスト分類のための特徴選択メトリクスに関する広範な実証的研究
Machine learning for text classification is the cornerstone of document categorization, news filtering, document routing, and personalization. In text domains, effective feature selection is essential to make the learning task efficient and more accurate. This paper presents an empirical comparison of twelve feature selection methods (e.g. Information Gain) evaluated on a benchmark of 229 text classification problem instances that were gathered from Reuters, TREC, OHSUMED, etc. The results are analyzed from multiple goal perspectives-accuracy, F-measure, precision, and recall-since each is appropriate in different situations. The results reveal that a new feature selection metric we call ‘Bi-Normal Separation’ (BNS), outperformed the others by a substantial margin in most situations. This margin widened in tasks with high class skew, which is rampant in text classification problems and is particularly challenging for induction algorithms. A new evaluation methodology is offered that focuses on the needs of the data mining practitioner faced with a single dataset who seeks to choose one (or a pair of) metrics that are most likely to yield the best performance. From this perspective, BNS was the top single choice for all goals except precision, for which Information Gain yielded the best result most often. This analysis also revealed, for example, that Information Gain and Chi-Squared have correlated failures, and so they work poorly together. When choosing optimal pairs of metrics for each of the four performance goals, BNS is consistently a member of the pair—e.g., for greatest recall, the pair BNS + F1-measure yielded the best performance on the greatest number of tasks by a considerable margin.
テキスト分類のための機械学習は、文書分類、ニュースフィルタリング、文書ルーティング、およびパーソナライゼーションの基礎です。テキスト領域では、学習タスクを効率的かつより正確にするために、効果的な特徴選択が不可欠です。この論文では、ロイター、TREC、OHSUMEDなどから収集された229のテキスト分類問題インスタンスのベンチマークで評価された12の特徴選択方法(情報ゲインなど)の実証的な比較を示します。結果は、それぞれが異なる状況に適しているため、複数の目標の観点(精度、F値、適合率、再現率)から分析されます。結果から、私たちが「Bi-Normal Separation」(BNS)と呼ぶ新しい特徴選択メトリックが、ほとんどの状況で他のメトリックを大幅に上回っていることが明らかになりました。このマージンは、テキスト分類問題で蔓延し、特に誘導アルゴリズムにとって困難な、クラス偏りの高いタスクで拡大しました。単一のデータセットに直面し、最高のパフォーマンスをもたらす可能性が最も高い1つの(または1組の)メトリックスを選択しようとするデータ マイニング担当者のニーズに焦点を当てた新しい評価方法が提案されています。この観点から、精度を除くすべての目標について、BNSが最優先の選択肢でした。精度については、情報ゲインが最も頻繁に最高の結果をもたらしました。この分析では、たとえば、情報ゲインとカイ2乗には相関する失敗があり、一緒に使用するとうまく機能しないことも明らかになりました。4つのパフォーマンス目標のそれぞれについて最適なメトリックスのペアを選択する場合、BNSは常にペアのメンバーです。たとえば、最大の再現率の場合、BNS + F1メジャーのペアは、かなりの差をつけて、最も多くのタスクで最高のパフォーマンスをもたらしました。
A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification
テキスト分類のための分割情報理論的特徴クラスタリングアルゴリズム
High dimensionality of text can be a deterrent in applyingcomplex learners such as Support Vector Machines to the task of textclassification. Feature clustering is a powerful alternative to feature selectionfor reducing the dimensionality of text data. In this paper we propose a newinformation-theoretic divisive algorithm for feature/word clustering andapply it to text classification.Existing techniques for such “distributional clustering” of words areagglomerative in nature and resultin (i) sub-optimal word clusters and (ii) high computational cost.In order to explicitly capture the optimality of word clusters inan information theoretic framework, we first derive a globalcriterion for feature clustering. We then present a fast, divisivealgorithm that monotonically decreases this objective function value.We show that our algorithmminimizes the “within-cluster Jensen-Shannon divergence” whilesimultaneously maximizing the “between-cluster Jensen-Shannon divergence”.In comparison to the previously proposed agglomerative strategies ourdivisive algorithm is much faster and achieves comparable or higher classificationaccuracies. We further show that feature clustering is aneffective technique for building smaller class models in hierarchicalclassification. We present detailed experimental resultsusing Naive Bayes and Support Vector Machineson the 20Newsgroups data set and a 3-level hierarchy of HTMLdocuments collected from the Open Directory project (www.dmoz.org).
テキストの高次元性は、サポート ベクター マシンなどの複雑な学習器をテキスト分類のタスクに適用する際の障害となる可能性があります。特徴クラスタリングは、テキスト データの次元性を削減するための特徴選択の強力な代替手段です。この論文では、特徴/単語クラスタリングのための新しい情報理論的分割アルゴリズムを提案し、それをテキスト分類に適用します。このような単語の「分散クラスタリング」の既存の手法は、本質的に凝集性があり、(i)最適でない単語クラスタと(ii)高い計算コストをもたらします。情報理論的フレームワークで単語クラスタの最適性を明示的に把握するために、まず特徴クラスタリングのグローバル基準を導き出します。次に、この目的関数値を単調に減少させる高速な分割アルゴリズムを紹介します。このアルゴリズムは、「クラスター内Jensen-Shannonダイバージェンス」を最小化すると同時に、「クラスター間Jensen-Shannonダイバージェンス」を最大化することを示しています。以前に提案された凝集戦略と比較すると、分割アルゴリズムははるかに高速で、同等以上の分類精度を実現します。さらに、特徴クラスタリングは、階層分類でより小さなクラス モデルを構築するのに効果的な手法であることを示しています。20のニュースグループ データ セットと、Open Directoryプロジェクト(www.dmoz.org)から収集された3レベルの階層のHTMLドキュメントに対して、Naive BayesとSupport Vector Machinesを使用して行った詳細な実験結果を紹介します。
Benefitting from the Variables that Variable Selection Discards
変数選択が破棄する変数の恩恵を受ける
In supervised learning variable selection is used to find a subsetof the available inputs that accurately predict the output. Thispaper shows that some of the variables that variable selectiondiscards can beneficially be used as extra outputs for inductivetransfer. Using discarded input variables as extra outputs forcesthe model to learn mappings from the variables that were selectedas inputs to these extra outputs. Inductive transfer makes whatis learned by these mappings available to the model that is beingtrained on the main output, often resulting in improvedperformance on that main output.We present three synthetic problems (two regression problems and oneclassification problem) where performance improves if some variablesdiscarded by variable selection are used as extra outputs. We thenapply variable selection to two real problems (DNA splice-junction andpneumonia risk prediction) and demonstrate the same effect: using someof the discarded input variables as extra outputs yields somewhat betterperformance on both of these problems than can be achieved by variableselection alone. This new approach enhances the benefit of variableselection by allowing the learner to benefit from variables that wouldotherwise have been discarded by variable selection, but withoutsuffering the loss in performance that occurs when these variables areused as inputs.
教師あり学習では、変数選択は、出力を正確に予測する利用可能な入力のサブセットを見つけるために使用されます。この論文では、変数選択によって破棄される変数のいくつかが、帰納的転送の追加出力として効果的に使用できることを示しています。破棄された入力変数を追加出力として使用すると、モデルは、入力として選択された変数からこれらの追加出力へのマッピングを学習する必要があります。帰納的転送により、これらのマッピングによって学習された内容が、メイン出力でトレーニングされているモデルで使用できるようになります。その結果、多くの場合、そのメイン出力のパフォーマンスが向上します。変数選択によって破棄された変数のいくつかを追加出力として使用すると、パフォーマンスが向上する3つの合成問題(2つの回帰問題と1つの分類問題)を示します。次に、変数選択を2つの実際の問題(DNAスプライス ジャンクションと肺炎リスク予測)に適用し、同じ効果を示します。破棄された入力変数のいくつかを追加出力として使用すると、変数選択のみで達成できるよりも、これらの両方の問題でいくらかパフォーマンスが向上します。この新しいアプローチは、変数選択によって破棄されるはずだった変数を学習者が利用できるようにすることで変数選択の利点を高めますが、これらの変数が入力として使用された場合に発生するパフォーマンスの低下は発生しません。
Dimensionality Reduction via Sparse Support Vector Machines
スパースサポートベクターマシンによる次元削減
We describe a methodology for performing variable ranking andselection using support vector machines (SVMs). The methodconstructs a series of sparse linear SVMs to generate linearmodels that can generalize well, and uses a subset of nonzeroweighted variables found by the linear models to produce a finalnonlinear model. The method exploits the fact that a linear SVM(no kernels) with l1-norm regularization inherently performsvariable selection as a side-effect of minimizing capacity of theSVM model. The distribution of the linear model weights provides amechanism for ranking and interpreting the effects of variables.Starplots are used to visualize the magnitude and variance of the weights for each variable. We illustrate the effectiveness ofthe methodology on synthetic data, benchmark problems, andchallenging regression problems in drug design. This method candramatically reduce the number of variables and outperforms SVMstrained using all attributes and using the attributes selectedaccording to correlation coefficients. The visualization of theresulting models is useful for understanding the role ofunderlying variables.
私たちは、サポートベクターマシン(SVM)を使用して変数のランク付けと選択を実行する方法論について説明します。この方法では、一連のスパース線形SVMを構築して、一般化に適した線形モデルを生成し、線形モデルによって検出された非ゼロ重み変数のサブセットを使用して最終的な非線形モデルを生成します。この方法では、l1ノルム正則化を使用した線形SVM (カーネルなし)が、SVMモデルの容量を最小化する副作用として、本質的に変数選択を実行するという事実を利用します。線形モデルの重みの分布は、変数の効果をランク付けして解釈するためのメカニズムを提供します。スタープロットは、各変数の重みの大きさと分散を視覚化するために使用されます。合成データ、ベンチマーク問題、および医薬品設計における困難な回帰問題に対する方法論の有効性を示します。この方法は、変数の数を大幅に削減し、すべての属性を使用してトレーニングされたSVMと相関係数に従って選択された属性を使用してトレーニングされたSVMよりも優れたパフォーマンスを発揮します。結果として得られるモデルの視覚化は、基礎となる変数の役割を理解するのに役立ちます。
Extensions to Metric-Based Model Selection
メトリクスベースのモデル選択の拡張
Metric-based methods have recently been introduced for model selection and regularization, often yielding verysignificant improvements over the alternatives tried (including cross-validation). All these methods require unlabeled dataover which to compare functions and detect gross differences in behavior away from the training points. We introduce threenew extensions of the metric model selection methods and apply them to feature selection. The first extension takesadvantage of the particular case of time-series data in which the task involves prediction with a horizon h. The idea isto use at t the h unlabeled examples that precede t for model selection. The second extension takes advantage of thedifferent error distributions of cross-validation and the metric methods: cross-validation tends to have a larger varianceand is unbiased. A hybrid combining the two model selection methods is rarely beaten by any of the two methods. The thirdextension deals with the case when unlabeled data is not available at all, using an estimated input density. Experimentsare described to study these extensions in the context of capacity control and feature subset selection.
最近、モデル選択と正則化にメトリックベースの方法が導入され、多くの場合、試行された代替方法(クロスバリデーションを含む)よりも大幅に改善されています。これらの方法はすべて、関数を比較し、トレーニング ポイントから離れた動作の大きな違いを検出するために、ラベルなしデータを必要とします。メトリック モデル選択方法の新しい3つの拡張を導入し、それらを特徴選択に適用します。最初の拡張は、タスクが期間hでの予測を伴う時系列データの特定のケースを利用します。アイデアは、tでtより前のhのラベルなしの例をモデル選択に使用することです。2番目の拡張は、クロスバリデーションとメトリック メソッドの異なるエラー分布を利用します。クロスバリデーションは、分散が大きく、偏りがありません。2つのモデル選択方法を組み合わせたハイブリッドは、2つの方法のいずれにも勝るものはほとんどありません。3番目の拡張は、推定入力密度を使用して、ラベルなしデータがまったく利用できない場合を扱います。容量制御と特徴サブセット選択のコンテキストでこれらの拡張を研究するための実験について説明します。
Distributional Word Clusters vs. Words for Text Categorization
テキスト分類のための分布単語クラスターと単語
We study an approach to text categorization that combinesdistributional clustering of words and a Support Vector Machine(SVM) classifier. This word-cluster representation is computedusing the recently introduced Information Bottleneck method,which generates a compact and efficient representation ofdocuments. When combined with the classification power of the SVM,this method yields high performance in text categorization. Thisnovel combination of SVM with word-cluster representation iscompared with SVM-based categorization using the simplerbag-of-words (BOW) representation. The comparison is performedover three known datasets. On one of these datasets (the 20Newsgroups) the method based on word clusters significantlyoutperforms the word-based representation in terms ofcategorization accuracy or representation efficiency. On the twoother sets (Reuters-21578 and WebKB) the word-based representationslightly outperforms the word-cluster representation. Weinvestigate the potential reasons for this behavior and relate itto structural differences between the datasets.
私たちは、単語の分布クラスタリングとサポートベクターマシン(SVM)分類器を組み合わせたテキスト分類のアプローチを研究しています。この単語クラスター表現は、最近導入された情報ボトルネック法を使用して計算され、文書のコンパクトで効率的な表現を生成します。SVMの分類能力と組み合わせると、この方法はテキスト分類で高いパフォーマンスを発揮します。SVMと単語クラスター表現のこの新しい組み合わせを、より単純な単語バッグ(BOW)表現を使用したSVMベースの分類と比較します。比較は、3つの既知のデータセットで実行されます。これらのデータセットの1つ(20Newsgroups)では、単語クラスターに基づく方法は、分類精度または表現効率の点で単語ベースの表現を大幅に上回ります。他の2つのセット(Reuters-21578とWebKB)では、単語ベースの表現は単語クラスター表現をわずかに上回ります。この動作の潜在的な理由を調査し、データセット間の構造の違いに関連付けます。
An Introduction to Variable and Feature Selection
変数と機能の選択の概要
Variable and feature selection have become the focus of muchresearch in areas of application for which datasets with tens orhundreds of thousands of variables are available. These areasinclude text processing of internet documents, gene expressionarray analysis, and combinatorial chemistry. The objective ofvariable selection is three-fold: improving the predictionperformance of the predictors, providing faster and morecost-effective predictors, and providing a better understanding ofthe underlying process that generated the data. The contributionsof this special issue cover a wide range of aspects of suchproblems: providing a better definition of the objective function,feature construction, feature ranking, multivariate featureselection, efficient search methods, and feature validityassessment methods.
変数と特徴の選択は、何万、何十万もの変数を持つデータセットが利用できる応用分野で多くの研究の焦点となっています。これらの分野には、インターネット文書のテキスト処理、遺伝子発現アレイ分析、およびコンビナトリアルケミストリーが含まれます。変数選択の目的は、予測子の予測パフォーマンスの向上、より高速でコスト効率の高い予測子の提供、およびデータを生成した基礎プロセスの理解の向上の3つです。この特別号の寄稿は、このような問題の幅広い側面をカバーしています。目的関数のより適切な定義の提供、特徴の構築、特徴のランク付け、多変量特徴の選択、効率的な検索方法、および特徴の有効性評価方法。
A Neural Probabilistic Language Model
神経確率的言語モデル
A goal of statistical language modeling is to learn the jointprobability function of sequences of words in a language. This isintrinsically difficult because of the curse of dimensionality:a word sequence on which the model will be tested is likely to bedifferent from all the word sequences seen during training.Traditional but very successful approaches based on n-grams obtaingeneralization by concatenating very short overlappingsequences seen in the trainingset. We propose to fight the curse of dimensionality bylearning a distributed representation for words which allows eachtraining sentence to inform the model about an exponential number ofsemantically neighboring sentences. The model learns simultaneously(1) a distributed representation for each word along with (2) theprobability function for word sequences, expressed in terms of theserepresentations. Generalization is obtained because a sequence ofwords that has never been seen before gets high probability if it ismade of words that are similar (in the sense of having a nearbyrepresentation) to words forming an already seen sentence. Trainingsuch large models (with millions of parameters) within a reasonabletime is itself a significant challenge. We report on experimentsusing neural networks for the probability function, showing on twotext corpora that the proposed approach significantly improves onstate-of-the-art n-gram models, and that the proposed approachallows to take advantage of longer contexts.
統計的言語モデリングの目標は、言語内の単語シーケンスの結合確率関数を学習することです。これは次元の呪いのため本質的に困難です。つまり、モデルがテストされる単語シーケンスは、トレーニング中に見られるすべての単語シーケンスとは異なる可能性があります。n-gramに基づく従来型で非常に効果的なアプローチは、トレーニング セットで見られる非常に短い重複シーケンスを連結することで一般化を実現します。私たちは、単語の分散表現を学習することで次元の呪いと戦うことを提案します。分散表現により、各トレーニング センテンスが、意味的に隣接するセンテンスの指数数についてモデルに通知できるようになります。モデルは、(1)各単語の分散表現と、(2)これらの表現で表現される単語シーケンスの確率関数を同時に学習します。一般化が得られるのは、これまでに見たことのない単語シーケンスが、すでに見たセンテンスを形成する単語に類似した単語(近くの表現があるという意味で)で構成されている場合、高い確率を得るためです。このような大規模なモデル(数百万のパラメータを持つ)を妥当な時間内にトレーニングすることは、それ自体が大きな課題です。確率関数にニューラル ネットワークを使用した実験について報告し、2つのテキスト コーパスで、提案されたアプローチが最先端のn-gramモデルを大幅に改善し、提案されたアプローチによってより長いコンテキストを活用できることを示しました。
Matching Words and Pictures
単語と画像のマッチング
We present a new approach for modeling multi-modal data sets,focusing on the specific case of segmented images with associatedtext. Learning the joint distribution of image regions and wordshas many applications. We consider in detail predicting wordsassociated with whole images (auto-annotation) and correspondingto particular image regions (region naming). Auto-annotation mighthelp organize and access large collections of images. Regionnaming is a model of object recognition as a process oftranslating image regions to words, much as one might translatefrom one language to another. Learning the relationships betweenimage regions and semantic correlates (words) is an interestingexample of multi-modal data mining, particularly because it istypically hard to apply data mining techniques to collections ofimages. We develop a number of models for the joint distributionof image regions and words, including several which explicitlylearn the correspondence between regions and words. We studymulti-modal and correspondence extensions to Hofmann’shierarchical clustering/aspect model, a translation model adaptedfrom statistical machine translation (Brown et al.), and amulti-modal extension to mixture of latent Dirichlet allocation(MoM-LDA). All models are assessed using a large collection ofannotated images of real scenes. We study in depth the difficultproblem of measuring performance. For the annotation task, we lookat prediction performance on held out data. We present threealternative measures, oriented toward different types of task.Measuring the performance of correspondence methods is harder,because one must determine whether a word has been placed on theright region of an image. We can use annotation performance as aproxy measure, but accurate measurement requires hand labeleddata, and thus must occur on a smaller scale. We show resultsusing both an annotation proxy, and manually labeled data.
私たちは、セグメント化された画像とそれに関連するテキストという特定のケースに焦点を当て、マルチモーダルデータセットをモデル化する新しいアプローチを提示します。画像領域と単語の結合分布の学習には多くの用途があります。私たちは、画像全体に関連付けられた単語(自動注釈)と特定の画像領域に対応する単語(領域名)の予測を詳細に検討します。自動注釈は、大量の画像コレクションを整理してアクセスするのに役立つ可能性があります。領域名とは、ある言語から別の言語に翻訳するのと同じように、画像領域を単語に翻訳するプロセスとしてのオブジェクト認識のモデルです。画像領域と意味的相関(単語)の関係を学習することは、マルチモーダルデータマイニングの興味深い例です。特に、データマイニング手法を画像コレクションに適用するのは通常難しいためです。私たちは、領域と単語の対応を明示的に学習するモデルを含む、画像領域と単語の結合分布のモデルをいくつか開発しました。私たちは、ホフマンの階層的クラスタリング/アスペクトモデルへのマルチモーダルおよび対応拡張、統計的機械翻訳(Brownら)から適応された翻訳モデル、潜在ディリクレ分布の混合(MoM-LDA)へのマルチモーダル拡張を研究します。すべてのモデルは、実際のシーンの注釈付き画像の大規模なコレクションを使用して評価されます。パフォーマンスを測定するという難しい問題を詳細に研究します。注釈タスクについては、保持されたデータに対する予測パフォーマンスを調べます。異なるタイプのタスクに向けた3つの代替測定法を示します。対応法のパフォーマンスの測定は、単語が画像の正しい領域に配置されているかどうかを判断する必要があるため、より困難です。注釈パフォーマンスをプロキシ測定法として使用できますが、正確な測定には手動でラベル付けされたデータが必要であり、したがって小規模で実行する必要があります。注釈プロキシと手動でラベル付けされたデータの両方を使用して結果を示します。
Kernel Methods for Relation Extraction
リレーション抽出のカーネルメソッド
We present an application of kernel methods to extractingrelations from unstructured natural language sources.We introduce kernels defined over shallow parse representations of text, anddesign efficient algorithms for computing the kernels. Weuse the devised kernels in conjunction with Support VectorMachine and Voted Perceptron learning algorithms for thetask of extracting person-affiliation andorganization-location relations from text. Weexperimentally evaluate the proposed methods and comparethem with feature-based learning algorithms, with promisingresults.
私たちは、非構造化自然言語ソースから関係を抽出するためのカーネルメソッドのアプリケーションを紹介します。テキストの浅い解析表現で定義されたカーネルを導入し、カーネルを計算するための効率的なアルゴリズムを設計します。私たちは、テキストから人、所属、組織、場所の関係を抽出するタスクのために、Support VectorMachineおよびVoted Perceptron学習アルゴリズムと組み合わせて、考案されたカーネルを使用します。提案された方法を実験的に評価し、特徴ベースの学習アルゴリズムと比較し、有望な結果をもたらします。
Word-Sequence Kernels
ワードシーケンスカーネル
We address the problem of categorising documents usingkernel-based methods such as Support Vector Machines. Since thework of Joachims (1998), there is ample experimental evidencethat SVM using the standard word frequencies as features yieldstate-of-the-art performance on a number of benchmark problems.Recently, Lodhi et al. (2002) proposed the use of stringkernels, a novel way of computing document similarity based ofmatching non-consecutive subsequences of characters. In thisarticle, we propose the use of this technique with sequences ofwords rather than characters. This approach has severaladvantages, in particular it is more efficient computationally andit ties in closely with standard linguistic pre-processingtechniques. We present some extensions to sequence kernels dealingwith symbol-dependent and match-dependent decay factors, andpresent empirical evaluations of these extensions on theReuters-21578 datasets.
私たちは、Support Vector Machinesのようなカーネルベースの方法を使用してドキュメントを分類する問題に対処します。ヨアヒムス(1998)の研究以来、SVMが標準語の頻度を特徴として使用すると、多くのベンチマーク問題で最先端のパフォーマンスが得られるという十分な実験的証拠があります。最近、Lodhiら(2002)は、文字列カーネルの使用を提案しました。これは、文字列の一致しない部分列に基づいてドキュメントの類似性を計算する新しい方法です。この記事では、この手法を文字ではなく単語のシーケンスで使用することを提案します。このアプローチにはいくつかの利点がありますが、特に計算効率が高く、標準的な言語前処理技術と密接に関連しています。シンボル依存およびマッチ依存の崩壊因子を扱うシーケンスカーネルのいくつかの拡張を提示し、Reuters-21578データセットでこれらの拡張の実証的評価を提示します。
A Family of Additive Online Algorithms for Category Ranking
カテゴリランキングのための付加オンラインアルゴリズムのファミリー
We describe a new family of topic-ranking algorithms for multi-labeleddocuments. The motivation for the algorithms stem from recent advancesin online learning algorithms. The algorithms are simple to implementand are also time and memory efficient. We provide a unified analysisof the family of algorithms in the mistake bound model. We then discussexperiments with the proposed family of topic-ranking algorithms on theReuters-21578 corpus and the new corpus released by Reuters in 2000.On both corpora, the algorithms we present achievestate-of-the-artresults and outperforms topic-ranking adaptations of Rocchio’s algorithmand of the Perceptron algorithm.
私たちは、マルチラベルドキュメント用のトピックランキングアルゴリズムの新しいファミリーについて説明します。アルゴリズムの動機は、オンライン学習アルゴリズムの最近の進歩に由来しています。アルゴリズムは実装が簡単で、時間とメモリの効率も優れています。ミスバウンドモデルにおけるアルゴリズムファミリーの統一的な分析を提供します。次に、Reuters-21578コーパスと2000年にロイターがリリースした新しいコーパスで、提案されたトピックランキングアルゴリズムのファミリーを使用した実験について説明します。両方のコーパスで、私たちが提示するアルゴリズムは最先端の結果を達成し、RocchioのアルゴリズムとPerceptronアルゴリズムのトピックランキングの適応を上回っています。
Introduction to the Special Issue on Machine Learning Methods for Text and Images
テキストと画像の機械学習手法に関する特集のご紹介
Latent Dirichlet Allocation
潜在ディリクレ配分
We describe latent Dirichlet allocation (LDA), a generative probabilistic model for collections of discrete data such as text corpora. LDA is a three-level hierarchical Bayesian model, in which each item of a collection is modeled as a finite mixture over an underlying set of topics. Each topic is, in turn, modeled as an infinite mixture over an underlying set of topic probabilities. In the context of text modeling, the topic probabilities provide an explicit representation of a document. We present efficient approximate inference techniques based on variational methods and an EM algorithm for empirical Bayes parameter estimation. We report results in document modeling, text classification, and collaborative filtering, comparing to a mixture of unigrams model and the probabilistic LSI model.
私たちは、テキストコーパスなどの離散データのコレクションの生成確率モデルである潜在ディリクレ割り当て(LDA)について説明します。LDAは3レベルの階層ベイジアン モデルであり、コレクションの各項目は、基になる一連のトピックに対する有限の混合物としてモデル化されます。各トピックは、基になるトピック確率のセットに対する無限の混合物としてモデル化されます。テキストモデリングのコンテキストでは、トピックの確率はドキュメントの明示的な表現を提供します。変分法に基づく効率的な近似推論手法と、経験的ベイズパラメータ推定のためのEMアルゴリズムを提示します。ドキュメントモデリング、テキスト分類、および協調フィルタリングの結果を報告し、ユニグラムモデルと確率的LSIモデルの組み合わせと比較します。
Ultraconservative Online Algorithms for Multiclass Problems
多クラス問題に対する超保守的なオンラインアルゴリズム
In this paper we study a paradigm to generalize online classificationalgorithms for binary classification problems to multiclass problems.The particular hypotheses we investigate maintain one prototype vectorper class. Given an input instance, a multiclass hypothesis computes asimilarity-score between each prototype and the input instance and setsthe predicted label to be the index of the prototype achieving the highestsimilarity. To design and analyze the learning algorithms in this paper weintroduce the notion of ultraconservativeness. Ultraconservativealgorithms are algorithms that update only the prototypes attainingsimilarity-scores which are higher than the score of the correct label’sprototype. We start by describing a family of additive ultraconservativealgorithms where each algorithm in the family updates its prototypes byfinding a feasible solution for a set of linear constraints that depend onthe instantaneous similarity-scores. We then discuss a specific onlinealgorithm that seeks a set of prototypes which have a small norm. Theresulting algorithm, which we term MIRA (for Margin Infused RelaxedAlgorithm) is ultraconservative as well. We derive mistake boundsfor all the algorithms and provide further analysis of MIRA using ageneralized notion of the margin for multiclass problems. We discussthe form the algorithms take in the binary case and show that all thealgorithms from the first family reduce to the Perceptron algorithm whileMIRA provides a new Perceptron-like algorithm with a margin-dependentlearning rate. We then return to multiclass problems and describe ananalogous multiplicative family of algorithms with corresponding mistakebounds. We end the formal part by deriving and analyzing a multiclassversion of Li and Long’s ROMMA algorithm. We conclude with a discussionof experimental results that demonstrate the merits of our algorithms.
この論文では、バイナリ分類問題に対するオンライン分類アルゴリズムをマルチクラス問題に一般化するパラダイムを研究します。私たちが調査する特定の仮説は、クラスごとに1つのプロトタイプ ベクトルを保持します。入力インスタンスが与えられると、マルチクラス仮説は各プロトタイプと入力インスタンス間の類似度スコアを計算し、予測ラベルを最も高い類似度を達成したプロトタイプのインデックスに設定します。この論文の学習アルゴリズムを設計および分析するために、超保守性の概念を導入します。超保守アルゴリズムは、正しいラベルのプロトタイプのスコアよりも高い類似度スコアを達成したプロトタイプのみを更新するアルゴリズムです。まず、瞬間的な類似度スコアに依存する一連の線形制約の実行可能なソリューションを見つけることによって、ファミリ内の各アルゴリズムがプロトタイプを更新する、加法的超保守アルゴリズムのファミリについて説明します。次に、小さなノルムを持つプロトタイプのセットを探す特定のオンライン アルゴリズムについて説明します。結果として得られるアルゴリズムは、MIRA (Margin Infused Relaxed Algorithm)と名付けられており、これも超保守的です。すべてのアルゴリズムのミス境界を導出し、マルチクラス問題に対するマージンの一般化された概念を使用してMIRAをさらに分析します。バイナリ ケースでアルゴリズムが取る形式について説明し、最初のファミリのすべてのアルゴリズムがパーセプトロン アルゴリズムに簡約される一方で、MIRAはマージン依存の学習率を持つ新しいパーセプトロンのようなアルゴリズムを提供することを示します。次に、マルチクラス問題に戻り、対応するミス境界を持つ類似の乗法アルゴリズム ファミリについて説明します。正式な部分は、LiとLongのROMMAアルゴリズムのマルチクラス バージョンを導出して分析することで終了します。最後に、アルゴリズムのメリットを示す実験結果について説明します。
Policy Search using Paired Comparisons
対応比較を使用したポリシー検索
Direct policy search is a practical way to solve reinforcementlearning (RL) problems involving continuous state and actionspaces. The goal becomes finding policy parameters that maximize anoisy objective function. The Pegasus method converts thisstochastic optimization problem into a deterministic one, by usingfixed start states and fixed random number sequences for comparingpolicies (Ng and Jordan, 2000). We evaluate Pegasus, and new pairedcomparison methods, using the mountain car problem, and adifficult pursuer-evader problem. We conclude that: (i) pairedtests can improve performance of optimization procedures; (ii)several methods are available to reduce the ‘overfitting’ effectfound with Pegasus; (iii) adapting the number of trials used foreach comparison yields faster learning; (iv) pairing also helpsstochastic search methods such as differential evolution.
直接方策探索は、連続状態と行動空間を含む強化学習(RL)問題を解く実用的な方法です。目標は、アノイジー目的関数を最大化する方策パラメータを見つけることです。Pegasus法は、固定開始状態と固定乱数列を比較ポリシーに使用することにより、この確率的最適化問題を決定論的問題に変換します(Ng and Jordan, 2000)。ペガサスと新しい対の比較方法、マウンテンカー問題、および難解な追跡者回避問題を使用して評価します。私たちは、(i)pairedtestsは最適化手順のパフォーマンスを向上させることができると結論付けます。(ii)ペガサスに見られる「過適合」効果を減らすためにいくつかの方法が利用可能であること。(iii)各比較に使用される試行回数を適応させることで、より迅速な学習が得られます。(iv)ペアリングは、微分進化などの確率的探索法にも役立ちます。
Learning to Construct Fast Signal Processing Implementations
高速信号処理実装の構築の学習
A single signal processing algorithm can be represented by manymathematically equivalent formulas. However, when these formulas areimplemented in code and run on real machines, they have very differentruntimes. Unfortunately, it is extremely difficult to model this broadperformance range. Further, the space of formulas for real signaltransforms is so large that it is impossible to search it exhaustivelyfor fast implementations. We approach this search question as a controllearning problem. We present a new method for learning to generatefast formulas, allowing us to intelligently search through only themost promising formulas. Our approach incorporates signal processingknowledge, hardware features, and formula performance data to learn toconstruct fast formulas. Our method learns from performance data for afew formulas of one size and then can construct formulas that will havethe fastest runtimes possible across many sizes.
1つの信号処理アルゴリズムは、数学的に等価な多数式で表すことができます。ただし、これらの数式をコードで実装し、実際のマシンで実行すると、ランタイムは大きく異なります。残念ながら、この広範な性能範囲をモデル化することは非常に困難です。さらに、実信号変換の式の空間は非常に大きいため、高速な実装のために網羅的に検索することは不可能です。この探索問題には、制御学習問題としてアプローチします。私たちは、最も有望な式だけをインテリジェントに検索できるように、高速な式を生成することを学ぶための新しい方法を提示します。当社のアプローチには、信号処理の知識、ハードウェア機能、およびフォーミュラ性能データが組み込まれており、高速フォーミュラの構築を学習します。この手法は、1つのサイズのいくつかの数式のパフォーマンス データから学習し、多くのサイズで可能な限り最速の実行時間を持つ数式を構築できます。
Stopping Criterion for Boosting-Based Data Reduction Techniques: from Binary to Multiclass Problem
ブースティングベースのデータ削減手法の停止基準:バイナリ問題から多クラス問題へ
So far, boosting has been used to improve the quality of moderately accurate learning algorithms, byweighting and combining many of their weak hypotheses into a final classifier with theoreticallyhigh accuracy. In a recent work (Sebban, Nock and Lallich, 2001), we have attempted to adapt boostingproperties to data reduction techniques. In this particular context, the objective was not only to improvethe success rate, but also to reduce the time and space complexities due to the storage requirements ofsome costly learning algorithms, such as nearest-neighborclassifiers. In that framework, each weak hypothesis, which is usually built and weighted from the learning set, is replaced by asingle learning instance. The weight given by boosting defines in that case the relevance of the instance,and a statistical test allows one to decide whether it can be discarded without damaging further classificationtasks. In Sebban, Nock and Lallich (2001), we addressed problems with two classes. It is the aim of thepresent paper to relax the class constraint, and extend our contribution to multiclass problems. Beyonddata reduction, experimental results are also provided on twenty-three datasets, showing the benefits thatour boosting-derived weighting rule brings to weighted nearest neighbor classifiers.
これまで、ブースティングは、中程度の精度の学習アルゴリズムの品質を向上させるために使用され、それらの弱い仮説の多くを重み付けして結合し、理論的に高い精度の最終分類器を作成してきました。最近の研究(Sebban、Nock、Lallich、2001)では、ブースティングの特性をデータ削減手法に適応させようと試みました。この特定のコンテキストでは、目標は成功率を向上させるだけでなく、最近傍分類器などの一部のコストの高い学習アルゴリズムのストレージ要件による時間と空間の複雑さを軽減することでした。そのフレームワークでは、通常学習セットから構築され重み付けされる各弱い仮説は、単一の学習インスタンスに置き換えられます。ブースティングによって与えられた重みは、その場合、インスタンスの関連性を定義し、統計テストによって、以降の分類タスクに悪影響を与えることなくインスタンスを破棄できるかどうかを判断できます。Sebban、Nock、Lallich (2001)では、2つのクラスの問題を扱いました。本論文の目的は、クラス制約を緩和し、マルチクラス問題への貢献を拡大することです。データ削減以外にも、23個のデータセットで実験結果が提供され、ブースティングから導出された重み付けルールが重み付けされた最近傍分類器にもたらす利点が示されています。
Finding the Most Interesting Patterns in a Database Quickly by Using Sequential Sampling
シーケンシャルサンプリングを使用してデータベース内の最も興味深いパターンをすばやく見つける
Many discovery problems, e.g. subgroup or association rule discovery, cannaturally be cast as n-best hypotheses problems where the goal is to findthe n hypotheses from a given hypothesis space that score best according toa certain utility function. We present a sampling algorithm that solves thisproblem by issuing a small number of database queries while guaranteeingprecise bounds on the confidence and quality of solutions. Known samplingapproaches have treated single hypothesis selection problems, assuming thatthe utility is the average (over the examples) of some function — which isnot the case for many frequently used utility functions. We show that ouralgorithm works for all utilities that can be estimated with bounded error. Weprovide these error bounds and resulting worst-case sample bounds for some ofthe most frequently used utilities, and prove that there is no samplingalgorithm for a popular class of utility functions that cannot be estimatedwith bounded error. The algorithm is sequential in the sense that it startsto return (or discard) hypotheses that already seem to be particularly good(or bad) after a few examples. Thus, the algorithm is almost always faster thanits worst-case bounds.
サブグループや関連ルールの発見など、多くの発見問題は、当然のことながら、n個のベスト仮説問題として表すことができます。その目的は、特定の効用関数に従って、与えられた仮説空間から最もスコアの高いn個の仮説を見つけることです。私たちは、少数のデータベース クエリを発行することで、ソリューションの信頼性と品質の正確な境界を保証しながらこの問題を解決するサンプリング アルゴリズムを紹介します。既知のサンプリング アプローチは、単一仮説選択問題を扱い、効用が何らかの関数の平均(例全体)であると仮定していましたが、これは頻繁に使用される多くの効用関数には当てはまりません。私たちは、私たちのアルゴリズムが、制限された誤差で推定できるすべての効用に対して機能することを示します。私たちは、最も頻繁に使用される効用のいくつかについて、これらの誤差境界と、その結果として生じる最悪のサンプル境界を提供し、制限された誤差で推定できない一般的な効用関数のクラスに対してはサンプリング アルゴリズムが存在しないことを証明します。このアルゴリズムは、いくつかの例の後で、すでに特に優れている（または悪い）と思われる仮説を返す（または破棄する）という意味で順次的です。したがって、このアルゴリズムはほとんどの場合、最悪のケースの境界よりも高速です。
Lyapunov Design for Safe Reinforcement Learning
安全な強化学習のためのLyapunov設計
Lyapunov design methods are used widely in control engineering todesign controllers that achieve qualitative objectives, such asstabilizing a system or maintaining a system’s state in a desiredoperating range. We propose a method for constructing safe, reliablereinforcement learning agents based on Lyapunov design principles. Inour approach, an agent learns to control a system by switching among anumber of given, base-level controllers. These controllers aredesigned using Lyapunov domain knowledge so that any switchingpolicy is safe and enjoys basic performance guarantees. Our approachthus ensures qualitatively satisfactory agent behavior for virtuallyany reinforcement learning algorithm and at all times, including whilethe agent is learning and taking exploratory actions. We demonstratethe process of designing safe agents for four different controlproblems. In simulation experiments, we find that our theoreticallymotivated designs also enjoy a number of practical benefits, includingreasonable performance initially and throughout learning, andaccelerated learning.
リャプノフ設計法は、システムの安定化やシステムの状態を望ましい動作範囲内に維持するなど、定性的な目的を達成するコントローラを設計するために、制御工学で広く使用されています。私たちは、リャプノフ設計原理に基づいて、安全で信頼性の高い強化学習エージェントを構築する方法を提案します。私たちのアプローチでは、エージェントは、いくつかの与えられた基本レベルのコントローラを切り替えることで、システムを制御することを学習します。これらのコントローラは、リャプノフのドメイン知識を使用して設計されているため、切り替えポリシーは安全であり、基本的なパフォーマンスが保証されます。したがって、私たちのアプローチは、エージェントが学習して探索的なアクションを実行している間も含め、事実上すべての強化学習アルゴリズムに対して、常に定性的に満足のいくエージェントの動作を保証します。私たちは、4つの異なる制御問題に対して安全なエージェントを設計するプロセスを示します。シミュレーション実験では、私たちの理論に基づいた設計は、学習初期および学習全体を通じて妥当なパフォーマンス、および学習の加速など、多くの実用的な利点も享受できることがわかりました。
Some Greedy Learning Algorithms for Sparse Regression and Classification with Mercer Kernels
マーサーカーネルによるスパース回帰と分類のための貪欲学習アルゴリズム
We present greedy learning algorithms for building sparse nonlinear regression and classification models from observational data using Mercer kernels. Our objective is to develop efficient numerical schemes for reducing the training and runtime complexities of kernel-based algorithms applied to largedatasets. In the spirit of Natarajan’s greedy algorithm (Natarajan, 1995),we iteratively minimize the L2$ loss function subject to a specified constraint on the degree of sparsity required of the final model or till a specified stopping criterion is reached. We discuss various greedy criteria for basis selection and numerical schemes for improving the robustness and computational efficiency. Subsequently, algorithms based on residual minimization and thin QR factorization are presented for constructing sparse regression and classification models. During thecourse of the incremental model construction, the algorithms are terminatedusing model selection principles such as the minimum descriptive length (MDL) and Akaike’s informationcriterion (AIC). Finally, experimental results onbenchmark data are presented to demonstrate the competitiveness of the algorithms developed in this paper.
私たちは、マーサーカーネルを使用して観測データからスパース非線形回帰および分類モデルを構築するための貪欲学習アルゴリズムを紹介します。私たちの目的は、大規模なデータセットに適用されるカーネルベースのアルゴリズムのトレーニングと実行時の複雑さを軽減するための効率的な数値スキームを開発することです。Natarajanの貪欲アルゴリズム(Natarajan、1995)の精神に則り、最終モデルに必要なスパース度の指定された制約に従って、または指定された停止基準に達するまで、L2$損失関数を反復的に最小化します。基底選択のためのさまざまな貪欲基準と、堅牢性と計算効率を向上させる数値スキームについて説明します。その後、残差最小化と薄いQR分解に基づくアルゴリズムを、スパース回帰および分類モデルの構築に使用します。増分モデル構築の過程で、最小記述長(MDL)や赤池の情報量基準(AIC)などのモデル選択原則を使用してアルゴリズムを終了します。最後に、本論文で開発されたアルゴリズムの競争力を実証するために、ベンチマーク データに関する実験結果を示します。
Coupled Clustering: A Method for Detecting Structural Correspondence
結合クラスタリング:構造的対応を検出するための手法
This paper proposes a new paradigm and a computational framework for revealing equivalencies (analogies) between sub-structures of distinct composite systems that are initially represented by unstructured data sets. For this purpose, we introduce and investigate a variant of traditional data clustering, termed coupled clustering, which outputs a configuration of corresponding subsets of two such representative sets. We apply our method to synthetic as well as textual data. Its achievements in detecting topical correspondences between textual corpora are evaluated through comparison to performance of human experts.
この論文では、最初は非構造化データセットによって表される異なる複合システムの下位構造間の等価性(類似性)を明らかにするための新しいパラダイムと計算フレームワークを提案します。この目的のために、従来のデータクラスタリングの変形である結合クラスタリングを導入し、調査します。これは、そのような2つの代表的なセットの対応するサブセットの構成を出力します。この手法を合成データだけでなく、テキストデータにも適用します。テクストコーパス間の局所的な対応を検出することにおけるその成果は、人間の専門家のパフォーマンスとの比較を通じて評価されます。
The Set Covering Machine
セットカバーマシン
We extend the classical algorithms of Valiant and Haussler forlearning compact conjunctions and disjunctions of Booleanattributes to allow features that are constructed from the dataand to allow a trade-off between accuracy and complexity. Theresult is a general-purpose learning machine, suitable forpractical learning tasks, that we call the set coveringmachine. We present a version of the set covering machine thatuses data-dependent balls for its set of features andcompare its performance with the support vector machine. Byextending a technique pioneered by Littlestone and Warmuth, webound its generalization error as a function of the amount of datacompression it achieves during training. In experiments withreal-world learning tasks, the bound is shown to be extremelytight and to provide an effective guide for model selection.
私たちは、Boolean属性のコンパクトな接続詞と分離を学習するためのValiantとHausslerの古典的なアルゴリズムを拡張して、データから構築される特徴を可能にし、精度と複雑さの間のトレードオフを可能にします。その結果、実用的な学習タスクに適した汎用学習マシンが誕生し、セットカバーマシンと呼んでいます。私たちは、その機能のセットにデータ依存のボールを使用し、そのパフォーマンスをサポートベクターマシンと比較するセットカバーマシンのバージョンを提示します。LittlestoneとWarmuthによって開拓された手法を拡張することにより、その一般化エラーをトレーニング中に達成するデータ圧縮量の関数としてバインドしました。実世界の学習タスクを使用した実験では、境界が非常に厳密であり、モデル選択の効果的なガイドを提供することが示されています。
The Representational Power of Discrete Bayesian Networks
離散ベイジアンネットワークの表現力
One of the most important fundamental properties of Bayesian networks is the representational power, reflecting what kind of functions they can or cannot represent. In this paper, we establish an association between the structural complexity of Bayesian networks and their representational power. We use the maximum number of nodes’ parents as the measure for the structural complexity of Bayesian networks,and the maximum XOR contained in a target function as the measure for the function complexity.A representational upper bound is establishedand proved. Roughly speaking, discrete Bayesian networks with each node having at most k parents cannot represent any function containing (k+1)-XORs. Our theoretical results help us to gaina deeper understanding on the capacities and limitations of Bayesian networks.
ベイジアンネットワークの最も重要な基本特性の1つは、表現できる機能と表現できない機能の種類を反映する表現力です。この論文では、ベイジアンネットワークの構造的複雑さとその表現力との間の関連性を確立します。ベイジアン ネットワークの構造的複雑さの尺度としてノードの親の最大数を使用し、関数の複雑さの尺度としてターゲット関数に含まれる最大XORを使用します。表象的な上限が確立され、証明されます。大まかに言えば、各ノードが最大でk個の親を持つ離散ベイジアン ネットワークは、(k+1)-XORを含む関数を表すことはできません。私たちの理論的結果は、ベイジアンネットワークの能力と限界についてより深い理解を得るのに役立ちます。
Learning Probabilistic Models of Link Structure
リンク構造の確率モデルの学習
Most real-world data is heterogeneous and richly interconnected.Examples include the Web, hypertext, bibliometric data andsocial networks.In contrast, moststatistical learning methods work with “flat” data representations,forcing us to convert our data into a form that loses much of thelink structure.The recently introduced framework ofprobabilistic relational models (PRMs) embraces the object-relationalnature of structured data by capturing probabilistic interactions between attributes of related entities. In this paper, weextend this framework by modeling interactions between the attributesand the link structure itself. An advantage of our approach is a unified generative model forboth content and relational structure.We propose two mechanisms forrepresenting a probabilistic distribution over link structures:reference uncertainty and existence uncertainty. We describe the appropriate conditions forusing each model and present learning algorithms for each. We presentexperimental results showing that the learned models can be used topredict link structure and, moreover, the observed linkstructure can be used to provide better predictions for the attributesin the model.
現実世界のデータのほとんどは、異種であり、相互に密接に関連しています。例としては、Web、ハイパーテキスト、計量書誌データ、ソーシャル ネットワークなどがあります。一方、統計学習法のほとんどは「フラット」なデータ表現で動作するため、リンク構造の多くを失った形式にデータを変換する必要があります。最近導入された確率関係モデル(PRM)のフレームワークは、関連するエンティティの属性間の確率的な相互作用を捉えることで、構造化データのオブジェクト リレーショナルな性質を取り入れています。この論文では、属性とリンク構造自体の間の相互作用をモデル化することで、このフレームワークを拡張します。このアプローチの利点は、コンテンツと関係構造の両方に対して統一された生成モデルであることです。リンク構造上の確率分布を表す2つのメカニズム、参照の不確実性と存在の不確実性を提案します。各モデルを使用するための適切な条件を説明し、それぞれの学習アルゴリズムを紹介します。学習したモデルを使用してリンク構造を予測できること、さらに、観察されたリンク構造を使用してモデル内の属性をより適切に予測できることを示した実験結果を紹介します。
Multiple-Instance Learning of Real-Valued Data
実価値データの複数インスタンス学習
The multiple-instance learning model has received much attentionrecently with a primary application area being that of drug activityprediction. Most prior work on multiple-instance learning has been forconcept learning, yet for drug activityprediction, the label is a real-valued affinity measurement giving thebinding strength. We present extensions ofk-nearest neighbors (k-NN), Citation-kNN, and the diverse density algorithm for the real-valuedsetting and study their performance on Boolean andreal-valued data. We also provide a method for generating chemicallyrealistic artificial data.
マルチインスタンス学習モデルは最近大きな注目を集めており、主な応用分野は薬物活動予測の分野です。マルチインスタンス学習に関する先行研究のほとんどは、概念学習のためのものでしたが、薬物活性予測の場合、ラベルは結合強度を与える実数値の親和性測定です。k-最近傍(k-NN)、Citation-kNN、および実数値設定の多様な密度アルゴリズムの拡張を提示し、ブール値データと実数値データでのパフォーマンスを調査します。また、化学的に現実的な人工データを生成する手法も提供しています。
Efficient Algorithms for Decision Tree Cross-validation
デシジョンツリーのクロスバリデーションのための効率的なアルゴリズム
Cross-validation is a useful and generally applicable techniqueoften employed in machine learning, including decisiontree induction. An important disadvantage of straightforward implementationof the technique is its computational overhead. In this paper we show that, for decision trees, the computational overhead of cross-validation can be reduced significantly by integrating thecross-validation with the normal decision tree induction process.We discuss how existing decision tree algorithms can be adapted to thisaim, and provide an analysis of the speedups these adaptationsmay yield. We identify a number of parameters that influence the obtainablespeedups, and validate and refine our analysis with experiments on a variety of data sets with two different implementations. Besides cross-validation, we also briefly explore the usefulness of these techniquesfor bagging. We conclude with some guidelines concerning when theseoptimizations should be considered.
クロスバリデーションは、デシジョンツリー帰納法など、機械学習でよく採用される有用で一般的に適用可能な手法です。この手法の簡単な実装の重要な欠点は、計算オーバーヘッドです。この論文では、決定木の場合、交差検証を通常の決定木誘導プロセスと統合することで、交差検証の計算オーバーヘッドを大幅に削減できることを示します。既存の決定木アルゴリズムをこの目的にどのように適応できるかを議論し、これらの適応がもたらす可能性のある高速化の分析を提供します。私たちは、得られるスピードアップに影響を与えるいくつかのパラメータを特定し、2つの異なる実装を持つさまざまなデータセットの実験で分析を検証し、改良します。クロスバリデーションに加えて、これらの手法の袋詰めの有用性についても簡単に説明します。最後に、これらの最適化をいつ考慮すべきかに関するいくつかのガイドラインを示します。
Special Issue on the Eighteenth International Conference on Machine Learning (ICML2001)
第18回機械学習国際会議(ICML2001)特集号
Cluster Ensembles — A Knowledge Reuse Framework for Combining Multiple Partitions
Cluster Ensembles — 複数のパーティションを組み合わせるためのナレッジ再利用フレームワーク
This paper introduces the problem of combining multiple partitioningsof a set of objects into a single consolidated clustering without accessing the features or algorithms that determined thesepartitionings. We first identify several application scenarios forthe resultant ‘knowledge reuse’ framework that we call cluster ensembles.The cluster ensemble problem is then formalized as a combinatorialoptimization problem in terms of shared mutual information. Inaddition to a direct maximization approach, we propose three effectiveand efficient techniques for obtaining high-quality combiners(consensus functions). The first combiner induces a similaritymeasure from the partitionings and then reclusters the objects. Thesecond combiner is based on hypergraph partitioning. The third onecollapses groups of clusters into meta-clusters which then compete foreach object to determine the combined clustering. Due to the lowcomputational costs of our techniques, it is quite feasible to use asupra-consensus function that evaluates all three approaches againstthe objective function and picks the best solution for a givensituation.We evaluate the effectiveness of cluster ensembles in threequalitatively different application scenarios: (i) where the originalclusters were formed based on non-identical sets of features, (ii)where the original clustering algorithms worked on non-identical setsof objects, and (iii) where a common data-set is used and the mainpurpose of combining multiple clusterings is to improve the quality androbustness of the solution. Promising results are obtained in allthree situations for synthetic as well as real data-sets.
この論文では、オブジェクト セットの複数のパーティションを、これらのパーティションを決定した機能やアルゴリズムにアクセスせずに、単一の統合クラスタリングに結合する問題を紹介します。まず、クラスター アンサンブルと呼ばれる、結果として得られる「知識再利用」フレームワークのいくつかのアプリケーション シナリオを特定します。次に、クラスター アンサンブルの問題を、共有相互情報の観点から組み合わせ最適化問題として形式化します。直接最大化アプローチに加えて、高品質のコンバイナ(コンセンサス関数)を取得するための3つの効果的で効率的な手法を提案します。最初のコンバイナは、パーティションから類似性尺度を誘導し、オブジェクトを再クラスタリングします。2番目のコンバイナは、ハイパーグラフ パーティションに基づいています。3番目のコンバイナは、クラスターのグループをメタ クラスターに縮小し、各オブジェクトを競合させて結合クラスタリングを決定します。我々の技術の計算コストが低いため、目的関数に対して3つのアプローチすべてを評価し、特定の状況に最適なソリューションを選択する超コンセンサス関数を使用することは十分に可能です。私たちは、質的に異なる3つのアプリケーション シナリオでクラスター アンサンブルの有効性を評価します。(i)元のクラスターが同一ではない機能セットに基づいて形成された場合、(ii)元のクラスタリング アルゴリズムが同一ではないオブジェクト セットで機能した場合、(iii)共通のデータ セットが使用され、複数のクラスタリングを組み合わせる主な目的がソリューションの品質と堅牢性を向上させることである場合です。これら3つの状況すべてで、合成データ セットと実際のデータ セットの両方で有望な結果が得られました。
A Robust Minimax Approach to Classification
分類に対する堅牢なミニマックスアプローチ
When constructing a classifier, the probability of correctclassification of future data points should be maximized. Weconsider a binary classification problem where the mean andcovariance matrix of each class are assumed to be known. Nofurther assumptions are made with respect to the class-conditionaldistributions. Misclassification probabilities are then controlledin a worst-case setting: that is, under all possible choices ofclass-conditional densities with given mean and covariance matrix,we minimize the worst-case (maximum) probability ofmisclassification of future data points. For a linear decisionboundary, this desideratum is translated in a very direct way intoa (convex) second order cone optimization problem, with complexitysimilar to a support vector machine problem. The minimax problemcan be interpreted geometrically as minimizing the maximum of theMahalanobis distances to the two classes. We address the issue ofrobustness with respect to estimation errors (in the means andcovariances of the classes) via a simple modification of the inputdata. We also show how to exploit Mercer kernels in this settingto obtain nonlinear decision boundaries, yielding a classifierwhich proves to be competitive with current methods, includingsupport vector machines. An important feature of this method isthat a worst-case bound on the probability of misclassification offuture data is always obtained explicitly.
分類器を構築する際、将来のデータ ポイントを正しく分類する確率を最大化する必要があります。各クラスの平均と共分散行列が既知であると仮定するバイナリ分類問題を検討します。クラス条件付き分布に関しては、これ以上の仮定は行いません。次に、誤分類確率を最悪の設定で制御します。つまり、平均と共分散行列が与えられたクラス条件付き密度のあらゆる可能な選択の下で、将来のデータ ポイントの誤分類の最悪(最大)確率を最小化します。線形決定境界の場合、この要件は、サポート ベクター マシンの問題に類似した複雑さを持つ(凸) 2次円錐最適化問題に非常に直接的に変換されます。ミニマックス問題は、2つのクラスへのマハラノビス距離の最大値の最小化として幾何学的に解釈できます。入力データの簡単な変更によって、推定誤差(クラスの平均と共分散)に関する堅牢性の問題を解決します。また、この設定でMercerカーネルを活用して非線形決定境界を取得し、サポート ベクター マシンを含む現在の方法と競合できる分類器を生成する方法も示します。この方法の重要な特徴は、将来のデータの誤分類の確率に関する最悪のケースの境界が常に明示的に得られることです。
Optimal Structure Identification With Greedy Search
Greedy Searchによる最適構造同定
In this paper we prove the so-called “Meek Conjecture”. Inparticular, we show that if a DAG H is an independence map ofanother DAG G, then there exists a finite sequence of edgeadditions and covered edge reversals in G such that (1) after eachedge modification H remains an independence map of G and (2)after all modifications G =H. As shown by Meek (1997), thisresult has an important consequence for Bayesian approaches tolearning Bayesian networks from data: in the limit of large samplesize, there exists a two-phase greedy search algorithmthat—when applied to a particular sparsely-connected searchspace—provably identifies a perfect map of the generativedistribution if that perfect map is a DAG. We provide a newimplementation of the search space, using equivalence classes asstates, for which all operators used in the greedy search can bescored efficiently using local functions of the nodes in thedomain. Finally, using both synthetic and real-world datasets, wedemonstrate that the two-phase greedy approach leads to good solutionswhen learning with finite sample sizes.
この論文では、いわゆる「ミーク予想」を証明します。特に、DAG Hが別のDAG Gの独立マップである場合、(1)各エッジ変更後もHはGの独立マップのままであり、(2)すべての変更後もG =Hとなるような、Gにおけるエッジ追加とカバーされたエッジ反転の有限シーケンスが存在することを示します。Meek (1997)で示されているように、この結果は、データからベイジアン ネットワークを学習するベイジアン アプローチにとって重要な結果をもたらします。つまり、サンプル サイズが大きいという制限では、特定の疎結合検索空間に適用すると、その完全マップがDAGである場合に、生成分布の完全マップを証明できる2段階の貪欲検索アルゴリズムが存在します。私たちは、同値クラスを状態として使用して、貪欲検索で使用されるすべての演算子をドメイン内のノードのローカル関数を使用して効率的にスコアリングできる、検索空間の新しい実装を提供します。最後に、合成データセットと現実世界のデータセットの両方を使用して、有限のサンプル サイズで学習する場合、2段階の貪欲アプローチが優れたソリューションにつながることを実証します。
On Boosting with Polynomially Bounded Distributions
多項式有界分布によるブースティングについて
We construct a framework which allows analgorithm to turn the distributions produced by some boostingalgorithms into polynomially smooth distributions (w.r.t. the PACoracle’s distribution), with minimal performance loss.Further, we explore the case of Freund and Schapire’s AdaBoost algorithm,bounding its distributions to polynomially smooth. The main advantageof AdaBoost over other boosting techniques is that it is adaptive, i.e.,it is able to take advantage of weak hypotheses that are more accuratethan it was assumed a priori. We show that the feature ofadaptiveness is preserved and improved by our technique.Our scheme allows the execution of AdaBoost in the on-line boosting mode (i.e.,to perform boosting “by filtering”). Executed this way (andpossessing the quality of smoothness), now AdaBoost may be efficientlyapplied to a wider range of learning problems than before.In particular, we demonstrate AdaBoost’s application to the task ofDNF learning using membership queries. This application resultsin an algorithm that chooses the number of boosting iterationsadaptively, and, consequently, adaptively chooses the size of theproduced final hypothesis. This answers affirmatively a questionposed by Jackson.
私たちは、いくつかのブースティング アルゴリズムによって生成された分布を、パフォーマンスの損失を最小限に抑えながら、多項式的に滑らかな分布(PACoracleの分布に対して)に変換するアルゴリズムを可能にするフレームワークを構築します。さらに、FreundとSchapireのAdaBoostアルゴリズムのケースを調査し、その分布を多項式的に滑らかなものに制限します。他のブースティング手法に対するAdaBoostの主な利点は、適応性があることです。つまり、事前に想定されていたよりも正確な弱い仮説を活用できます。私たちは、適応性の特徴が我々の手法によって維持され、改善されることを示します。我々のスキームでは、オンライン ブースティング モードでAdaBoostを実行できます(つまり、「フィルタリングによって」ブースティングを実行します)。このように実行され(かつ滑らかさも備えているため)、AdaBoostは以前よりも幅広い学習問題に効率的に適用できるようになりました。特に、メンバーシップ クエリを使用したDNF学習タスクへのAdaBoostの適用を示します。この適用により、ブースティング反復回数を適応的に選択し、その結果、生成される最終仮説のサイズを適応的に選択するアルゴリズムが実現します。これは、Jacksonが提起した質問に肯定的に答えています。
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
RademacherとGaussの複雑さ:リスク境界と構造的結果
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and Gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes. We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.
私たちは、関数クラスの複雑さに関する特定のデータ依存推定値(RademacherおよびGaussian complexities)の使用を調査します。決定理論的な設定では、これらの複雑さの観点から一般的なリスク限界を証明します。基底クラスの関数の組み合わせとして表現できる関数クラスを検討し、そのような関数クラスのラーデマッハとガウスの複雑さを基底クラスの複雑さの観点から制限する方法を示します。これらの手法を、デシジョンツリー、ニューラルネットワーク、およびサポートベクターマシンのデータ依存リスク境界を見つけるための適用例を挙げます。
Limitations of Learning Via Embeddings in Euclidean Half Spaces
ユークリッド半空間への埋め込みによる学習の限界
The notion of embedding a class of dichotomies in a class of linearhalf spaces is central to the support vector machines paradigm.We examine the question of determining the minimal Euclidean dimensionand the maximal margin that can be obtained when the embedded classhas a finite VC dimension.We show that an overwhelming majority of the family of finite conceptclasses of any constant VC dimension cannot be embedded inlow-dimensional half spaces. (In fact, we show that the Euclideandimension must be almost as high as the size of the instance space.)We strengthen this result even further by showing that an overwhelmingmajority of the family of finite concept classes of any constant VCdimension cannot be embedded in half spaces (of arbitrarily highEuclidean dimension) with a large margin. (In fact, the margin cannotbe substantially larger than the margin achieved by the trivialembedding.) Furthermore, these bounds are robust in the sense thatallowing each image half space to err ona small fraction of the instances does not imply a significantweakening of these dimension and margin bounds.Our results indicate that any universal learning machine, whichtransforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningfulgeneralization guarantees that are based on either VC dimension ormargins considerations. This failure of generalization bounds applieseven to classes for which “straight forward” empirical risk minimizationdoes enjoy meaningful generalization guarantees.
二分法のクラスを線形半空間のクラスに埋め込むという概念は、サポート ベクター マシン パラダイムの中心です。埋め込まれたクラスが有限のVC次元を持つ場合に得られる最小のユークリッド次元と最大マージンを決定する問題を検討します。任意の定数VC次元の有限概念クラス ファミリの圧倒的多数は、低次元の半空間に埋め込むことができないことを示します(実際、ユークリッド次元はインスタンス空間のサイズとほぼ同じ高さでなければならないことを示します)。任意の定数VC次元の有限概念クラス ファミリの圧倒的多数は、大きなマージンで半空間(任意の高いユークリッド次元)に埋め込むことができないことを示すことで、この結果をさらに強化します。(実際、マージンは、トリビアルなエンベディングによって達成されるマージンよりも大幅に大きくなることはありません。)さらに、これらの境界は、各画像の半空間がインスタンスのごく一部でエラーを起こすことを許可しても、これらの次元とマージン境界が大幅に弱まるわけではないという意味で堅牢です。私たちの結果は、データをユークリッド空間に変換してから線形(または大きなマージン)分類を適用するユニバーサル学習マシンは、VC次元またはマージンのいずれかの考慮に基づく意味のある一般化保証を享受できないことを示しています。この一般化境界の失敗は、「単純な」経験的リスク最小化が意味のある一般化保証を享受するクラスにも当てはまります。
Efficient Algorithms for Universal Portfolios
ユニバーサルポートフォリオのための効率的なアルゴリズム
A constant rebalanced portfolio is an investment strategy that keeps the same distribution of wealth among a set of stocks from day to day. There has been much work on Cover’s Universal algorithm, which is competitive with the best constant rebalanced portfolio determined in hindsight (Cover, 1991, Helmbold et al, 1998, Blum and Kalai, 1999,Foster and Vohra, 1999, Vovk, 1998, Cover and Ordentlich, 1996a,Cover, 1996c).While this algorithm has good performance guarantees, all known implementations are exponential in the number of stocks, restricting the number of stocks used in experiments (Helmbold et al, 1998, Cover and Ordentlich, 1996a,Ordentlich and Cover, 1996b, Cover, 1996c, Blum and Kalai, 1999). We present an efficient implementation of the Universal algorithm that is based on non-uniform random walks that are rapidly mixing (Applegateand Kannan, 1991, Lovasz and Simonovits, 1992, Frieze and Kannan, 1999).This same implementation also works for non-financial applications of the Universal algorithm, such as data compression (Cover, 1996c) and language modeling (Chen et al, 1999).
一定再バランス ポートフォリオは、一連の株式間で日々同じ富の分配を維持する投資戦略です。Coverのユニバーサル アルゴリズムに関する研究は数多く行われており、これは後から判断した最良の一定再バランス ポートフォリオと競合します(Cover、1991、Helmbold他、1998、BlumとKalai、1999、FosterとVohra、1999、Vovk、1998、CoverとOrdentlich、1996a、Cover、1996c)。このアルゴリズムは優れたパフォーマンスが保証されていますが、既知の実装はすべて株式の数に対して指数関数的であるため、実験に使用する株式の数が制限されます(Helmbold他、1998、CoverとOrdentlich、1996a、OrdentlichとCover、1996b、Cover、1996c、BlumとKalai、1999)。ここでは、急速に混合する非均一ランダム ウォークに基づくユニバーサル アルゴリズムの効率的な実装を紹介します(ApplegateとKannan、1991、LovaszとSimonovits、1992、FriezeとKannan、1999)。この同じ実装は、データ圧縮(Cover、1996c)や言語モデリング(Chenら、1999)など、ユニバーサル アルゴリズムの非金融アプリケーションにも適用できます。
Using Confidence Bounds for Exploitation-Exploration Trade-offs
エクスプロイテーションと探索のトレードオフに対する信頼限界の使用
We show how a standard tool from statistics — namely confidencebounds — can be used to elegantly deal with situations which exhibitan exploitation-exploration trade-off. Our technique for designing andanalyzing algorithms for such situations is general and can be appliedwhen an algorithm has to make exploitation-versus-explorationdecisions based on uncertain information provided by a random process. We apply our technique to two models with such anexploitation-exploration trade-off. For the adversarial banditproblem with shifting our new algorithm suffers onlyO((ST)1/2) regret with highprobability over T trials with S shifts. Such aregret bound was previously known only in expectation. Thesecond model we consider is associative reinforcement learning withlinear value functions. For this model our technique improves theregret from O(T3/4) to O(T1/2).
私たちは、統計の標準的なツールである信頼限界を使用して、利用と探索のトレードオフを示す状況を巧みに処理する方法を示します。このような状況のアルゴリズムを設計および分析する当社の手法は汎用的であり、ランダム プロセスによって提供される不確実な情報に基づいてアルゴリズムが利用と探索の決定を行う必要がある場合に適用できます。このような利用と探索のトレードオフがある2つのモデルにこの手法を適用します。シフトを伴う敵対的バンディット問題の場合、新しいアルゴリズムは、SシフトのT試行で高い確率でO((ST)1/2)の後悔しか生じません。このような後悔の限界は、以前は期待値でのみ知られていました。2番目に検討するモデルは、線形価値関数を使用した連想強化学習です。このモデルでは、当社の手法により後悔がO(T3/4)からO(T1/2)に改善されます。
Tracking a Small Set of Experts by Mixing Past Posteriors
過去の後頭部をミックスして少数の専門家を追跡する
In this paper, we examine on-line learning problems in which the targetconcept is allowed to change over time. In each trial a master algorithmreceives predictions from a large set of n experts. Its goal is to predictalmost as well as the best sequence of such experts chosen off-line bypartitioning the training sequence into k+1 sections and then choosingthe best expert for each section. We build on methods developed byHerbster and Warmuth and consider an open problem posed byFreund where the experts in the best partition are from a smallpool of size m.Since k >> m, the best expert shifts back and forthbetween the experts of the small pool.We propose algorithms that solvethis open problem by mixing the past posteriors maintained by the masteralgorithm. We relate the number of bits needed for encoding the bestpartition to the loss bounds of the algorithms. Instead of paying log n forchoosing the best expert in each section we first pay log (n choose m)bits in the bounds for identifying the pool of m experts and then log m bits per new section. In the bounds we also pay twice for encoding theboundaries of the sections.
この論文では、ターゲット概念が時間とともに変化することが許されるオンライン学習の問題を考察します。各試行で、マスター アルゴリズムはn人の専門家の大規模なセットから予測を受け取ります。その目標は、トレーニング シーケンスをk+1セクションに分割し、各セクションに最適な専門家を選択することで、オフラインで選択された専門家の最良のシーケンスとほぼ同じように予測することです。HerbsterとWarmuthによって開発された方法に基づいて、Freundによって提起された未解決の問題を検討します。この未解決の問題では、最良のパーティションの専門家はサイズmの小さなプールから選出されます。k >> mであるため、最良の専門家は小さなプールの専門家の間を行ったり来たりします。マスター アルゴリズムによって保持される過去の事後確率を混合することで、この未解決の問題を解決するアルゴリズムを提案します。最良のパーティションをエンコードするために必要なビット数を、アルゴリズムの損失境界に関連付けます。各セクションで最良の専門家を選択するためにlog nを支払う代わりに、最初にm人の専門家のプールを識別する境界でlog (n選択m)ビットを支払い、次に新しいセクションごとにlog mビットを支払います。境界内では、セクションの境界をエンコードするために2倍のコストがかかります。
Introduction to the Special Issue on Computational Learning Theory
特集「計算学習理論」の紹介
The Subspace Information Criterion for Infinite Dimensional Hypothesis Spaces
無限次元仮説空間の部分空間情報量規準
A central problem in learning is selection of an appropriate model. This is typically done by estimating the unknown generalization errors of a set of models to be selected from and then choosing the model with minimal generalization error estimate. In this article, we discuss the problem of model selection and generalization error estimation in the context of kernel regression models, e.g., kernel ridge regression, kernel subset regression or Gaussian process regression. Previously, a non-asymptotic generalization error estimator called the subspace information criterion (SIC) was proposed, that could be successfully applied to finite dimensional subspace models. SIC is an unbiased estimator of the generalization error for the finite sample case under the conditions that the learning target function belongs to a specified reproducing kernel Hilbert space (RKHS) H and the reproducing kernels centered on training sample points span the whole space H. These conditions hold only if dim H < l, where l < infinity is the number of training examples. Therefore, SIC could be applied only to finite dimensional RKHSs. In this paper, we extend the range of applicability of SIC, and show that even if the reproducing kernels centered on training sample points do not span the whole space H, SIC is an unbiased estimator of an essential part of the generalization error. Our extension allows the use of any RKHSs including infinite dimensional ones, i.e., richer function classes commonly used in Gaussian processes, support vector machines or boosting. We further show that when the kernel matrix is invertible, SIC can be expressed in a much simpler form, making its computation highly efficient. In computer simulations on ridge parameter selection with real and artificial data sets, SIC is compared favorably with other standard model selection techniques for instance leave-one-out cross-validation or an empirical Bayesian method.
学習における中心的な問題は、適切なモデルの選択です。これは通常、選択対象となるモデル セットの未知の一般化誤差を推定し、一般化誤差推定が最小のモデルを選択することによって行われます。この記事では、カーネル回帰モデル(カーネル リッジ回帰、カーネル サブセット回帰、ガウス過程回帰など)のコンテキストにおけるモデル選択と一般化誤差推定の問題について説明します。以前、サブスペース情報基準(SIC)と呼ばれる非漸近一般化誤差推定量が提案されました。これは、有限次元サブスペース モデルにうまく適用できます。SICは、学習ターゲット関数が指定された再生カーネル ヒルベルト空間(RKHS) Hに属し、トレーニング サンプル ポイントを中心とする再生カーネルが空間H全体に広がるという条件下で、有限サンプル ケースの一般化誤差の不偏推定量です。これらの条件は、dim H < l (l <無限大はトレーニング例の数)の場合にのみ当てはまります。したがって、SICは有限次元のRKHSにのみ適用できます。この論文では、SICの適用範囲を拡張し、トレーニング サンプル ポイントを中心とした再生カーネルが空間H全体に及ばない場合でも、SICは一般化誤差の重要な部分の不偏推定量であることを示します。この拡張により、無限次元のRKHS、つまりガウス過程、サポート ベクター マシン、ブースティングで一般的に使用されるより豊富な関数クラスを含む任意のRKHSを使用できます。さらに、カーネル マトリックスが可逆である場合、SICをはるかに単純な形式で表現できるため、計算が非常に効率的になることも示します。実際のデータ セットと人工データ セットを使用したリッジ パラメーター選択のコンピューター シミュレーションでは、SICは、leave-one-outクロス検証や経験的ベイズ法などの他の標準的なモデル選択手法と比較して優れています。
Minimal Kernel Classifiers
最小カーネル分類子
A finite concave minimization algorithm is proposed for constructingkernel classifiers that use a minimal number of data points both in generating and characterizing a classifier.The algorithm is theoretically justified on the basis of linear programming perturbation theory and a leave-one-outerror bound as well as effective computational resultson seven real world datasets. A nonlinear rectangular kernelis generated by systematically utilizingas few of the data as possible both in training and incharacterizing a nonlinear separating surface. This can result in substantial reduction in kernel data-dependence(over 94% in six of the seven public datasets tested on) and with testset correctness equal to that obtained by using a conventional support vector machine classifier that depends on many more data points. This reduction in data dependence results in a much faster classifier that requires less storage.To eliminate data points, the proposed approachmakes use of a novel loss function, the “pound” function ()#, whichis a linear combination of the 1-norm and the step function that measuresboth the magnitude and the presence of any error.
分類器の生成と特性評価の両方で最小限の数のデータ ポイントを使用するカーネル分類器を構築するための有限凹面最小化アルゴリズムが提案されています。このアルゴリズムは、線形計画摂動理論と1つ残すエラー境界、および7つの実際のデータセットでの有効な計算結果に基づいて理論的に正当化されています。非線形の長方形カーネルは、非線形分離面のトレーニングと特性評価の両方で可能な限り少ないデータを体系的に使用することで生成されます。これにより、カーネル データ依存性が大幅に削減され(テストされた7つの公開データセットのうち6つで94%以上)、テスト セットの正確性は、より多くのデータ ポイントに依存する従来のサポート ベクター マシン分類器を使用した場合と同等になります。このデータ依存性の削減により、より少ないストレージでより高速な分類器が実現します。データ ポイントを削除するために、提案されたアプローチでは、新しい損失関数である「ポンド」関数()#を使用します。これは、1ノルムとステップ関数の線形結合であり、エラーの大きさと存在の両方を測定します。
On Online Learning of Decision Lists
決定リストのオンライン学習について
A fundamental open problem in computational learning theory iswhether there is an attribute efficient learning algorithm for theconcept class of decision lists (Rivest, 1987; Blum, 1996). We consider aweaker problem, where the concept class is restricted to decisionlists with D alternations. For this class, we present a novelonline algorithm that achieves a mistake bound ofO(rD/log n),where r is the number of relevant variables, and n is thetotal number of variables. The algorithm can be viewed as astrict generalization of the famous Winnow algorithm byLittlestone (1988), and improves the O(r^(2D)/log n) mistakebound of Balanced Winnow. Our bound is stronger than a similarPAC-learning result of Dhagat and Hellerstein (1994). A combination of ouralgorithm with the algorithm suggested by Rivest (1987) mightachieve even better bounds.
計算学習理論における基本的な未解決問題は、決定リストの概念クラスに対して属性効率の良い学習アルゴリズムがあるかどうかである(Rivest、1987;Blum、1996)。ここでは、概念クラスがD個の交替を持つ決定リストに制限される、より弱い問題を考察します。このクラスに対して、O(rD/log n)の誤り境界を達成する新しいオンライン アルゴリズムを提示します。ここで、rは関連変数の数、nは変数の合計数です。このアルゴリズムは、Littlestone (1988)による有名なWinnowアルゴリズムの厳密な一般化と見なすことができ、Balanced WinnowのO(r^(2D)/log n)の誤り境界を改善しています。この境界は、DhagatとHellerstein (1994)による同様のPAC学習結果よりも強力です。このアルゴリズムとRivest (1987)によって提案されたアルゴリズムを組み合わせると、さらに優れた境界を達成できる可能性があります。
PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification
ガウス過程分類のためのPAC-Bayes一般化誤差限界
Approximate Bayesian Gaussian process (GP) classification techniques arepowerful non-parametric learning methods, similar in appearance and performanceto support vector machines. Based on simple probabilistic models, they renderinterpretable results and can be embedded in Bayesian frameworks for modelselection, feature selection, etc. In this paper, by applying the PAC-Bayesiantheorem of McAllester (1999a), we prove distribution-free generalisationerror bounds for a wide range of approximate Bayesian GP classificationtechniques. We also provide a new and much simplified proof for this powerfultheorem, making use of the concept of convex duality which is a backbone ofmany machine learning techniques. We instantiate and test our bounds for twoparticular GPC techniques, including a recent sparse method which circumventsthe unfavourable scaling of standard GP algorithms. As is shown in experimentson a real-world task, the bounds can be very tight for moderate trainingsample sizes. To the best of our knowledge, these results provide the tightestknown distribution-free error bounds for approximate Bayesian GPC methods,giving a strong learning-theoretical justification for the use of thesetechniques.
近似ベイジアン ガウス過程(GP)分類技術は、サポート ベクター マシンと外観およびパフォーマンスが類似した、強力なノンパラメトリック学習方法です。単純な確率モデルに基づいて解釈可能な結果を提供し、モデル選択、特徴選択などのベイジアン フレームワークに組み込むことができます。この論文では、McAllester (1999a)のPAC-ベイジアン定理を適用することにより、広範囲の近似ベイジアンGP分類技術の分布フリー一般化誤差境界を証明します。また、多くの機械学習技術のバックボーンである凸双対性の概念を利用して、この強力な定理の新しい、大幅に簡素化された証明も提供します。標準GPアルゴリズムの不利なスケーリングを回避する最近のスパース メソッドを含む2つの特定のGPC技術について、境界をインスタンス化してテストします。実際のタスクでの実験で示されているように、中程度のトレーニング サンプル サイズでは境界が非常に狭くなる可能性があります。私たちの知る限りでは、これらの結果は近似ベイジアンGPC法に対する最も厳密な分布フリー誤差境界を提供し、これらの技術の使用に対する強力な学習理論的正当性を与えます。
R-MAX – A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning
R-MAX – 最適強化学習のための一般多項式時間アルゴリズム
R-MAX is a very simple model-based reinforcement learning algorithm which can attain near-optimal average reward in polynomial time. In R-MAX, the agent always maintains a complete, but possibly inaccurate model of its environment and acts based on the optimal policy derived from this model. The model is initialized in an optimistic fashion: all actions in all states return the maximal possible reward (hence the name). During execution, it is updated based on the agent’s observations. R-MAX improves upon several previous algorithms: (1) It is simpler and more general than Kearns and Singh’s E^3 algorithm, covering zero-sum stochastic games. (2) It has a built-in mechanism for resolving the exploration vs. exploitation dilemma. (3) It formally justifies the “optimism under uncertainty” bias used in many RL algorithms. (4) It is simpler, more general, and more efficient than Brafman and Tennenholtz’s LSG algorithm for learning in single controller stochastic games. (5) It generalizes the algorithm by Monderer and Tennenholtz for learning in repeated games. (6) It is the only algorithm for learning in repeated games, to date, which is provably efficient, considerably improving and simplifying previous algorithms by Banos and by Megiddo.
R-MAXは、非常にシンプルなモデルベースの強化学習アルゴリズムで、多項式時間でほぼ最適な平均報酬を得ることができます。R-MAXでは、エージェントは常に環境の完全だが不正確な可能性のあるモデルを維持し、このモデルから導き出された最適なポリシーに基づいて行動します。モデルは楽観的な方法で初期化されます。つまり、すべての状態のすべてのアクションは、可能な限り最大の報酬を返します(これが名前の由来です)。実行中は、エージェントの観察に基づいて更新されます。R-MAXは、いくつかの以前のアルゴリズムを改良したものです。(1) KearnsとSinghのE^3アルゴリズムよりもシンプルで汎用性が高く、ゼロサム確率ゲームをカバーしています。(2)探索と活用のジレンマを解決するためのメカニズムが組み込まれています。(3)多くのRLアルゴリズムで使用される「不確実性下での楽観主義」バイアスを正式に正当化します。(4)これは、単一コントローラの確率的ゲームにおける学習のためのBrafmanとTennenholtzのLSGアルゴリズムよりも単純で、より一般的で、より効率的です。(5)これは、繰り返しゲームにおける学習のためにMondererとTennenholtzのアルゴリズムを一般化したものです。(6)これは、これまでの繰り返しゲームにおける学習のための唯一のアルゴリズムであり、効率的であることが証明されており、BanosとMegiddoによる以前のアルゴリズムを大幅に改善し、簡素化しています。
Algorithmic Luckiness
アルゴリズムのラッキーネス
Classical statistical learning theory studies the generalisationperformance of machine learning algorithms rather indirectly. Oneof the main detours is that algorithms are studied in terms of thehypothesis class that they draw their hypotheses from. In this paper,motivated by the luckiness framework of Shawe-Taylor et al. (1998), westudy learning algorithms more directly and in a way that allows usto exploit the serendipity of the training sample. The main differenceto previous approaches lies in the complexity measure; rather thancovering all hypotheses in a given hypothesis space it is only necessaryto cover the functions which could have been learned using the fixedlearning algorithm. We show how the resulting framework relates tothe VC, luckiness and compression frameworks. Finally, we presentan application of this framework to the maximum margin algorithm forlinear classifiers which results in a bound that exploits the margin,the sparsity of the resultant weight vector, and the degree of clusteringof the training data in feature space.
古典的な統計学習理論は、機械学習アルゴリズムの一般化パフォーマンスを間接的に研究しています。主な回り道の1つは、アルゴリズムが仮説を引き出す仮説クラスの観点から研究されることです。この論文では、Shawe-Taylorら(1998)の幸運フレームワークに触発されて、学習アルゴリズムをより直接的に、トレーニング サンプルの偶然の幸運を利用できる方法で研究します。以前のアプローチとの主な違いは、複雑さの尺度にあります。特定の仮説空間内のすべての仮説をカバーするのではなく、固定学習アルゴリズムを使用して学習できた関数をカバーするだけで済みます。結果として得られるフレームワークがVC、幸運、および圧縮フレームワークとどのように関係するかを示します。最後に、このフレームワークを線形分類器の最大マージン アルゴリズムに適用して、マージン、結果の重みベクトルのスパース性、および特徴空間でのトレーニング データのクラスタリングの程度を活用する境界値を提示します。
ε-MDPs: Learning in Varying Environments
ε-MDP:さまざまな環境での学習
In this paper ε-MDP-models are introduced and convergencetheorems are proven using the generalized MDP framework ofSzepesvari and Littman. Using this model family, we show thatQ-learning is capable of finding near-optimal policies in varyingenvironments. The potential of this new family of MDP models isillustrated via a reinforcement learning algorithm calledevent-learning which separates the optimization of decisionmaking from the controller. We show that event-learning augmentedby a particular controller, which gives rise to an ε-MDP, enablesnear optimal performance even if considerable and sudden changesmay occur in the environment. Illustrations are provided on thetwo-segment pendulum problem.
この論文では、ε-MDPモデルを紹介し、SzepesvariとLittmanの一般化されたMDPフレームワークを使用して収束定理を証明します。このモデルファミリーを使用して、Q-learningがさまざまな環境で最適に近い方策を見つけることができることを示します。この新しいMDPモデルファミリーの可能性は、意思決定の最適化をコントローラーから分離するイベント学習と呼ばれる強化学習アルゴリズムを介して示されています。特定のコントローラによって拡張されたイベント学習がε-MDPを生じさせると、環境に大きく急激な変化が生じても、ほぼ最適なパフォーマンスが可能になることを示しています。図は、2セグメント振り子問題で提供されています。
Learning Precise Timing with LSTM Recurrent Networks
LSTM リカレント ネットワークによる正確なタイミングの学習
The temporal distance between events conveys information essentialfor numerous sequential tasks such as motor control and rhythm detection.While Hidden Markov Models tend to ignore this information, recurrentneural networks (RNNs) can in principle learn to make use of it.We focus on Long Short-Term Memory (LSTM) because it has been shownto outperform other RNNs on tasks involving long time lags.We find that LSTM augmented by “peephole connections”from its internal cells to its multiplicative gates can learn the finedistinction between sequences of spikes spaced either 50 or 49time steps apart without the help of any short training exemplars.Without external resets or teacher forcing,our LSTM variant also learns to generatestable streams of precisely timed spikes and other highly nonlinearperiodic patterns. This makes LSTM a promising approach fortasks that require the accurate measurement or generation oftime intervals.
イベント間の時間的距離は、運動制御やリズム検出など、多数のシーケンシャルタスクに不可欠な情報を伝えます。隠れマルコフモデルはこの情報を無視する傾向がありますが、リカレントニューラルネットワーク(RNN)は原則としてこの情報を利用することを学ぶことができます。私たちがLong Short-Term Memory(LSTM)に注目するのは、長いタイムラグを伴うタスクで他のRNNよりも優れていることが示されているからです。LSTMは、その内部細胞からその乗算ゲートへの「のぞき穴接続」によって増強され、短いトレーニングの模範の助けを借りずに、50または49時間ステップ間隔でスパイクのシーケンス間の細かい区別を学習できることがわかりました。外部リセットや教師による強制なしに、LSTMバリアントは、正確にタイミングを合わせたスパイクやその他の高度に非線形な周期パターンの安定したストリームを生成することも学習します。これにより、LSTMは、時間間隔の正確な測定または生成を必要とするタスクの有望なアプローチになります。
Variational Learning of Clusters of Undercomplete Nonsymmetric Independent Components
不完全非対称独立成分のクラスタの変分学習
We apply a variational method to automatically determine the number ofmixtures of independent components in high-dimensional datasets, in which thesources may be nonsymmetrically distributed. The data are modeled by clusterswhere each cluster is described as a linear mixture of independent factors.The variational Bayesian method yields an accurate density model for theobserved data without overfitting problems. This allows the dimensionality ofthe data to be identified for each cluster. The new method was successfullyapplied to a difficult real-world medical dataset for diagnosing glaucoma.
私たちは、高次元データセット内の独立成分の混合物の数を自動的に決定するために変分法を適用し、ソースが非対称的に分布している可能性があります。データはクラスターによってモデル化され、各クラスターは独立した要因の線形混合物として記述されます。変分ベイズ法では、オーバーフィットの問題なしに、観測データの正確な密度モデルが得られます。これにより、各クラスターのデータの次元を識別できます。この新しい方法は、緑内障を診断するための困難な現実世界の医療データセットにうまく適用されました。
Data-dependent margin-based generalization bounds for classification
分類のためのデータ依存の余裕に基づく汎化限界
We derive new margin-based inequalities for the probability of errorof classifiers. The main feature of these bounds is that they can becalculated using the training data and therefore may be effectivelyused for model selection purposes. In particular, the bounds involveempirical complexities measured on the training data (such as theempirical fat-shattering dimension) as opposed to their worst-casecounterparts traditionally used in such analyses. Also, our boundsappear to be sharper and more general than recent results involvingempirical complexity measures. In addition, we develop analternative data-based bound for the generalization error of classesof convex combinations of classifiers involving an empiricalcomplexity measure that is easier to compute than the empiricalcovering number or fat-shattering dimension. We also show examples ofefficient computation of the new bounds.
私たちは、分類器の誤差の確率について、新しいマージンベースの不等式を導き出します。これらの境界の主な特徴は、トレーニングデータを使用して計算できるため、モデル選択の目的に効果的に使用できることです。特に、学習データで測定された経験的な複雑さ(経験的な脂肪粉砕次元など)は、そのような分析で伝統的に使用されていた最悪の場合の対応物とは対照的に、境界は含みます。また、私たちの境界は、経験的複雑性測定を含む最近の結果よりも鋭く、より一般的であるように見えます。さらに、経験的被覆数や脂肪粉砕次元よりも計算が容易な経験的複雑性尺度を含む分類器の凸型組み合わせのクラスの一般化誤差に対する代替データベースの境界を開発します。また、新しい境界の効率的な計算の例も示します。
On the Convergence of Optimistic Policy Iteration
楽観的政策反復の収束について
We consider a finite-state Markov decision problem andestablish the convergence of a special case ofoptimistic policy iteration that involves Monte Carlo estimationof Q-values, in conjunction with greedy policy selection.We provide convergence results for a number of algorithmic variations,including one thatinvolves temporal difference learning (bootstrapping) instead of Monte Carloestimation. We also indicate some extensions that either fail or are unlikelyto go through.
私たちは、有限状態マルコフ決定問題を検討し、Q値のモンテカルロ推定を含む楽観的な政策反復の特殊なケースの収束を確立し、貪欲な政策選択と併せて確立します。モンテカルロ推定の代わりに時間差分学習(ブートストラップ)を含むものを含む、いくつかのアルゴリズムバリエーションの収束結果を提供します。また、失敗する、または通過する可能性が低い拡張も示します。
Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries
メンバーシップのクエリにほとんど答えない教師からのモノトーンDNFの学習
We present results concerning the learning of Monotone DNF (MDNF) fromIncomplete Membership Queries and Equivalence Queries. Our main resultis a new algorithm that allows efficient learning of MDNF usingEquivalence Queries and Incomplete Membership Queries with probabilityof p=1-1/poly(n,t) of failing. Our algorithm is expected tomakeO((tn/(1-p))2)queries, when learning a MDNF formula with t terms over nvariables. Note that this is polynomial for any failure probabilityp=1-1/poly(n,t). The algorithm’s running time is alsopolynomial in t,n, and 1/(1-p). In a sense this is the bestpossible, as learning with p=1-1/w(poly(n,t)) wouldimply learning MDNF, and thus also DNF, from equivalence queriesalone.An early version of this paper appeared as Bshouty and Eiron (2001).
私たちは、Monotone DNF (MDNF)の学習に関する結果を、Incomplete Membership QueriesとEquivalence Queriesから提示します。私たちの主な結果は、同等性クエリと不完全なメンバーシップクエリを使用して、失敗の確率がp=1-1/poly(n,t)であるMDNFの効率的な学習を可能にする新しいアルゴリズムです。私たちのアルゴリズムは、n変数に対してt項を持つMDNF式を学習するときに、O((tn/(1-p))2)クエリを作成することが期待されています。これは、任意の故障確率p=1-1/poly(n,t)の多項式であることに注意してください。アルゴリズムの実行時間も、t、n、および1/(1-p)の多項式です。p=1-1/w(poly(n,t))で学習すると、同等性クエリのみからMDNFを学習し、したがってDNFも学習するので、ある意味ではこれが最善です。この論文の初期版は、Bshouty and Eiron (2001)として出版されました。
Kernel Independent Component Analysis
カーネルに依存しないコンポーネント分析
We present a class of algorithms for independent componentanalysis (ICA) which use contrast functions based on canonicalcorrelations in a reproducing kernel Hilbert space. On the onehand, we show that our contrast functions are related to mutualinformation and have desirable mathematical properties as measuresof statistical dependence. On the other hand, building on recentdevelopments in kernel methods, we show that these criteria andtheir derivatives can be computed efficiently. Minimizing thesecriteria leads to flexible and robust algorithms for ICA. Weillustrate with simulations involving a wide variety of sourcedistributions, showing that our algorithms outperform many of thepresently known algorithms.
私たちは、再現カーネルヒルベルト空間における正準相関に基づくコントラスト関数を使用する独立成分分析(ICA)のためのアルゴリズムのクラスを提示します。一方では、対比関数が相互情報に関連しており、統計的依存性の尺度として望ましい数学的特性を持っていることを示します。一方、カーネル法の最近の開発に基づいて、これらの基準とその導関数を効率的に計算できることを示します。これらの基準を最小限に抑えることで、ICAの柔軟で堅牢なアルゴリズムが得られます。さまざまなソース分布を含むシミュレーションで説明し、私たちのアルゴリズムが現在知られている多くのアルゴリズムよりも優れていることを示しています。
