Разработка методов оптимизации метрик качества в задачах многозначной классификации тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Бергер Анна Игоревна

• Бергер Анна Игоревна
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Бергер Анна Игоревна

Введение

Глава 1. Математическое исследование модели многозначной

классификации

1.1 Постановка задачи

1.2 Пороговость оптимального классификатора для F-macroPU

1.3 Состоятельность метрики F-macroPU в классе пороговых метрик

с ограничением на точность

1.4 Сведение к двумерному отображению на квадрате [0,1]2

1.4.1 Покоординатный максимум

1.4.2 Сведение к двумерной задаче

Заключение к главе

Глава 2. Численные методы нахождения вектора оптимальных

порогов для модели многозначной классификации

2.1 Методы линеаризации целевой метрики

2.1.1 Метод линеаризации

2.1.2 Расширенный метод линеаризации

2.1.3 Пример использования расширенного метода линеаризации

2.2 Методы исследования области определения отображения V . . . 40 Заключение к главе

Глава 3. Приложения разработанных численных методов к

различным наборам данных

3.1 Комплекс программ «F-MACRO THRESHOLD OPTIMIZATION»

3.2 Применение методов линеаризации

3.3 Применение метода исследования области определения

3.4 Сравнительный анализ свойств методов двух групп

3.4.1 Погрешность алгоритмов в зависимости от числа классов

3.4.2 Погрешность алгоритмов в зависимости от в

3.4.3 Погрешность быстрого алгоритма анализа области определения в зависимости от числа полярных углов

3.5 Многозначность V

Стр.

3.6 Выбор метрики качества

Заключение к главе

Глава 4. Восстановление многомерной условной плотности

вероятности

4.1 Постановка задачи и выбор метрики качества

4.2 Обзор методов восстановления условной плотности вероятности

4.3 Наборы данных

4.4 Применение методов восстановления условной плотности вероятности к различным наборам данных

Заключение к главе

Заключение

Список литературы

Список рисунков

Список таблиц

Приложение А. Комплекс программ «F-macro threshold

optimization»

А.1 Метод линеаризации

А.2 Метод исследования области определения

Приложение Б. Свидетельство о государственной регистрации

программ для ЭВМ

Б.1 Реферат

Введение диссертации (часть автореферата) на тему «Разработка методов оптимизации метрик качества в задачах многозначной классификации»

Введение

Математические модели многозначной классификации широко распространены во многих областях, где было накоплено значительное количество данных — например, определение категорий для статей в Википедии [1—3] или проставление ключевых слов для видео [4—6] и научных статей [7; 8]. На практике эти задачи часто решаются простыми численными методами без какого-либо анализа асимптотического поведения построенной модели и доказательств состоятельности полученного решения [9—11]. Классическим путем решения таких задач является задание некоторой метрики качества решения и поиск оптимальных параметров модели, максимизирующих данную метрику.

В статистическом машинном обучении существует два подхода к оптимизации сложносоставных метрик, описанные сначала y D. Lewis [12] и N. Ye [13] и позже в других терминах в работе K. Dembczynski[14]: один он называет предельной метрикой («population utility», PU), а второй - ожидаемой выборочной оценкой («expected test utility», ETU). При использовании PU-подхода к оптимизации меры ищется решение, оптимальное для заданного вероятностного распределения. Найденное решение затем применяется к каждому объекту. В ETU-подходе решение строится путем оптимизации условного математического ожидания по заданной выборке. PU-подход более устойчив к неверному выбору модели, в то время как ETU-подход обычно лучше справляется с предсказаниями для редких классов и показывает более стабильные результаты в случае, когда распределение на тестовом множестве отличается от распределения на тренировочном[13].*

Получением строгих математических результатов для моделей классификации занимались и отечественные ученые. Так, теория Вапника-Червонен-киса[15] предоставляет количественные оценки, дающие достаточные условия обучаемости, а также формулирует необходимые и достаточные условия равномерной сходимости частоты к вероятности, хотя и часто критикуется за завышенность этих оценок. Основателем научной школы в области распознавания и прогнозирования стал Ю. Журавлев, предложивший алгебраический

Некоторые авторы используют другие названия этих подходов: эмпирическая максимизация полезности (expected utility maximization, EUM) и анализ теории принятия решений (decision theoretic approach, DTA) (вместо PU и ETU соответственно).

подход к проблеме синтеза корректных алгоритмов[16]. Алгоритмические модели классификации с точки зрения их устойчивости, точности и надежности, а также колмогоровская сложность в машинном обучении, рассматриваются, например, в книге [17], докторских [18; 19] и кандидатских[20] диссертациях.

Одной из популярных метрик качества, используемых для оценки многозначного классификатора, является ^-мера[21]. Она обычно используется в задачах, в которых важна не только точность, т.е. правильное определение объектов, принадлежащих определенному классу, но и полнота - нахождение достаточно большого процента объектов этого класса. Примерами таких задач могут служить задача информационного поиска[22] или задача определения именованных сущностей[23]. Для обеспечения равного вклада в метрику классов разного размера используется макро-усреднение, которое может производиться двумя способами, отличающимися порядком применения операций усреднения и вычисления гармонического среднего. Усреднение значений ^-меры, вычисленных в каждом классе (шасго-Р), является более простым с точки зрения оптимизации и используется, например, в работах[24—27], в то время как у [28—30] находит применение вычисление ^-меры от средних точности и полноты (Р-шасго). Точность и полнота входят в определение шасго-Р таким образом, что обе они должны имеет высокие значения, для того чтобы метрика шасго-Р достигла оптимума, в то время как оптимизация Р-шасго позволяет оптимизировать в некоторых классах только точность, жертвуя полнотой, и наоборот.

Одним из самых популярных подходов к оптимизации метрик качества является двухступенчатый модульный подход. На первом шаге бинарный классификатор упорядочивает объекты согласно некоторым оценкам вероятности их принадлежности этому классу. На втором шаге в каждом классе выбирается тот порог, который оптимизирует выбранную метрику качества. В условиях РИ-подхода, ^-мера, как любая другая метрика качества, являющаяся непрерывной и монотонно возрастающей функции от доли ложно положительных классификаций (ТРИ,), может быть оптимизирована с помощью порогового классификатора[12; 31].

На практике точные условные вероятности принадлежности классам неизвестны, и на первом шаге либо применяется некоторая процедура оценки вероятностей[32] принадлежности объектов классам, либо объекты упорядочиваются путем оптимизации некоторой ранжирующей функции потерь, как в методах экстремальной многозначной классификации (например, пЭСС в

[33]). В этом случае, хотя мера оптимизирована и не с помощью порогового классификатора, состоятельность все равно присутствует. Как показано в разделе 4.2 статьи [14], если ограничиться только пороговыми классификаторами, то качество работы классификатора, оптимизирующего меру, использующую эмпирические, а не точные оценки вероятностей, отличается не более, чем на 0(1Д/ш), где т - число объектов, от качества работы классификатора, оптимального в PU смысле. Это утверждение неверно для ETU-подхода, потому что он требует точной оценки вероятностей.

Выбор оптимального порога для моделей многозначной классификации исследовался в работах [25; 32; 34]; подробный обзор приведен в работе [35]. Y.Yang [34] исследовал качество работы и риск переобучения для различных методов выбора порогов: в работе рассматривался выбор порогов на основе ранга (RCut), доли (PCut) и локальная оптимизация на основе оценок (SCut). Впоследствии, этим методы использовались в работах [36—38]. Методы RCut и PCat возвращают приближенные значения порогов. Как отмечено в [25], метод SCut, являющийся результатом циклического процесса оптимизации, описанного в [38], возвращает оптимальное значение в особом покоординатном смысле: функция порогов достигает оптимума в точке как функция от каждого порога по отдельности. Свойства меры, исследуемой в [25], помогают доказать, что этот максимум является и обычным максимумом, что неверно для F-macro меры, рассматриваемой в этой работе, и демонстрируется в Примере 1.

