15 最小記述長

属性評価を計算する監視あり手法である最小記述長を使用する方法を学習します。

MDLとは

最小記述長(MDL)は、情報理論モデルの選択原理の1つである。それは、情報理論(情報の定量化の研究)および学習理論(経験的データに基づく一般化の容量の研究)における重要な概念です。

MDLでは、最も単純でコンパクトな表現が、データの説明として最適かつ最も可能性が高いとみなされます。MDL原理は、Oracle Data Miningの属性評価モデルの作成に使用されます。

属性評価の作成プロセスはパラレル実行をサポートします。パラレル実行の詳細は、『Oracle Database VLDBおよびパーティショニング・ガイド』を参照してください。

圧縮とエントロピ

データ圧縮は、元の表現より少ないビット数を使用して情報をエンコードするプロセスです。MDL原理は、データの最も短い説明が最も可能性が高いという考えに基づきます。この原理の典型的な事例では、モデルは、次に示すとおり不確実性(エントロピ)を低減してデータを圧縮するために使用されます。データの説明には、モデルの説明と、モデルの説明に従ったデータが含まれます。

エントロピは、不確実性の測度です。それは、値を指定するために必要な情報として、不確実性を確率変数に定量化します。ここでは情報は、完全な仕様で答える必要のあるビット(0または1としてエンコード)と呼ばれるyes/no質問の数として定義されます。このため、情報は、変数が想定できる値の数に依存します。

たとえば、変数が個人の性別を表す場合、指定可能な値の数は2つ(女性と男性)です。変数が全額ドルで示される個人の給与を表す場合、その値の範囲は$0から$10B (数十億の一意の値)になる可能性があります。明らかに、個人の性別を指定するより正確な給与を指定する方が多くの情報を必要とします。

確率変数の値: 統計的分布

情報(ビット数)は、変数の値の統計的分布と、変数の値の数に依存します。Yes/No質問の選択を慎重に行う場合、給与指定の情報量は、最初に示したほど多くはならない可能性があります。ほとんどの人々は、10億ドルの給与をもらっていません。大多数の人々の給与の範囲が$32000から$64000である場合、通常、その給与を特定するために必要な質問数は、15個のみです($0から$1000000000のすべての給与が同様に確からしい場合、質問数は30個必要です)。前者の例で、その人が妊娠している場合、性別は女性であることがわかります。不確実性は存在せず、Yes/No質問を尋ねる必要はありません。エントロピは0です。

確率変数の値: 重要な予測子

一部の確率変数で、その値がわかっているときに確率変数の不確実性が低下する予測子が存在すると仮定します。たとえば、ある人物が妊娠しているかどうかを知ることで、確率変数の個人の性別の不確実性は低下します。この予測子は、モデルに含める必要のある重要な特徴のように見えます。名前はどうでしょうか。特定の人物の名前を知っている場合、その人物の性別もわかると仮定します。その場合、名前の予測子は、不確実性を0 (ゼロ)に低下するように見えます。ただし、名前が一意である場合、どうなるでしょうか。その人物の名前はサリーでしょうか。その人物の名前はジョージでしょうか... このように、存在する人の数だけ名前モデルのYes/No予測子を使用することになります。つまり、名前モデルを指定する場合、各人物の性別指定と同じ数のビットが必要になります。

合計エントロピ

確率変数Xで、合計エントロピは、確率(X)の2を底とする対数によって乗じられたマイナスの確率(X)として定義されます。これは、変数の最も効率的なエンコーディングとみなすことができます。

モデル・サイズ

最小記述長(MDL)では、モデルのサイズに加え、モデルの使用を要因とする不確実性の低下が考慮されます。モデル・サイズとエントロピは、両方ともビットで測定されます。ここでの目的のため、量的予測子と質的予測子の両方がビニングされます。そのため、各単一予測子のモデルのサイズは、予測子ビンの数です。不確実性は、ビン内のターゲット分布まで低下します。

モデル選択

最小記述長(MDL)は、各属性をターゲット・クラスの単純な予測モデルと見なします。モデル選択とは、単一予測子のモデルを比較およびランク付けするプロセスのことです。

MDLでは、モデル選択の問題を解決するために通信モデルを使用します。通信モデルには、送信者、受信者および送信するデータがあります。

単一予測子のこれらのモデルは、MDLメトリック(ビット単位での相対的な圧縮)に関して互いに比較され、ランク付けされます。MDLでは、オーバーフィットを回避するため、モデルの複雑性にペナルティが課されます。これは、比較を公平に行うために(モデルとしての)予測子の複雑性を考慮した、合理的なアプローチです。

MDLメトリック

属性評価では、2つの部分で構成されるコードをメトリックとして使用し、各データ単位を送信します。前半部分(プリアンブル)ではモデルを送信します。モデルのパラメータは、予測の各値に関連するターゲットの確率です。

ターゲットの値がj個、予測子の値がk個、各値に対してn_i (i= 1、...、k)個の行がある場合、C_i個(n_i-1個からj-1個を一度に選び出す組合せの数)の条件付き確率が考えられます。プリアンブルのビット・サイズは、Sum(log₂(C_i))と示すことができ、ここで、Sumはkに対する合計です。こうして計算した値が、それぞれの単一予測モデルに関連付けられるペナルティを表します。コードの後半部分では、モデルを使用してターゲット値を送信します。

シーケンスの最もコンパクトな符号化とは、記号(ターゲット・クラス値)の確率に最も適合する符号化であることがよく知られています。したがって、シーケンスに最も高い確率を割り当てるモデルには、最小のターゲット・クラス値の送信コストが含まれます。これは、ビットではSum(log₂(p_i))となり、ここで、p_iは、モデルに関連する行_iの予測確率です。

予測子のランクは、関連付けられた記述長のリストにおける位置で表されます(最短が先頭)。

MDL用のデータ準備

自動データ準備は、最小記述長(MDL)の監視ありビニングを実行します。監視ありビニングでは、ディシジョン・ツリーを使用して最適なビンの境界が作成されます。質的属性と量的属性のいずれもビニングされます。

MDLでは、欠損値をそのまま(ランダムに欠損している値として)処理します。スパースな量的データは0 (ゼロ)に置換され、スパースな質的データはゼロ・ベクトルに置換されます。ネストした列の欠損値はスパースとして解釈されます。単純なデータ型の列の欠損値は、ランダムに欠損した値として解釈されます。

独自のデータ準備を行う場合、MDLでは通常ビニングを行うことによってメリットが得られます。ただし、データ内に外れ値が存在する場合に外部等幅ビニングを使用すると、属性評価モデルの識別能力が著しく低下することがあります。この手法では、ほとんどのデータが少数のビン(極端な場合は単一のビン)に集中する可能性があります。この場合、より優れた解決策として、分位ビニングを使用します。