Round Robin Classification
ラウンドロビン分類
In this paper, we discuss round robin classification (aka pairwise classification), a technique for handling multi-class problems with binary classifiers by learning one classifier for each pair of classes. We present an empirical evaluation of the method, implemented as a wrapper around the Ripper rule learning algorithm, on 20 multi-class datasets from the UCI database repository. Our results show that the technique is very likely to improve Ripper’s classification accuracy without having a high risk of decreasing it. More importantly, we give a general theoretical analysis of the complexity of the approach and show that its run-time complexity is below that of the commonly used one-against-all technique. These theoretical results are not restricted to rule learning but are also of interest to other communities where pairwise classification has recently received some attention. Furthermore, we investigate its properties as a general ensemble technique and show that round robin classification with C5.0 may improve C5.0’s performance on multi-class problems. However, this improvement does not reach the performance increase of boosting, and a combination of boosting and round robin classification does not produce any gain over conventional boosting. Finally, we show that the performance of round robin classification can be further improved by a straight-forward integration with bagging.
この論文では、ラウンドロビン分類(別名ペアワイズ分類)について説明します。これは、クラスのペアごとに1つの分類器を学習することで、バイナリ分類器を使用してマルチクラス問題を処理する手法です。Ripperルール学習アルゴリズムのラッパーとして実装されたこの手法を、UCIデータベース リポジトリの20のマルチクラス データセットで実証的に評価しました。結果は、この手法により、Ripperの分類精度を低下させるリスクを高くすることなく、精度を向上させる可能性が非常に高いことを示しています。さらに重要なことは、このアプローチの複雑さに関する一般的な理論的分析を行い、その実行時の複雑さが、一般的に使用されている1対1手法よりも低いことを示しています。これらの理論的結果は、ルール学習に限定されるものではなく、ペアワイズ分類が最近注目を集めている他のコミュニティにとっても興味深いものです。さらに、一般的なアンサンブル手法としての特性を調査し、C5.0を使用したラウンドロビン分類により、マルチクラス問題におけるC5.0のパフォーマンスが向上する可能性があることを示しています。しかし、この改善はブースティングのパフォーマンス向上には達せず、ブースティングとラウンドロビン分類を組み合わせても、従来のブースティングを超える利点は得られません。最後に、ラウンドロビン分類のパフォーマンスは、バギングとの直接的な統合によってさらに向上できることを示します。
Shallow Parsing using Noisy and Non-Stationary Training Material
ノイズの多い非定常的なトレーニング教材を使用した浅い解析
Shallow parsers are usually assumed to be trained on noise-freematerial, drawn from the same distribution as the testingmaterial. However, when either the training set is noisy or elsedrawn from a different distributions,performance may be degraded. Using the parsed Wall Street Journal, we investigate the performance of four shallow parsers (maximum entropy,memory-based learning, N-grams and ensemble learning) trained using various types of artificially noisy material. Our first set of results show that shallow parsersare surprisingly robust to synthetic noise, with performance graduallydecreasing as the rate of noise increases. Furtherresults show that no single shallow parser performs best in all noisesituations. Final results show that simple, parser-specific extensionscan improve noise-tolerance.Our second set of results addresses the question of whether naturallyoccurring disfluencies undermines performance more than does a changein distribution. Results using the parsed Switchboard corpus suggest that, although naturallyoccurring disfluencies might harm performance, differences indistribution between the training set and the testing set are moresignificant.
浅いパーサーは通常、テスト素材と同じ分布から抽出されたノイズのない素材でトレーニングされていると想定されています。ただし、トレーニング セットにノイズがあったり、異なる分布から抽出されたりすると、パフォーマンスが低下する可能性があります。解析されたウォール ストリート ジャーナルを使用して、さまざまな種類の人工的にノイズのある素材を使用してトレーニングされた4つの浅いパーサー(最大エントロピー、メモリ ベース学習、Nグラム、アンサンブル学習)のパフォーマンスを調査します。最初の結果セットは、浅いパーサーが合成ノイズに対して驚くほど堅牢であり、ノイズ率が増加するにつれてパフォーマンスが徐々に低下することを示しています。さらに、すべてのノイズ状況で最高のパフォーマンスを発揮する単一の浅いパーサーがないことを示しています。最終結果は、単純なパーサー固有の拡張機能によってノイズ耐性が向上することを示しています。2番目の結果セットは、自然に発生する不自然な表現が分布の変更よりもパフォーマンスを損なうかどうかという問題に対処しています。解析されたSwitchboardコーパスを使用した結果によると、自然に発生する不自然な表現はパフォーマンスに悪影響を及ぼす可能性があるものの、トレーニング セットとテスト セット間の分布の違いの方が重要であることが示唆されています。
Learning Rules and Their Exceptions
学習ルールとその例外
We present in this article a top-down inductive system, ALLiS, for learning linguistic structures.Two difficulties came up during the development of the system: the presence of a significant amount of noise in the data and the presence of exceptions linguistically motivated.It is then a challenge for an inductive system to learn rules from this kind of data.This leads us to add a specific mechanism, refinement, which enables learning rules and their exceptions.In the first part of this article we evaluate the usefulness of this device and show that it improves results when learning linguistic structures.In the second part, we explore how to improve the efficiency of the system by using prior knowledge.Since Natural Language is a strongly structured object, it may be important to investigate whether linguistic knowledge can help to make natural language learning more efficiently and accurately.This article presents some experiments demonstrating that linguistic knowledge improves learning.The system has been applied to the shared task of the CoNLL’00 workshop.
私たちは、この記事では、言語構造を学習するためのトップダウンの帰納的システムALLiSを紹介します。システムの開発中に、データに大量のノイズが存在することと、言語に起因する例外が存在するという2つの問題が発生しました。帰納的システムにとって、この種のデータからルールを学習することは困難です。このため、ルールとその例外を学習できるようにする特定のメカニズムである改良を追加しました。この記事の前半では、このデバイスの有用性を評価し、言語構造を学習する際の結果が改善されることを示します。後半では、事前の知識を使用してシステムの効率を改善する方法について説明します。自然言語は強く構造化されたオブジェクトであるため、言語知識が自然言語学習をより効率的かつ正確に行うのに役立つかどうかを調査することが重要になる場合があります。この記事では、言語知識が学習を改善することを示すいくつかの実験を紹介します。このシステムは、CoNLL’00ワークショップの共有タスクに適用されました。
Shallow Parsing with PoS Taggers and Linguistic Features
PoSタガーと言語機能による浅い解析
Three data-driven publicly available part-of-speech taggers are applied to shallow parsing of Swedish texts. The phrase structure is represented by nine types of phrases in a hierarchical structure containing labels for every constituent type the token belongs to in the parse tree. The encoding is based on the concatenation of the phrase tags on the path from lowest to higher nodes. Various linguistic features are used in learning; the taggers are trained on the basis of lexical information only, part-of-speech only, and a combination of both, to predict the phrase structure of the tokens with or without part-of-speech. Special attention is directed to the taggers’ sensitivity to different types of linguistic information included in learning, as well as the taggers’ sensitivity to the size and the various types of training data sets. The method can be easily transferred to other languages.
3つのデータ駆動型の公開品詞タガーは、スウェーデン語のテキストの浅い解析に適用されます。フレーズ構造は、構文解析ツリー内でトークンが属するすべての構成タイプのラベルを含む階層構造内の9種類のフレーズで表されます。エンコードは、パス上のフレーズタグを最下位ノードから上位ノードに連結することに基づいています。学習にはさまざまな言語的特徴が使用されます。タガーは、語彙情報のみ、品詞のみ、および両方の組み合わせに基づいてトレーニングされ、品詞の有無にかかわらずトークンのフレーズ構造を予測します。学習に含まれるさまざまな種類の言語情報に対するタガーの感度と、サイズとさまざまなタイプのトレーニングデータセットに対するタガーの感度に特に注意が払われています。この方法は、他の言語に簡単に移行できます。
Text Chunking based on a Generalization of Winnow
Winnow の一般化に基づくテキスト チャンク
This paper describes a text chunking system based on a generalization of the Winnow algorithm. We propose a general statistical model for text chunking which we then convert into a classification problem. We argue that the Winnow family of algorithms is particularly suitable for solving classification problems arising from NLP applications, due to their robustness to irrelevant features. However in theory, Winnow may not converge for linearly non-separable data. To remedy this problem, we employ a generalization of the original Winnow method. An additional advantage of the new algorithm is that it provides reliable confidence estimates for its classification predictions. This property is required in our statistical modeling approach. We show that our system achieves state of the art performance in text chunking with less computational cost then previous systems.
この論文では、Winnowアルゴリズムの一般化に基づくテキスト チャンク システムについて説明します。テキストチャンキングの一般的な統計モデルを提案し、それを分類問題に変換します。私たちは、Winnowファミリーのアルゴリズムは、無関係な機能に対する堅牢性を備えているため、NLPアプリケーションから生じる分類問題を解決するのに特に適していると主張します。ただし、理論的には、Winnowは線形分離不可能なデータに対して収束しない可能性があります。この問題を解決するために、元のWinnowメソッドの一般化を採用しています。新しいアルゴリズムのその他の利点は、分類予測に対して信頼性の高い信頼推定値を提供することです。このプロパティは、統計モデリングアプローチで必要です。私たちのシステムは、以前のシステムよりも少ない計算コストでテキストチャンキングの最先端のパフォーマンスを達成していることを示しています。
Shallow Parsing using Specialized HMMs
特殊なHMMを使用した浅い解析
We present a unified technique to solve different shallow parsing tasks as atagging problem using a Hidden Markov Model-based approach (HMM). This technique consists of theincorporation of the relevant information for each task into the models. To dothis, the training corpus is transformed to take into account thisinformation. In this way, no change is necessary for either the training ortagging process, so it allows for the use of a standard HMM approach. Takinginto account this information, weconstruct a Specialized HMM which gives more complete contextual models. We have tested our system on chunking and clause identification tasks usingdifferent specialization criteria. The results obtained are in line with theresults reported for most of the relevant state-of-the-artapproaches.
私たちは、隠れマルコフモデルベースのアプローチ(HMM)を使用して、タグ付け問題としてさまざまな浅い解析タスクを解くための統一的な手法を紹介します。この手法は、各タスクの関連情報をモデルに組み込むことで構成されます。これを行うために、トレーニングコーパスはこの情報を考慮に入れるように変換されます。このように、トレーニングプロセスとタグ付けプロセスのいずれにも変更が必要ないため、標準のHMMアプローチを使用できます。この情報を考慮に入れて、より完全なコンテキストモデルを提供するSpecialized HMMを構築します。私たちは、さまざまな専門化基準を使用して、チャンキングと節の識別タスクでシステムをテストしました。得られた結果は、関連する最先端のアプローチのほとんどで報告された結果と一致しています。
Memory-Based Shallow Parsing
メモリベースの浅い解析
We present memory-based learning approaches to shallow parsing and apply these to five tasks: base noun phrase identification, arbitrary base phrase recognition, clause detection, noun phrase parsing and full parsing. We use feature selection techniques and system combination methods for improving the performance of the memory-based learner. Our approach is evaluated on standard data sets and the results are compared with that of other systems. This reveals that our approach works well for base phrase identification while its application towards recognizing embedded structures leaves some room for improvement.
私たちは、浅い解析に対する記憶ベースの学習アプローチを提示し、これらを基本名詞句の識別、任意の基本句の認識、節の検出、名詞句の解析、および完全な構文解析の5つのタスクに適用します。特徴選択技術やシステム組み合わせ手法を用いて、記憶ベースの学習器の性能を向上させています。私たちのアプローチは、標準的なデータセットで評価され、その結果は他のシステムの結果と比較されます。このことから、私たちのアプローチはベースフレーズの識別にはうまく機能している一方で、埋め込まれた構造の認識への適用には改善の余地があることが明らかになりました。
Introduction to Special Issue on Machine Learning Approaches to Shallow Parsing
浅い解析への機械学習アプローチに関する特集の紹介
This article introduces the problem of partial or shallow parsing(assigning partial syntactic structure to sentences) and explains whyit is an important natural language processing (NLP) task. Thecomplexity of the task makes Machine Learning an attractive option incomparison to the handcrafting of rules. On the other hand, because of thesame task complexity, shallow parsing makes an excellent benchmarkproblem for evaluating machine learning algorithms. We sketch theorigins of shallow parsing as a specific task for machine learning oflanguage, and introduce the articles accepted for this special issue,a representative sample of current research in this area. Finally,future directions for machine learning of shallow parsing aresuggested.
この記事では、パーシャルパースまたはシャローパース(文に部分構文構造を割り当てること)の問題を紹介し、それが重要な自然言語処理(NLP)タスクである理由を説明します。タスクの複雑さにより、機械学習は、ルールの手作りと比較して魅力的なオプションになります。一方、タスクの複雑さが同じであるため、浅い解析は機械学習アルゴリズムを評価するための優れたベンチマーク問題になります。言語の機械学習の具体的な課題として、浅解析の起源をスケッチし、この分野の現在の研究の代表的なサンプルである本特集号で採択された論文を紹介します。最後に、浅い解析の機械学習の将来の方向性が示唆されています。
Covering Number Bounds of Certain Regularized Linear Function Classes
特定の正則化線形関数クラスの数値境界のカバー
Recently, sample complexity bounds have been derived for problems involving linear functions such as neural networks and support vector machines. In many of these theoretical studies, the concept of covering numbers played an important role. It is thus useful to study covering numbers for linear function classes. In this paper, we investigate two closely related methods to derive upper bounds on these covering numbers. The first method, already employed in some earlier studies, relies on the so-called Maurey’s lemma; the second method uses techniques from the mistake bound framework in online learning. We compare results from these two methods, as well as their consequences in some learning formulations.
最近、ニューラルネットワークやサポートベクターマシンなどの線形関数が関与する問題に対して、サンプルの複雑さの境界が導出されています。これらの理論的研究の多くでは、数字をカバーするという概念が重要な役割を果たしました。したがって、線形関数クラスの被覆数を研究することは有用です。この論文では、これらの被覆数の上限を導出するための密接に関連する2つの方法を調査します。最初の方法は、以前のいくつかの研究ですでに採用されていますが、いわゆるモーリーの補題に依存しています。2つ目の方法では、オンライン学習のMistake Boundフレームワークの手法を使用します。これら2つの方法の結果と、いくつかの学習定式化におけるそれらの結果を比較します。
Stability and Generalization
安定性と一般化
We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we use can be applied in the regression framework as well as in the classification one when the classifier is obtained by thresholding a real-valued function. We study the stability properties of large classes of learning algorithms such as regularization based algorithms. In particular we focus on Hilbert space regularization and Kullback-Leibler regularization. We demonstrate how to apply the results to SVM for regression and classification.
私たちは、学習アルゴリズムの安定性の概念を定義し、これらの概念を使用して、経験的誤差とleave-one-out誤差に基づいて一般化誤差の範囲を導出する方法を示します。私たちが使用する方法は、回帰フレームワークだけでなく、分類器が実数値関数をしきい値化することによって取得される場合の分類フレームワークにも適用できます。私たちは、正則化ベースのアルゴリズムなどの大規模な学習アルゴリズムの安定性特性を研究しています。特に、ヒルベルト空間正則化とKullback-Leibler正則化に着目します。結果をSVMに適用して回帰と分類を行う方法を示します。
Learning Equivalence Classes of Bayesian-Network Structures
ベイジアンネットワーク構造の等価クラスの学習
Two Bayesian-network structures are said to be equivalent if the set of distributions that can be represented withone of those structures is identical to the set of distributions thatcan be represented with the other. Many scoring criteria that are usedto learn Bayesian-network structures from data are scoreequivalent; that is, these criteria do not distinguish among networksthat are equivalent. In this paper, we consider using a scoreequivalent criterion in conjunction with a heuristic search algorithmto perform model selection or model averaging. We argue that it isoften appropriate to search among equivalence classes of networkstructures as opposed to the more common approach of searching amongindividual Bayesian-network structures. We describe a convenientgraphical representation for an equivalence class of structures, andintroduce a set of operators that can be applied to thatrepresentation by a search algorithm to move among equivalenceclasses. We show that our equivalence-class operators can be scoredlocally, and thus share the computational efficiency of traditionaloperators defined for individual structures. We show experimentallythat a greedy model-selection algorithm using our representationyields slightly higher-scoring structures than the traditionalapproach without any additional time overhead, and we argue that moresophisticated search algorithms are likely to benefit much more.
2つのベイジアン ネットワーク構造は、一方の構造で表現できる分布の集合が、もう一方の構造で表現できる分布の集合と同一である場合に、同等であると言えます。データからベイジアン ネットワーク構造を学習するために使用される多くのスコアリング基準は、スコア同等です。つまり、これらの基準は、同等であるネットワークを区別しません。この論文では、スコア同等基準をヒューリスティック検索アルゴリズムと組み合わせて使用して、モデル選択またはモデル平均化を実行することを検討します。個々のベイジアン ネットワーク構造を検索する一般的な方法ではなく、ネットワーク構造の同等クラスを検索する方が適切であることが多いと主張します。構造の同等クラスの便利なグラフィカル表現について説明し、検索アルゴリズムによってその表現に適用して同等クラス間を移動できる演算子のセットを紹介します。同等クラス演算子はローカルにスコアリングできるため、個々の構造に対して定義される従来の演算子と同じ計算効率が得られることを示します。実験的に、私たちの表現を使用した貪欲なモデル選択アルゴリズムは、追加の時間オーバーヘッドなしで、従来のアプローチよりもわずかに高いスコアの構造を生み出すことを示し、より洗練された検索アルゴリズムの方がはるかに多くの利益が得られる可能性が高いと主張します。
Text Classification using String Kernels
文字列カーネルを使用したテキスト分類
We propose a novel approach for categorizing text documents based onthe use of a special kernel. The kernel isan inner product in the feature space generated by all subsequences oflength k. A subsequence is any ordered sequence of k charactersoccurring in the text though not necessarily contiguously. The subsequencesare weighted by an exponentially decaying factor of their full length in thetext, hence emphasising those occurrences that are close to contiguous. Adirect computation of this feature vector would involve a prohibitive amountof computation even for modest values of k, since the dimension of thefeature space grows exponentially with k. The paper describes how despitethis fact the inner product can be efficiently evaluated by a dynamicprogramming technique. Experimental comparisons of theperformance of the kernel compared with a standard word feature spacekernel (Joachims, 1998) show positive results on modestly sized datasets.The case of contiguous subsequences is also considered for comparisonwith the subsequences kernel with different decay factors.For larger documents and datasets the paper introduces an approximation technique that is shown to deliver good approximations efficiently for largedatasets.
私たちは、特別なカーネルの使用に基づいてテキスト文書を分類する新しいアプローチを提案します。カーネルは、長さkのすべてのサブシーケンスによって生成される特徴空間の内積です。サブシーケンスとは、テキスト内で出現するk文字の順序付けられたシーケンスですが、必ずしも連続しているとは限りません。サブシーケンスは、テキスト内での全長の指数関数的に減少する係数によって重み付けされるため、連続に近い出現が強調されます。この特徴ベクトルを直接計算するには、特徴空間の次元がkとともに指数関数的に増加するため、kの値が適度であっても膨大な計算量が必要になります。この論文では、この事実にもかかわらず、動的プログラミング手法によって内積を効率的に評価できる方法について説明します。標準的な単語特徴空間カーネル(Joachims、1998)と比較したカーネルのパフォーマンスの実験的比較では、適度なサイズのデータセットで肯定的な結果が示されています。連続したサブシーケンスのケースも、異なる減衰係数を持つサブシーケンス カーネルとの比較で検討されています。この論文では、大規模なドキュメントとデータセット向けに、大規模なデータセットに対して効率的に優れた近似値を提供することが示されている近似手法を紹介しています。
The Learning-Curve Sampling Method Applied to Model-Based Clustering
モデルベースクラスタリングに適用される学習曲線サンプリング法
We examine the learning-curve sampling method, an approach forapplying machine-learning algorithms to large data sets. Theapproach is based on the observation that the computational costof learning a model increases as a function of the sample size ofthe training data, whereas the accuracy of a model hasdiminishing improvements as a function of sample size. Thus, thelearning-curve sampling method monitors the increasing costs andperformance as larger and larger amounts of data are used fortraining, and terminates learning when future costs outweighfuture benefits. In this paper, we formalize the learning-curvesampling method and its associated cost-benefit tradeoff in termsof decision theory. In addition, we describe the application ofthe learning-curve sampling method to the task of model-basedclustering via the expectation-maximization (EM) algorithm. Inexperiments on three real data sets, we show that thelearning-curve sampling method produces models that are nearly asaccurate as those trained on complete data sets, but withdramatically reduced learning times. Finally, we describe anextension of the basic learning-curve approach for model-basedclustering that results in an additional speedup. This extension isbased on the observation that the shape of the learning curve fora given model and data set is roughly independent of the numberof EM iterations used during training. Thus, we run EM for only afew iterations to decide how many cases to use for training, andthen run EM to full convergence once the number of cases isselected.
私たちは、機械学習アルゴリズムを大規模データ セットに適用するアプローチである学習曲線サンプリング法について検討します。このアプローチは、モデルを学習するための計算コストはトレーニング データのサンプル サイズの関数として増加するのに対し、モデルの精度はサンプル サイズの関数として改善が減少するという観察に基づいています。したがって、学習曲線サンプリング法は、トレーニングに使用されるデータの量が増えるにつれて増加するコストとパフォーマンスを監視し、将来のコストが将来の利点を上回ると学習を終了します。この論文では、学習曲線サンプリング法とそれに関連するコストと利点のトレードオフを意思決定理論の観点から形式化します。さらに、期待値最大化(EM)アルゴリズムによるモデル ベース クラスタリングのタスクへの学習曲線サンプリング法の適用について説明します。3つの実際のデータ セットでの実験で、学習曲線サンプリング法によって、完全なデータ セットでトレーニングされたモデルとほぼ同じ精度のモデルが生成され、学習時間が大幅に短縮されることを示します。最後に、モデルベースのクラスタリングのための基本的な学習曲線アプローチの拡張について説明します。これにより、さらなる高速化が実現します。この拡張は、特定のモデルとデータ セットの学習曲線の形状は、トレーニング中に使用されるEM反復回数とほぼ無関係であるという観察に基づいています。したがって、トレーニングに使用するケースの数を決定するために、EMを数回の反復のみ実行し、ケースの数を選択したら、EMを完全に収束するまで実行します。
On Using Extended Statistical Queries to Avoid Membership Queries
メンバーシップ クエリを回避するための拡張統計クエリの使用について
The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the”large” Fourier coefficients of a Boolean function. It is the main tool forlearning decision trees and DNF expressions in the PAC model with respect tothe uniform distribution. The algorithm requires access to the membershipquery (MQ) oracle. The access is often unavailable in learning applicationsand thus the KM algorithm cannot be used. We significantly weaken thisrequirement by producing an analogue of the KM algorithm that uses extendedstatistical queries (SQ) (SQs in which the expectation is taken with respectto a distribution given by a learning algorithm). We restrict a set ofdistributions that a learning algorithm may use for its statistical queriesto be a set of product distributions with each bit being 1 with probabilityrho, 1/2 or 1-rho for a constant 1/2 > rho > 0 (we denote the resultingmodel by SQ-Drho). Our analogue finds all the “large” Fourier coefficientsof degree lower than clog(n) (we call it the Bounded Sieve (BS)). We use BSto learn decision trees and by adapting Freund’s boosting technique we givean algorithm that learns DNF in SQ-Drho. An important property of the modelis that its algorithms can be simulated by MQs with persistent noise. Withsome modifications BS can also be simulated by MQs with product attributenoise (i.e., for a query x oracle changes every bit of x with some constantprobability and calculates the value of the target function at the resultingpoint) and classification noise. This implies learnability of decision treesand weak learnability of DNF with this non-trivial noise. In the second partof this paper we develop a characterization for learnability with theseextended statistical queries. We show that our characterization when appliedto SQ-Drho is tight in terms of learning parity functions. We extend theresult given by Blum et al. by proving that there is a class learnable inthe PAC model with random classification noise and not learnable inSQ-Drho.
Kushilevitz-Mansour (KM)アルゴリズムは、ブール関数の「大きな」フーリエ係数をすべて見つけるアルゴリズムです。これは、一様分布に関するPACモデルの決定木とDNF式を学習するための主要なツールです。このアルゴリズムでは、メンバーシップ クエリ(MQ)オラクルへのアクセスが必要です。学習アプリケーションではアクセスできないことが多く、そのためKMアルゴリズムは使用できません。拡張統計クエリ(SQ) (学習アルゴリズムによって与えられた分布に関して期待値が取得されるSQ)を使用するKMアルゴリズムの類似物を作成することで、この要件を大幅に緩和します。学習アルゴリズムが統計クエリに使用できる分布のセットを、各ビットが1になる確率がrho、1/2、または1-rho (定数1/2 > rho > 0の場合)である積分布のセットに制限します(結果のモデルをSQ-Drhoで示します)。我々の類似物は、clog(n)より低い次数の「大きな」フーリエ係数をすべて見つけます(これを有界ふるい(BS)と呼びます)。我々はBSを使用して決定木を学習し、フロイントのブースティング手法を適応させることで、SQ-DrhoでDNFを学習するアルゴリズムを提供します。このモデルの重要な特性は、そのアルゴリズムが持続ノイズを持つMQによってシミュレートできることです。いくつかの変更を加えると、BSは製品属性ノイズ(つまり、クエリxに対して、オラクルはxのすべてのビットを一定の確率で変更し、結果のポイントでターゲット関数の値を計算する)と分類ノイズを持つMQによってシミュレートすることもできます。これは、決定木の学習可能性と、この重要なノイズを持つDNFの弱い学習可能性を意味します。この論文の後半では、これらの拡張された統計クエリによる学習可能性の特性について説明します。SQ-Drhoに適用した場合、パリティ関数の学習という点で、我々の特性が厳密であることを示します。私たちは、Blumらによって示された結果を拡張します。ランダム分類ノイズのあるPACモデルでは学習可能だが、SQ-Drhoでは学習できないクラスがあることを証明します。
Machine Learning with Data Dependent Hypothesis Classes
データ依存仮説クラスによる機械学習
We extend the VC theory of statistical learning todata dependent spaces of classifiers.This theory can be viewed as a decompositionof classifier design into two components;the first component is a restriction to a data dependenthypothesis classand the second is empirical risk minimizationwithin that class.We define a measure of complexity fordata dependent hypothesis classes andprovide data dependent versions ofbounds on error deviance and estimation error.We also providea structural risk minimization procedureover data dependent hierarchies and prove consistency.We use this theory to provide a framework forstudying the trade-offs between performance andcomputational complexity in classifier design.As a consequence we obtaina new family of classifiers with dimension independentperformance bounds and efficient learning procedures.
私たちは、統計的学習のVC理論を分類器のデータ依存空間に拡張します。この理論は、分類器の設計を2つのコンポーネントに分解したものと見なすことができます。最初のコンポーネントは、データ依存仮説クラスに対する制限であり、2番目のコンポーネントは、そのクラス内の経験的リスクの最小化です。データ依存仮説クラスの複雑さの尺度を定義し、誤差逸脱度と推定誤差に関するデータ依存バージョンの境界を提供します。また、データ依存階層に対する構造的なリスク最小化手順を提供し、一貫性を証明します。この理論を使用して、分類器の設計におけるパフォーマンスと計算の複雑さの間のトレードオフを研究するためのフレームワークを提供します。その結果、次元に依存しないパフォーマンス境界と効率的な学習手順を備えた新しい分類器ファミリーが得られます。
Recommender Systems Using Linear Classifiers
線形分類器を使用したレコメンダー システム
Recommender systemsuse historical data on user preferences and other availabledata on users (for example, demographics) and items (for example, taxonomy)to predict items a new user might like. Applications of these methods includerecommending items for purchase and personalizing thebrowsing experience on a web-site.Collaborative filtering methods have focused on using just thehistory of user preferences to make the recommendations.These methods have been categorized as memory-based if they operateover the entire data to make predictions and as model-based ifthey use the data to build a model which is then used for predictions.In this paper, we propose the use of linear classifiers in amodel-based recommender system.We compare our method with another model-based method usingdecision trees and withmemory-based methods using data from various domains.Our experimental results indicate that these linear modelsare well suited for this application.They outperform a commonly proposedmemory-based method in accuracy and alsohave a better tradeoff between off-line and on-line computational requirements.
レコメンデーション システムは、ユーザーの嗜好に関する履歴データと、ユーザー(人口統計など)およびアイテム(分類など)に関するその他の利用可能なデータを使用して、新しいユーザーが好む可能性のあるアイテムを予測します。これらの方法の用途には、購入アイテムの推奨やWebサイトでの閲覧エクスペリエンスのパーソナライズなどがあります。協調フィルタリング手法は、ユーザーの嗜好の履歴のみを使用して推奨を行うことに重点を置いています。これらの方法は、データ全体を操作して予測を行う場合はメモリベース、データを使用してモデルを構築し、そのモデルを予測に使用する場合はモデルベースに分類されます。この論文では、モデルベースのレコメンデーション システムで線形分類器を使用することを提案します。この方法を、決定木を使用する別のモデルベースの方法や、さまざまなドメインのデータを使用するメモリベースの方法と比較します。実験結果から、これらの線形モデルがこの用途に適していることがわかります。これらのモデルは、一般的に提案されているメモリベースの方法よりも精度が高く、オフラインとオンラインの計算要件のトレードオフも優れています。
Classes of Kernels for Machine Learning: A Statistics Perspective
機械学習のためのカーネルのクラス: 統計の視点
In this paper, we present classes of kernels for machine learning from a statistics perspective. Indeed, kernels are positive definite functions and thus also covariances. After discussing key properties of kernels, as well as a new formula to construct kernels, we present several important classes of kernels: anisotropic stationary kernels, isotropic stationary kernels, compactly supported kernels, locally stationary kernels, nonstationary kernels, and separable nonstationary kernels. Compactly supported kernels and separable nonstationary kernels are of prime interest because they provide a computational reduction for kernel-based methods. We describe the spectral representation of the various classes of kernels and conclude with a discussion on the characterization of nonlinear maps that reduce nonstationary kernels to either stationarity or local stationarity.
この論文では、統計学の観点から機械学習用のカーネルのクラスを紹介します。実際、カーネルは正定値関数であり、したがって共分散でもあります。カーネルの主要な特性と、カーネルを構築するための新しい式について説明した後、いくつかの重要なクラスのカーネルを紹介します:異方性固定カーネル、等方性固定カーネル、コンパクトに支持されたカーネル、局所固定カーネル、非定常カーネル、および分離可能な非固定カーネル。コンパクトにサポートされているカーネルと分離可能な非定常カーネルは、カーネルベースの方法の計算削減を提供するため、最も興味深いものです。さまざまなクラスのカーネルのスペクトル表現について説明し、最後に、非定常カーネルを定常性または局所定常性に還元する非線形マップの特性付けについて説明します。
Exact Simplification of Support Vector Solutions
サポートベクターソリューションの正確な簡略化
This paper demonstrates that standard algorithms for training support vector machines generally produce solutions with a greater number of support vectors than are strictly necessary. An algorithm is presented that allows unnecessary support vectors to be recognized and eliminated while leaving the solution otherwise unchanged. The algorithm is applied to a variety of benchmark data sets (for both classification and regression) and in most cases the procedure leads to a reduction in the number of support vectors. In some cases the reduction is substantial.
この論文では、サポート ベクター マシンをトレーニングするための標準アルゴリズムは、一般に、厳密に必要な数よりも多くのサポート ベクトルを持つソリューションを生成することを示しています。不要なサポート ベクトルを認識して排除し、それ以外の解は変更しないままにするアルゴリズムが提示されます。このアルゴリズムは、さまざまなベンチマークデータセット(分類と回帰の両方)に適用され、ほとんどの場合、この手順によりサポートベクトルの数が減少します。場合によっては、大幅な削減になります。
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines
多クラスカーネルベースベクトルマシンのアルゴリズム実装について
In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy.
この論文では、マルチクラスカーネルベースのベクターマシンのアルゴリズム実装について説明します。出発点は、マルチクラス問題に対するマージンという一般化された概念です。この概念を使用して、マルチクラス分類問題を、2次目的関数を持つ制約付き最適化問題として扱います。通常、マルチクラス問題を複数の独立したバイナリ分類タスクに分解する従来のアプローチのほとんどとは異なり、マージンの概念は、マルチクラス予測子をトレーニングするための直接的な方法を生み出します。最適化問題の双対を使用することで、コンパクトな制約セットを持つカーネルを組み込み、双対問題を複数の縮小されたサイズの最適化問題に分解できます。縮小された最適化問題を解決するための効率的な固定小数点アルゴリズムについて説明し、その収束を証明します。次に、大規模なデータセットで実行時間を大幅に短縮する技術的な詳細について説明します。最後に、このアプローチを以前に研究されたカーネルベースの方法と比較するさまざまな実験について説明します。実験では、マルチクラス問題に対して最先端の精度を達成できることを示しています。
Efficient SVM Training Using Low-Rank Kernel Representations
低ランクのカーネル表現を使用した効率的な SVM トレーニング
SVM training is a convex optimization problemwhich scales with the training set size rather than the feature space dimension. While this is usually considered to be a desired quality, in large scale problems it may cause training to be impractical.The common techniques to handle this difficulty basically build a solutionby solving a sequence of small scale subproblems. Our current effort is concentrated on the rank of the kernel matrix as asource for further enhancement of the training procedure. We first show that for a low rank kernel matrix it is possible to design a betterinterior point method (IPM) in terms of storage requirementsas well as computational complexity. We then suggest an efficientuse of a known factorization technique to approximate a given kernel matrixby a low rank matrix, which in turn will be used to feed the optimizer.Finally, we derive an upper bound on the change in the objective functionvalue based on the approximation error and the number of active constraints(support vectors). This bound is general in the sense that it holds regardless of the approximation method.
SVMトレーニングは凸最適化問題であり、特徴空間の次元ではなくトレーニング セットのサイズに応じてスケールします。これは通常望ましい品質と見なされますが、大規模な問題ではトレーニングが非実用的になる可能性があります。この問題に対処するための一般的な手法は、基本的に、一連の小規模なサブ問題を解くことによってソリューションを構築します。現在の取り組みは、トレーニング手順をさらに強化するためのソースとして、カーネル マトリックスのランクに集中しています。まず、低ランクのカーネル マトリックスの場合、ストレージ要件と計算の複雑さの点で、より優れた内部点法(IPM)を設計できることを示します。次に、既知の因数分解手法を効率的に使用して、特定のカーネル マトリックスを低ランク マトリックスで近似し、次にそれをオプティマイザーに入力する方法を提案します。最後に、近似誤差とアクティブな制約(サポート ベクター)の数に基づいて、目的関数値の変化の上限を導出します。この上限は、近似方法に関係なく保持されるという意味で一般的です。
A New Approximate Maximal Margin Classification Algorithm
新しい近似最大マージン分類アルゴリズム
A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data.Our algorithm, called ALMA_p (Approximate Large Margin algorithm w.r.t. norm p),takes O( (p-1) / (α2 γ2 ) )corrections to separate the data with p-norm margin larger than (1-α)γ,where g is the (normalized) p-norm margin of the data.ALMA_p avoids quadratic (or higher-order) programming methods. It isvery easy to implement and is as fast as on-line algorithms, such asRosenblatt’s Perceptron algorithm.We performed extensive experiments on both real-world and artificial datasets.We compared ALMA_2 (i.e., ALMA_p with p = 2) to standard Support vector Machines (SVM) and to two incremental algorithms: the Perceptron algorithm and Li and Long’s ROMMA.The accuracy levels achieved by ALMA_2 are superior to thoseachieved by the Perceptron algorithm and ROMMA, but slightly inferior to SVM’s. On the other hand, ALMA_2 is quite faster and easier to implement than standard SVM training algorithms.When learning sparse target vectors, ALMA_p with p > 2 largely outperforms Perceptron-like algorithms, such as ALMA_2.
線形に分離可能なデータのセットに対して、ノルムp≥2に関して最大マージン超平面を近似する新しい増分学習アルゴリズムについて説明します。ALMA_p (ノルムpに関する近似大マージン アルゴリズム)と呼ばれるアルゴリズムは、(1-α)γ より大きいpノルム マージンを持つデータを分離するためにO( (p-1) / (α2γ2 ) )の修正を行います。ここで、gはデータの(正規化された) pノルム マージンです。ALMA_pは、2次(または高次)プログラミング手法を回避します。実装が非常に簡単で、Rosenblattのパーセプトロン アルゴリズムなどのオンライン アルゴリズムと同じくらい高速です。実際のデータセットと人工データセットの両方で広範な実験を行いました。ALMA_2 (つまり、p = 2のALMA_p)を標準のサポート ベクター マシン(SVM)および2つの増分アルゴリズム(パーセプトロン アルゴリズムとLiとLongのROMMA)と比較しました。ALMA_2によって達成される精度レベルは、パーセプトロン アルゴリズムおよびROMMAによって達成される精度レベルよりも優れていますが、SVMよりもわずかに劣っています。一方、ALMA_2は標準のSVMトレーニング アルゴリズムよりもかなり高速で実装が簡単です。スパース ターゲット ベクトルを学習する場合、p > 2のALMA_pは、ALMA_2などのパーセプトロンのようなアルゴリズムよりも大幅に優れています。
A Generalized Kernel Approach to Dissimilarity-based Classification
非類似度に基づく分類への一般化カーネルアプローチ
Usually, objects to be classified are represented by features. In this paper, we discuss an alternative object representation based ondissimilarity values. If such distances separate the classes well,the nearest neighbor method offers a good solution. However, dissimilarities used in practice are usually far from ideal and the performance of the nearest neighbor rule suffers from its sensitivity to noisy examples. We show that other, more global classification techniques are preferable to the nearest neighbor rule, in such cases.For classification purposes, two different ways of using generalized dissimilarity kernels are considered. In the first one, distances are isometrically embedded in a pseudo-Euclidean space and the classification task is performed there. In the second approach, classifiers are built directly on distance kernels. Both approaches are described theoretically and then compared using experiments with different dissimilarity measures and datasets including degraded data simulating the problem of missing values.
通常、分類されるオブジェクトは特徴によって表されます。この論文では、相違値に基づく代替オブジェクト表現について説明します。このような距離がクラスをうまく分離する場合、最近傍法は優れたソリューションを提供します。ただし、実際に使用される相違は通常、理想からはほど遠く、最近傍ルールのパフォーマンスはノイズの多い例に対する感度に影響を受けます。このような場合、最近傍ルールよりも他のよりグローバルな分類手法が適していることを示します。分類の目的で、一般化相違カーネルを使用する2つの異なる方法が検討されます。最初の方法では、距離が擬似ユークリッド空間に等尺的に埋め込まれ、分類タスクがそこで実行されます。2番目の方法では、分類器が距離カーネル上に直接構築されます。両方のアプローチを理論的に説明し、異なる相違度尺度と、欠損値の問題をシミュレートする劣化データを含むデータセットを使用した実験を使用して比較します。
Uniform Object Generation for Optimizing One-class Classifiers
1 クラス分類子を最適化するための統一オブジェクト生成
In one-class classification, one class of data, called the targetclass, has to be distinguished from the rest of the feature space. Itis assumed that only examples of the target class are available. Thisclassifier has to be constructed such that objects not originating from thetarget set, by definition outlier objects, are not classified as targetobjects. In previous research the support vector data description (SVDD) isproposed to solve the problem of one-class classification. It models ahypersphere around the target set, and by the introduction of kernelfunctions, more flexible descriptions are obtained. In the originaloptimization of the SVDD, two parameters have to be given beforehand by theuser. To automatically optimize the values for these parameters, the error onboth the target and outlier data has to be estimated. Because no outlierexamples are available, we propose a method for generating artificialoutliers, uniformly distributed in a hypersphere. An (relative) efficientestimate for the volume covered by the one-class classifiers is obtained, andso an estimate for the outlier error. Results are shown for artificial dataand for real world data.
1クラス分類では、ターゲット クラスと呼ばれる1つのデータ クラスを、特徴空間の残りの部分と区別する必要があります。ターゲット クラスの例のみが利用可能であると想定されます。この分類器は、ターゲット セットに由来しないオブジェクト(定義上、外れ値オブジェクト)がターゲット オブジェクトとして分類されないように構築する必要があります。以前の研究では、1クラス分類の問題を解決するためにサポート ベクター データ記述(SVDD)が提案されています。これは、ターゲット セットの周囲に超球をモデル化し、カーネル関数の導入によって、より柔軟な記述が得られます。SVDDの元の最適化では、ユーザーが2つのパラメーターを事前に指定する必要があります。これらのパラメーターの値を自動的に最適化するには、ターゲット データと外れ値データの両方のエラーを推定する必要があります。外れ値の例が利用できないため、超球に均一に分散された人工外れ値を生成する方法を提案します。1クラス分類器によってカバーされるボリュームの(相対的な)効率的な推定値が得られ、外れ値エラーの推定値も得られます。人工データと実世界のデータの結果を示します。
One-Class SVMs for Document Classification
ドキュメント分類用のOne-Class SVM
We implemented versions of the SVM appropriate for one-class classificationin the context of information retrieval. The experiments were conducted onthe standard Reuters data set. For the SVM implementation we used both a version of Schoelkopf et al.and a somewhat different version of one-classSVM based on identifying “outlier” data as representative of the second-class.We report on experiments with different kernels for both of these implementations and with different representations of the data, includingbinary vectors, tf-idf representation and a modification called “Hadamard”representation.Then we compared it with one-class versions of the algorithmsprototype (Rocchio), nearest neighbor, naive Bayes,and finally a natural one-class neural network classification method based on “bottleneck” compression generated filters.The SVM approach as represented by Schoelkopf was superior to all the methods except the neural network one, where it was, althoughoccasionally worse, essentially comparable. However, the SVM methodsturned out to be quite sensitive to the choice of representation andkernel in ways which are not well understood; therefore, for the time beingleaving the neural network approach as the most robust.
私たちは、情報検索のコンテキストで1クラス分類に適したSVMのバージョンを実装しました。実験は、標準のReutersデータ セットで実施しました。SVM実装では、Schoelkopfらのバージョンと、2番目のクラスの代表として「外れ値」データを識別することに基づく1クラスSVMの若干異なるバージョンの両方を使用しました。これらの両方の実装で異なるカーネルを使用した実験と、バイナリ ベクトル、tf-idf表現、および「Hadamard」表現と呼ばれる修正を含むデータの異なる表現を使用した実験について報告します。次に、アルゴリズム プロトタイプ(Rocchio)、最近傍法、ナイーブ ベイズ、および最後に「ボトルネック」圧縮生成フィルタに基づく自然な1クラス ニューラル ネットワーク分類方法の1クラス バージョンと比較しました。Schoelkopfによって表されたSVMアプローチは、ニューラル ネットワーク以外のすべての方法よりも優れていました。ニューラル ネットワークでは、時折劣るものの、基本的に同等でした。しかし、SVM法は、よく理解されていない方法で表現とカーネルの選択に非常に敏感であることが判明しました。そのため、当面はニューラル ネットワーク アプローチが最も堅牢な方法であると考えられます。
Support Vector Clustering
サポート ベクター クラスタリング
We present a novel clustering methodusing the approach of support vector machines.Data points are mapped by means of a Gaussian kernelto a high dimensional feature space, where we search for the minimalenclosing sphere.This sphere, when mapped back to data space, can separateinto several components, each enclosing a separate cluster of points.We present a simple algorithm for identifying these clusters.The width of the Gaussian kernel controls the scale at which the datais probed while the soft margin constant helps coping with outliers and overlapping clusters.The structure of a dataset is explored by varying the twoparameters, maintaining a minimal number of support vectorsto assure smooth cluster boundaries.We demonstrate the performance of our algorithm on several datasets.
私たちは、サポートベクターマシンのアプローチを使用した新しいクラスタリング手法を紹介します。データポイントは、ガウスカーネルによって高次元の特徴空間にマッピングされ、そこで最小の囲み球を探します。この球体は、データ空間にマップし直すと、複数のコンポーネントに分離でき、それぞれが個別のポイントのクラスターを囲むことができます。これらのクラスタを識別するための簡単なアルゴリズムを示します。ガウス カーネルの幅は、データがプローブされるスケールを制御し、ソフト マージン定数は外れ値やクラスターの重なりに対処するのに役立ちます。データセットの構造は、2つのパラメーターを変化させ、最小限のサポート ベクトルを維持してスムーズなクラスター境界を確保することで探索されます。いくつかのデータセットでアルゴリズムのパフォーマンスを実証します。
Kernel Partial Least Squares Regression in Reproducing Kernel Hilbert Space
カーネルヒルベルト空間の再現におけるカーネル偏最小二乗回帰
A family of regularized least squares regression models in a Reproducing Kernel Hilbert Space is extended by the kernel partial least squares (PLS) regression model. Similar to principal components regression (PCR), PLS is a method based on the projection of input (explanatory) variables to the latent variables (components). However, in contrast to PCR, PLS creates the components by modeling the relationship between input and output variables while maintaining most of the information in the input variables. PLS is useful in situations where the number of explanatory variables exceeds the number of observations and/or a high level of multicollinearity among those variables is assumed. Motivated by this fact we will provide a kernel PLS algorithm for construction of nonlinear regression models in possibly high-dimensional feature spaces.We give the theoretical description of the kernel PLS algorithm and we experimentally compare the algorithm with the existing kernel PCR and kernel ridge regression techniques. We will demonstrate that on the data sets employed kernel PLS achieves the same results as kernel PCR but uses significantly fewer, qualitatively different components.
再生カーネル ヒルベルト空間の正則化された最小二乗回帰モデルのファミリーは、カーネル部分最小二乗(PLS)回帰モデルによって拡張されます。主成分回帰(PCR)と同様に、PLSは、入力(説明)変数を潜在変数(コンポーネント)に投影することに基づく方法です。ただし、PCRとは対照的に、PLSは、入力変数の情報のほとんどを維持しながら、入力変数と出力変数の関係をモデル化することでコンポーネントを作成します。PLSは、説明変数の数が観測数を超える場合や、それらの変数間に高いレベルの多重共線性が想定される場合に役立ちます。この事実に基づいて、高次元の特徴空間で非線形回帰モデルを構築するためのカーネルPLSアルゴリズムを提供します。カーネルPLSアルゴリズムの理論的説明を示し、このアルゴリズムを既存のカーネルPCRおよびカーネル リッジ回帰手法と実験的に比較します。使用したデータ セットでカーネルPLSはカーネルPCRと同じ結果を達成しますが、使用するコンポーネントが大幅に少なく、質的に異なることを実証します。
Introduction to the Special Issue on Kernel Methods
カーネルメソッドに関する特集号の紹介
On the Influence of the Kernel on the Consistency of Support Vector Machines
カーネルがサポートベクターマシンの一貫性に及ぼす影響について
In this article we study the generalization abilitiesof several classifiers of support vector machine (SVM) type using a certain classof kernels that we call universal. It is shown that the soft margin algorithms with universal kernelsare consistent fora large class of classification problems including some kind of noisy tasks provided that the regularization parameter is chosen well. In particular we derive a simplesufficient condition for this parameter in the case of Gaussian RBF kernels.On the one hand our considerations are based on an investigation of an approximation property—the so-called universality—of the used kernels that ensures that all continuous functions can be approximated by certain kernel expressions.This approximation propertyalso gives a new insight into the role of kernels in these and otheralgorithms. On the other hand the results are achieved by a precise study of theunderlying optimization problems of the classifiers.Furthermore, we show consistency for the maximal margin classifier as well as for the soft margin SVM’sin the presence of large margins. In this case it turns out that also constant regularization parametersensure consistency for the soft margin SVM’s. Finally we prove that even for simple, noise free classification problems SVM’s with polynomial kernels can behave arbitrarily badly.
この記事では、ユニバーサルと呼ばれる特定のクラスのカーネルを使用して、サポート ベクター マシン(SVM)タイプのいくつかの分類器の一般化能力について検討します。ユニバーサル カーネルを使用したソフト マージン アルゴリズムは、正規化パラメーターが適切に選択されていれば、ある種のノイズの多いタスクを含む大規模な分類問題に対して一貫性があることが示されています。特に、ガウスRBFカーネルの場合、このパラメーターの簡単な十分条件を導出します。一方で、私たちの考察は、すべての連続関数を特定のカーネル式で近似できることを保証する、使用されるカーネルの近似特性(いわゆるユニバーサル性)の調査に基づいています。この近似特性は、これらのアルゴリズムやその他のアルゴリズムにおけるカーネルの役割についても新たな洞察をもたらします。一方、結果は、分類器の根本的な最適化問題を正確に調査することで達成されます。さらに、大きなマージンがある場合でも、最大マージン分類器とソフト マージンSVMの一貫性を示します。この場合、一定の正則化パラメーターもソフト マージンSVMの一貫性を保証することがわかります。最後に、単純でノイズのない分類問題でも、多項式カーネルを持つSVMが任意に悪い動作をする可能性があることを証明します。
Support Vector Machine Active Learning with Applications to Text Classification
テキスト分類への応用によるベクトル機械学習のアクティブラーニングのサポート
Support vector machines have met with significant success in numerousreal-world learning tasks. However, like most machine learningalgorithms, they are generally applied using a randomly selectedtraining set classified in advance. In many settings, we also havethe option of using pool-based active learning. Instead of usinga randomly selected training set, the learner has access to a pool ofunlabeled instances and can request the labels for some number ofthem. We introduce a new algorithm for performing active learningwith support vector machines, i.e., an algorithm for choosing whichinstances to request next. We provide a theoretical motivation for thealgorithm using the notion of a version space. We presentexperimental results showing that employing our active learning methodcan significantly reduce the need for labeled training instances inboth the standard inductive and transductive settings.
サポートベクターマシンは、多くの実世界の学習タスクで大きな成功を収めています。ただし、ほとんどの機械学習アルゴリズムと同様に、通常は、事前に分類されたランダムに選択されたトレーニングセットを使用して適用されます。多くの設定では、プールベースのアクティブラーニングを使用するオプションもあります。ランダムに選択されたトレーニングセットを使用する代わりに、学習者はラベル付けされていないインスタンスのプールにアクセスでき、そのうちのいくつかのラベルをリクエストできます。サポートベクターマシンを用いてアクティブラーニングを行うための新しいアルゴリズム、すなわち、次にリクエストするインスタンスを選択するアルゴリズムを紹介します。バージョン空間の概念を使用して、アルゴリズムの理論的な動機を提供します。アクティブラーニングの方法を採用することで、標準的な帰納的設定と変換的設定の両方でラベル付けされたトレーニングインスタンスの必要性を大幅に減らすことができることを示す実験結果を紹介します。
Graph-Based Hierarchical Conceptual Clustering
グラフベースの階層的概念クラスタリング
Hierarchical conceptual clustering has proven to be a useful, although under-explored, data mining technique. A graph-based representation of structural information combined with a substructure discovery technique has been shown to be successful in knowledge discovery. The SUBDUE substructure discovery system provides one such combination of approaches. This work presents SUBDUE and the development of its clustering functionalities. Several examples are used to illustrate the validity of the approach both in structured and unstructured domains, as well as to compare SUBDUE to the Cobweb clustering algorithm. We also develop a new metric for comparing structurally-defined clusterings. Results show that SUBDUE successfully discovers hierarchical clusterings in both structured and unstructured data.
階層的な概念クラスタリングは、まだ十分に検討されていないものの、有用なデータマイニング手法であることが証明されています。構造情報のグラフベースの表現と下部構造の発見技術を組み合わせることで、知識の発見に成功することが示されています。SUBDUEサブストラクチャー探索システムは、そのようなアプローチの組み合わせの1つです。この作業では、SUBDUEとそのクラスタリング機能の開発について説明します。構造化ドメインと非構造化ドメインの両方でのアプローチの有効性を説明するため、また、SUBDUEとCobwebクラスタリング アルゴリズムを比較するために、いくつかの例が使用されます。また、構造的に定義されたクラスタリングを比較するための新しいメトリックも開発します。結果は、SUBDUEが構造化データと非構造化データの両方で階層クラスタリングを正常に検出したことを示しています。
On the Size of Convex Hulls of Small Sets
小型セットの凸包のサイズについて
We investigate two different notions of “size” which appearnaturally in Statistical Learning Theory. We present quantitativeestimates on the fat-shattering dimension and on thecovering numbers of convex hulls of sets of functions, given thenecessary data on the original sets. The proofs we present arerelatively simple since they do not require extensive backgroundin convex geometry.
私たちは、統計的学習理論に自然に現れる「サイズ」の2つの異なる概念を調査します。私たちは、脂肪を粉砕する次元と、元のセットに関する必要なデータを考慮して、関数のセットの凸包の被覆数に関する定量的推定値を提示します。私たちが提示する証明は、凸幾何学の広範な背景を必要としないため、比較的単純です。