В диссертации рассмотрена задача оптимизации F-macro применительно к модели многозначной классификации. Введены различные критерии оптимизации сложносоставных метрик качества — PU, EM и ETU а также исследованы отношения, возникающие при различных способах оптимизации сложносоставных метрик. Доказана пороговость оптимального байесовского классификатора для F-macro, что позволяет разбить решение задачи многозначной классификации на два этапа: построение ранжирующей функции и поиск оптимальных порогов для каждого класса. Для второго этапа разработан метод сведения к задаче поиска неподвижной точки некоторого специально введенного отображения на квадрате [0,1]2. Исследована состоятельность решения, полученного с использованием оценок вероятностей, в смысле его близости к решению, оптимальному в PU-смысле, для пороговых ранжирующих функций. Предложены несколько численных методов решения задачи поиска оптимальных порогов, оценена их сложность и возникающая погрешность их работы, а также прове-

ден сравнительный анализ их свойств. Представлены результаты нескольких вычислительных экспериментов с предложенными алгоритмами применительно к наборам данных "^ЫЬЗНТС, Соге15К и ЕБРСаше различной природы с большим числом классов, а также к смежной задаче восстановления многомерной условной плотности распределения.

Актуальность темы определяется тем, что для задач экстремальной многозначной классификации[33; 39—41] существует потребность в создании алгоритмов оптимизации, позволяющих за разумное время находить значения порогов, оптимизирующих выбранную метрику качества. Метрика Р-шасго не была полноценно исследована с точки зрения состоятельности полученного решения при различных подходах к ее оптимизации, в отличие от родственной ей шасго-Р, являющейся более простой для оптимизации, так как возможна ее декомпозиция и независимая максимизация в каждом классе. Напротив, оптимизация Р-шасго не позволяет избавиться от нелинейной зависимости от элементов матрицы ошибок, что составляет дополнительную трудность. Кроме того, в задачах экстремальной многозначной классификации определение оптимальных порогов происходит в пространстве, размерность которого может превышать сотни тысяч, что осложняет применение классических методов оптимизации, которые, помимо прочего, не дают теоретических оценок оптимальности полученного решения.

Целью данной работы является построение аналитических методов исследования модели многозначной классификации для большого числа классов и разработка численных алгоритмов оптимального решения задач многозначной классификации в случае большого количества классов и Р-шасго меры в качестве метрики оценки качества.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследовать модель многозначной классификации в случае большого количества классов и Р-шасго меры в качестве метрики оценки качества.

2. Провести теоретическое исследование асимптотических свойств метрики Р-шасго.

3. Доказать состоятельность статистической оценки Р-шасго для моделей многозначной классификации.

4. Разработать алгоритмы поиска оптимальных порогов, изучить свойства предложенных численных методов, доказать близость находимых ими решений к оптимальному, оценить возникающие погрешности.

5. Реализовать программный комплекс и с его помощью провести вычислительные эксперименты применительно к различным прикладным задачам классификации с большим числом классов.

6. Исследовать различные методы восстановления условной плотности вероятности применительно к задаче предсказания молекулярной структуры, заданной спектром ХЛКЕБ.

Научная новизна. В диссертации получены следующие новые результаты:

1. Произведено сведение задачи поиска оптимальных порогов в модели многозначной классификации к задаче поиска неподвижной точки отображения на квадрате [0,1]2.

2. Получены асимптотические оценки области оптимального решения для Р-шасго

3. Доказана близость решения, получаемого с использованием оценок вероятностей, к оптимальному в РИ-смысле.

4. Предложены численные методы оптимизации ^-меры от средних точности и полноты: на основе анализа линеаризованного отображения и на основе анализа дискретной области определения отображения.

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

6. Проведено экспериментальное сравнение различных методов восстановления условной плотности вероятности, лучший из который использован для задачи предсказания молекулярной структуры, заданной спектром ХЛКЕБ.

Практическая значимость. Диссертационная работа имеет как теоретическую, так и практическую значимость. С теоретической точки зрения предложено сведение задачи поиска оптимальных порогов к задаче поиска неподвижной точки, которое может быть проведено и для других метрик качества. Также показано, что находимые решения близки к оптимальному, и предоставлены теоретические оценки области, содержащей оптимальное решение для метрики Р-шасго.

На практике разработанные вычислительные методы решения задачи оптимизации F-меры показывают существенное улучшение качества решения реальных прикладных задач многозначной классификации из различных областей: тексты, изображения. Предложенные численные методы позволяют находить оптимальные решения достаточно быстро, на любом современном персональном компьютере. Реализованный программный комплекс содержит весь необходимый функционал для решения задачи поиска оптимальных порогов для новых наборов данных и заданной ранжирующей функции.

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

В качестве языка программирования для реализации программного комплекса был выбран язык Python с библиотекой автоматического дифференцирования и обучения нейронных сетей Pytorch[42] и библиотекой экстремальной многозначной классификации с использованием деревьев PFastreXML[40]. Для ускорения вычислений использовалась библиотека JIT-компиляции Numba[43], генерирующая оптимизированный машинный код с использованием компилятора LLVM[44].

На защиту выносятся следующие результаты и положения: в области математического моделирования:

1. Сведение задачи поиска оптимальных порогов в модели многозначной классификации к задаче поиска неподвижной точки некоторого специально введенного отображения на квадрате [0,1]2.

2. Вывод асимптотических оценок области оптимального решения для F-меры от средних точности и полноты.

3. Доказательство близости решения, получаемого с использованием оценок вероятностей, к решению, оптимальному в PU-смысле, при слабом ограничении, наложенном на множество пороговых классификаторов.

в области численных методов:

4. Численный метод оптимизации F-меры от средних точности и полноты на основе анализа линеаризованного отображения.

5. Численный метод оптимизации F-меры от средних точности и полноты на основе анализа дискретной области определения специально введенного отображения.

в области программного обеспечения:

6. Комплекс программ «F-MACRO THRESHOLD OPTIMIZATION» (№2021610200, зарегистрирован 12.01.2021), позволяющий находить оптимальное решение задачи многозначной классификации для фиксированной ранжирующей функции.

общие результаты:

7. Результаты вычислительных экспериментов, проведенных путем применения разработанного комплекса программ к известным наборам данных многозначной классификации различной природы (WikiLSHTC-325K - тексты; Corel5K, ESP Game - изображения).

8. Результаты вычислительных экспериментов предсказания молекулярной структуры, заданной спектром XANES, с использованием различных методов восстановления условной плотности вероятности.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на международных конференциях и семинарах:

— на научном семинаре кафедры алгебры и дискретной математики Южного федерального университета, доклад «Разработка методов оптимизации метрик качества в задачах многозначной классификации»;

— на VIII международной конференции AIST (Казань, 17 - 19 июля 2019 года), доклад «Experimental Analysis of Approaches to Multidimensional Conditional Density Estimation»;

— на 28-й конференции Организации Открытых Инноваций FRUCT (Москва, 27 - 29 января 2021 года), доклад «Multi-label classification based on domain analysis in fixed point method».

Работа поддержана грантом Российского Фонда Фундаментальных исследований "Аспиранты"№20-37-90038.

Публикации и личный вклад автора. Основные результаты диссертации изложены в 5 печатных работах: 1 статья в журнале, рекомендованном Перечнем научных изданий для специальности 1.2.2 (Scopus, Q4)[45]; 1 статья в журнале Pattern Recognition (Scopus, Web of Science, Q1) [46]; 1 свидетельство о регистрации программы для ЭВМ[47]. Кроме того, опубликованы 2 статьи в сборниках трудов конференций[48; 49], 1 из которых принадлежит издательству Springer и индексируется в базах Scopus и Web of Science (Q2) [48].

В опубликованных работах совместно с к.ф.-м.н С.А. Гудой осуществлялась разработка общих математических подходов и обсуждение результатов. А.И. Бергер проводила теоретические исследования свойств модели и доказательства теорем, разрабатывала численные методы оптимизации F-меры, специализированные программные средства и проводила анализ результатов вычислительных экспериментов.

