Что означает метрика качества в машинном обучении. Универсальный подход (почти) к любой задаче машинного обучения. Обучающая и тестовая выборка

УДК 519.816

С. В. СЕМЕНИХИН Л. А. ДЕНИСОВА

Омский государственный технический университет

МЕТОД МАШИННОГО ОБУЧЕНИЯ РАНЖИРОВАНИЮ

НА ОСНОВЕ МОДИФИЦИРОВАННОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ МЕТРИКИ ЫРСО

Рассмотрены задача ранжирования документов на странице результатов информационного поиска и вопросы машинного обучения ранжированию. Предложен подход к оптимизации функции ранжирования с использованием метрики качества ЫОСО на основе модифицированного генетического алгоритма. Проведены исследования разработанных алгоритмов (на тестовых коллекциях ЬЕТО^ и показана их эффективность для машинного обучения ранжированию.

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

1. Введение. В современных информационно-поисковых системах (ИПС) объемы данных, которыми оперирует система, настолько велики, что ключевой задачей становится ранжирование релевантных документов в ответ на поисковый запрос пользователя. На данном этапе развития ИПС наибольший интерес представляет машинное обучение (МО) ранжированию. Существующие подходы к МО, основанные на численных методах (в частности, на градиентных методах) или на аналитических расчетах , имеют ряд недостатков, которые существенно влияют на качество информационного поиска и временные затраты, необходимые для ранжирования релевантных документов.

В начале проведенных исследований были рассмотрены списочные подходы к машинному обучению ранжированию , в большинстве из которых используется метод градиентного спуска . В рассмотренных работах МО сводится к оптимизации метрик качества поиска (МКП), однако используются только метрики, представленные непрерывными функциями. Это ограничение зачастую приводит к тому, что в результате оптимизации функция ранжирования имеет менее высокие оценки по многим важным принятым показателям (DCG, nDCG, Graded Mean Reciprocal Rank и т.д.), являющимся дискретным функциями. В работе предложено применение генетических алгоритмов (ГА) при обучении ранжированию для минимизации функции потерь Хубера с использованием экспертных оценок релевантности в качестве эталонных значений. Также был предложен подход к МО на основе оптимизации дискретных метрик качества информационного поиска .

2. Постановка задачи машинного обучения ранжированию. В большинстве современных информационно-поисковых систем функция ранжирования строится на основе n простых ранжирующих функций (ПРФ) и может быть записана в виде:

где SRF¡ - ¡-ая простая ранжирующая функция для документа d и запроса д, WCi - весовой коэффициент ¡-ой простой ранжирующей функции, п - количество ПРФ в системе ранжирования.

В ходе машинного обучения ранжированию использован набор поисковых документов Б и запросов О из тестовой коллекции ЬБТОЯ . Для всех запросов деО сформирована пара с каждым документом dеD. Для каждой такой пары ИПС определяет значения релевантности, которые используются для ранжирования поисковой выдачи. Для того чтобы произвести оценку качества ранжирования, системе требуются эталонные значения релевантности Е для каждой пары документ-запрос ^, д). Для этих целей используются экспертные оценки релевантности.

Для проведения исследования использована ИПС, в которой ранжирование производится на основе N = 5 простых ранжирующих функций SRFi(WC)l г = 1, N, которые образуют векторный критерий оптимальности:

где WCе {WC} - вектор варьируемых параметров; {ШС}, {ЯБ} - пространства параметров и векторных критериев соответственно.

Применение генетических алгоритмов для МО ранжированию делает возможным максимизацию дискретных метрик качества, таких как nDCG. Метрика nDCG ранжирования документов в поисковой системе определяется в соответствии с выражением :

DCG @ n = X 2---

RF(q, d)= X WC. ■ SRF., i=1 1 1

где grade(p) - средняя оценка релевантности, выставленная экспертами документу, расположенному на позиции p в списке результатов, gradee ; 1/log2(2 + p) - коэффициент, зависящий от позиций документа (первые документы имеют больший вес).

Тогда нормализованная версия NDCG запишется в виде

N000 @ п = ОСО @ П / г,

где г - фактор нормализации, который равен максимально возможному значению 0С0@п для данного запроса (т.е. равен ООО идеального ранжирования).

Таким образом, для оптимизации (максимизации) метрики пОСО, целевая функция (ЯМ) запишется в следующем виде

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

1. Критерий точности информационного поиска

где a - количество найденных релевантных документов, b - количество документов, ошибочно принятых за релевантные.

2. Критерий Bpref, оценивающий релевантность информационного поиска, используется для обработки задания с R релевантными документами и вычисляется по формуле

Bpref = - ^ (1 - Non Re ¡Before(r)/ R). (4)

