Категория утилита

Полезность категории — это мера «качественности категории», определенная в Gluck & Corter (1985) и Corter & Gluk (1992) . Он пытается максимизировать как вероятность того, что два объекта в одной и той же категории имеют общие значения атрибутов, так и вероятность того, что объекты из разных категорий имеют разные значения атрибутов. Он был предназначен для замены более ограниченных показателей качества категории, таких как « действительность сигнала » ( Рид 1972 ; Рош и Мервис 1975 ) и «индекс словосочетания» ( Джонс 1983 ). Он обеспечивает нормативную теоретико-информационную меру предсказательного преимущества, получаемого наблюдателем, обладающим знанием данной структуры категорий (т. е. метками классов экземпляров), над наблюдателем, который не обладает знаниями о структуре категорий. В этом смысле мотивация для показателя полезности категории аналогична показателю получения информации , используемому при обучении дерева решений . В некоторых представлениях это также формально эквивалентно взаимной информации , как обсуждается ниже. Обзор полезности категории в ее вероятностном воплощении с приложениями к машинное обучение представлено в Witten & Frank (2005 , стр. 260–262).

Теоретико-вероятностное определение категории полезности

Теоретико -вероятностное определение категории полезности, данное Фишером (1987) и Виттеном и Франком (2005), выглядит следующим образом:

CU(C,F)={\tfrac {1}{p}}\sum _{c_{j}\in C}p(c_{j})\left[\sum _{f_{i}\in F}\sum _{k=1}^{m}p(f_{ik}|c_{j})^{2}-\sum _{f_{i}\in F}\sum _{k=1}^{m}p(f_{ik})^{2}\right]

где $F=\{f_{i}\},\ i=1\ldots n$ это размер- $n\$ набор $m\$ -арные особенности и $C=\{c_{j}\}\ j=1\ldots p$ представляет собой набор $p\$ категории. Термин $p(f_{ik})\$ обозначает предельную вероятность того, что функция $f_{i}\$ приобретает ценность $k\$ и термин $p(f_{ik}|c_{j})\$ обозначает категорию- условную вероятность того, что признак $f_{i}\$ приобретает ценность $k\$ учитывая , что рассматриваемый объект относится к категории $c_{j}\$ .

Мотивация и развитие этого выражения для категории полезности и роль множимого $\textstyle {\tfrac {1}{p}}$ как грубый контроль переобучения, приведен в вышеуказанных источниках. В общих чертах ( Fisher 1987 ) этот термин $\textstyle p(c_{j})\sum _{f_{i}\in F}\sum _{k=1}^{m}p(f_{ik}|c_{j})^{2}$ — это ожидаемое количество значений атрибутов, которые может правильно угадать наблюдатель, используя стратегию сопоставления вероятностей вместе со знанием меток категорий, в то время как $\textstyle p(c_{j})\sum _{f_{i}\in F}\sum _{k=1}^{m}p(f_{ik})^{2}$ — это ожидаемое количество значений атрибутов, которые наблюдатель может правильно угадать с помощью той же стратегии, но без каких-либо знаний о метках категорий. Таким образом, их различие отражает относительное преимущество, получаемое наблюдателем благодаря знанию структуры категорий.

Теоретико-информационное определение категории полезности

Теоретико -информационное определение категории полезности для набора сущностей с размером $n\$ двоичный набор функций $F=\{f_{i}\},\ i=1\ldots n$ и двоичная категория $C=\{c,{\bar {c}}\}$ дается в Gluck & Corter (1985) следующим образом:

CU(C,F)=\left[p(c)\sum _{i=1}^{n}p(f_{i}|c)\log p(f_{i}|c)+p({\bar {c}})\sum _{i=1}^{n}p(f_{i}|{\bar {c}})\log p(f_{i}|{\bar {c}})\right]-\sum _{i=1}^{n}p(f_{i})\log p(f_{i})