Основные положения, выносимые на защиту, являются личным вкладом автора в опубликованные работы.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. Полный объём диссертации составляет 111 страниц, включая 20 рисунков и 8 таблиц. Список литературы содержит 81 наименование.

Глава 1. Математическое исследование модели многозначной

классификации

Первая глава посвящена математическому исследованию модели многозначной классификации. В §1.1 вводится необходимая для этого исследования терминология: модель многозначной классификации, критерии оценки качества классификатора, несколько вариантов усреднения ^-меры и несколько подходов к ее вычислению, РИ и ЕМ, которые приводят к формулированию двух вариантов постановки задачи.

В §1.2 доказывается пороговость оптимального байесовского классификатора Н*к(ж) = [при(ж) ^ Ьк], где пГ(ж) = Р(ук = 1|ж), где Ьк — некоторый вектор порогов, для Р-шаегори, что позволяет применить модульный подход при построении оптимального классификатора.

В §1.3 доказывается состоятельность метрики Р-шаего в классе пороговых классификаторов 'Нрри с некоторым ограничением снизу на точность, а затем доказывается принадлежность оптимального в РИ смысле классификатора этому множеству. Для этого вводится еще один подход к вычислению метрики ^-меры - ожидаемая выборочная оценка ЕТИ.

В §1.4 вводится определение покоординатного максимума, который, вообще говоря, не является максимумом в обычном смысле этого слов, при этом обычный максимум всегда является покоординатным. С использованием введенного определения, в пространстве порогов задается отображение ^, действующее как Т ^ W (Т), для которого все покоординатные максимумы функции Р-шаего являются неподвижными точками. Поиск неподвижной точки отображения ^ по-прежнему является сложной проблемой из-за высокой размерности пространства порогов, равной числу классов п. Чтобы упростить процесс поиска, рассматривается «двойник» отображения ^ — отображение V, определенное на квадрате [0; 1]2 так, что V о (Р, Я) = (Р, Я) о W.

1.1 Постановка задачи

Рассмотрим модель многозначной классификации объектов из множества X на п возможно пересекающихся классов ci, с2, ..., сп. Обозначим Y = {0,1}п - множество всех возможных двоичных векторов длины n (1 - означает принадлежность соответствующему классу, 0 - непринадлежность). Будем рассматривать многозначный классификатор как отображение h : X ^ Y.

Оценка качества классификатора. Для оценки качества работы классификатора используются такие метрики, как точность и полнота, характеризующие его с разных сторон. Для того чтобы определить их, введем на декартовом произведении X х Y вероятностную меру P. Тогда для многозначного классификатора

h : X ^ Y, h(x) = (hi(x),h2(x),... ,hn(x)) точность и полнота вычисляются в каждом классе Ск следующим образом: Plu{hk) = P(yk = 1|hk = 1), rlU(hk) = P(h* = 1|yk = 1),k = 1, . . . ,n. (1.1)

При вычислении качества работы классификатора на практике точные вероятности неизвестны, и мы вынуждены ограничиваться статистическими оценками по заданной тестовой выборке: {(xi,yi)}]=1

т т

^2Угкhk (Xi) Т^Угкhk (Xi) PlM(hk) = ^-, rEM(hk) = ^-. (1.2)

Eh^ (xi) Т^Угк

i=1 i= 1

Будем обозначать первый вариант (1.1), подробно рассматриваемый в §1.3, аббревиатурой PU, так как в англоязычной литературе чаще всего для него используется термин «population utility», имеющий смысл «метрики, вычисленной для бесконечной выборки» или «предельной метрики». Для второго варианта метрики будем использовать аббревиатуру EM (EMpirical, основанный на опыте, выборочный).

Точность классификатора - условная вероятность объекта быть правильно классифицированным, то есть принадлежать классу при условии того, что классификатор отнёс его к этому классу. Среди множества пороговых

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

Полнота - условная вероятность объекта быть отнесённым к классу, если объект действительно ему принадлежит. Полнота порогового классификатора будет максимальной, в частности, в том случае, когда он относит к классу все объекты множества X, чему соответствует последнее положение порога.

Варианты усреднения ^-меры. Чтобы найти компромисс между этими двумя противоположными оценками, используют ^-меру, представляющую собой гармоническое среднее между точностью и полнотой: Р = . Но в условиях многозначной классификации расчет метрики может происходить двумя способами, отличающимися порядком применения операций усреднения по классам и гармонического среднего. Первый способ заключается в усреднении значений ^-меры, вычисленных независимо в каждом классе:

1 п

шаегс-Рри(Л) = ^ (ррки(кк )). (1.3)

тъ

к=1

Другой вариант ^-меры, исследуемый в данной работе, состоит в расчете среднего гармонического средних точности и полноты:

Р-шаегсри(Л) = ^ (Рри(Н),Яри(Н)),

1 А 1 А (1.4)

¡и IV

к=1 к=1

Аналогично метрике Р-шаегс, которая по своей природе симметрична относительно точности и полноты, можно ввести метрику Рр-шаегс, которая придает точности и полноте различный вес, что может быть удобно при решении некоторых реальных задач многозначной классификации:

Рр-шаегс(Л) = (Л), Д(Л)) = 1 „Т-V Г^Л (1.5)

(1 + в2)Р (НЩН) Р (Л) + в2Я(Н)

При 0 < в < 1 приоритет при оптимизации отдается точности, при в > 1 полноте. Р-шаегс является частным случаем Рр-шаегс при в = 1.

Метрика шаего-Р является более простой с точки зрения оптимизации, так как допускает независимую оптимизацию порога в каждом классе, в то время как при оптимизации Р-шаего маленькая полнота в одних классах может быть компенсирована высокой точностью в других, что не позволяет разделить оптимизацию на п независимых задач и делает ее вычислительно трудной.

Эмпирический вариант ^-меры. Эмпирические варианты метрик Р-шаегоЕМ и шаего-РЕМ определяются как оценки РИ-метрик:

1 п

шаего-РЕМ(И) = ^ (рЕМ(кк ),гЕМ(^)); (1.6)

тъ

к=1

п п

рЕМ(^) = - ЕркМ(^), = - ЕгкМ(Ьк) , ^ п к=1 п к=1 (1.7)

Р-шаегоЕМ(И) = ^ (РЕМ(И), ДЕМ(И))

Постановка задачи. Рассмотрим два варианта постановки задачи для случаев метрик Р-шаегори(И) и Р-шаегоЕМ(И):

— Пусть заданы множество X объектов и множество ¥ меток, и пусть задано совместное вероятностное распределение Р, определенное на декартовом произведении X х ¥. Требуется найти классификатор И : X ^ ¥, доставляющий максимум функции Р-шаегори(И)(1.4).

— Пусть заданы множество X объектов и множество ¥ меток, и пусть задана обучающая выборка - множество пар (х(г\ у(г))Г^=1. Требуется найти классификатор И : X ^ ¥, доставляющий максимум функции Р-шаегоЕМ (И) (1.7).

Выбор оптимальных порогов. В §1.2 доказано, что мера Р-шаегори монотонна по переменным рри и гри (Лемма 1), и как следствие получено, что классификатор И*, оптимальный в смысле метрики Р-шаегори, имеет пороговую форму: к*к(ж) = [лри(ж) ^ ¿к], где пГ(ж) = Р(Ук = 1|ж), % -некоторый вектор порогов (см. §1.2, Теорема 1). Этот факт позволяет применить двухступенчатый модульный подход для построения классификатора, на первом шаге которого обучается ранжирующая функция п : X ^ [0; 1]п, после чего на втором этапе определяется вектор оптимальных порогов Т = (Ь1,Ь2, • • • ¿п). Если зафиксировать ранжирующую функцию п, то задача поиска оптимального классификатора сводится к задаче нахождения вектора порогов, максимизирующего метрику Р-шаегори. Состоятельность Р-шаего меры, дока-заннная в §1.3, позволяет строить пороговые классификаторы, оптимизируя

метрику Р-шаегсЕМ, использующую оценки вероятностей принадлежностей объектов классам.

Далее в тексте работы будем обозначать функции Р-шаегс, шаегс-Р, рк, гк, Р, Я, зависящие от искомого вектора порогов Т = {Ьк}П= посредством порогового классификатора Л : X ^ ¥, Нк(ж) = [лк(ж) ^ ^к 1 теми же буквами: Р-шаегс(Т), шаегс-Р(Т), рк (¿к), П (¿к), Р (Т), Я(Т).

Предложенные алгоритмы могут быть применены как к Р-шаегсри, так и к эмпирическому варианту меры Р-шаегсЕМ. Поэтому в Главе 2 будем использовать неуточненные обозначения:

Р-шаегс(Т) = ^ (Р (Т ),Я(Т)),

1 1 ^ (1.8)

Р (Т) = Рк (1к), ЩТ) = Гк (1к). 1 }