Здесь символом r обозначен известный релевантный документ, а NonRelBefore(r) - число известных нерелевантных документов, ранжированных выше, чем r (при вычислении учитываются только первые R оцененных нерелевантных документов из прогона).

3. Критерий полноты поисковой выдачи

r = a / (a + с),

где a - количество найденных релевантных документов, с - количество ненайденных релевантных документов.

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

ранжирования поисковой выдачи системой. В процессе МО тестовые коллекции используются в качестве обучающей выборки и, следовательно, оказывают значительное влияние на результаты. Для проведения исследований использована тестовая коллекция документов и запросов LETOR. Эта коллекция используется в исследованиях в области поиска информации подразделениями Microsoft Research. В табл. 1 приведены характеристики тестовых коллекций LETOR.

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

Следует отметить, что ГА наиболее эффективны в поисках области глобального экстремума, однако они могут медленно работать, когда необходимо найти локальный минимум в этой области. Предлагаемый способ избежать этого недостатка - создание модифицированного генетического алгоритма (МГА), который будет переключаться на локальный (быстродействующий) алгоритм оптимизации после нахождения области глобального оптимума с помощью базового ГА. Предлагаемый в работе МГА представляет собой гибридный метод на основе классического ГА и метода Нелдера - Мида (симплекс-алгоритма). Метод Нелдера - Мида, часто используемый алгоритм нелинейной оптимизации, является численным методом для нахождения минимума целевой функции в многомерном пространстве . Предлагаемый в данной работе гибридный алгоритм MGA переключается на метод Нелдера - Мида после выполнения условий остановки ГА. Блок-схема алгоритма MGA показана на рис. 1.

При выполнении исследований принято ограничение на количество вычислений целевой функции (Nrf= 16 000) при поиске области глобального экстремума и условие перехода на алгоритм локальный оптимизации на основе метода Нелдера - Мида (после того как базовый генетический алгоритм выполнит 75 % Nrf операций).

6. Результаты. В результате проведенных исследований с помощью алгоритма машинного обучения

Таблица 1

Количество документов и запросов в тестовых коллекциях

Название тестовой коллекции Название подсистемы Количество запросов Количество документов

LETOR 4.0 MQ2007 1692 69623

LETOR 4.0 MQ2008 784 15211

LETOR 3.0 OHSUMED 106 16140

LETOR 3.0 Gov03td 50 49058

LETOR 3.0 Gov03np 150 148657

LETOR 3.0 Gov03hp 150 147606

LETOR 3.0 Gov04td 75 74146

LETOR 3.0 Gov04np 75 73834

LETOR 3.0 Gov04hp 75 74409

Рис. 1. Блок-схема гибридного алгоритма МвЛ на основе генетических алгоритмов и метода Нелдера-Мида

ранжированию LTR-MGA получен вектор весовых коэффициентов WC* для функции ранжирования. Далее на основе данных из тестовой коллекции ЬЕТОЯ произведена оценка качества ранжирования, для чего вычислены метрики качества. Дискретная метрика качества ранжирования NDCG@n оценивает качество первых п документов ответа системы. Общепринятыми метриками для оценки качества ранжирования являются NDCG@1, NDCG@5 и NDCG@10. Однако для более детального рассмотрения изменений метрики в зависимости были рассмотрены значения NDCG@n для всех п от 1 до 10. Для сравнения эффективности разработанного алгоритма с существующими решениями проведен сравнительный анализ с использованием ранжирующих алгоритмов, предоставленных в коллекциях ЬЕТОЯ 3.0. Результаты выполнения алгоритмов для тестовых коллекций ТБ2003 и ТБ2004 для метрики NDCG представлены на рис. 2. Результаты показывают, что алгоритм LTR-MGA превосходит тестовые алгоритмы, причем наиболее высокие значения име-

ются для NDCG@1 (на уровне первого документа). Превосходство алгоритма LTR-MGA вызвано тем, что, в отличие от рассмотренных в экспериментах тестовых ранжирующих функций, в предлагаемом подходе для оптимизации функции ранжирования именно метрика NDCG используется в качестве целевой функции.

Для того, чтобы оценить качество ранжирования при использовании предлагаемого алгоритма LTR-MGA вычислены значения метрик качества ранжирования документов в поисковой выдаче (рис. 3). Сравнение результатов ранжирования (табл. 2) при использовании базовой ранжирующей функции, базового алгоритма LTR-GA и модифицированного алгоритма LTR-MGA свидетельствует о преимуществе последнего.

Кроме того, при исследовании выполнена оценка времени, требуемого для МО ранжированию. Это необходимо для подтверждения того, что предложенный метод LTR-MGA превосходит в этом показателе подход, основанный на использовании традици-

Рис. 2. Сравнение алгоритмов машинного обучения ранжированию

