Категория полезности

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

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

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

${\ Displaystyle 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]}$

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

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

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

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

${\displaystyle 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})}$

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

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

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

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

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

${\displaystyle 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})}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle 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})}$

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

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

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

Категория «добро»: модели и философия [ править ]

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

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

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

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

Какой цели служат концепции? [ редактировать ]

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

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

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

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

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

Попытки формализации [ править ]

Было предложено множество различных мер с целью формального закрепления этого понятия «категория добродетели», наиболее известной из которых, вероятно, является « достоверность реплики ». Достоверность признака по отношению к категории определяется как условная вероятность категории, данной признаку ( Reed 1972 ; Rosch & Mervis 1975 ; Rosch 1978 ) , или как отклонение условной вероятности от базовой ставки категории ( Edgell +1993 ; Kruschke & Джохэнсен 1 999 ), . Очевидно, что эти меры количественно определяют только вывод от характеристики к категории (т. Е. Достоверность сигнала ), но не от категории к функции, т. Е.${\displaystyle f_{i}\ }$${\displaystyle c_{j}\ }$${\displaystyle p(c_{j}|f_{i})\ }$${\displaystyle p(c_{j}|f_{i})-p(c_{j})\ }$категория валидность . Кроме того, хотя достоверность реплики изначально предназначалась для объяснения очевидного появления базовых категорий в человеческом познании - категорий определенного уровня общности, которые, очевидно, предпочитают человеческие ученики, - в этом быстро выявился ряд серьезных недостатков валидности реплики. внимание ( Jones 1983 ; Murphy 1982 ; Corter & Gluck 1992 и др.).${\displaystyle p(f_{i}|c_{j})\ }$

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

Приложения [ править ]

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

См. Также [ править ]

• Абстракция
• Концептуальное обучение
• Универсалии
• Обучение без учителя

Ссылки [ править ]