ТЪ

к=1 к=1 1п

шаегс-Р(Т) = (Рк (г к ),П (¿к)), (1.9)

тъ

к=1

где в качестве Р, Я, рк, Т'к могут выступать как РИ величины (1.1), (1.4), так и их эмпирические ЕМ аналоги (1.2), (1.7).

1.2 Пороговость оптимального классификатора для Р-шаегсри

Чтобы убедиться в возможности применения двухступенчатого модульного подхода для построения оптимального классификатора для метрики Р-шаегсри, докажем сначала вспомогательную лемму, а затем соответствующую теорему.

Лемма 1. Мера Р-шаегсри(Л) — монотонно убывающая функция по переменным р1и(Нк), гри(Нк):

если ррк(кк) ^ ррк(к'к), то Р-шаегсри(Л) ^ Р-шаегсри(Л')

если г1и(Нк) ^ гки(Нк), то Р-шаегсри(Л) ^ Р-шаегсри(Л')

Доказательство. Напомним, что

п

2£ рпь) Е гт(нк)

Р-шаегори(Н) =

2Р ри(Н)Дри(Н) к=1 к=1

рри(Н) + дри(Н) П Е (ркУ(кк) + гри(^к))

к=1

„ри/

В контексте Леммы 1 для краткости будем обозначать рр](Кк), гри(Кк), Рри(Н) и Яри(Н) как рк, гк, Р и Л соответственно. Тогда

