Теорема о гадком утенке

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

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

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

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

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

Булевы функции

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

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

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

Обсуждение

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

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

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

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

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

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

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

См. также

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