где $p(c)\$ - априорная вероятность принадлежности объекта к положительной категории $c\$ (при отсутствии какой-либо информации об особенностях), $p(f_{i}|c)\$ - это условная вероятность объекта, имеющего особенность $f_{i}\$ учитывая, что объект относится к категории $c\$ , $p(f_{i}|{\bar {c}})$ также является условной вероятностью объекта, обладающего признаком $f_{i}\$ учитывая, что объект относится к категории ${\bar {c}}$ , и $p(f_{i})\$ - априорная вероятность того, что объект обладает особенностью $f_{i}\$ (при отсутствии какой-либо информации о категории).

Интуиция, лежащая в основе приведенного выше выражения, заключается в следующем: Термин $p(c)\textstyle \sum _{i=1}^{n}p(f_{i}|c)\log p(f_{i}|c)$ представляет стоимость (в битах) оптимального кодирования (или передачи) информации о признаках, когда известно, что описываемые объекты принадлежат категории $c\$ . Аналогично, термин $p({\bar {c}})\textstyle \sum _{i=1}^{n}p(f_{i}|{\bar {c}})\log p(f_{i}|{\bar {c}})$ представляет стоимость (в битах) оптимального кодирования (или передачи) информации о признаках, когда известно, что описываемые объекты принадлежат категории ${\bar {c}}$ . Таким образом, сумма этих двух слагаемых в скобках представляет собой средневзвешенное значение этих двух затрат. Последний срок, $\textstyle \sum _{i=1}^{n}p(f_{i})\log p(f_{i})$ , представляет стоимость (в битах) оптимального кодирования (или передачи) информации о признаках, когда информация о категории недоступна. В приведенной выше формулировке значение категории полезности будет неотрицательным.

Категория полезности и взаимная информация

Глюк и Кортер (1985) и Кортер и Глюк (1992) отмечают, что категория полезности эквивалентна взаимной информации . Вот простая демонстрация природы этой эквивалентности. Предположим, что существует набор сущностей, каждый из которых имеет одинаковые $n$ функции, т. е. набор функций $F=\{f_{i}\},\ i=1\ldots n$ , где каждая функциональная переменная имеет мощность $m$ . То есть каждая функция имеет возможность принять любую из $m$ отдельные значения (которые не обязательно упорядочивать; все переменные могут быть номинальными); для особого случая $m=2$ эти функции будут считаться бинарными , но в более общем смысле для любых $m$ , особенности просто м-арные . Для целей этой демонстрации, без потери общности, набор функций $F$ можно заменить одной агрегатной переменной $F_{a}$ который имеет мощность $m^{n}$ и принимает уникальное значение $v_{i},\ i=1\ldots m^{n}$ соответствующий каждой комбинации признаков в декартовом произведении $\otimes F$ . (Порядковость не имеет значения, поскольку взаимная информация не чувствительна к порядковости.) В дальнейшем будет использоваться такой термин, как $p(F_{a}=v_{i})$ или просто $p(v_{i})$ относится к вероятности, с которой $F_{a}$ принимает особое значение $v_{i}$ . (Используя переменную совокупного признака $F_{a}$ заменяет многократное суммирование и упрощает изложение.)

Для этой демонстрации также предположим, что существует одна переменная категории $C$ , который имеет мощность $p$ . Это эквивалентно системе классификации, в которой существуют $p$ непересекающиеся категории. В частном случае $p=2$ существует случай двух категорий, описанный выше. Из определения взаимной информации для дискретных переменных взаимная информация $I(F_{a};C)$ между переменной совокупного признака $F_{a}$ и переменная категории $C$ дается:

I(F_{a};C)=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i},c_{j})\log {\frac {p(v_{i},c_{j})}{p(v_{i})\,p(c_{j})}}

где $p(v_{i})$ - априорная вероятность переменной признака $F_{a}$ принятие ценности $v_{i}$ , $p(c_{j})$ - предельная вероятность переменной категории $C$ принятие ценности $c_{j}$ , и $p(v_{i},c_{j})$ - совместная вероятность переменных $F_{a}$ и $C$ одновременно принимая эти соответствующие ценности. В терминах условных вероятностей это можно переписать (или определить) как

