Теорема о гадком утенке - Ugly duckling theorem

Теорема о гадком утенке - это аргумент, показывающий, что классификация невозможна без какой-либо предвзятости . В частности, он предполагает конечное число свойств, комбинируемых с помощью логических связок , и конечное число объектов; он утверждает, что любые два разных объекта имеют одинаковое количество ( экстенсиональных ) свойств. Теорема названа в честь рассказа Ганса Христиана Андерсена « Гадкий утенок » 1843 года , потому что она показывает, что утенок так же похож на лебедя, как два лебедя друг на друга. Он был получен Сатоси Ватанабе в 1969 году.

Математическая формула

Пример Ватанабэ с использованием объектов A , B , C и свойств F («первый»), W («белый»). «0», «1», « ¬ », « ∧ », « ∨ » и « ⊕ » означают « ложь », « истина », « не », « и », « или », и « исключающее или ». , соответственно. Так как F происходит подразумевать W, каждый предикат , который может быть сформирован из F и W совпадает с другим, следовательно , есть только 8 экстенсионально различные возможные предикаты, каждый из которых показаны на отдельной строке. Белые утята A и B соглашаются с четырьмя из них (строки 2, 3, 4, 8), но то же самое делают и A и C (строки 3, 5, 7, 8), а также B и C (строка 1 , 3, 6, 8).

Предположим, что во вселенной есть n вещей, и кто-то хочет разделить их на классы или категории. У человека нет предвзятых представлений или предубеждений относительно того, какие категории являются «естественными» или «нормальными», а какие нет. Таким образом, нужно рассмотреть все возможные классы, все возможные способы создания наборов из n объектов. Есть такие способы, размер набора мощности из п объектов. Это можно использовать для измерения сходства между двумя объектами: и можно увидеть, сколько наборов у них общего. Однако нельзя. Любые два объекта имеют точно такое же количество общих классов, если мы можем сформировать любой возможный класс, а именно (половину общего количества классов). Чтобы убедиться, что это так, можно представить, что каждый класс представлен n- битной строкой (или целым числом в двоичной кодировке ), с нулем для каждого элемента не в классе и единицей для каждого элемента в классе. Как выясняется, такие струны есть. ${\ displaystyle 2 ^ {n}}$${\ Displaystyle 2 ^ {п-1}}$${\ displaystyle 2 ^ {n}}$

Поскольку есть все возможные варианты выбора нулей и единиц, любые две битовые позиции будут согласовываться ровно в половине случаев. Можно выбрать два элемента и переупорядочить биты так, чтобы они были первыми двумя, и представить числа, отсортированные лексикографически. Для первых чисел бит # 1 будет установлен в ноль, а для второго - в единицу. В каждом из этих блоков верхний бит № 2 будет установлен в ноль, а другой - как один, поэтому они согласны по двум блокам или по половине всех случаев. Независимо от того, какие два элемента вы выберете. Итак, если у нас нет предвзятого мнения о том, какие категории лучше, тогда все будет одинаково похоже (или одинаково непохожим). Количество предикатов, которым одновременно удовлетворяют два неидентичных элемента, постоянно для всех таких пар. Таким образом, требуется некоторая индуктивная предвзятость, чтобы делать суждения о предпочтении определенных категорий над другими. ${\ displaystyle 2 ^ {n} / 2}$${\ displaystyle 2 ^ {n} / 2}$${\ displaystyle 2 ^ {n} / 4}$${\ displaystyle 2 ^ {n} / 4}$${\ displaystyle 2 ^ {n} / 4}$

Логические функции

Позвольте быть набор векторов логических значений каждый. Гадкий утенок - это вектор, который меньше всего похож на других. Учитывая логические значения, это можно вычислить, используя расстояние Хэмминга . ${\ displaystyle x_ {1}, x_ {2}, \ dots, x_ {n}}$${\ displaystyle k}$

Однако выбор логических функций для рассмотрения мог быть несколько произвольным. Возможно, на основе оригинальных черт были черты, которые были важны для идентификации гадкого утенка. Набор логических значений в векторе может быть расширен за счет новых функций, вычисляемых как логические функции исходных функций. Единственный канонический способ сделать это - расширить его всеми возможными логическими функциями. Полученные завершенные векторы имеют особенности. Теорема о гадком утенке утверждает, что не существует гадкого утенка, потому что любые два завершенных вектора будут либо равны, либо различаться ровно в половине признаков. ${\ displaystyle k}$${\ displaystyle 2 ^ {k}}$