по метрике NDCG для тестовых коллекций: слева - набор данных Gov03td, справа - набор данных Gov04td

Рис. 3. Оценка метрик качества ранжирования для базовой ранжирующей формулы и алгоритмов обучения LTR-GA и LTR-MGA

Метрики качества ранжирования для разных алгоритмов машинного обучения ранжированию

Таблица 2

Метрика качества ранжирования Базовая ранжирующая функция LTR-GA LTR-MGA Повышение значения метрики, %

Точность 0,201 0,251 0,267 26,81

NDCG@5 (первые 5 документов) 0,149 0,31 0,339 90,47

NDCG@10 (первые 10 документов) 0,265 0.342 0,362 29,14

Bpref 0,303 0,316 0,446 51,49

Полнота 0,524 0,542 0,732 39,03

* Серым выделены лучшие значения для соответствующей метрики

онного генетического алгоритма (ЬТЯ-ОЛ). Результаты сравнения временных затрат на выполнение алгоритмов ЬТЯ-ОЛ и ЬТЯ-МОЛ приведены в табл. 3.

7. Заключение. Таким образом, проведенные исследования показали, что при использовании предлагаемого подхода значения рассмотренных метрик ранжирования в ИПС увеличиваются (в среднем на 19,55 % по сравнению с алгоритмом ЬТЯ-ОЛ). Это подтверждает, что ЬТЯ-МОЛ работает корректно и значительно улучшает функцию ранжирования, другими словами - успешно решает задачу оптимизации. С помощью модифицированного алгоритма

за счет применения метода локальной оптимизации и введенных ограничений на количество вычислений целевой функции время машинного обучения снизилось (в среднем на 17,71 % по сравнению с использованием традиционного генетического алгоритма ЬТЯОЛ).

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

Оценка времени выполнения машинного обучения ранжированию в зависимости от размера обучающей выборки

Таблица 3

Размер текстовой коллекции документов

Время выполнения LTR-GA

Время выполнения LTR-MGA

Уменьшение времени выполнения, %

Среднее значение

*Серым цветом выделены лучшие значения для соответствующего размера тестовой коллекции

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

Библиографический список

1. Tie-Yan Liu. Learning to Rank for Information Retrieval // Journal Foundations and Trends in Information Retrieval. Vol. 3, issue 3. March 2009. P. 225-331.

2. Christopher J. C. Burges, Tal Shaked, Erin Renshaw. Learning to Rank using Gradient Descent // Proceeding ICML "05 Proceedings of the 22nd international conference on Machine learning. 2005. P. 89-96.

3. Семенихин, С. В. Исследование подходов к машинному обучению ранжированию документов поисковой системой на базе генетических алгоритмов / С. В. Семенихин // Россия молодая: передовые технологии - в промышленность. - 2013. - № 2. - С. 82 - 85.

4. Многокритериальная оптимизация на основе генетических алгоритмов при синтезе систем управления: моногр. / Л. А. Денисова. - Омск: Изд-во ОмГТУ, 2014. - 170 с. - ISBN 978-5-8149-1822-2.

5. Денисова, Л. А. Автоматизация параметрического синтеза системы регулирования с использованием генетического алгоритма / Л. А. Денисова, В. А. Мещеряков // Автоматизация в промышленности. - 2012. - № 7. - С. 34 - 38.

6. Huber, Peter J. Robust Estimation of a Location Parameter // Annals of Statistics. - 1964. - № 53. - P. 73-101.

7. Семенихин, С. В. Автоматизация информационного поиска на базе многокритериальной оптимизации и генетических алгоритмов / С. В. Семенихин, Л. А. Денисова // Динамика систем, механизмов и машин. - 2014. - № 3. - С. 224 - 227.

8. Tie-Yan Liu, Jun Xu, Tao Qin, Wenying Xiong and Hang Li. LETOR: Benchmark Dataset for Research on Learning to Rank for Information Retrieval // SIGIR 2007 Workshop on Learning to Rank for Information Retrieval. - 2007. - С. 3-10.

9. Агеев, М. С. Официальные метрики Р0МИП"2004 / М. С. Агеев, И. Е Кураленок // II Россиискии семинар по оценке методов информационного поиска (РОМИП 2004), Пущино, 2004: тр. ; под ред. И. С. Некрестьянова. - СПб. : НИИ химии СПбГУ. - С. 142-150.

10. J. A. Nelder, R. Mead, A simplex method for function minimization, The Computer Journal 7 (1965). 308-313.

СЕМЕНИХИН Святослав Витальевич, аспирант кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: [email protected] ДЕНИСОВА Людмила Альбертовна, доктор технических наук, доцент кафедры «Автоматизированные системы обработки информации и управления». Адрес для переписки: [email protected]

На элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента (например, «релевантен» или «не релевантен»; возможно использование и более, чем двух градаций). Цель ранжирующей модели - наилучшим образом (в некотором смысле) приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.

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

Энциклопедичный YouTube

1 / 5
Во время обучения ранжирующей модели и при её работе, каждая пара документ-запрос переводится в числовой вектор из ранжирующих признаков (также называемых ранжирующими факторами или сигналами), характеризующих свойства документа, запроса и их взаимоотношение. Такие признаки можно разделить на три группы:

Ниже приведены некоторые примеры ранжирующих признаков, использующиеся в широко известном в данной области исследований наборе данных LETOR:
- Значения мер TF, TF-IDF , BM25 , и языковой модели соответствия запросу различных зон документа (заголовка, URL, основного текста, текста ссылок);
- Длины и IDF-суммы зон документа;
- Ранги документа, полученные различными вариантами таких алгоритмов ссылочного ранжирования, как PageRank и HITS .
Метрики качества ранжирования

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

Классификация алгоритмов

В своей статье «Learning to Rank for Information Retrieval» и выступлениях на тематических конференциях, Тай-Ян Лью из Microsoft Research Asia проанализировал существующие на тот момент методы для решения задачи обучения ранжированию и предложил их классификацию на три подхода, в зависимости от используемого входного представления данных и функции штрафа:

Поточечный подход

Примечания
1. Tie-Yan Liu (2009), Learning to Rank for Information Retrieval , Foundations and Trends in Information Retrieval: Vol. 3: No 3, с. 225-331, ISBN 978-1-60198-244-5 , DOI 10.1561/1500000016 . Доступны слайды c выступления Т. Лью на конференции WWW 2009.
1
В последние годы уделяется много внимания реконструкции изображений, соответственно оценка качества является важной задачей для сравнения различных методов восстановления изображений. Во многих случаях методы реконструкции приводят к размытию текстуры и структуры при восстановлении больших областей с искаженными значениями пикселей. Объективная количественная оценка результатов восстановления в настоящее время отсутствует, в связи, с чем во многих подходах используется экспертная оценка. В данной статье рассматривается новый подход оценки качества восстановления изображений на основе машинного обучения с использование модели зрения человека, который заключается в том, что локальные области изображений могут быть представлены дескрипторами в виде некоторых параметрических распределений. Далее метод опорных векторов регрессии позволяет предсказать воспринимаемое качество восстановленных изображений в соответствии с экспертной оценкой. В работе продемонстрировано, что оценка качества, полученная с использованием приведенного подхода коррелирует с субъективной оценкой качества.

машинное обучение
визуальное качество
реконструкция
обработка изображений

1. Gastaldo P. Machine learning solutions for objective visual quality assessment / 6th international workshop on video processing and quality metrics for consumer electronics, VPQM. - Vol. 12. - 2012.
2. Bertalmio M., Bertozzi A., Sapiro G. Navier-Stokes, ﬂuid dynamics, and image and video inpainting/ Hawaii: Proc. IEEE Computer Vision and Pattern Recognition (CVPR) . - 2001.– PP. 213–226.
3. Criminisi A., Perez P., Toyama K. Region ﬁlling and object removal by exemplar-based image inpainting / IEEE Trans. Image Process. - 13(9) . - 2004. - PP. 28–34.
4. Vijay M., Cheung, S.S. Eye tracking based perceptual image inpainting quality analysis/ Image Processing (ICIP), 17th IEEE International Conference on IEEE. - 2010. - PP. 1109 - 1112.
5. Ardis P.A., Singhal A. Visual salience metrics for image inpainting /SPIE Electronic Imaging. International Society for Optics and Photonics. - 2009.
6. Cheung S.S., Zhao J., Venkatesh V. Efficient object-based video inpainting / Image Processing, 2006 IEEE International Conference on. - 2006. - PP. 705-708.
7. Перетягин Г.И. Представление изображений гауссовыми случайными полями/ Автометрия. – № 6. – 1984. – С. 42 – 48.
8. Frantc V.A., Voroni V.V., Marchuk V.I., Sherstobitov A.I., Agaian S., Egiazarian K. Machine learning approach for objective inpainting quality assessment/ Proc. SPIE 9120, Mobile Multimedia/Image Processing, Security, and Applications. – Vol. 91200S. – 2014.
9. Paul A., Singhal A., and. Brown C. Inpainting quality assessment / Journal of Electronic Imaging. – Vol. 19. – 2010. – PP. 011002-011002.

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

Возможны два подхода к оценке качества изображений: количественная оценка с помощью использования математических методов (среднеквадратическая ошибка, Lp-норма , меры, учитывающие особенности восприятия изображения зрительной системой человека) и субъективная оценка на основе экспертных оценок .

