醜小鴨定理

醜小鴨定理是一項論證，其表明若無某種偏見，分類實際上是無法進行的。更具體地說，該定理假設存在有限多個可由邏輯連接詞組合的屬性，以及有限多個物體；它斷言任何兩個不同的物體都共享相同數量的（外延）屬性。該定理得名於安徒生1843年的故事《醜小鴨》，因為它表明一隻小鴨與一隻天鵝的相似程度，等同於兩隻天鵝之間的相似程度。此定理由渡邊慧於1969年提出。

數學公式

假設宇宙中有 n 個事物，而我們想將它們歸入不同的類別或範疇。我們對於何種類別是「自然的」或「正常的」，何者不是，沒有任何先入為主的觀念或偏見。因此，我們必須考慮所有可能的類別，也就是從 n 個物體中建立集合的所有可能方式。這樣的方式共有 <math>2^n</math> 種，即 n 個物體的冪集合的大小。我們可以用這個方式來衡量兩個物體之間的相似性，看看它們共同隸屬多少個集合。然而，這樣做是行不通的。如果我們可以形成任何可能的類別，那麼任何兩個物體所共同隸屬的類別數量是完全相同的，即 <math>2^{n-1}</math> 個（是總類別數量的一半）。為了理解這一點，我們可以想像每個類別都由一個 n 位元字串（或二進位編碼整數）表示，若某元素不在此類別中，其對應位元為0，若在，則為1。我們會發現，這樣的字串共有 <math>2^n</math> 個。

由於所有可能的0和1的組合都存在，任何兩個位元位置上的值會有一半的情況是相同的。我們可以選取兩個元素，並重新排序位元，使它們位於前兩位，然後想像這些數字按字典序排序。前 <math>2^n/2</math> 個數字的第1位元將設為0，後 <math>2^n/2</math> 個數字的第1位元將設為1。在每一個區塊中，前 <math>2^n/4</math> 個數字的第2位元將設為0，其餘 <math>2^n/4</math> 個數字的第2位元則為1，因此無論選擇哪兩個元素，它們在兩個 <math>2^n/4</math> 大小的區塊中、即所有情況的一半中，位元值都會相同。所以，如果我們對於哪些類別更好沒有先入為主的偏見，那麼萬物之間的相似（或不相似）程度都是相等的。任意兩個不同元素同時滿足的謂詞數量，對於所有這樣的元素對都是一個常數。因此，需要某種歸納偏置，才能做出判斷，偏好某些類別而非其他類別。

布林函數

令 <math>x_1, x_2, \dots, x_n</math> 為一組向量，每個向量包含 <math>k</math> 個布林值。醜小鴨是指與其他向量最不相似的那個向量。給定這些布林值，這可以透過漢明距離計算出來。

然而，要考慮哪些布林特徵的選擇可能有些隨意。或許有些從原始特徵中衍生的特徵，對於辨識醜小鴨很重要。向量中的布林值集合可以擴展，加入由原始 <math>k</math> 個特徵的布林函數計算出的新特徵。唯一標準的做法是將其擴展至包含所有可能的布林函數。由此產生的完備向量具有 <math>2^k</math> 個特徵。醜小鴨定理指出，不存在醜小鴨，因為任何兩個完備向量若不相等，則它們恰好會在半數的特徵上有所不同。

證明。令 x 和 y 為兩個向量。如果它們相同，那麼它們的完備向量也必然相同，因為對 x 進行任何布林函數運算的結果都會與對 y 進行相同布林函數運算的結果一致。如果 x 和 y 不同，則存在一個座標，使得 x 的第 個座標與 y 的第 個座標不同。現在，完備特徵包含了對 <math>k</math> 個布林變數的每一個可能的布林函數，且每個函數只出現一次。將這些布林函數視為 GF(2) 上 <math>k</math> 個變數的多項式，並將這些函數分成數對 <math>(f,g)</math>，其中 <math>f</math> 包含第 個座標作為線性項，而 <math>g</math> 則是 <math>f</math> 去掉該線性項後的結果。如此一來，對於每一對 <math>(f,g)</math>，x 和 y 將在兩個函數中的其中一個達成一致。 如果它們在其中一個函數上達成一致，就必然在另一個函數上不一致，反之亦然。（此證明據信由渡邊慧提出。）

討論

要迴避醜小鴨定理，一個可能的方法是透過限制分類時所涉及的屬性，來對相似性的衡量方式加以約束，例如在 A 和 B 之間。然而，Medin 等人（1993）指出，這實際上並未解決任意性或偏見的問題，因為 A 在哪些方面與 B 相似這一點：「會隨著刺激情境和任務而變化，因此『一個物體與另一個物體的相似程度為何』這個問題，沒有唯一的答案」。例如：「如果『條紋』這個特徵有足夠的權重，那麼理髮店的旋轉燈柱和斑馬會比馬和斑馬更相似。當然，如果這些特徵權重是固定的，那麼這些相似性關係就會受到約束」。然而，將「條紋」這個屬性作為一個權重「定值」或約束本身就是任意的，這意味著：「除非能明確指出此類標準，否則基於屬性匹配進行分類的主張幾乎是完全空洞的」。

Stamos（2003）評論道，從實用性的角度來看，一些關於整體相似性的判斷並非是任意的：

除非某些屬性被認為比其他屬性更顯著，或被賦予更高的「權重」，否則萬物看起來都會同樣相似，因此渡邊慧（1986）寫道：「任何物體，只要它們是可區分的，它們的相似程度就都相等」。

在一個假設屬性無限多的較弱設定下，Murphy 和 Medin（1985）舉了兩個假定被分類的事物為例：李子和割草機。

根據 Woodward 的說法， 醜小鴨定理與夏弗的泛化性能守恆定律（Schaffer's Conservation Law for Generalization Performance）有關，該定律指出，所有從輸入／輸出範例中學習布林函數的演算法，其整體的泛化性能與隨機猜測相同。 後一個結果被 Woodward 推廣到可數無限域上的函數。

參見

• 搜尋與最佳化中的「沒有免費的午餐」
• 沒有免費午餐定理
• 不可區分者同一性原則 – 分類（可區分性）是可能的（無論有無偏見），但不可能存在擁有一切共同屬性的獨立物體或實體。
• 歸納法的新謎題