(п/п п \ п п \

Егк(Е Рк + Е - Е № Е гк)

(Р-шаего («))„. =-—--к=^-к=1 У

Список литературы диссертационного исследования кандидат наук Бергер Анна Игоревна, 2024 год

Список литературы

1. Weale, T. Utilizing Wikipedia categories for document classification [Текст] / T. Weale // Evaluation. — 2006. — С. 4.

2. Schonhofen, P. Identifying document topics using the Wikipedia category network [Текст] / P. Schonhofen // Web Intelligence and Agent Systems: An International Journal. — 2009. — Т. 7, № 2. — С. 195—207.

3. Pairwise multi-class document classification for semantic relations between wikipedia articles [Текст] / M. Ostendorff [и др.] // Proceedings of the ACM/IEEE Joint Conference on Digital Libraries in 2020. — 2020. — С. 127—136.

4. Correlation-based pruning of stacked binary relevance models for multi-label learning [Текст] / G. Tsoumakas [и др.] // Proceedings of the 1st international workshop on learning from multi-label data. — 2009. — С. 101—116.

5. A transductive multi-label learning approach for video concept detection [Текст] / J. Wang [и др.] // Pattern Recognition. — 2011. — Т. 44, № 10/ 11. — С. 2274—2286.

6. Garg, S. Learning video features for multi-label classification [Текст] / S. Garg // Proceedings of the European Conference on Computer Vision (ECCV) Workshops. — 2018. — С. 0-0.

7. Semantic-based tag recommendation in scientific bookmarking systems [Текст] / H. A. M. Hassan [и др.] // Proceedings of the 12th ACM Conference on Recommender Systems. — 2018. — С. 465—469.

8. Che, X. Feature distribution-based label correlation in multi-label classification [Текст] / X. Che, D. Chen, J. Mi // International Journal of Machine Learning and Cybernetics. — 2021. — Т. 12, № 6. — С. 1705—1719.

9. Correlative multi-label video annotation [Текст] / G.-J. Qi [и др.] // Proceedings of the 15th ACM international conference on Multimedia. — 2007. — С. 17—26.

10. Mohammed, A. A. Effectiveness of hierarchical softmax in large scale classification tasks [Текст] / A. A. Mohammed, V. Umaashankar // 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI). — IEEE. 2018. — С. 1090—1094.

11. Multi-label classification with label graph superimposing [Текст] / Y. Wang [и др.] // Proceedings of the AAAI Conference on Artificial Intelligence. Т. 34. — 2020. — С. 12265—12272.

12. Evaluating and optimizing autonomous text classification systems [Текст] / D. D. Lewis [и др.] // SIGIR. Т. 95. — Citeseer. 1995. — С. 246—254.

13. Optimizing F-measure: A Tale of Two Approaches [Текст] / N. Ye [и др.] // CoRR. — 2012. — Т. abs/1206.4625.

14. Consistency analysis for binary classification revisited [Текст] / K. Dembczynski [и др.] // Proceedings of the 34th International Conference on Machine Learning-Volume 70. — JMLR. org. 2017. — С. 961—969.

15. Вапник, В. О методе упорядоченной минимизации риска. I [Текст] / В. Вап-ник, А. Червоненкис // Automation and Remote Control. — 1974. — Т. 35, № 8. — С. 1226—1235.

16. Журавлев, Ю. И. Экстремальные алгоритмы в алгебре над некорректными алгоритмами [Текст] / Ю. И. Журавлев // Доклады Академии наук. Т. 237. — Российская академия наук. 1977. — С. 509—512.

17. Донской, В. Алгоритмические модели обучения классификации [Текст] / В. Донской. — 2014.

18. Дьяконов, А. Г. Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок: дис. ... д-ра физ.-мат. наук : 01.01.09 [Текст] / А. Г. Дьяконов. — М., 2009. — 258 с.

19. Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: дис. ... д-ра физ.-мат. наук : 05.13.17 [Текст] / К. В. Воронцов. — М., 2010. — 232 с.

20. Ветров, Д. В. Влияние устойчивости алгоритмов классификации на точность их работы: дис. ... канд. физ.-мат.. наук : 01.01.09 [Текст] / Д. В. Ветров. — М., 2007. — 138 с.

21. Rijsbergen, C. J. V. Information Retrieval [Текст] / C. J. V. Rijsbergen. — 2nd. — Newton, MA, USA : Butterworth-Heinemann, 1979.

22. Manning, C. D. Introduction to information retrieval [Текст] / C. D. Manning. — Syngress Publishing, 2008.

23. Sang, T. K. EF and De Meulder, F.(2003) [Текст] / T. K. Sang // Introduction to the CoNLL-2003 shared task: Language independent named entity recognition. InProceedings of the seventh conference on Natural language learning at HLT-NAACL. Т. 4. — 2003. — С. 142—147.

24. Fan, R.-E. A study on threshold selection for multi-label classification [Текст] / R.-E. Fan, C.-J. Lin // Department of Computer Science, National Taiwan University. — 2007. — С. 1—23.

25. Pillai, I. Threshold Optimisation for Multi-label Classifiers [Текст] / I. Pillai, G. Fumera, F. Roli // Pattern Recogn. — New York, NY, USA, 2013. — July. — Vol. 46, no. 7. — P. 2055—2065. — URL: http://dx.doi.org/10. 1016/j.patcog.2013.01.012.

26. Lipton, Z. C. Optimal thresholding of classifiers to maximize F1 measure [Текст] / Z. C. Lipton, C. Elkan, B. Naryanaswamy // Joint European Conference on Machine Learning and Knowledge Discovery in Databases. — Springer. 2014. — С. 225—239.

27. Deep f-measure maximization in multi-label classification: A comparative study [Текст] / S. Decubber [и др.] // Joint European Conference on Machine Learning and Knowledge Discovery in Databases. — Springer. 2018. — С. 290—305.

28. Cornolti, M. A Framework for Benchmarking Entity-annotation Systems [Текст] / M. Cornolti, P. Ferragina, M. Ciaramita // Proceedings of the 22Nd International Conference on World Wide Web. — Rio de Janeiro, Brazil : ACM, 2013. — С. 249—260. — (WWW '13). — URL: http://doi.acm.org/10.1145/ 2488388.2488411.

29. A LSTM based framework for handling multiclass imbalance in DGA botnet detection [Текст] / D. Tran [и др.] // Neurocomputing. — 2018. — Т. 275. — С. 2401—2413. — URL: https://doi.org/10.1016/j.neucom.2017.11.018.

30. Luo, L. Defining and Evaluating Classification Algorithm for High-Dimensional Data Based on Latent Topics [Текст] / L. Luo, L. Li // PloS one. — 2014.

31. Narasimhan, H. On the statistical consistency of plug-in classifiers for non-decomposable performance measures [Текст] / H. Narasimhan, R. Vaish, S. Agarwal // Advances in Neural Information Processing Systems. — 2014. — С. 1493—1501.

32. Extreme F-measure Maximization Using Sparse Probability Estimates [Текст] / K. Jasinska [и др.] // Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48. — New York, NY, USA : JMLR.org, 2016. — С. 1435—1444. — (ICML'16). — URL: http://dl.acm.org/citation.cfm?id=3045390.3045542.

33. Prabhu, Y. FastXML: A fast, accurate and stable tree-classifier for extreme multi-label learning [Текст] / Y. Prabhu, M. Varma // Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — 2014. — Авг.

34. Yang, Y. A Study of Thresholding Strategies for Text Categorization [Текст] / Y. Yang // Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. — New Orleans, Louisiana, USA : ACM, 2001. — С. 137—145. — (SIGIR '01). — URL: http://doi.acm.org/10.1145/383952.383975.

35. Pillai, I. Designing Multi-label Classifiers That Maximize F Measures [Текст] / I. Pillai, G. Fumera, F. Roli // Pattern Recogn. — New York, NY, USA, 2017. — Янв. — Т. 61, № C. — С. 394—404. — URL: https://doi.org/10.1016/j.patcog. 2016.08.008.

36. RCV1: A New Benchmark Collection for Text Categorization Research [Текст] / D. D. Lewis [и др.] //J. Mach. Learn. Res. — 2004. — Дек. — Т. 5. — С. 361—397. — URL: http://dl.acm.org/citation.cfm?id=1005332.1005345.

37. Triguero, I. Labelling Strategies for Hierarchical Multi-label Classification Techniques [Текст] / I. Triguero, C. Vens // Pattern Recogn. — New York, NY, USA, 2016. — Авг. — Т. 56, № C. — С. 170—183. — URL: http://dx.doi. org/10.1016/j.patcog.2016.02.017.

38. Fan, R.-E. A study on threshold selection for multi-label classification [Текст] : тех. отч. / R.-E. Fan, C.-J. Lin ; Department of Computer Science, National Taiwan University. — 11.2018.

39. Sparse local embeddings for extreme multi-label classification [Текст] / K. Bhatia [и др.] // Advances in neural information processing systems. — 2015. — Т. 28.

40. Jain, H. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications [Текст] / H. Jain, Y. Prabhu, M. Varma // Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. — 2016. — С. 935—944.

41. Babbar, R. Data scarcity, robustness and extreme multi-label classification [Текст] / R. Babbar, B. Scholkopf // Machine Learning. — 2019. — Т. 108, № 8. — С. 1329—1351.

42. Pytorch: An imperative style, high-performance deep learning library [Текст] / A. Paszke [и др.] // Advances in neural information processing systems. — 2019. — Т. 32.

43. Lam, S. K. Numba: A llvm-based python jit compiler [Текст] / S. K. Lam, A. Pitrou, S. Seibert // Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC. — 2015. — С. 1—6.

44. Lattner, C. LLVM: A compilation framework for lifelong program analysis & transformation [Текст] / C. Lattner, V. Adve // International Symposium on Code Generation and Optimization, 2004. CGO 2004. — IEEE. 2004. — С. 75—86.

45. Бергер, А. Свойства алгоритмов поиска оптимальных порогов для задач многозначной классификации [Текст] / А. Бергер, С. Гуда // Компьютерные исследования и моделирование. — 2022. — Т. 14, № 6. — С. 1221—1238.

46. Berger, A. Threshold optimization for F measure of macro-averaged precision and recall [Текст] / A. Berger, S. Guda // Pattern Recognition. — 2020. — Vol. 102. — P. 107250.

47. Свидетельство о гос. регистрации программы для ЭВМ. F-MACRO THRESHOLD OPTIMIZATION [Текст] / А. И. Бергер, С. А. Гуда. — № 2021610200 ; заявл. 22.12.2020 ; опубл. 12.01.2021 (Рос. Федерация).

48. Berger, A. Experimental Analysis of Approaches to Multidimensional Conditional Density Estimation [Текст] / A. Berger, S. Guda // In: van der Aalst, W., et al. Analysis of Images, Social Networks and Texts. AIST 2019. Lecture Notes in Computer Science. — 2019. — Vol. 11832. — P. 27—38.

49. Berger, A. Multi-label Classification Based on Domain Analysis in Fixed Point Method [Текст] / A. Berger, S. Guda // 2021 28th Conference of Open Innovations Association (FRUCT). — IEEE. 2021. — P. 1—7.

50. Optimal Classification with Multivariate Losses [Текст] / N. Natarajan [и др.] // ICML. — 2016. — С. 1530—1538.

51. Consistent Multilabel Classification [Текст] / O. Koyejo [и др.] // Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2. — Montreal, Canada : MIT Press, 2015. — С. 3321—3329. — (NIPS'15). — URL: http://dl.acm.org/citation.cfm?id=2969442.2969610.

52. Hueter, I. The convex hull of a normal sample [Текст] / I. Hueter // Advances in applied probability. — 1994. — Т. 26, № 4. — С. 855—875.

53. Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary [Текст] / P. Duygulu [и др.] // European conference on computer vision. — Springer. 2002. — С. 97—112.

54. Von Ahn, L. Labeling images with a computer game [Текст] / L. Von Ahn, L. Dabbish // Proceedings of the SIGCHI conference on Human factors in computing systems. — ACM. 2004. — С. 319—326.

55. LSHTC: A benchmark for large-scale text classification [Текст] / I. Partalas [и др.] // arXiv preprint arXiv:1503.08581. — 2015.

56. Varma, M. The Extreme Classification Repository: Multi-label Datasets & Code [Электронный ресурс] / M. Varma. — 2018. — URL: http : / / manikvarma.org/downloads/XC/XMLRepository.html.

57. Chollet, F. Xception: Deep Learning with Depthwise Separable Convolutions [Текст] / F. Chollet. — 2017. — Июль.

58. Keras [Электронный ресурс] / F. Chollet [и др.]. — 2015. — https://keras.io.

59. Imagenet: A large-scale hierarchical image database [Текст] / J. Deng [и др.] // Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. — Ieee. 2009. — С. 248—255.

60. Rethinking the Inception Architecture for Computer Vision [Текст] / C. Szegedy [и др.] // 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). — 2016. — С. 2818—2826.

61. Jain, H. Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking &#38; Other Missing Label Applications [Текст] / H. Jain, Y. Prabhu, M. Varma // Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — San Francisco, California, USA : ACM, 2016. — С. 935—944. — (KDD '16). — URL: http: //doi.acm.org/10.1145/2939672.2939756.

62. Babbar, R. DiSMEC: Distributed Sparse Machines for Extreme Multi-label Classification [Текст] / R. Babbar, B. Scholkopf // Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. — Cambridge, United Kingdom : ACM, 2017. — С. 721—729. — (WSDM '17). — URL: http: //doi.acm.org/10.1145/3018661.3018741.

63. PPDsparse: A Parallel Primal-Dual Sparse Method for Extreme Classification [Текст] / I. E. Yen [и др.] // Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — Halifax, NS, Canada : ACM, 2017. — С. 545—553. — (KDD '17). — URL: http://doi. acm.org/10.1145/3097983.3098083.

64. Murthy, V. N. Automatic Image Annotation Using Deep Learning Representations [Текст] / V. N. Murthy, S. Maji, R. Manmatha // Proceedings of the 5th ACM on International Conference on Multimedia Retrieval. — Shanghai, China : ACM, 2015. — С. 603—606. — (ICMR '15). — URL: http://doi.acm.org/10.1145/2671188.2749391.

65. A survey and analysis on automatic image annotation [Текст] / Q. Cheng [и др.] // Pattern Recognition. — 2018. — Т. 79. — С. 242—259. — URL: http://www.sciencedirect.com/science/article/pii/S0031320318300670.

66. Angrist, J. D. Mostly harmless econometrics: An empiricist's companion [Текст] / J. D. Angrist, J.-S. Pischke. — Princeton university press, 2008.

67. Burnaev, E. Conformalized kernel ridge regression [Текст] / E. Burnaev, I. Nazarov // 2016 15th IEEE international conference on machine learning and applications (ICMLA). — IEEE. 2016. — С. 45—52.

68. Kuleshov, A. P. Conformal prediction in manifold learning [Текст] / A. P. Kuleshov, A. Bernstein, E. Burnaev // 7th Symposium on Conformal and Probabilistic Prediction and Applications, COPA 2018, 11-13 June 2018, Maastricht, The Netherlands. — 2018. — С. 234—253.

69. Kuleshov, A. P. Kernel Regression on Manifold Valued Data [Текст] / A. P. Kuleshov, A. Bernstein, E. Burnaev // 5th IEEE International Conference on Data Science and Advanced Analytics, DSAA 2018, Turin, Italy, October 1-3, 2018. — 2018. — С. 120—129.

70. Bohm, G. Introduction to statistics and data analysis for physicists [Текст]. Т. 1 / G. Bohm, G. Zech. — Desy Hamburg, 2010.

71. Accurate photometric redshift probability density estimation-method comparison and application [Текст] / M. M. Rau, S. Seitz, F. Brimioulle [и др.] // Monthly Notices of the Royal Astronomical Society. — 2015. — Т. 452, № 4. — С. 3710—3725.

72. Kemp, G. C. Regression towards the mode [Текст] / G. C. Kemp, J. S. Silva // Journal of Econometrics. — 2012. — Т. 170, № 1. — С. 92—101.

73. Yao, W. A new regression model: modal linear regression [Текст] / W. Yao, L. Li // Scandinavian Journal of Statistics. — 2014. — Т. 41, № 3. — С. 656—671.

74. Quantitative structural determination of active sites from in situ and operando XANES spectra: From standard ab initio simulations to chemometric and machine learning approaches [Текст] / A. A. Guda, S. A. Guda, K. A. Lomachenko [и др.] // Catalysis Today. — 2018.

75. Converting high-dimensional regression to high-dimensional conditional density estimation [Текст] / R. Izbicki, A. B. Lee [и др.] // Electronic Journal of Statistics. — 2017. — Т. 11, № 2. — С. 2800—2831.

76. Pospisil, T. RFCDE: Random Forests for Conditional Density Estimation [Текст] / T. Pospisil, A. B. Lee // arXiv preprint arXiv:1804.05753. — 2018.

77. Izbicki, R. ABC-CDE: Toward Approximate Bayesian Computation With Complex High-Dimensional Data and Limited Simulations [Текст] / R. Izbicki, A. B. Lee, T. Pospisil // Journal of Computational and Graphical Statistics. — 2019. — С. 1—20.

78. PyFitit: the software for quantitative analysis of XANES spectra using machine-learning algorithms [Электронный ресурс] / A. Martini, S. A. Guda, A. A. Guda [и др.] // Mendeley Data. — 2019.

79. PyFitit: the software for quantitative analysis of XANES spectra using machine-learning algorithms [Электронный ресурс] / A. Martini, S. A. Guda, A. A. Guda [и др.] // Computer Physics Communications. — to appear.

80. Optimized Finite Difference Method for the Full-Potential XANES Simulations: Application to Molecular Adsorption Geometries in MOFs and Metal-Ligand Intersystem Crossing Transients [Текст] / S. A. Guda, A. A. Guda, M. A. Soldatov [и др.] // Journal of Chemical Theory and Computation. — 2015. — Сент. — Т. 11, № 9. — С. 4512—4521.

81. Lightgbm: A highly efficient gradient boosting decision tree [Текст] / G. Ke [и др.] // Advances in neural information processing systems. — 2017. — Т. 30.

Список рисунков

2.1 Область определения V(V) для 5 (а) и 10 (b) классов набора

данных ESP Game............................. 41

3.1 График функции ArgV для различных наборов данных:

WikiLSHTC-325K, ESPGame, Corel5K. Точка пересечения графика для каждого набора данных с графиком тождественной функции является аргументом неподвижной точки V. Разрывы на графиках соответствуют скоплениям классов, у которых совпадают

PR-кривые................................. 51

3.2 Оценка абсолютной ошибки |V(P,R) — V(P,R) |, допущенной Алгоритмом 2 для набора данных Corel5k. Цветом обозначены значения ^(pmax — pmin)2 + (дтах — ^min)2. Черная область

содержит все неподвижные точки точного отображения V (P,R). . . 53

3.3 PR-кривые для категорий 4023, 4656, 15017, 15461 и 16729 из набора данных WikiLSHTC-325K и ранжирующей функции, построенной с помощью метода PfastreXML. Выбор категорий случаен среди категорий, содержащих как минимум 30 документов. 55

3.4 Область определения функции V для тестового набора данных WikiLSHTC-325K. Зеленая точка соотвествует оптимальным значениям точности и полноты Р и R.................. 56

3.5 Оценка абсолютной ошибки |V(P,R) — V(P,R)I, допущенной Алгоритмом 2 для набора данных ESP Game и числа классов п = 50 (a), 100 (b), 200 (c). Цветом обозначены значения

y/(Pmax — Pmin)2 + (Pmax — ^min)2. Черная область содержит все неподвижные точки отображения V(P,R): Р G [Pmin; pmax], R G [Pmin; Pmax]............................... 57

3.6 Оценка абсолютной ошибки |У(Р,Я) — У(Р,Л)|, допущенной

Алгоритмом 2 для набора данных "^к1Ь8НТС-325К и количества классов п = 50 (а), 100 (Ь), 1000 (с). Цветом обозначены значения ^/(ртах — ртт)2 + (дтах — дтт)2. Черная область содержит все

неподвижные точки отображения

V(РД)\ Р е [Р™п; Ртах], Я е [Дт1п; Лтах]................ 57

3.7 Область определения V(V) и найденные оценки оптимального значения F-macro (синий и черный кресты - оценки снизу и сверху соответственно) для 2, 3 и 4 первых классов ESP Game и фиксированного количества полярных углов па= 14. Синие точки -истинная область определения V, красный - выпуклая оболочка На, построенная Алгоритмом 4, зеленая область - найденная область расположения максимума F-macro (точки (P,R) многогранника На для которых значения F-macro больше оценки оптимума снизу) .............................. 58

3.8 (a) Оценка абсолютной ошибки |V(P,R) — V(P,R)I, допущенной Алгоритмом 2 для набора данных Example и числа классов п = 80; (b) Область определения V(V) и найденные оценки оптимального значение F-macro (синий и черный кресты - оценки снизу и сверху соответственно) для числа классов п = 80 и числа полярных углов

Па= 100................................... 59

3.9 Погрешности определения максимума Fp-macro в зависимости от p для наборов данных ESPGame, WikiLSHTC и Example с использованием Алгоритмов 2 и 4. ................... 62

3.10 Зависимость оптимального значения Fp-macro и значения погрешности |V(P,R) — V(P,R)I от значения p для разных значений количества полярных углов для набора данных ESPGame. Число классов фиксировано и равно 5.................. 63

3.11 Голубым цветом обозначен график разрывной функции ArgV для задачи, описанной в Примере 3. Зеленым цветом - тождественная функция. Неподвижной точки для этого примера не существует. . . 64

3.12 Оценка ошибки |V(P,R) — V(P,R)I, допущенной Алгоритмом 1 для п = 1000 классов из Примера 3. Черная область должна содержать неподвижную точку: Р G [Pmin; Pmax], R G [Rmin; Rmax]. Серый отрезок соединяет точки (1, 3) и (2, 1).................. 65

3.13 Линии уровня функции плотности распределения наилучших значений точности р и полноты г в классах для (a) F-macro меры и (b) macro-F меры для набора данных ESP Game. Чтобы получить рисунок (a), используются точки (рь),гк(4а))), к = 1,..,п для