{\begin{aligned}I(F_{a};C)&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i},c_{j})\log {\frac {p(v_{i}|c_{j})}{p(v_{i})}}\\&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\left[\log p(v_{i}|c_{j})-\log p(v_{i})\right]\\&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\log p(v_{i}|c_{j})-\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\log p(v_{i})\\&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\log p(v_{i}|c_{j})-\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i},c_{j})\log p(v_{i})\\&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\log p(v_{i}|c_{j})-\sum _{v_{i}\in F_{a}}\log p(v_{i})\sum _{c_{j}\in C}p(v_{i},c_{j})\\&=\sum _{v_{i}\in F_{a}}\sum _{c_{j}\in C}p(v_{i}|c_{j})p(c_{j})\log p(v_{i}|c_{j})-\sum _{v_{i}\in F_{a}}p(v_{i})\log p(v_{i})\\\end{aligned}}

Если исходное определение категории полезности, данное выше, переписать с помощью $C=\{c,{\bar {c}}\}$ ,

CU(C,F)=\sum _{f_{i}\in F}\sum _{c_{j}\in C}p(f_{i}|c_{j})p(c_{j})\log p(f_{i}|c_{j})-\sum _{f_{i}\in F}p(f_{i})\log p(f_{i})

Это уравнение явно имеет ту же форму, что и ( синее ) уравнение, выражающее взаимную информацию между набором признаков и переменной категории; разница в том, что сумма $\textstyle \sum _{f_{i}\in F}$ в категории уравнение полезности пробегает независимые двоичные переменные $F=\{f_{i}\},\ i=1\ldots n$ , тогда как сумма $\textstyle \sum _{v_{i}\in F_{a}}$ во взаимной информации пробегает значения одного $m^{n}$ -арная переменная $F_{a}$ . Эти две меры фактически эквивалентны только тогда , когда функции $\{f_{i}\}$ , независимы (и предполагая, что члены суммы, соответствующие $p({\bar {f_{i}}})$ также добавлены).

Нечувствительность категории полезности к ординальности

Как и взаимная информация, утилита категории нечувствительна к какому-либо порядку значений переменных функции или категории. То есть, что касается полезности категории, набор категорий {small,medium,large,jumbo} качественно не отличается от набора категорий {desk,fish,tree,mop} поскольку формулировка категории полезности не учитывает какой-либо порядок переменной класса. Аналогично, функциональная переменная, принимающая значения {1,2,3,4,5} качественно не отличается от функциональной переменной, принимающей значения {fred,joe,bob,sue,elaine}. Что касается полезности категории или взаимной информации , все переменные категорий и признаков являются номинальными переменными. По этой причине категория полезности не отражает никаких гештальт- аспектов «категории добра», которые могли бы быть основаны на таких эффектах упорядочивания. Одна из возможных корректировок этой нечувствительности к порядковому номеру дается с помощью схемы взвешивания, описанной в статье для взаимной информации .

Категория «добро»: модели и философия

В этом разделе представлены некоторые сведения о происхождении и необходимости формальных показателей «качественности категории», таких как полезность категории, а также некоторые истории, которые привели к разработке этой конкретной метрики.

Что делает категорию хорошей?

По крайней мере, со времен Аристотеля в философии наблюдалось огромное увлечение природой понятий и универсалий . Что за сущность представляет собой такое понятие, как «лошадь»? Такие абстракции не обозначают какого-либо конкретного индивидуума в мире, и тем не менее мы едва ли можем представить себе возможность постичь мир без их использования. Имеет ли понятие «лошадь» независимое существование вне разума? Если да, то каково место этого независимого существования? Вопрос локуса был важным вопросом, по которому классические школы Платона и Аристотеля расходились во мнениях. Однако они остались согласны с тем, что универсалии действительно существуют независимо от разума. Таким образом, всегда существовал факт , какие понятия и универсалии существуют в мире.

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

Какой цели служат понятия?

Один из подходов к ответу на такие вопросы — исследовать «роль» или «цель» концепций в познании. Таким образом, ответ на вопрос: «Для чего вообще нужны концепции?» Милля (1843 , стр. 425) и многих других заключается в том, что классификация (концепция) является предшественником индукции : навязывая Вселенной определенную категоризацию, организм приобретает способность иметь дело с физически неидентичными объектами или ситуациями в одинаковым образом, тем самым получая существенную предсказательную силу ( Smith & Medin 1981 ; Harnad 2005 ). Как Дж. С. Милль выразился ( Mill 1843 , стр. 466–468),