Оценка качества, полученная с использованием существующих подходов, может значительно отличаться от оценки, полученной с помощью людей-экспертов. Большинство существующих подходов для оценки качества используют эталонное изображение. Но, к сожалению, во многих случаях эталонное изображение недоступно. К таким задачам относится и задача реконструкции утраченных пикселей. Таким образом, задача разработки количественной метрики оценки качества реконструированных изображений является актуальной.

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

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

Математическая модель

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

Рис 1. Модель изображения

Известно изображение и область Ω внутри его. Задача реконструкции состоит в модификации значений пикселей изображения внутри области Ω, таким образом, чтобы область не выделялась на фоне окружающего изображения . Цель реконструкции может состоять в восстановлении поврежденных частей изображения (например, царапин и трещин на старых фотографиях) или удаления нежелательных объектов на изображении. Показанная на рисунке 1 область Ω всегда определяется пользователем, т.е. определение области Ω не является частью задачи реконструкции.

Алгоритм оценки качества восстановления изображений

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

1. Определение пространства признаков , служащих описанием входных сигналов.

2. Выбор функции отображения из пространства признаков в пространство оценок качества .

3. Обучение системы и проверка ее устойчивости (проверка на переобучение и т.д.).

Структурная схема выбранного подхода представлена на рисунке 2 и содержит следующие этапы:

1. Выбор области интереса (с использованием карты внимания);

2. Вычисление низкоуровневых признаков изображения;

3. Построение дескриптора восстановленной области на базе низкоуровневых особенностей;

4. Решение задачи регрессии с целью получения численной оценки качества на основе полученного вектора-дескриптора.

Рис. 2. Блок-схема алгоритма

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

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

.

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

В качестве низкоуровневых признаков локальных областей используются спектральные представления. Далее предлагается анализ следующих базисов Фурье, Уолша, Хаара с использованием вектора эффективности. Для корректного вычисления составляющих системного критерия эффективности при наличии помех и искажений требует применения статистического усреднения.

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

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

При конечном числе членов ряда Фурье можно охарактеризовать погрешностью: , где - расстояние в некоторой метрике, - частичная сумма членов ряда Фурье.

Аппаратурное определение коэффициентов ряда Фурье или их вычисление связанно с определенными вычислительными затратами . Введем функцию потерь, учитывающую как потери, связанные с погрешностью усечения ряда Фурье, так и затраты аппаратурных и вычислительных ресурсов:

.

Значение условного риска зависит как от подкласса сигналов, так и от базиса и вычисляется путем усреднения функции потерь по реализациям:

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

Средний риск определяется путем усреднения условного риска по подклассам сигналов:

,

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

В соответствии с критерием минимума среднего риска из базисов выбирается тот, для которого средний риск минимален.

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

В качестве примера в статье рассматривается представление случайных реализаций с различными корреляционными функциями в базисах тригонометрических функций (Фурье), Уолша и Хаара. Проведем анализ в выбранных базисах для созданных моделей изображений размером 256 на 256 пикселей. Зададимся также тремя типами распределения вероятностей подклассов: 1) равномерное: ; 2) убывающее: ;
3) возрастающее: . Выберем функцию стоимости в виде: .

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

Таблица 1

Величины среднего риска

Виды распределения вероятностей

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

На основе проведенного анализа выберем базис Хаара для представления локальных областей изображений. Следует отметить, что размер восстановленной области различен для различных изображений. В связи с этим на основе низкоуровневых признаков следует формировать высокоуровневое представление фиксированного размера. В качестве высокоуровневого представления используется подход «мешок слов». Процедура построения дескриптора (сигнатуры) восстановленной области состоит из двух шагов. На первом шаге строится словарь. Для этого используются низкоуровневые особенности, извлеченные из всех изображений обучающего набора изображений. Для построения словаря извлеченные особенности делятся на 100 классов с помощью алгоритма кластеризации k-средних. Каждый элемент словаря представляет собой центроид для одного из классов, найденных процедурой кластеризации. Каждое слово в словаре представляет преобразование Хаара в блоке изображения размером 8x8. Полученный словарь используется на втором этапе при построении гистограмм частот для слов из словаря в качестве вектора признаков - дескриптора восстановленной области (рис. 3). Полученный набор дескрипторов используется для обучения машины регрессии (Support Vector Regression). Для получения гистограммы частот слов из словаря извлекаются все визуально заметные области (заметность определяется с использованием карт внимания) конкретного изображения. Затем к каждому из извлеченных блоков применяется преобразование Хаара и выполняется классификация согласно полученному словарю на основе евклидова расстояния .

Каждый бин результирующей гистограммы содержит число низкоуровневых особенностей конкретного класса в данной восстановленной области. После нормализации гистограммы получается «сигнатура» изображения - высокоуровневое представление восстановленной области .