вектора порогов Т(а) = (t^,^,... ,tia)), который максимизирует меру F-macro. Аналогично строится рисунок (b) для macro-F меры. 69

3.14 Усредненные РЯ-кривые для подмножеств классов (1) - с одинаковыми порогами для Р-шаего и шаего-Р мер, (2) - с различными порогами, где р ^ г для Р-шаего меры, (3) - с различными порогами, где р < г для Р-шаего меры. Сплошные серые линии - линии уровня Р меры для отдельного класса, пунктирные линии - линии уровня линейной функции Е^р + г, где (Ро,Д)) - оптимальная неподвижная точка. Рисунок (а) построен для набора данных Соге15к, Рисунок (Ь) - для набора

данных WikiLSHTC-325K......................... 71

4.1 (a) Набор данных SURD(nx = 10, пу = 1, nz = 2, d = [0.1,1], а = 0.01, а = [0.3,0.3], ф = п), (b) функция плотности распределения, заданного в (а) при х = 0................ 80

4.2 Относительные ошибки для прямого (красный) и приближенного (синий) подход к вычислению метрики MISE для наборов данных (а) SURD(nx = 2, пу = 1, nz = 2, d = [0.1,1], а = 0, а = [0,0],

ф = п), (b) SURD(nx = 2, пу = 1, nz = 2, d = [1,1], а = 0,

а = [0,0], ф = п), (c) SURD(nx = 2, пу = 1, nz = 3, d = [1,1,1],

а = 0, а = [0,0,0], ф = п), (d) Fork(nx = 10, пу = 1, т = 2, а = 1). . 82