Общая проблема классификации... [состоит] в том, чтобы обеспечить, чтобы вещи рассматривались в таких группах и в таком порядке, который лучше всего способствует запоминанию и установлению их законов... [и ] одно из применений такой классификации, которое, привлекая внимание к свойствам, на которых она основана и которые, если классификация хороша, являются признаками многих других, облегчает открытие этих других.

На этой основе Милль приходит к следующему выводу, который предвещает многие последующие размышления о категории добра, включая понятие категории полезности:

Цели научной классификации лучше всего достигаются, когда объекты формируются в группы, относительно которых можно сделать большее число общих предложений, причем эти предложения более важны, чем можно было бы сделать относительно любых других групп, по которым можно было бы распределить те же самые вещи. Следовательно, свойства, по которым классифицируются объекты, должны, по возможности, быть теми, которые являются причинами многих других свойств; или, во всяком случае, которые являются их верными признаками.

Это можно сравнить с «гипотезой полезности категории», предложенной Кортером и Глюком (1992) : «Категория полезна в той степени, в которой можно ожидать, что она улучшит способность человека точно предсказывать характеристики экземпляров этой категории». ." Здесь Милль, по-видимому, предполагает, что лучшая структура категорий — это та, в которой признаки (свойства) объекта максимально информативны о классе объекта, и одновременно класс объекта максимально информативен о характеристиках объекта. Другими словами, полезная схема классификации — это такая схема, в которой знание категорий может использоваться для точного вывода о свойствах объекта, а знание свойств может использоваться для точного вывода о классах объектов. Эту идею можно также сравнить с Аристотеля критерием контрпредикации для определяющих предикатов, а также с понятием понятий, описанным в формальном анализе понятий .

Попытки формализации

С целью формального отражения понятия «качественности категории» было предложено множество различных показателей, наиболее известным из которых, вероятно, является « валидность сигнала ». Сигнал валидности функции $f_{i}\$ относительно категории $c_{j}\$ определяется как условная вероятность категории с учетом признака ( Рид 1972 ; Рош и Мервис 1975 ; Рош 1978 ), $p(c_{j}|f_{i})\$ или как отклонение условной вероятности от базовой ставки категории ( Edell 1993 ; Kruschke & Johansen 1999 ), $p(c_{j}|f_{i})-p(c_{j})\$ . Очевидно, что эти меры количественно определяют только вывод от признака к категории (т. е. достоверность сигнала ), но не от категории к признаку, т. е. валидность категории. $p(f_{i}|c_{j})\$ . Кроме того, хотя изначально валидность сигнала была предназначена для объяснения наглядного появления базовых категорий в человеческом познании — категорий определенного уровня общности, которые, очевидно, предпочитаются обучающимися людьми, — в этом исследовании быстро выявился ряд серьезных недостатков валидности сигнала. уважение ( Джонс 1983 ; Мерфи 1982 ; Кортер и Глюк 1992 и другие).

Одна из попыток решить обе проблемы путем одновременной максимизации достоверности признаков и достоверности категорий была предпринята Джонсом (1983), определив «индекс коллокации» как произведение $p(c_{j}|f_{i})p(f_{i}|c_{j})\$ , но эта конструкция была довольно специальной (см. Corter & Gluck 1992 ). Категория полезности была введена как более сложная модификация валидности сигнала, которая пытается более строго количественно оценить полную силу вывода структуры класса. Как показано выше, в определенном представлении полезность категории эквивалентна взаимной информации между переменной признака и переменной категории. Было высказано предположение, что категории, имеющие наибольшую общую полезность, — это те, которые являются не только «лучшими» в нормативном смысле, но и теми, которые учащиеся предпочитают использовать, например, «базовые» категории ( Corter & Gluck 1992 ). Другими родственными мерами категории доброты являются «сплоченность» ( Хэнсон и Бауэр, 1989 ; Дженнари, Лэнгли и Фишер, 1989 ) и «выдаемость» ( Дженнари, 1989 ).

