醜いアヒルの子の定理

醜いアヒルの子の定理
平成１５年６月６日（金）
発表者藤井丈明
醜いアヒルの子の定理
醜いアヒルの子と普通のアヒルの子、すな
わち、白鳥の子とアヒルの子とは、似通っ
た2羽のアヒルの子が似ているのと同じ程
度に似ている
証明（１）
• 1羽の醜いアヒルの子を含むアヒル：n
• 特徴： d (S1（体が白い）､S2（目が黒
い）､･･･､S d )ただしここでの特徴は２値
• 識別可能なアヒルの数
n2
d
• 必要な特徴数
d  log2 n
証明（2）
• ここでは1羽のアヒルが１つのクラスを構成
する
 x1
S1
 x3
S2
 x8
 x4
 x6
 x7
 x5
S3
 x2
醜いアヒルの子の定理（特徴数が３の例）
証明（３）
• 得られる記述の数：N (S1 , S1  S2 , S1  S etc
N は任意の i (1  i  n) 個のクラスを含む集合
の総数
n
N   n Ci  2  1
n
i 1
証明（４）
• (4d 1)個の記述のうちあるアヒルについて
真であるものの個数： N T
自分以外の任意の i(0  i  n  1)個を含
む集合の数
n 1
NT   n1 Ci  2
n 1
i 0
これはどのアヒルについても同数
証明（５）
• 任意の2羽のアヒルが共有する（共に真で
ある）記述は2羽の属するクラス以外の任
意のi (0  i  n  2)個を含む集合の数
2
n2
これは2羽の選び方によらない
証明（６）
ともに真である記述の個数によって2羽のア
ヒルの類似性を評価する。任意の2羽を
選んだ時ともに真である記述数はいずれ
も等しい
醜いアヒルの子と普通のア
ヒルの子、同一ではない2羽のアヒルの子
の類似性は等しい。よって醜いアヒルと普
通のアヒルの識別は不可能である
まとめ
認識対象からある特徴を選び出すだけでは、
対象を複数のクラスに分けることは不可
能
特徴に重要性を付加することがパ
ター
ン選択の本質
人間価値判断
認識工学特徴の重み付け

Download Report