Доказательство. Пусть x и y - два вектора. Если они одинаковы, то их завершенные векторы также должны быть одинаковыми, потому что любая логическая функция от x будет согласована с одной и той же логической функцией от y. Если x и y различны, то существует координата, в которой -я координата отличается от -ой координаты . Теперь завершенные функции содержат все логические функции для логических переменных, причем каждая из них ровно один раз. Рассматривая эти булевы функции как полиномы от переменных над GF (2), разделите функции на пары, где -я координата содержится в виде линейного члена и не содержит этого линейного члена. Теперь, для каждой такой пары , и согласует точно одну из двух функций. Если они согласны с одним, они должны не согласиться с другим, и наоборот. (Считается, что это доказательство принадлежит Ватанабэ.) ${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle x}$${\ displaystyle i}$${\ displaystyle y}$${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle (е, г)}$${\ displaystyle f}$${\ displaystyle i}$${\ displaystyle g}$${\ displaystyle f}$${\ Displaystyle (е, г)}$${\ displaystyle x}$${\ displaystyle y}$

Обсуждение

Решением теоремы о гадком утенке было бы введение ограничения на способ измерения сходства путем ограничения свойств, участвующих в классификации, скажем, между A и B. Однако Medin et al. (1993) отмечают, что это на самом деле не решает проблему произвольности или предвзятости, поскольку в каких отношениях A похож на B: «зависит от контекста стимула и задачи, так что не существует однозначного ответа на вопрос о том, насколько схоже. один объект к другому ». Например, «стержень и зебра были бы более похожи, чем лошадь и зебра, если бы полосатый элемент имел достаточный вес. Конечно, если бы эти веса элементов были фиксированными, то эти отношения сходства были бы ограничены». Тем не менее, свойство «полосатая» как весовое «исправление» или ограничение само по себе является произвольным, что означает: «если нельзя указать такие критерии, утверждение о том, что категоризация основана на сопоставлении атрибутов, почти полностью бессмысленно».

Стамос (2003) заметил, что некоторые суждения об общем сходстве не произвольны в том смысле, что они полезны:

«Предположительно, процессы восприятия и концептуальные представления людей развились так, что информация, имеющая значение для человеческих потребностей и целей, может быть приблизительно аппроксимирована эвристикой подобия ... Если вы находитесь в джунглях и видите тигра, но вы решаете не использовать стереотипы (возможно, потому что вы полагаете, что сходство - ложный друг), тогда вы, вероятно, будете съедены. Другими словами, в биологическом мире стереотипы, основанные на достоверных суждениях об общем сходстве, статистически приводят к большему выживанию и репродуктивному успеху ».

Если одни свойства не считаются более заметными или «взвешенными» более важными, чем другие, все будет казаться одинаково похожим, поэтому Ватанабе (1986) писал: «любые объекты, поскольку они различимы, одинаково похожи».

В более слабой обстановке, предполагающей бесконечно много свойств, Мерфи и Медин (1985) приводят пример двух предполагаемых классифицированных вещей, слив и газонокосилок:

"Предположим, что нужно перечислить общие черты слив и газонокосилок, чтобы судить об их сходстве. Легко видеть, что список может быть бесконечным: оба весят менее 10 000 кг (и менее 10 001 кг), оба не существовало 10 000 000 лет назад (и 10 000 001 год назад), оба плохо слышат, оба могут быть отброшены, оба занимают место и т. д. Точно так же список различий может быть бесконечным ... любые два объекта могут быть произвольно похожими или отличается, изменяя критерий того, что считается релевантным атрибутом ".

Согласно Вудворду, теорема о гадком утенке связана с законом сохранения Шаффера для производительности обобщения , который гласит, что все алгоритмы для обучения булевых функций из примеров ввода / вывода имеют такую ​​же общую производительность обобщения, как и случайное угадывание. Последний результат обобщен Вудвордом на функции на счетно бесконечных областях.

Смотрите также

• Никаких бесплатных обедов в поиске и оптимизации
• Теорема о бесплатном обеде
• Идентичность неразличимого - Классификация (различимость) возможна (со смещением или без него ), но не может быть отдельных объектов или сущностей, которые имеют все свои общие свойства.

Примечания