Приложения

Полезность категории используется в качестве меры оценки категории в популярном алгоритме концептуальной кластеризации под названием COBWEB ( Fisher 1987 ).

См. также

Ссылки

Кортер, Джеймс Э.; Глюк, Марк А. (1992), «Объяснение основных категорий: предсказуемость функций и информация» (PDF) , Psychoological Bulletin , 111 (2): 291–303, doi : 10.1037/0033-2909.111.2.291 , заархивировано из оригинала ( PDF) от 10 августа 2011 г.
Эджелл, Стивен Э. (1993), «Использование конфигурационной и размерной информации», Н. Джон Кастеллан (редактор), « Принятие индивидуальных и групповых решений: текущие проблемы» , Хиллсдейл, Нью-Джерси : Лоуренс Эрлбаум, стр. 43–64.
Фишер, Дуглас Х. (1987), «Получение знаний посредством поэтапной концептуальной кластеризации», Machine Learning , 2 (2): 139–172, doi : 10.1007/BF00114265
Дженнари, Джон Х. (1989), «Формирование целенаправленной концепции», Альберто Мария Сегре (ред.), Труды шестого международного семинара по машинному обучению , Итака, Нью-Йорк : Морган Кауфманн, стр. 379–382.
Дженнари, Джон Х.; Лэнгли, Пэт; Фишер, Дуг (1989), «Модели постепенного формирования концепций» , Искусственный интеллект , 40 (1–3): 11–61, doi : 10.1016/0004-3702(89)90046-5
Глюк, Марк А.; Кортер, Джеймс Э. (1985), «Информация, неопределенность и полезность категорий», Программа седьмой ежегодной конференции Общества когнитивных наук , стр. 283–287.
Хэнсон, Стивен Хосе; Бауэр, Малкольм (1989), «Концептуальная кластеризация, категоризация и полиморфия», Machine Learning , 3 (4): 343–372, doi : 10.1007/BF00116838
Харнад, Стеван (2005), «Познавать — значит классифицировать: Познание — это категоризация» , в книге Анри Коэна и Клэр Лефевр (ред.), Справочник по категоризации в когнитивной науке , Амстердам: Elsevier, стр. 19–43.
Джонс, Грегори В. (1983), «Определение основных категорий», Psychoological Bulletin , 94 (3): 423–428, doi : 10.1037/0033-2909.94.3.423
Крушке, Джон К .; Йохансен, Марк К. (1999), «Модель вероятностного категорийного обучения», Журнал экспериментальной психологии: обучение, память и познание , 25 (5): 1083–1119, doi : 10.1037/0278-7393.25.5.1083 , PMID 10505339
Милль, Джон Стюарт (1843), Система логики, рациональности и индуктивности: взаимосвязанный взгляд на принципы доказывания и методы научного исследования , Лондон: Лонгманс, Грин и компания .
Мерфи, Грегори Л. (1982), «Достоверность сигнала и уровни категоризации», Psychoological Bulletin , 91 (1): 174–177, doi : 10.1037/0033-2909.91.1.174
Рид, Стивен К. (1972), «Распознавание образов и категоризация», Cognitive Psychology , 3 (3): 382–407, doi : 10.1016/0010-0285(72)90014-x
Рош, Элеонора (1978), «Принципы категоризации», в книге Элеоноры Рош и Барбары Б. Ллойд (редактор), « Познание и категоризация» , Хиллсдейл, Нью-Джерси : Лоуренс Эрлбаум, стр. 27–48.
Рош, Элеонора; Мервис, Кэролин Б. (1975), «Семейные сходства: исследования внутренней структуры категорий», Cognitive Psychology , 7 (4): 573–605, doi : 10.1016/0010-0285(75)90024-9 , S2CID 17258322
Смит, Эдвард Э.; Медин, Дуглас Л. (1981), Категории и понятия , Кембридж, Массачусетс : Издательство Гарвардского университета
Виттен, Ян Х.; Франк, Эйбе (2005), Интеллектуальный анализ данных: практические инструменты и методы машинного обучения , Амстердам: Морган Кауфманн.