醜いアヒルの子の定理

醜いアヒルの子の定理 (ugly duckling theorem)†

醜いアヒルの子を含む \(n\)匹のアヒルがいるとする．このとき，醜いアヒルの子と普通のアヒルの子の類似性は，任意の二匹の普通のアヒルの子の間の類似性と同じになるという定理．

\(n\)匹のアヒルの子を区別するために，\(K=\log(n)\)個の二値の特徴量を使う．これらの特徴量を使ってできるルールは，各アヒルについて含む・含まないが独立にありうるが，どのアヒルも含まないルールは除外するので，全部で \(N=2^n-1\)個存在．

これら \(N\)個のルールのうち，醜いアヒルの子とある普通のアヒルの子のどちらも含むようなルールは \(2^{n-2}\)個．一方，任意の二匹の普通のアヒルの子を同時に含むルールはやはり \(2^{n-2}\)個．二匹のアヒルの類似性を，これらを共通に真にするルールの数で評価すると，醜いアヒルの子と普通のアヒルの子は，アヒルの子どうしと同じくらい類似していることになる．

これは，各特徴量を全て同等に扱っていることにより成立する定理．すなわち，クラスというものを特徴量で記述するときには，何らかの形で特徴量に重要性を考えていることになる．この定理は，特徴選択や特徴抽出が識別やパターン認識にとって本質的であることを示唆している．