4.3 Относительные ошибки для CDE методов в зависимости от значения параметра а = [а, а], а £ (0, 0.6) для наборов данных (а) SURD(nx = 10, пу = 0, nz = 2, d = [1,1], а = 0, ф = п) и (b) такого

же, как (а), за исключением d = [0.1,1]................. 83

4.4 Относительные ошибки для CDE методов в зависимости от (а) d = [d, 1], d £ (0,1) для набора данных SURD(nx = 10, пу = 0, nz = 2, а = [0.3, 0.3], а = 0, ф = 0) и (b) ф £ (0, п) для набора данных SURD(nx = 10, пу = 0, nz = 2, а = [0.1,0.1], d = [0.1,1],

а = 0).................................... 84

4.5 Относительные ошибки для CDE методов в зависимости от

пу £ [1, 20] для наборов данных (а) SURD(nx = 1, nz = 2, а = [2, 2], d = [1,1], а = 0, ф = 0) (b) Fork(nx = 1, т = 2, а = 0.1)........ 85

Список таблиц

1 Значения функции F(Р(t1,t2),R(t1,t2)) для всех возможных пар порогов (t1,t2) в классах с1, с2, описанных в Примере 1........ 27

2 Значения линеаризованной функции 0.25р(т) + 0.25г(т) для

т G [1;6] и класса, описанного в Примере 2............... 39

3 Результаты применения метода линеаризации к тестовой части наборов данных Corel5k, ESP Game и WikiLSHTC-325K. Ошибка в наборе данных WikiLSHTC-325K составляет менее 10—5 вследствие большого числа классов п. Столбец «WikiLSHTC 5 lpi» содержит результаты работы метода применительно к набору данных WikiLSHTC-325K, когда метод PfastreXML предсказывает 5 категорий каждому объекту (значение этого параметра по умолчанию для метода PfastreXML)................... 52

4 Значения F меры для тестовой части наборов данных Corel5k, ESP Game и WikiLSHTC-325K. Строка F(Р, R) содержит значения, достигнутые при работе предложенного Алгоритма 1. Значения F-macro(Tb) и macro-F(Tb), приведенные для сравнения, получены для вектора порогов Тъ, который максимизирует F меру

независимо в каждом классе. (см. (3.2))................. 52

5 Значения F-меры для тестовой части набора данных WikiLSHTC-325K. Значение F(P,R) найдено с помощью Алгоритма 4. Значения F-macro(Tb) и macro-F(Tb), приведенные для сравнения, получены для вектора порогов Тъ,

максимизирующего F-меру независимо в каждом классе.......54

6 Погрешности работы методов линеаризации и анализа области определения V(V) для наборов данных ESP Game, WikiLSHTC и Example в зависимости от числа классов п (число полярных углов фиксировано па = 100): разброс значений точности (dP), полноты (dR), F-macro меры (dF-macro), полярного радиуса (dRad) и полярного угла (dArg) для возвращаемой ими области нахождения оптимума F-macro............................. 60

7 Значения функции R0p(t) + Р02г(т) для т G [1; 7] и класса из Примера 3.................................. 64

8 Значения метрики (4.1) для методов СБЕ применительно к

наборам данных Ее£егру.......................... 86

Приложение А

Комплекс программ «F-macro threshold optimization» А.1 Метод линеаризации

Листинг А.1: Точка входа в программу, реализующую метод линеаризации на языке Python

import argparse

from pathlib import Path

from numba.typed import List import numpy as np

from src.estimation import estimate_grid from src . io import format_output , load

OUTPUT_FOLDER = Path("./data/outputs/")

if __name__ == "__main__":

parser = argparse.ArgumentParser("Linear approximation algorithm.")

parser.add_argument("--db_file", type = str , required = True) parser.add_argument("--num_categs", type=int, required=True) parser.add_argument("--n_p", type=int, required=True) parser.add_argument("--beta", type = float , default=1) parser.add_argument("--output_folder", type=Path, default= OUTPUT_FOLDER) args = parser.parse_args()

raw_data = load(args.db_file) db_name = Path(args.db_file).stem data = List ()

[data.append(x) for x in raw_data]

res_p , res_r = estimate_grid(

data, num_categs=args.num_categs, n_p=args.n_p, beta= args.beta )

output = format_output(res_p, res_r, args.n_p, args.beta)

np.savetxt (

OUTPUT_FOLDER / (

f"python_{db_name}_{args.num_categs}_" f"{args.n_p}x{args.n_p}_{args.beta}.txt"

) ,

output ,

delimiter = " " ,

)

Листинг А.2: Основная функция, реализущая расширенный метод линеаризации на языке Python

@ j it(nopython=True) def estimate_grid(

data: List, num_categs: int, n_p: int, num_docs: int = -1, beta: int = 1 ) -> Tuple[np.ndarray , np.ndarray] :

Estimating F-macro in every point of a unit square grid, the number of points in grid is (n_p + 1) * (n_p + 1).

num_docs = len(data[0].pred) if num_docs == -1 else num_docs num_categs = len(data) if len(data) < num_categs else num_categs

print(f"num categories = {num_categs}")

n_r = n_p # the same amount of points in x and y axis p_0, p_1, r_0, r _1 = 0.0, 1.0, 0.0, 1.0

res_p = np . zeros ((3 , n_p + 1, n_r + 1), dtype = np. f loat64) res_r = np . zeros ((3 , n_p + 1, n_r + 1), dtype = np. f loat64)

for i_p in range (n_p + 1) :

for i_r in range(n_r + 1) :