Рис.3. Построение гистограммы

Оценка эффективности алгоритма оценки качества восстановления изображений

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

Эксперты оценивали качество по шкале, в которой 5 соответствует «Отлично», а 1 - соответствует «Очень плохо». Для оценки эффективности полученной метрики используется коэффициент корреляции между векторами полученных с помощью объективной метрики и экспертным методом оценок качества. Анализ полученных результатов в таблице 2 показывает, что предложенный подход превосходит известные метрики качества на выбранном наборе тестовых данных.

Таблица 2

Коэффициент корреляции для различных методов вычисления объективной
метрики качества изображений

Предложенный подход

Заключение

В статье представлена объективная метрика оценки качества изображений на основе машинного обучения. Количественные меры качества изображения необходимы для проектирования и оценки систем воспроизведения изображений. Эти меры во многом помогут избавиться от трудоемкой и неточной современной методики оценки изображений посредством субъективной экспертизы. Кроме того, на основе количественных мер можно развивать методы оптимизации систем обработки изображений. Продемонстрировано, что оценка качества, полученная с использованием приведенного подхода коррелирует с субъективной оценкой качества.

Работа поддержана Минобрнауки России в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы» (соглашение №14.586.21.0013).

Рецензенты:

Федосов В.П., д.т.н., профессор, заведующий кафедрой ТОР инженерно-технологической академии Южного Федерального Университета, г.Ростов-на-Дону;

Марчук В.И., д.т.н., профессор, заведующий кафедрой «Радиоэлектронные и электротехнические системы и комплексы» ИСОиП (филиал ДГТУ), г.Шахты.

Библиографическая ссылка
Воронин В.В. ОЦЕНКА КАЧЕСТВА ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ МАШИННОГО ОБУЧЕНИЯ // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=16294 (дата обращения: 01.02.2020). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
В данной главе представлены популярные методы оценки качества работы модели классификации, которые в том числе используются в других работах на эту тему. Приведено их описание и обоснование используемых для данной оценки метрик.

Метрики оценки качества

Полная точность (accuracy)

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

Точность, полнота и F-мера

Такие метрики, как точность (precision) и полнота (recall) впервые получили широкое распространение в оценке качества работы систем решающих задачу информационного поиска. Точность системы в пределах одного класса представляет собой долю объектов действительно принадлежащих определенному классу относительно всех объектов отнесенных системой к этому классу. Полнота выражается как доля найденных классификатором объектов принадлежащих классу относительно всех объектов этого класса . Таблица 4 представляет собой таблицу сопряженности отдельного класса, где TP (true positive) - истинно-положительное решение, TN (true negative) - истинно-отрицательное решение, FP (false positive) - ложно-положительное решение и FN (false negative) - ложно-отрицательное решение.

Таблица 1 - Таблица сопряженности класса объектов

Таким образом, точность и полнота вычисляются как:

F-мера объединяет в себе информацию о точности и полноте оцениваемого алгоритма. Вычисляется она как гармонические среднее показателей точности и полноты:

В силу того, что F-мера вычисляется отдельно для каждого класса ее удобно использовать для поиска и анализа конкретных ошибок алгоритма, для оценки классификации с несколькими классами. При этом в случае большого числа классов необходима характеристика, которая бы агрегировала полноту и точность по всем классам и характеризовала бы общее поведение системы. В данной работе для этой цели применяется следующие агрегированные величины: макро точность (macro precision), которая вычисляется как среднее арифметическое значения точности по всем классам, макро полнотой (macro recall), которая вычисляется как среднее арифметическое значение полноты по всем классам и макро F-мера (Macro F-score), которая является гармоническим средним между ними .

Кросс-валидация

Одним из наиболее распространенных методов для проведения полноценного тестирования и оценки качества работы различных алгоритмов машинного обучения, является скользящий контроль (cross-validation). Для независимой выборки данный метод позволяет получить несмещенную оценку вероятности ошибки в отличие от средней ошибки на обучаемой выборке, которая может являться смещенной оценкой вероятности ошибки из-за переобучения алгоритма . Другим достоинством данной процедуры является способность получения оценки вероятности ошибки алгоритма, при отсутствии специально разработанной для тестирования контрольной выборки.

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

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

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

Это была преамбула к тезису о том, что системный аналитик должен хорошо владеть математическим аппаратом и заодно уметь объяснять «математику» заказчику. А теперь рассмотрим пример.

О задаче классификации

Предположим, что мы пишем FRD для системы контекстной рекламы, похожей на Amazon Omakase . Одним из модулей нашей будущей системы будет контекстный анализатор:

Анализатор принимает на входе текст веб-страницы и производит его контекстный анализ. То, каким образом он это делает, нас особо не интересует; важно, что на выходе мы получаем набор товарных категорий (множество которых заранее определено). Далее на основе этих категорий мы можем показывать баннеры, товарные ссылки (как Amazon) и т.п. Анализатор для нас пока является черным ящиком, которому мы можем задать вопрос (в виде текста документа) и получить ответ.

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

Метрики оценки

Рассмотрим метрики оценки, применимые к задаче классификации. Допустим, что мы знаем правильные категории для некоторого числа документов. Сгруппируем ответы нашего гипотетического анализатора следующим образом:
- Истинно-положительные (true positives ) — те категории, которые мы ожидали увидеть и получили на выходе
- Ложно-положительные (false positives ) — категории, которых быть на выходе не должно и анализатор их ошибочно вернул на выходе
- Ложно-отрицательные (false negatives ) — категории, которые мы ожидали увидеть, но анализатор их не определил
- Истинно-отрицательные (true negatives ) — категории, которых быть на выходе не должно и на выходе анализатора они тоже совершенно правильно отсутствуют.
Назовем тестовой выборкой множество документов (веб-страниц), для которых мы знаем правильные ответы. Если подсчитать по каждой категории число попаданий (считаем попадания по парам документ — категория), получим каноническую табличку распределения ответов:

Левая колонка таблицы — это «правильные» сочетания документов и категорий (присутствия которых мы ожидаем на выходе), правая — неправильные. Верхняя строка таблицы — положительные (positive) ответы классификатора, нижняя — отрицательные (в нашем случае — отсутствие категории в ответе). Если число всех пар документ — категория равно N , то нетрудно увидеть, что

В общем-то, теперь можно записать требование заказчика в виде (число неправильных ответов равно нулю) и на этом остановиться. Однако на практике таких систем не бывает и анализатор будет, разумеется, работать с ошибками относительно тестовой выборки. Понять процент ошибок нам поможет метрика правильности (accuracy):

В числителе мы видим диагональ матрицы — суммарное число правильных ответов, который делится на общее число вопросов. Например, анализатор, давший 9 правильных ответов из 10 возможных, имеет accuracy 90%.

Метрика F 1

Простым примером неприменимости accuracy-метрики является задача определения обувного бренда. Допустим, мы хотим подсчитать число упоминаний обувных брендов в тексте. Рассмотрим задачу классификации, целью которой будет определить, является ли указанная сущность обувным брендом (Timberland, Columbia, Ted Baker, Ralph Lauren и т.п.). Иначе говоря, мы разбиваем сущности в тексте на два класса: A — Обувной бренд, B — Все остальное.

Теперь рассмотрим вырожденный классификатор, который просто возвращает класс B (Все остальное) для любых сущностей. Для этого классификатора число истинно-положительных ответов будет равно 0. Вообще говоря, давайте подумаем на тему, а часто ли при чтении текста в интернете нам встречаются обувные бренды? Оказывается, как ни странно, что в общем случае 99.9999% слов текста не являются обувными брендами . Построим матрицу распределения ответов для выборки в 100.000:

Вычислим его accuracy, который будет равен 99990 / 100000 = 99.99%! Итак, мы легко построили классификатор, который по сути не делает ничего, однако имеет огромный процент правильных ответов. В то же время совершенно понятно, что задачу определения обувного бренда мы не решили. Дело в том, что правильные сущности в нашем тексте сильно «разбавлены» другими словами, которые для классификации никакого значения не имеют. Учитывая этот пример, вполне понятно желание использовать другие метрики. Например, значение tn явно является «мусорным» — оно вроде как означает правильный ответ, но разрастание tn в итоге сильно «подавляет» вклад tp (который нам важен) в формулу accuracy.

Определим меру точности (P, precision) как:

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

Мера точности, однако, не дает представление о том, все ли правильные ответы вернул классификатор. Для этого существует так называемая мера полноты (R, recall):

Мера полноты характеризует способность классификатора «угадывать» как можно большее число положительных ответов из ожидаемых. Заметим, что ложно-положительные ответы никак не влияют на эту метрику.

Precision и Recall дают довольно исчерпывающую характеристику классификатора, причем «с разных углов». Обычно при построении подобного рода систем приходится все время балансировать между двумя этими метриками. Если вы пытаетесь повысить Recall, делая классификатор более «оптимистичным», это приводит к падению Precision из-за увеличения числа ложно-положительных ответов. Если же вы подкручиваете свой классификатор, делая его более «пессимистичным», например, строже фильтруя результаты, то при росте Precision это вызовет одновременное падение Recall из-за отбраковки какого-то числа правильных ответов. Поэтому удобно для характеристики классификатора использовать одну величину, так называемую метрику F 1:

Фактически это просто среднее гармоническое величин P и R. Метрика F 1 достигает своего максимума 1 (100%), если P = R = 100%.
(нетрудно прикинуть, что для нашего вырожденного классификатора F 1 = 0). Величина F 1 является одной из самых распространенных метрик для подобного рода систем. Именно F 1 мы и будем использовать, чтобы сформулировать пороговое качество нашего анализатора в FRD.

В вычислении F 1 для задачи классификации есть два основных подхода.
- Суммарный F 1 : результаты по всем классам сводим в одну единую таблицу, по которой затем вычисляется метрика F 1 .
- Средний F 1 : для каждого класса формируем свою contingency matrix и свое значение F 1 , затем берем простое арифметическое среднее для всех классов.
Зачем нужен второй способ? Дело в том, что размеры выборки для разных классов могут сильно различаться. Для каких-то классов у нас может быть очень мало примеров, а для каких-то — много. В итоге метрики одного «большого» класса, будучи сведенными в одну общую таблицу, будут «забивать» все остальные. В ситуации, когда мы хотим оценить качество работы системы более-менее равномерно для всех классов, второй вариант подходит лучше.

Обучающая и тестовая выборка

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

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

Мы вычисляем значение F 1 по заданной выборке, которая известна заранее. Эта выборка обычно называется обучающей . Однако мы не знаем, как поведет себя классификатор на тех данных, которые нам неизвестны. Для этих целей обычно используется так называемая тестовая выборка , иногда называемая golden set . Разница между обучающей и тестовой выборкой чисто умозрительная: ведь имея некоторое множество примеров, мы можем разрезать его на обучающую и тестовую выборку как нам угодно. Но для самообучающихся систем формирование правильной обучающей выборки очень критично. Неправильно подобранные примеры могут сильно повлиять на качество работы системы.

Типична ситуация, когда классификатор показывает хороший результат на обучающей выборке и совершенно провальный — на тестовой выборке. Если наш алгоритм классификации основан на машинном обучении (т.е. зависит от обучающей выборки), мы можем оценить его качество по более сложной «плавающей» схеме. Для этого все имеющиеся у нас примеры делим, скажем, на 10 частей. Изымаем первую часть и используем ее для обучения алгоритма; оставшиеся 90% примеров используем как тестовую выборку и вычисляем значение F 1 . Затем изымаем вторую часть и используем в качестве обучающей; получаем другое значение F 1 , и т.д. В итоге мы получили 10 значений F 1 , теперь берем их среднее арифметическое значение, которое и станет окончательным результатом. Повторюсь, что это способ (называемый также cross-fold validation ) имеет смысл только для алгоритмов, основанных на машинном обучении.

Возвращаясь к написанию FRD, замечаем, что у нас ситуация куда хуже. Мы имеем потенциально неограниченный набор входных данных (все веб-страницы интернета) и нет никакого способа оценить контекст страницы, кроме как участие человека . Таким образом, наша выборка может быть сформирована только вручную, причем сильно зависеть от капризов составителя (а решение о том, отнести ли страницу к какой-то категории, принимает человек). Мы можем оценить меру F 1 на известных нам примерах, но никак не можем узнать F 1 для всех страниц интернета . Поэтому для потенциально неограниченных наборах данных (таких, как веб-страницы, коих неисчислимо много), иногда используют «метод тыка» (unsupervised). Для этого случайным образом выбирают определенное число примеров (страниц) и по ним оператор (человек) составляет правильный набор категорий (классов). Затем мы можем испытать классификатор на этих выбранных примерах. Далее, считая, что выбранные нами примеры являются типичными , мы можем приближенно оценить точность алгоритма (Precision). При этом Recall мы оценить не можем (неизвестно, сколько правильных ответов находятся за пределами выбранных нами примеров), следовательно, не можем вычислить и F 1 .

Таким образом, если мы хотим узнать, как ведет себя алгоритм на всех возможных входных данных, самое лучшее, что сможем оценить в этой ситуации — это приближенное значение Precision. Если же все согласны использовать заранее определенную фиксированную выборку, то можно вычислить средние значение F 1 по этой выборке .

В итоге?

А в итоге нам придется сделать следующее:
1. Зафиксировать обучающую выборку. Обучающая выборка будет построена исходя из представлений заказчика о «правильном» контексте.
2. Зафиксировать набор категорий для нашего анализатора. Не можем же мы вычислять F 1 по неопределенному набору классов?
3. Описать требование в виде: Анализатор должен определять контекст с средней величиной F 1 не менее 80%. (например)
4. Объяснить это заказчику.
Как видим, написать FRD на такую систему нелегко (особенно последний пункт), но возможно. Что касается порогового значения F 1 , в таких случаях можно отталкиваться от значений F 1 для похожих задач классификации.