Вероятностные модели и методы оценки качества эталонных массивов текстов при классификации © В. Г. Васильев ООО «ЛАН-ПРОЕКТ», г. Москва vvg_2000@mail.ru Оценку качества эталонных массивов проводить Аннотация в следующих двух ситуациях. В работе рассматриваются вероятностные 1. Эталонный массив подготовлен ранее модели ошибок экспертов при неизвестными экспертами – в данном случае у формировании эталонных массивов текстов, документа имеется только одна оценка, полученная а также методы их вычисления. В рамках неизвестным экспертом, и нет возможности данных моделей находятся взаимосвязи управления работой экспертов. между истинными и наблюдаемыми 2. Эталонный массив формируется известными показателями качества, определяются экспертами – в данном случае для каждого размеры тестовых выборок и максимальные документа имеется фиксированное число оценок, значения показателей качества. Приводятся выполненных известными экспертами, и можно примеры вычисления ошибок на материалах управлять процессом оценки документов. дорожек РОМИП. В современной литературе основное внимание уделяется второй ситуации и оценка качества 1 Введение эталонного массива часто сводится к простой При практическом построении средств оценке степени согласованности мнений экспертов. автоматической классификации возникает большое Для оценки согласованности мнений экспертов количество различных проблем, связанных разработано много различных коэффициентов и сложностью и недостатками исходных данных, показателей. При этом наибольшее распространение ограниченностью существующих методов получили методы [1],[3],[5],[14], основанные на классификации и др. [7],[10],[12],[15]. использовании различных вариантов статистики 𝜅, При оценке качества классификации обычно которая имеет следующий вид: производится сравнение результатов 𝐴0 − 𝐴𝑒 автоматической классификации с результатами 𝜅= , 𝐴𝑚𝑎𝑥 − 𝐴𝑒 ручной классификации, выполненной экспертами. где 𝐴0 - базовая статистика, оценивающая При этом предполагается, что в эталонной ручной согласованность мнений экспертов, 𝐴𝑒 - оценка классификации ошибки отсутствуют. Однако на значения 𝐴0 в случае выполнения случайной практике эксперты при оценивании документов классификации объектов, 𝐴𝑚𝑎𝑥 - оценка также совершают ошибки, которые могут быть максимально возможного значения 𝐴0 . вызваны различными причинами: невнимательностью, случайными опечатками, Для проверки гипотезы о наличии статистически неоднозначностью наименования рубрик, низкой значимого отклонения меры согласованности от квалификацией экспертов в рассматриваемой нулевого значения требуется знание распределения предметной области, большим количеством рубрик 𝜅. На практике такое распределение удается и др. В результате получаемые оценки качества аналитически описать только для простейших являются искаженными и даже для полностью случаев. По этой причине для проверки правильной классификации показатели качества соответствующих гипотез обычно используют могут отличаться от своих максимальных значений. бутстреп метод [9]. В некоторых работах [2] предлагают использовать следующие неформальные Развитие специальных сервисов в сети Интернет, которые обеспечивают привлечение к работе по оценки значений 𝜅. Если 𝜅 < 0.4, то считается, что формированию эталонных массивов текстов мнения не согласованы, если 0.4 ≤ 𝜅 < 0.75, то большого количества анонимных пользователей, считается, что мнения слабо согласованы, и, если дополнительно повышают актуальность 𝜅 > 0.8, то мнения сильно согласованы. Однако исследований в области оценки качества такой подход является не совсем корректным, так получаемых таким образом массивов. как с ростом числа объектов статистически значимыми являются и меньшие отклонения 𝜅 от 0. 127 Основным же недостатком данных методов является 𝐶̂ 0 = �𝑐̂𝑗𝑖0 � – наблюдаемая экспертная матрица 𝑘×𝑛 то, что значения статистики 𝜅 напрямую не связаны эталонной классификации, в которой есть ошибки; со значениями показателей качества классификации. 𝐶 1 = �𝑐𝑗𝑖1 � – наблюдаемая матрица Отдельные вопросы прямого влияния ошибок 𝑘×𝑛 экспертов на качество классификации и автоматической классификации, качество которой информационного поиска также рассматривались в оценивается, ряде работ. В частности, в [6] приводятся где 𝑐𝑗𝑖0 , 𝑐̂𝑗𝑖0 , 𝑐𝑗𝑖1 = 1, если объект 𝑥𝑖 относится к классу теоретические оценки влияния ошибок экспертов на 𝜔𝑗 , и 𝑐𝑗𝑖0 , 𝑐̂𝑗𝑖0 , 𝑐𝑗𝑖1 = 0, в противном случае, 𝑖 = 1, … , 𝑛, величину ошибки классификации, ее дисперсию, 𝑗 = 1, … . , 𝑘. размер тестовых выборок, в [12] проводится анализ вероятностей ошибок, допускаемых оценщиками в Основные показатели качества классификации различных ситуациях, в [4] информация о могут быть представлены в виде следующих вероятностях ошибок экспертов использовалась для вероятностей: улучшения функций ранжирования документов, а в 𝑃𝑗0 = 𝑃( 𝑐𝑗0 = 1| 𝑐𝑗1 = 1), 𝑃𝑗1 = 𝑃( 𝑐̂𝑗0 = 1| 𝑐𝑗1 = 1) [8] для оценки верхних границ для показателей – истинное и наблюдаемое значение точности; качества информационного поиска. Основной 𝑅𝑗0 = 𝑃( 𝑐𝑗1 = 1| 𝑐𝑗0 = 1), 𝑅𝑗1 = 𝑃( 𝑐𝑗1 = 1| 𝑐̂𝑗0 = 1) проблемой, которая пока не получила эффективного – истинное и наблюдаемое значение полноты; решения, при этом является нахождение соответствующих оценок вероятностей ошибок 𝐸𝑗0 = 𝑃( 𝑐𝑗0 ≠ 𝑐𝑗1 ), 𝐸𝑗1 = 𝑃( 𝑐̂𝑗0 ≠ 𝑐𝑗1 ) – истинное экспертов. и наблюдаемое значение ошибки классификации; Рассмотрим теперь формальное описание 2𝑃� 𝑐𝑗0 =1, 𝑐𝑗1 =1� 2𝑃� 𝑐̂𝑗0 =1, 𝑐𝑗1 =1� моделей ошибок экспертов, в рамках которых 𝐹𝑗0 = , 𝐹𝑗1 = – 𝑃� 𝑐𝑗0 =1�+𝑃� 𝑐𝑗1 =1� 𝑃� 𝑐̂𝑗0 =1�+𝑃� 𝑐𝑗1 =1� можно явным образом оценивать их вероятности и истинное и наблюдаемое значение F-меры. влияние на показатели качества классификации. При этом для обозначения вероятностей классов будем использовать следующие обозначения: 2 Вероятностные модели ошибок 𝜋𝑗0 = 𝑃� 𝑐𝑗0 = 1�, 𝜋𝑗1 = 𝑃� 𝑐𝑗1 = 1�, 𝜋�𝑗 = 𝑃� 𝑐̂𝑗0 = 1�. экспертов Далее будем считать, что зафиксирован класс 2.1 Общее описание вероятностных моделей 𝜔𝑗 , 𝑗 = 1, … , 𝑘, и все показатели качества, а также элементы векторов и матриц классификации, для Для анализа влияния ошибок в эталонном сокращения записи будем записывать без индекса 𝑗. массиве на показатели качества классификации Например, элементы 𝑐𝑗0 , 𝑐̂𝑗0 , 𝑐𝑗1 будем записывать будем считать, что имеется объект (текст) 𝑥, 𝑐 0 , 𝑐̂ 0 , 𝑐1 . который может быть одновременно отнесен к нескольким классам из множества Ω = {𝜔1 , … , 𝜔𝑘 }. Рассмотрим следующие модели ошибок экспертов: Результаты классификации отдельного объекта 𝑥 можно представить с помощью следующих - модель независимых ошибок – предполагается, векторов: что ошибки носят случайный характер и не зависят от значений истинного вектора эталонной 𝑐 0 = (𝑐10 , … , 𝑐𝑘0 ), 𝑐𝑗0 ∈ {0,1} – ненаблюдаемый классификации; истинный вектор эталонной классификации объекта - модель условных ошибок – предполагается, что 𝑥; ошибки, совершаемые экспертом, зависят от 𝑐̂ 0 = (𝑐̂10 , … , 𝑐̂𝑘0 ), 𝑐̂𝑗0 ∈ {0,1} – наблюдаемый значений истинного вектора эталонной экспертный вектор эталонной классификации классификации. объекта 𝑥 (данный вектор может отличаться от истинного вектора из-за наличия ошибок); 2.2 Модель независимых ошибок экспертов 𝑐1 = (𝑐11 , … , 𝑐𝑘1 ), 𝑐𝑗1 ∈ {0,1} – наблюдаемый В рамках данной модели взаимосвязь истинной и вектор оцениваемой (автоматической) экспертной классификации можно представить в классификации объекта 𝑥 (данный вектор может виде следующего соотношения: отличаться от истинного вектора), 𝑐̂ 0 = 𝑐 0 (1 − 𝑧) + (1 − 𝑐 0 )𝑧 = 𝑐 0 + 𝑧 − 2𝑐 0 𝑧, где 𝑐𝑗0 , 𝑐̂𝑗0 , 𝑐𝑗1 = 1, если объект 𝑥 относится к классу где 𝑧 ∼ 𝐵𝑒𝑟(𝜖) – независимая случайная величина, 𝜔𝑗 , и 𝑐𝑗0 , 𝑐̂𝑗0 , 𝑐𝑗1 = 0, в противном случае, 𝑗 = 1, … , 𝑘. 𝜖 ∈ [0,1] – вероятность успеха, т.е. 𝑃(𝑧 = 1) = 𝜖 и Соответственно результаты классификации 𝑛 𝑃(𝑧 = 0) = 1 − 𝜖. Заметим, что при z = 1 объектов 𝑥1 , … , 𝑥𝑛 , которые распределены по 𝑘 справедливо c� 0 ≠ c 0 , а при z = 1 справедливо классам 𝜔1 , … , 𝜔𝑘 , могут быть представлены с c� 0 = c 0 . помощью следующих матриц размера 𝑘 × 𝑛: Можно показать, что вероятности ошибок первого и второго рода, а также ошибки 𝐶 0 = �𝑐𝑗𝑖0 � – ненаблюдаемая истинная 𝑘×𝑛 классификации совпадают и равны 𝜖. Также матрица эталонной классификации, в которой нет справедливо свойство о независимости ошибок ошибок; экспертной и автоматической классификации. 128 1 Утверждение 1. Пусть 𝜖 ≠ , тогда в рамках 1 2 модели независимых ошибок справедливы R1=0.8 R1=0.6 следующие соотношения между истинными и 0.9 R1=0.5 наблюдаемыми значениями показателей качества R1=0.4 классификации: 0.8 𝐸 1 −𝜖 𝐸0 = , 𝐸1 = 𝐸 0 (1 − 2𝜖) + 𝜖 , где 𝐸1 ≥ 𝜖, 0.7 R0 1−2𝜖 𝑃1 −𝜖 𝑃0 = , 𝑃1 = 𝑃0 (1 − 2𝜖) + 𝜖, где 𝑃0 ≥ 𝜖, 0.6 1−2𝜖 𝑅1𝜋 � −𝜖𝜋1 �(1−2𝜖)𝜋0 𝑅 0 +𝜖𝜋1 � 𝑅0 = , 𝑅1 = (1−2𝜖)𝜋0 +𝜖 , где 𝑅1 𝜋� ≥ 0.5 𝜋 � −𝜖 1 𝜖𝜋 0.4 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 1 1 1 𝐹 �𝜋 +𝜋� �−𝜖𝜋1 𝜖𝜋1 +(1−2𝜖)�𝜋1 +𝜋0 �𝐹0 ε, π1=0.2 0 1 𝐹 = 2 1 ,𝐹 =2 .█ (1−2𝜖)𝜋 +(𝜋 � −𝜖) 𝜋1 +𝜋0 (1−2𝜖)+𝜖 Рис. 2. График зависимости оценки истинной Таким образом, с использованием выражений, полноты 𝑅0 от вероятности ошибки эксперта при приведенных в утверждении 1, можно зная уровень различных фиксированных значениях наблюдаемой ошибок экспертов восстанавливать истинные полноты 𝑅1 и фиксированных значениях 𝜋 1 = 𝜋� = значения показателей качества классификации по 0.2 наблюдаемым экспертным показателям. Как можно заметить из приведенного рисунка 1 Заметим, что при 𝜖 = экспертные оценки даже при небольших значениях вероятности ошибки 2 показателей качества становятся не связанными с эксперта 𝜖 истинные и наблюдаемые значения истинными значениями показателей качества, так полноты могут существенно отличаться. как в данном случае 𝐸1 = 1/2, 𝑃1 = 1/2, 𝑅1 = 𝜋 1 , 1 что не позволяет восстанавливать значения F1=0.8 истинных показателей качества. 0.9 F1=0.6 F1=0.5 С использованием приведенных соотношений 0.8 F1=0.4 можно оценить диапазон изменения показателей 0.7 качества при изменении уровня ошибок экспертов. Следствие 1. При фиксированном значении 0.6 F0 ϵ ∈ (0,1) получаем, что E1 ∈ (ϵ, 1 − ϵ), P1 ∈ 0.5 1 ϵπ1 ϵ�1−π1 � (ϵ, 1 − ϵ), R ∈ � , 1 − (1−2ϵ)π0 �. 0.4 (1−2ϵ)π0 +ϵ +ϵ На следующих рисунках приведены значения 0.3 наблюдаемых показателей качества при 0.2 фиксированных значениях истинных показателях 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 ε, π1=0.2 качества и различных значениях ошибки. Рис. 3. График зависимости оценки истинной F- 1 меры 𝐹 0 от вероятности ошибки эксперта 𝜖 при P1=0.8 0.9 P1=0.6 различных фиксированных значениях наблюдаемой 0.8 P1=0.5 F-меры 𝐹1 и фиксированных значениях 𝜋 1 = 𝜋� = 0.2 P1=0.4 0.7 Как можно заметить из приведенного рисунка 0.6 ошибка эксперта оказывает относительно меньшее 0.5 влияние на значения F-меры, чем на значения P0 0.4 полноты, но наблюдаемые значения все равно могут 0.3 заметно отличаться. 0.2 0.1 2.3 Модель условных ошибок экспертов 0 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 В рамках данной модели предполагается, что ε вероятность ошибки эксперта зависит от того Рис. 1. График зависимости оценки истинной относится документ к рубрике или нет. Взаимосвязь точности 𝑃0 от ошибки эксперта при различных истинной и экспертной классификации можно наблюдаемых значениях точности 𝑃1 представить в виде следующего соотношения: Из приведенного рисунка видно, что при 𝑐̂ 0 = 𝑐 0 (1 − 𝑧1 ) + (1 − 𝑐 0 )𝑧 2 , наблюдаемых значениях точности меньше 0.5 при 1 где 𝑧 ∼ 𝐵𝑒𝑟(𝛼) – независимая случайная величина, наличии ошибок истинные значения могут быть еще которая определяет ошибки первого рода, 𝑧2 ∼ меньше. При наблюдаемой точности выше 0.5, 𝐵𝑒𝑟(𝛽) – независимая случайная величина, которая напротив, истинные значения оказываются выше определяет ошибки второго рода. наблюдаемых значений. 129 Действительно, если 𝑐 0 = 1 и 𝑧1 = 1, то 𝑐̂ 0 = 0, 𝐸�𝑅�1 � = 𝑅1 , 𝐷�𝑅�1 � = 𝑅1 (1 − 𝑅1 )𝑁 � 0, что соответствует ошибке первого рода. Если же 1 𝑛 где 𝑁 1 = ∑𝑛𝑠=1 � � (𝜋 1 ) 𝑠 (1 − 𝜋 1 )𝑛−𝑠 , �0 = 𝑁 𝑐 0 = 0 и 𝑧2 = 1, то 𝑐̂ 0 = 1, что соответствует 𝑠 𝑠 ошибке второго рода. 1 𝑛 ∑𝑛𝑠=1 � � (𝜋�)𝑠 (1 − 𝜋�)𝑛−𝑠 . █ 𝑠 𝑠 Утверждение 2. В рамках модели независимых Из приведенного утверждения следует, что ошибок справедливы следующие соотношения оценки показателей качества являются между истинными и наблюдаемыми значениями несмещенными, но при этом дисперсия является показателей качества классификации: сложной функцией от размера выборки и 𝑃1 −𝛽 𝑃1 = (1 − 𝛼 − 𝛽)𝑃0 + 𝛽, 𝑃0 = , вероятности успеха. 1−𝛼−𝛽 𝜋(1−𝛼−𝛽)𝑅 0 +𝜋1 𝛽 𝑅1 𝜋 � −𝛽𝜋1 Для оценки показателей и зависимостей между 𝑅1 = , 𝑅0 = ..█ истинными и наблюдаемыми показателями можно 𝜋(1−𝛼−𝛽)+𝛽 𝜋 � −𝛽 найти оценки истинных показателей с Таким образом, если известны оценки использованием следующих статистик. вероятностей ошибок первого и второго рода для экспертов и наблюдаемые экспертные оценки 𝐸�1 − 𝜖 𝐸� 0 = 𝑃� (c 0 ≠ c1 ) = , точности и полноты, то можно вычислить истинные 1 − 2𝜖 значения показателей точности и полноты. 𝑃�1 − 𝜖 Полученные соотношения между истинными и 𝑃�0 = 𝑃� (с0 = 1|𝑐1 = 1) = , 1 − 2𝜖 наблюдаемыми показателями качества позволяют 𝑅�1 𝜋� 0 − 𝜖𝜋� 1 оценить максимально возможные значения 𝑅� 0 = 𝑃� (𝑐1 = 1|𝑐 0 = 1) = , показателей качества, достижимые при 𝜋� 0 − 𝜖 определенном уровне ошибок. Утверждение 3. Для статистик 𝐸� 0 , 𝑃� 0 и 𝑅� 0 справедливы следующие свойства для Следствие 1. При фиксированных значениях математических ожиданий и дисперсий: α, 𝛽 ∈ (0,1) получаем, что P1 ∈ (β, 1 − α), R1 ∈ 1 𝐸 −𝜖 1 𝜖(1−𝜖) � 𝜋1 𝛽 ,1 − (1−𝜋1 )𝛽 �. 𝐸�𝐸� 0 � = , 𝐷�𝐸� 0 � = �(1−2𝜖)2 + 𝐸 0 (1 − 𝐸 0 )�, 1−2𝜖 𝑛 𝜋(1−𝛼−𝛽)+𝛽 𝜋(1−𝛼−𝛽)+𝛽 𝑃1 −𝜖 𝜖(1−𝜖) �0 𝐸�𝑃 � = , 𝐷�𝑃� 0 � = �(1−2𝜖)2 + 𝑃0 (1 − 3 Оценка размеров эталонных массивов 1−2𝜖 текстов 𝑃0 )� 𝑁 1 , 𝑅 𝜋 � −𝜖𝜋1 1 3.1 Оценка размеров эталонных массивов в 𝐸�𝑅� 0 � = , 𝐷�𝑅�0 � = �𝑅0 (1 − 𝑅0 ) + 𝜋 � −𝜖 рамках модели независимых ошибок 𝜖�𝑅 0 (𝜋 � −𝜖)�1−2𝜋1 �+𝜋1 �𝜋 � −𝜖𝜋1 �� � 𝑁 0, Для оценки размеров эталонных массивов � −𝜖)2 (𝜋 текстов рассмотрим влияние, оказываемое 1 𝑛 где 𝑁 1 = ∑𝑛𝑠=1 � � (𝜋 1 ) 𝑠 (1 − 𝜋 1 )𝑛−𝑠 , �0 = 𝑁 ошибками экспертов на дисперсию выборочных 𝑠 𝑠 1 𝑛 оценок ошибки 𝐸�1 , точности 𝑃�1 и полноты 𝑅�1 , ∑𝑛𝑠=1 � � (𝜋�)𝑠 (1 − 𝜋�)𝑛−𝑠 █ 𝑠 𝑠 которые вычисляются следующим образом. Заметим, что если бы имелась возможность 𝑛 1 напрямую подсчитать статистики для истинных 𝐸�1 = � 𝐼(𝑐̃𝑖0 ≠ 𝑐𝑖1 ), значений показателей качества, то их дисперсии 𝑛 𝑖=1 были бы равны следующим величинам: ∑𝑛𝑖=1,𝑐 1=1 𝐼 (𝑐̂𝑖0 = 1) 𝑛 ∑𝑖=1 𝑐̂𝑖0 𝑐𝑖1 1 𝑃�1 = 𝑖 = , 𝐷 �𝐸� 0 � = 𝐸 0 (1 − 𝐸 0 ), 𝑛 ∑𝑛𝑖=1 𝐼 (𝑐𝑖1 = 1) ∑𝑛𝑖=1 𝑐𝑖1 𝐷 �𝑃� 0 � = 𝑃0 (1 − 𝑃0 )𝑁 1 , ∑𝑛𝑖=1,𝑐̂0 =1 𝐼 (𝑐̂𝑖0 = 1) 𝑛 ∑𝑖=1 𝑐̂𝑖0 𝑐𝑖1 𝑅 =�1 𝑖 = , ∑𝑛𝑖=1 𝐼 (𝑐̂𝑖0 = 1) ∑𝑛𝑖=1 𝑐̂𝑖0 𝐷 �𝑅� 0 � = 𝑅0 (1 − 𝑅0 )𝑁 0 , 𝑛 0 где 𝐼(𝑥) ∈ {0,1} – индикаторная функция, 𝑛�0 = где 1 𝐸� 0 = ∑𝑛𝑖=1 𝐼(𝑐𝑖0 ≠ 𝑐𝑖1 ), ∑ 𝑃� 0 = 𝑖=1 1 𝐼 �𝑐𝑖 =1,𝑐𝑖 =1� , 𝑛 ∑𝑛𝑖=1 𝑐̂𝑖0 , 𝑛�1 = ∑𝑖=1 𝑐𝑖1 . Несложно показать, что 𝑛 ∑𝑛 1 𝑖=1 𝐼 �𝑐𝑖 =1� 𝑛 0 1 данные статистики имеют следующие 𝑅� 0 = 𝑖=1𝑛 𝑖 0 𝑖 . ∑ 𝐼 �𝑐 =1,𝑐 =1� ∑𝑖=1 𝐼 �𝑐𝑖 =1� математические ожидания и дисперсии: 1 Отсюда получаем, что справедливо следующее 𝐸�𝐸�1 � = 𝐸1 , 𝐷�𝐸�1 � = 𝐸1 (1 − 𝐸1 ), 𝑛 следствие из приведенного утверждения. 𝐸�𝑃�1 � = 𝑃1 , 𝐷�𝑃�1 � = 𝑃1 (1 − 𝑃1 )𝑁 1 , Следствие 1. Для обеспечения сохранения дисперсии оценок показателей на исходном уровне (соответствует ситуации, когда ошибки Труды 15-й Всероссийской научной конференции отсутствуют) требуется увеличение размера «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» — RCDL-2013, выборки в следующее число раз: Ярославль, Россия, 14-17 октября 2013 г. 𝜖(1−𝜖) 𝑙𝐸 = (1−2𝜖)2 + 1 – увеличение размера выборки для сохранения точности оценивания 𝐸 0 , 130 𝜖(1−𝜖) 𝑙𝑃 = (1−2𝜖)2 + 1 – увеличение размера выборки 𝐷�𝑅�0 � = 𝛽�𝑅 0 (𝜋 � −𝛽)�1−2𝜋1 �+𝜋1 �𝜋 � −𝛽𝜋1 �� для сохранения точности оценивания показателя 𝑃0 , �𝑅0 (1 − 𝑅0 ) + � 𝑁 0, � −𝛽)2 (𝜋 𝜖�𝑅 0 (𝜋 � −𝜖)�1−2𝜋1 �+𝜋1 �𝜋 � −𝜖𝜋1 �� 𝑙𝑅 = + 1 – увеличение 1 𝑛 � −𝜖)2 (𝜋 где 𝑁 1 = ∑𝑛𝑠=1 � � (𝜋 1 )𝑠 (1 − 𝜋 1 )𝑛−𝑠 , 𝑁�0 = 𝑠 𝑠 размера выборки для сохранения точности 1 𝑛 оценивания 𝑅0 . ∑𝑛𝑠=1 � � (𝜋�)𝑠 (1 − 𝜋�)𝑛−𝑠 █ 𝑠 𝑠 На следующем рисунке показаны Отсюда получаем, что справедливо следующее соответствующие зависимости для различных следствие из приведенного утверждения. показателей качества. Следствие 1. Для обеспечения сохранения дисперсии оценок показателей на исходном уровне 80 lE,lP (соответствует ситуации, когда ошибки 70 lR отсутствуют) требуется увеличение размера 60 выборки в следующее число раз: 𝜖(1−𝜖) 𝛼−𝛽 50 𝑙𝑃 = (1−𝛼−𝛽)2 + 𝑃0 +1 – увеличение (1−𝛼−𝛽) 40 размера выборки для сохранения точности 30 оценивания показателя 𝑃0 , 𝛽�𝑅 0 (𝜋 � −𝛽)�1−2𝜋1 �+𝜋1 �𝜋 � −𝛽𝜋1 �� 20 𝑙𝑅 = + 1 – увеличение � −𝛽)2 (𝜋 10 размера выборки для сохранения точности 0 оценивания 𝑅0 . 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 ε,R0=0.8,π1=0.2,π=0.2 4 Оценка вероятностей ошибок Рис. 4. Графики зависимости увеличения размера выборки для различных показателей экспертов качества от величины вероятности ошибки экспертной классификации 4.1 Общее описание подхода Из приведенного рисунка можно сделать вывод, Для возможности практического использования что даже при относительно небольших значениях выявленных зависимостей между истинными и ошибки классификации может потребоваться наблюдаемыми значениями показателей качества существенное увеличение количества данных для классификации необходимо знать значения обеспечения заданного уровня качества оценивания вероятностей ошибок экспертов. Однако их оценка показателей. Более того чем меньше относительный является достаточно сложной задачей по размер класса, тем большее влияние оказывают следующим причинам: случайные ошибки на показатели качества 1. Истинные матрицы эталонных классификаций классификации. В частности, если размер класса являются неизвестными, что не позволяет составляет 20% от размера массива данных, то уже вычислить ошибки экспертов напрямую; при уровне ошибки в 15% может потребоваться увеличение объема выборки в 10 раз. 2. В большинстве случаев доступной является только одна матрица экспертной классификации, 3.2 Оценка размеров эталонных массивов в что не позволяет оценивать качество работы одних рамках модели условных ошибок экспертов экспертов по отношению к другим экспертам. В ситуации, когда доступна только одна Для оценивания значений показателей качества эталонная экспертная классификация массива воспользуемся статистиками 𝑃�1 , 𝑅�1 , которые были документов, можно воспользоваться методами рассмотрены ранее. При этом можно использовать кластерного анализа для выявления «почти следующие статистики для оценки истинных дубликатов» документов. Такой подход, в значений показателей качества классификации: частности, подробно рассматривается и применяется 𝑃�1 −𝛽 𝑅� 1 𝜋 � 0 −𝛽𝜋 �1 в работах [10] и [4]. При отсутствии ошибок у 𝑃� 0 = , 𝑅� 0 = , 1−𝛼−𝛽 � 0 −𝛽 𝜋 документов, которые являются «почти Утверждение 4. Для статистик 𝑃�0 и 𝑅� 0 дубликатами», должны быть одинаковые векторы справедливы следующие свойства для классификации. При наличии же ошибок данные математических ожиданий и дисперсий: вектора будут отличаться. 1 𝐸�𝑃� 0 � = 𝑃 −𝛽 , 𝐷�𝑃�0 � = �𝑃0 (1 − 𝑃0 ) + Результаты выявления «почти дубликатов» или 1−𝛼−𝛽 повторного оценивания объектов (документов) 𝜖(1−𝜖) 0 𝛼−𝛽 (1−𝛼−𝛽)2 +𝑃 (1−𝛼−𝛽) � 𝑁1, экспертами из множества 𝑥1 , … , 𝑥𝑛 можно 1 1 представить в виде набора кластеров Ψ = 𝑅 𝜋 � −𝛽𝜋 𝐸�𝑅� 0 � = , (𝜓1 , … , 𝜓𝑠 ), где 𝜓𝑙 = �𝑥𝑙1 , … , 𝑥𝑙𝑚𝑙 �, 𝑚𝑙 – число 𝜋 � −𝛽 элементов в кластере, 𝑠 – число кластеров (число документов с повторной оценкой экспертами). 131 Пусть, как и ранее, зафиксирован некоторый Утверждение 5. При 𝑚𝑙 = 2, 𝑙 = 1, … , 𝑠 и 𝜖 < 1 2 класс 𝜔𝑗 , 𝑗 = 1, … , 𝑘. Тогда каждому кластеру 𝜓𝑙 , максимум функции правдоподобия 𝐿(𝑢1 , … 𝑢𝑠 |𝜖) 𝑙 = 1, … , 𝑠, можно поставить в соответствие 𝑐𝑙0 ∈ достигается при {0,1} – истинный признак относимости к классу 𝜔𝑗 и 1 1 2 вектор наблюдаемых экспертных оценок 𝑐𝑙 = 𝜖 ∗ = − � ∑𝑠𝑙=1 𝑢𝑙 − 1.█ 2 2 𝑠 �𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 �, где 𝑐𝑙𝑡 ∈ {0,1}. Таким образом, в ситуации, когда для каждого Рассмотрим теперь более подробно оценивание документа имеется только две оценки, возможно вероятностей ошибок экспертов в рамках модели явное нахождение оценки вероятности ошибки независимых ошибок и в рамках модели условных эксперта. В общем же случае, требуется применение ошибок. итерационных методов. 4.2 Оценка вероятностей ошибок в рамках Нахождение оценки вероятности ошибки с модели независимых ошибок использованием ЕМ-алгоритма. В данном случае для нахождения оценки вероятности ошибки В рамках модели независимых ошибок рассмотрим расширенную функцию правдоподобия справедливы следующие равенства: 𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 |𝜖, 𝜋), в которую входят 𝑐𝑙𝑡 = 𝑐𝑙0 + 𝑧𝑙𝑡 − 2𝑐𝑙0 𝑧𝑙𝑡 , наблюдаемые признаки 𝑐𝑙 = �𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 � и не где 𝑧𝑙𝑡 ∈ {0,1} – независимая случайная величина, наблюдаемые признаки 𝑐𝑙0 , 𝑙 = 1, … , 𝑠, где 𝜋 = 𝑃(𝑧𝑙𝑡 = 1) = 𝜖, 𝑡 = 1, . . , 𝑚𝑙 . 𝑃(𝑐𝑙0 = 1), 𝜖 – вероятность ошибки эксперта. Для нахождения оценки вероятности ошибки С учетом приведенных обозначений в рамках рассмотрим два подхода: модели независимых ошибок справедливо следующее равенство - прямая максимизация функции правдоподобия, - использование ЕМ-алгоритма. 𝑙𝑜𝑔𝐿�𝑐11 , … , 𝑐1𝑚𝑙 , 𝑐10 , … , 𝑐𝑠1 , … , 𝑐𝑠𝑚𝑠 , 𝑐𝑠0 |𝜖� = Нахождение оценки вероятности ошибки ∑𝑠𝑙=1�𝑐𝑙0 log 𝜋 + (1 − 𝑐𝑙0 ) log(1 − 𝜋) + 𝑚𝑙 путем максимизации специальной функции ∑𝑡=1 �𝑐𝑙0 (𝑐𝑙𝑡 log(1 − 𝜖) + (1 − 𝑐𝑙𝑡 ) log 𝜖) + правдоподобия. В данном случае для решения (1 − 𝑐𝑙0 )(𝑐𝑙𝑡 log 𝜖 + (1 − 𝑐𝑙𝑡 ) log(1 − 𝜖))� �. поставленной задачи рассмотрим для каждого В соответствии с общей схемой построения EM- кластера величину 𝑢𝑙 ∈ {0,1}, 𝑙 = 1, … , 𝑠, которая алгоритма требуется решение следующих двух принимает значение равное 1, если 𝑐𝑙1 = 𝑐𝑙2 = ⋯ = задач: 𝑐𝑙𝑚𝑙 , и 0, в противном случае. Тогда для 𝑙 = 1, … , 𝑠 - найти условное математическое ожидание справедливо следующее равенство расширенной функции правдоподобия при 𝑃(𝑢𝑙 = 1) = 𝑃�𝑐𝑙1 = ⋯ = 𝑐𝑙𝑚𝑙 � = (1 − 𝜖)𝑚𝑙 + 𝜖 𝑚𝑙 . фиксированных неизвестных параметрах (E-шаг); Из приведенного утверждения следует, что - найти максимум условного математического 𝑃(𝑢𝑙 = 1) является функцией от вероятности ожидания расширенной функции правдоподобия по ошибки 𝜖, но при этом для вычисления значений 𝑢𝑙 неизвестным параметрам (M-шаг). не требуется знание истинных значений 𝑐𝑙0 , 𝑙 = В данном случае в рамках E-шага требуется 1, … , 𝑠. Это свойство позволяет для нахождения 𝜖 найти следующее условное математическое воспользоваться методом максимального ожидание: правдоподобия. В данном случае оценка 𝜖 является 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 , 𝜖, 𝜋)|𝑐1 , . . , 𝑐𝑠 , , 𝜖, 𝜋). решением следующей оптимизационной задачи: Его вычисление сводится к нахождению 𝜖 ∗ = arg max 𝐿(𝑢1 , … 𝑢𝑠 |𝜖), следующих апостериорных вероятностей ϵ где 𝐿(𝑢1 , … 𝑢𝑠 |𝜖) = ∑𝑠𝑙=1 log(𝑃(𝑢𝑙 = 1)𝑢𝑙 (1 − 𝑔𝑙 = 𝑃�𝑐𝑙0 = 1|𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 , 𝜖, 𝜋�, 𝑙 = 1, … , 𝑠, 𝑃(𝑢𝑙 = 1) )1−𝑢𝑙 ) - логарифм функции которые можно вычислить следующим образом: правдоподобия. −1 𝑚𝑙 −2𝑛𝑙 Можно показать, что максимум 𝐿(𝑢1 , … 𝑢𝑠 |𝜖) 1 1 𝑔𝑙 = �1 + � − 1� � − 1� � , находится как решение следующего уравнения: 𝜋 𝜖 𝑢𝑙 𝑚 ∑𝑠𝑙=1 𝑚𝑙 (𝜖 𝑚𝑙 −1 − (1 − 𝜖)𝑚𝑙 −1 ) � − где 𝑛𝑙 = ∑𝑡=1𝑙 𝑐𝑙𝑡 - число единиц в векторе (1−𝜖)𝑚𝑙 +𝜖 𝑚𝑙 (1−𝑢𝑙 ) результатов экспертной классификации. � = 0. 1−(1−𝜖)𝑚𝑙 −𝜖 𝑚𝑙 Отсюда получаем выражение для нахождения Прямое решение данного уравнения является математического ожидания логарифма функции достаточно сложной задачей. По этой причине для правдоподобия: его решения можно воспользоваться численными 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 , 𝜖, 𝜋)|𝑐1 , . . , 𝑐𝑠 , 𝜖, 𝜋) = методами. В тоже время в частном случае, когда 𝑠 ∑𝑙=1�𝑔𝑙 log 𝜋 + (1 − 𝑔𝑙 ) log(1 − 𝜋) + 𝑚𝑙 = 2, 𝑙 = 1, … , 𝑠, можно найти точное решение 𝑚𝑙 ∑𝑡=1�𝑔𝑙 (𝑐𝑙𝑡 log(1 − 𝜖) + (1 − 𝑐𝑙𝑡 ) log 𝜖) + данного уравнения. (1 − 𝑔𝑙 )(𝑐𝑙𝑡 log 𝜖 + (1 − 𝑐𝑙𝑡 ) log(1 − 𝜖))� �. 132 Найдем теперь в рамках M-шага решение Для нахождения оценок значений параметров 𝛼 следующей задачи: и 𝛽 воспользуемся методом максимального (ϵ∗ , π∗ ) = правдоподобия и построим соответствующий ЕМ- 0 0 arg max 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐1 , … , 𝑐𝑠 , 𝑐𝑠 , 𝜖, 𝜋)|𝑐1 , . . , 𝑐𝑠 , 𝜖, 𝜋). алгоритм. ϵ,π Рассмотрим расширенную функцию Можно показать, что максимум будет правдоподобия 𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 |𝛼, 𝛽, 𝜋), в которую достигаться при входят наблюдаемые признаки 𝑐𝑙 = �𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 � и 𝑠 ∗ 1 не наблюдаемые признаки 𝑐𝑙0 , 𝑙 = 1, … , 𝑠, где 𝜋 = � 𝑔𝑙 , 𝜋 = 𝑃(𝑐𝑙0 = 1). 𝑠 𝑙=1 𝑠 𝑚𝑙 С учетом приведенных обозначений в рамках ∑𝑙=1 ∑𝑡=1(𝑔𝑙 + 𝑐𝑙𝑡 − 2𝑔𝑙 𝑐𝑙𝑡 ) модели независимых ошибок справедливо 𝜖∗ = ∑𝑠𝑙=1 𝑚𝑙 следующее равенство ∑𝑠𝑙=1(𝑚𝑙 𝑔𝑙 + 𝑛𝑙 − 2𝑔𝑙 𝑛𝑙 ) = 𝑙𝑜𝑔𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 |𝛼, 𝛽, 𝜋) = ∑𝑠𝑙=1�𝑐𝑙0 log 𝜋 + ∑𝑠𝑙=1 𝑚𝑙 (1 − 𝑐𝑙0 ) log(1 − 𝜋) + ∑𝑡=1 𝑚𝑙 �𝑐𝑙0 (𝑐𝑙𝑡 log(1 − 𝜖) + Для задания начальных значений параметров 𝜖 и 0 (1 − 𝑐𝑙𝑡 ) log 𝜖) + (1 − 𝑐𝑙 )(𝑐𝑙𝑡 log 𝜖 + (1 − 𝜋 можно положить 𝜖 равной небольшому числу 𝑐𝑙𝑡 ) log(1 − 𝜖))� �. 1 больше 0, например, 𝜖 = 0.01, а 𝜋 = . В качестве В данном случае в рамках E-шага требуется 2 критерия завершения работы алгоритма можно найти следующее условное математическое использовать два условия: число итераций равно ожидание: 𝑡𝑚𝑎𝑥 – положительное целое число, разница между 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 |𝛼, 𝛽, 𝜋)|𝑐1 , . . , 𝑐𝑠 , 𝛼, 𝛽, 𝜋). новым и старым значениями 𝜖 меньше Δ𝜖 ∈ (0,1). Несложно заметить, что его вычисление Теперь можно описать ЕМ-алгоритм оценивания сводится к нахождению следующих апостериорных вероятности ошибки экспертов полностью. В вероятностей качестве входных параметров у него выступают следующие: 𝑡𝑚𝑎𝑥 , Δ𝜖 , 𝑐𝑙 = �𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 � , 𝑙 = 1, … , 𝑠, - 𝑔𝑙 = 𝑃�𝑐𝑙0 = 1|𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 , 𝛼, 𝛽, 𝜋�, 𝑙 = 1, … , 𝑠, вектора экспертных классификаций. которые можно записать в следующем виде: −1 1 𝛽 𝑛𝑙 1 − 𝛽 𝑚𝑙 −𝑛𝑙 ЕМ-алгоритм оценивания вероятности 𝑔𝑙 = �1 + � − 1� � � � � � , 𝜋 1−𝛼 𝛼 ошибки экспертов 𝑚 где 𝑛𝑙 = ∑𝑡=1 𝑙 𝑐𝑙𝑡 . 1. Инициализация. Положить 𝑡 = 0, 𝜖 (𝑡) = 0.01, 1 𝑚𝑙 Отсюда получаем выражение для нахождения 𝜋 (𝑡) = , 𝑛𝑙 = ∑𝑗=1 𝑐𝑙𝑗 , 𝑙 = 1, … , 𝑠. математического ожидания логарифма функции 2 2. Е-Шаг. Вычислить для 𝑙 = 1, … , 𝑠 правдоподобия: (𝑡) апостериорные вероятности 𝑔𝑙 с использованием 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐10 , … , 𝑐𝑠 , 𝑐𝑠0 |𝛼, 𝛽, 𝜋)|𝑐1 , . . , 𝑐𝑠 , 𝛼, 𝛽, 𝜋) = 𝑠 следующего выражения: ∑𝑙=1�𝑔𝑙 log 𝜋 + (1 − 𝑔𝑙 ) log(1 − 𝜋) + 𝑚𝑙 (𝑡) 1 1 𝑚𝑙 −2𝑛𝑙 −1 ∑𝑡=1�𝑔𝑙 (𝑐𝑙𝑡 log(1 − 𝛼) + (1 − 𝑐𝑙𝑡 ) log 𝛼) + 𝑔𝑙 = �1 + � (𝑡) − 1� � (𝑡) − 1� � . (1 − 𝑔𝑙 )(𝑐𝑙𝑡 log 𝛽 + (1 − 𝑐𝑙𝑡 ) log(1 − 𝛽))� �. 𝜋 𝜖 (𝑡+1) 3. М-Шаг. Вычислить оценки параметров 𝜖 и Найдем теперь в рамках M-шага решение 𝜋 (𝑡+1) с использованием следующих выражений: следующей задачи: (𝑡) ∑𝑠𝑙=1�𝑔𝑙 (𝑚𝑙 −2𝑛𝑙 )+𝑛𝑙 � (α∗ , β∗ , π∗ ) = 𝜖 (𝑡+1) = ∑𝑠𝑙=1 𝑚𝑙 , 0 0 arg max 𝐸(𝑙𝑜𝑔𝐿(𝑐1 , 𝑐1 , … , 𝑐𝑠 , 𝑐𝑠 |𝛼, 𝛽, 𝜋)|с, 𝛼, 𝛽, 𝜋). α,β ,π 1 (𝑡) 𝜋 (𝑡+1) = ∑𝑠𝑙=1 𝑔𝑙 . Можно показать, что максимум будет 𝑠 4. Критерий завершения работы. Положить достигаться при следующих значениях параметров: 𝑠 𝑡 = 𝑡 + 1. Если 𝑡 > 𝑡𝑚𝑎𝑥 или �𝜖 (𝑡+1) − 𝜖 (𝑡) � < Δ𝜖 , то 1 ∗ завершить работу алгоритма, в противном случае, 𝜋 = � 𝑔𝑙 , 𝑠 перейти к шагу 2. █ 𝑙=1 ∑𝑠𝑙=1 𝑔𝑙 𝑛𝑙 4.3 Оценка вероятностей ошибок в рамках 𝛼∗ = 1 − 𝑠 , ∑𝑙=1 𝑔𝑙 𝑚𝑙 модели условных ошибок ∑𝑠𝑙=1(1 − 𝑔𝑙 )𝑛𝑙 𝛽∗ = 𝑠 . В рамках модели независимых ошибок ∑𝑙=1(1 − 𝑔𝑙 )𝑚𝑙 справедливы следующие равенства: Для задания начальных значений параметров 𝑐𝑙𝑡 = 𝑐𝑙0 (1 − 𝑧𝑙𝑡 1) + (1 − 𝑐𝑙0 )𝑧𝑙𝑡2 , 1 𝛼, 𝛽 и 𝜋 можно положить 𝛼 = 𝛽 = 0.01, а 𝜋 = . В 1 2 где 𝑧𝑙𝑡 , 𝑧𝑙𝑡2 ∈ {0,1} – независимые случайные качестве критерия завершения работы алгоритма 1 величины, 𝑃(𝑧𝑙𝑡 = 1) = 𝛼, 𝑃(𝑧𝑙𝑡2 = 1) = 𝛽, 𝑡 = можно использовать два условия: число итераций 1, . . , 𝑚𝑙 . равно 𝑡𝑚𝑎𝑥 – положительное целое число, разница 133 между новым и старым значениями 𝛼, 𝛽 меньше Таблица 1. Вероятности ошибок экспертов для Δ𝜖 ∈ (0,1). массива с оценками книг Теперь можно описать ЕМ-алгоритм оценивания 2 3 5 вероятности ошибки экспертов полностью. В класса класса классов качестве входных параметров у него выступают Ошибки 0.017 0.011 0.013 следующие: 𝑡𝑚𝑎𝑥 , Δ𝜖 , 𝑐𝑙 = �𝑐𝑙1 , … , 𝑐𝑙𝑚𝑙 � , 𝑙 = 1, … , 𝑠, - вектора экспертных классификаций. 0.017 0.094 0.026 0.081 0.070 ЕМ-алгоритм оценивания условных 0.150 вероятностей ошибок 0.094 1. Инициализация. Положить 𝑡 = 0, 𝛼 (𝑡) = 𝛽 (𝑡) = Вероятности 0.083 0.0519 0.000 1 𝑚𝑙 0.01, 𝜋 (𝑡) = , 𝑛𝑙 = ∑𝑗=1 𝑐𝑙𝑗 , 𝑙 = 1, … , 𝑠. классов 0.918 0.294 0.030 2 2. Е-Шаг. Вычислить для 𝑙 = 1, … , 𝑠 0.626 0.147 (𝑡) 0.290 апостериорные вероятности 𝑔𝑙 с использованием следующего выражения: 0.357 𝑛𝑙 −1 (𝑡) 1 𝛽 1−𝛽 𝑚𝑙 −𝑛𝑙 𝑔𝑙 = �1 + � − 1� � � � � � . 𝜋 1−𝛼 𝛼 Приведенный пример показывает, что на 3. М-Шаг. Вычислить оценки параметров практике величины ошибок могут быть достаточно 𝛼 (𝑡+1) , 𝛽 (𝑡+1) и 𝜋 (𝑡+1) с использованием следующих большими и существенно отличаться для различных выражений: классов. Знание вероятностей ошибок позволяет получить оценки истинных значений показателей ∑𝑠𝑙=1 𝑔𝑙(𝑡) 𝑛𝑙 𝛼 (𝑡+1) = 1 − , качества классификации, оценить объем исходных ∑𝑠𝑙=1 𝑔𝑙(𝑡) 𝑚𝑙 данных, необходимых для получения требуемой точности оценивания показателей качества. ∑𝑠𝑙=1�1 − 𝑔𝑙(𝑡) �𝑛𝑙 𝛽 (𝑡+1) = , Пример оценивания условных ошибок ∑𝑠𝑙=1�1 − 𝑔𝑙(𝑡) �𝑚𝑙 экспертов в рамках дорожки по классификации 𝑠 1 тональности оценок пользователей РОМИП- (𝑡+1) (𝑡) 𝜋 = � 𝑔𝑙 . 2012. Для иллюстрации оценивания вероятностей 𝑠 𝑙=1 ошибок рассмотрим опять массив с оценками книг, 4. Критерий завершения работы. Положить который был сформирован в рамках РОМИП-2012. 𝑡 = 𝑡 + 1. Если 𝑡 > 𝑡𝑚𝑎𝑥 или max��𝛼 (𝑡+1) − В следующей таблице приведены оценки 𝛼 (𝑡) |, �𝛽 (𝑡+1) − 𝛽 (𝑡) �� < Δ𝜖 , то завершить работу вероятности ошибок первого и второго рода экспертов для различного числа классов, а также алгоритма, в противном случае, перейти к шагу 2. █ оценки вероятности ошибок, которые были получены в рамках модели независимых ошибок. 5 Примеры оценивания ошибок Таблица 2. Вероятности ошибок экспертов для экспертов массива с оценками книг 5.1 Примеры оценивания вероятностей ошибок 𝝅 𝝐 𝜶 𝜷 при наличии нескольких экспертных 2-класса 0.103 0.0166 0.120 0.006 классификаций 0.897 0.0166 0.0061 0.121 Пример оценивания вероятности ошибки 3-класса 0.063 0.0110 0.0998 0.006 экспертов в рамках модели независимых 0.302 0.0944 0.1055 0.090 ошибок. Для иллюстрации оценивания 0.572 0.0811 0.0437 0.137 вероятностей ошибок на практике рассмотрим задачу построения классификаторов для оценивания 5- 0.006 0.013 0.983 0.013 мнений пользователей, которая предлагалась в классов 0.042 0.026 0.174 0.021 рамках семинара РОМИП-2012. В рамках РОМИП 0.155 0.070 0.095 0.066 для оценки качества работы систем вручную были 0.261 0.150 0.113 0.164 сформированы 3 эталонных массива текстов (массив с оценками книг, массив с оценками фильмов, 0.323 0.094 0.054 0.115 массив с оценками камер), в которых каждый текст был оценен двумя экспертами по 2-х бальной шкале, Приведенные данные показывают, что ошибки 3-х бальной шкале, 5 бальной шкале. В следующей могут принимать достаточно большие значения и таблице приведены оценки вероятностей ошибок при этом заметно отличаться для различных экспертов и оценки вероятностей классов, классов. Это приводит к тому, что оценки качества, полученные с помощью ЕМ-алгоритма для массива получаемые на таком массиве, могут существенно с оценками книг. отличаться от истинных значений. 134 С учетом найденных ошибок можно оценить 180 максимально достижимые значения показателей точности и полноты с использованием следующих 160 соотношений: 140 P1 ∈ (β, 1 − α), 120 Число рубрик 𝜋1 𝛽 (1−𝜋1 )𝛽 100 R1 ∈ � ,1 − �. 𝜋(1−𝛼−𝛽)+𝛽 𝜋(1−𝛼−𝛽)+𝛽 80 Максимальные и минимальные значения 60 показателей для массива с оценками книг 40 приведены в следующей таблице. 20 Таблица 3. Оценки максимальных и 0 минимальных значений для точности и полноты при 0 0.1 0.2 0.3 0.4 0.5 α 0.6 0.7 0.8 0.9 1 классификации на 2 класса Рис. 5. Гистограмма распределения ошибок Класс 1 Класс 2 первого рода по рубрикам (отрицательные (положительные отзывы) отзывы) 300 Точность 1%-88% 12%-99% 250 Полнота 1%-91% 11%-98% 200 Число рубрик Полученные результаты показывают, что при 150 классификации отрицательных отзывов ошибки могут быть значительно выше, чем при 100 классификации положительных отзывов. 50 5.2 Пример оценивания вероятностей ошибок при наличии одной экспертной классификации 0 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 β Рассмотрим теперь пример оценивания вероятностей ошибок экспертов в ситуации, когда Рис. 6. Гистограмма распределения ошибок имеется только одна матрица эталонной второго рода по рубрикам классификации. В качестве массива текстов возьмем Анализ полученных результатов показывает, что материалы дорожки классификации нормативно- ошибки первого рода принимают достаточно правовых документов, которая проводилась в большие значения и значительно больше ошибок рамках РОМИП-2009. Обучающее множество второго рода, что соответствует известному содержит 29943 документа, которые распределены эмпирическому наблюдению, что эксперты при по 721 классу. ручной классификации чаше пропускают рубрики, Для получения оценивания вероятности ошибок чем добавляют неправильные. экспертов проведем выявление «дубликатов» На следующем рисунке также приведены документов. При этом будем считать, что максимальные значения показателей точности и документы являются дубликатами, если мера полноты для рубрик, которые вычислены с косинусной близости между векторами документов использованием полученных оценок для ошибок будет больше 0.9. Непосредственный просмотр первого и второго рода. документов, мера близости между которыми больше данного порога, показал, что они действительно 1 являются почти дубликатами. 0.9 0.8 В результате оценивания ошибок экспертов первого и второго рода представлены в форме 0.7 гистограмм распределения значения ошибок по 0.6 рубрикам на следующих двух рисунках (такая 0.5 P форма выбрана из-за большого числа рубрик). 0.4 0.3 0.2 0.1 0 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 R Рис. 7. Значения максимальных значений показателей точности и полноты для рубрик, полученные в рамках модели условных ошибок 135 Средние значения максимальных значений [4] Gulin A., Kuralenok I., Pavlov D. Winning The показателей точности и полноты по всем рубрикам Transfer Learnin Track of Yahoo!'s Learning To равны следующим значениям: Rank Challenge with YetiRank // Journal of 𝑚𝑎𝑥𝑃 = 0.53, Machine Learning Research, Vol. 14, 2011. - p. 63-76. 𝑚𝑎𝑥𝑅 = 0.63. [5] Gwet K. L. Handbook of Inter-Rater Reliability: Сравнение полученных максимальных значений The Definitive Guide to Measuring the Extent of показателей качества с теми, которые были Agreement Among Multiple Raters: Advanced достигнуты участниками дорожки (максимальное Analytics, LLC, 2010. – 294 p. значение точности – 35%, максимальное значение [6] Lam C. P., Stork D. G. Evaluating classifiers by полноты было равно 45%), объясняет получение means of test data with noisy labels // Proceedings участниками низких значений показателей качества. of the International Joint Conference on Artificial 6 Заключение Intelligence, AAAI Press, 2003. – p. 513-518. [7] Lewis D. D., Sebastiani F. Report on the В работе рассмотрены две модели ошибок Workshop on Operational Text Classification экспертов, а также предложен подход к оцениванию systems (OTC-01) // SIGIR Forum. - 2001. - 2: их вероятностей, основанный на использовании ЕМ- Vol. 35. - p. 8-11. алгоритма. [8] Metricov P., Pavlu V., Aslam J. A. Impact of Разработанные модели и методы позволяют Assessor Disagreement on Ranking Performance // решать следующие прикладные задачи: SIGIR'12. - Portland, Oregon, USA, 2012. - p. - вычислять значения ошибок экспертов как при 1091-1092. наличии нескольких, так и при наличии только [9] Reichenheim M. E. Confidence intervals for the одной эталонной экспертной классификации; kappa statistic // The Stata Journal. - 2004: Vol. 4. - восстанавливать истинные значения - p. 421-428. показателей качества классификации по [10] Scholer F., Turpin A., Sanderson M. Quantifying наблюдаемым экспертным оценкам значений Test Collection Quality Based on the Consistency соответствующих показателей; of Relevance Judgements // SIGIR'11, Beijing, - вычислять максимально возможные значения China, 2011. - p. 1063-1072. показателей качества классификации при данном [11] Sebastiani F. Machine learning in automated text уровне ошибок экспертов; categorization // ACM Comput. Surv. - 2002. - 1: Vol. 34. - p. 1-47. - оценивать величину дисперсии показателей качества и определять размер тестовых выборок, [12] Webber W., Oard D. W., Scholer F. Assessor необходимый для обеспечения требуемой точности Error in Stratified Evaluation // CIKM'10, их оценивания, в зависимости от уровня ошибок Toronto, Ontario, 2010. - p. 539-548. экспертов; [13] Агеев М. С., Добров Б. В., Лукашевич Н. В. - определять рубрики, которые требуют более Поддержка системы автоматического рубрицирования для сложных задач внимательного оценивания. классификации текстов // Труды 6-ой Предложенный подход к оценке вероятностей Всероссийской научной конференции – ошибок экспертов является достаточно общим и его RCDL2004, 2004. – 10 c. можно обобщить и для случая оценивания матриц [14] Заславский А. А., Пригарина Т. А. Оценка условных вероятностей, рассматриваемых в работах согласованности субъективных классификаций [4] и [8]. при заданных классах // Социология. - 1994: Практическое использование предложенных Vol. 3-4. - c. 84-109. моделей и методов показано на примерах [15] Лукашевич Н. В. Тезаурусы в задачах оценивания ошибок экспертов и максимальных информационного поиска. - М.: Издательство значений показателей качества на материалах Московского Университета, 2011. - 512 с. дорожек РОМИП-2009 и РОМИП-2012. Probabilistic models and methods for Литература classifier etalon datasets quality estimation [1] Cohen J. A coefficient of agreement for nominal scales // Educ. Psychol. Measurement. - 1960: Vitaly G. Vasilyev Vol. 20. - p. 37-46. In this paper two probabilistic models of expert [2] Eye A., Mun E. Y. Analyzing Rater Agreement: errors and special iterative methods of their estimation Manifest Variable Methods: Taylor and Francis, are proposed. By using this framework the expert errors, 2006. – 190 p. size of etalon datasets, maximum values for quality [3] Fleiss J. L. Measuring nominal scale agreement metrics can be calculated. Examples of real calculations among many raters // Psychological Bulletin. - are shown on materials of the ROMIP tracks. 1971: Vol. 76. - p. 378-382. 136