map_0: float = p_0 + (p_1 - p_0) / n_p * i_p mar_0: float = r_0 + (r_1 - r_0) / n_r * i_r

w_1, w_2 = mar_0 ** 2, beta ** 2 * map_0 ** 2 delta = 1.0 / num_categs

eps = ( 2

* delta ** 2

* (map_0 + mar_0 + 2 * delta) ** 2 / (map_0 + mar_0 - 2 * delta) ** 3 if map_0 + mar_0 > 2 * delta

else 1e10

)

num_good_categs = 0

for ind in range(num_categs): categ = data[ind]

tp , fp = 0, 0

min_VP , max_VP , min_VR, max_VR = 1.0, 0.0, 1.0,

0.0

# 1) find best d_f_macro best_d_f_macro = -1e6 best_p_k : float = 0.0

for thr in range(1, len(categ.pred) + 2): if thr <= len(categ.pred) :

if categ.pred [thr - 1] == 1: tp += 1 else:

fp += 1

else:

tp = categ.size

fp = num_docs - categ.size

p_k_thr: float = tp * 1.0 / (tp + fp) r_k_thr: float = tp * 1.0 / categ.size d_f_macro = w_1 * p_k_thr + w_2 * r_k_thr

if d_f_macro > best_d_f_macro + 1e-12: best_p_k = p_k_thr best_r_k = r_k_thr best_d_f_macro = d_f_macro

assert best_d_f_macro > -1e6

# 2) find estimated region - this cycle can be optimized by storing

tp, fp = 0, 0

** 2

for thr in range(1, len(categ.pred) + 2): if thr <= len(categ.pred) :

if categ.pred [thr - 1] == 1: tp += 1 else :

fp += 1

else:

tp = categ.size

fp = num_docs - categ.size

p_k_thr = tp * 1.0 / (tp + fp)

r_k_thr = tp * 1.0 / categ.size

d_f_macro = w_1 * p_k_thr + w_2 * r_k_thr

neighb = num_categs * eps * (map_0 + mar_0)

if d_f_macro > best_d_f_macro - neighb: min_VP = min(min_VP, p_k_thr) max_VP = max(max_VP, p_k_thr)

min_VR = min(min_VR, r_k_thr) max_VR = max(max_VR, r_k_thr)

if (map_0 > 0) or (mar_0 > 0):

res_p[0, i_p, i_r] += min_VP

res_p [1, i_p, i_r] += best_p_k

res_p [2, i_p, i_r] += max_VP

res_r[0, i_p, i_r] += min_VR res_r[1, i_p, i_r] += best_r_k res_r[2, i_p, i_r] += max_VR

assert min_VP <= max_VP assert min_VR <= max_VR

num_good_categs += 1

if num_good_categs == 0: continue

res_p [: , i_p, i_r] /= num_good_categs res_r [: , i_p, i_r] /= num_good_categs

| return res_p, res_r

А.2 Метод исследования области определения

Листинг А.3: Точка входа в программу, реализующую метод исследования области определения на языке Python

import argparse

from pathlib import Path

from numba.typed import List import numpy as np

from src.estimation import estimate_DV from src . io import format_output , load

OUTPUT_FOLDER = Path("./data/outputs/")

if __name__ == "__main__":

parser = argparse.ArgumentParser("Domain analysis algorithm. ")

parser.add_argument("--db_file", type=str, required=True) parser.add_argument("--num_categs", type=int, required=True) parser.add_argument("--n_angles", type=int, required=True) parser.add_argument("--output_folder", type=Path, default= OUTPUT_FOLDER) args = parser.parse_args()

raw_data = load(args.db_file) db_name = Path(args.db_file).stem data = List ()

[data.append(x) for x in raw_data]

hull = estimate_DV(

data, num_categs=args.num_categs, num_angles=args. n_angles )

np.savetxt (

OUTPUT_FOLDER

/ (f"python_{db_name}_{args.num_categs}_{args.n_angles}. txt") ,

hull,

delimiter = " " ,

)

Листинг А.4: Основная функция, реализущая быстрый метод исследования области определения на языке Python

@ j it(nopython = True) def estimate_DV(

data: List, num_categs: int, num_angles: int, num_docs: int = -1

) -> np.ndarray :

"""Returns coordinates of D(V) border""" d_angle = 2.0 * np.pi / num_angles

num_docs = len(data [0] .pred) if num_docs == -1 else num_docs num_categs = len(data) if len(data) < num_categs else num_categs i0 = 0

hull = np.zeros((num_angles, 2))

count =0 # initial weight of start hull

for angle_i in range(num_angles):

hull[angle_i] = [0.2, 0.2] for i in range(num_categs) : cat = data[i0 + i]

catPR = np.zeros((cat.pred.size + 1, 2)) tp, fp = 0, 0

for barrier in range(1, cat.pred.size + 2): if barrier <= cat.pred.size:

if cat.pred[barrier - 1] == 1: tp += 1 else :

fp += 1

else :

tp = cat.size fp = num_docs - cat.size catPR[barrier -1,0] = tp * 1.0 / (tp + fp) catPR[barrier - 1, 1] = tp * 1.0 / cat.size

# ind = scipy.spatial. ConvexHull(catPR). vertices

# catPR = catPR[ind, :] catPR = get_convex_hull(catPR) assert len(catPR) > 1

for pi in range(len(catPR)):

prev = catPR[len(catPR) - 1] if pi == 0 else catPR[

pi - 1]

cur = catPR[pi]

next = catPR [0] if pi == len(catPR) - 1 else catPR[

pi + 1]

a = complex(prev [0] - cur [0] , prev [1] - cur [1] ) b = complex(next[0] - cur [0] , next [1] - cur [1] ) phi1 = (np.angle(a) + np.pi / 2) % (2 * np.pi) phi2 = (np.angle(b) - np.pi / 2) % (2 * np.pi) if phi 1 < phi2 :

for angle_i in range(

int(np.ceil(phi 1 / d_angle)), int(phi2 //

d_angle) + 1

) :

hull[angle_i, 0] = (hull[angle_i, 0] * count

+ cur [0]) / (

count + 1

)

hull[angle_i, 1] = (hull[angle_i, 1] * count

+ cur [ 1]) / (

count + 1

)

else: # we jump over 0

for angle_i in range(0, int(phi2 // d_angle) +

1) :

hull[angle_i, 0] = (hull[angle_i, 0] * count

+ cur [0]) / (

count + 1

)

hull[angle_i, 1] = (hull[angle_i, 1] * count

+ cur [ 1]) / (

count + 1

)

for angle_i in range(int(np.ceil(phi 1 / d_angle) ) , num_angles) :

hull[angle_i, 0] = (hull[angle_i, 0] * count

+ cur [0]) / (

count + 1

)

hull[angle_i, 1] = (hull[angle_i, 1] * count

+ cur [ 1]) / (

count + 1

)

count += 1 return hull

Приложение Б

Свидетельство о государственной регистрации программ для ЭВМ

Свидетельство о государственной регистрации программ для ЭВМ № 2021610200 от 12.01.2021. Российская Федерация. Программа F-MACRO THRESHOLD OPUTIMIZATION для расчета оптимального вектора порогов в ходе оптимизации метрики macro F-score в задаче многозначной классификации. - правообладатели Бергер А. И., Гуда С. А. - патентообладатели Бергер А. И., Гуда С. А., 1 с.

Б.1 Реферат

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

JLj.

ФВДИРДЩШШ

ШШШШ

$$$$$$

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ № 2021610200

F-MACRO THRESHOLD OPTIMIZATION

Правообладатели: Бергер Анна Игоревна (RU), Гуда Сергей Александрович (RU)

Авторы: Бергер Анна Игоревна (RU), Гуда Сергей Александрович (RU)

Заявка № 2020667204

Дата поступления 22 декабря 2020 Г.

Дата государственной регистрации в Реестре программ для ЭВМ 12 января 2021 г.

Руководитель Федеральной службы по интеллектуальной собственности

Г.П. Ивлиев