«

»

May 03

05 – машинное обучение для классификации изображений

Машинное обучение – для компьютерного зрения

компьютерное зрение - как научить компьютер думать

компьютерное зрение – как научить компьютер думать

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

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

Машинное обучение это когда компьютеру скормили учебную выборку данных (положительные и отрицательные примеры), а он на их основе научился работать с новыми данными(не входящими в учебную выборку). Конкретный объект можно описать с помощью признаков и характеристик, если проанализировать несколько объектов одного класса – можно выделить их общие признаки, и при изучении нового объекта отталкиваться от нашего представления о базовом классе, для того чтобы понять относится ли новый объект к известному нам классу. Например, мы хотим распознавать на любом изображении человека. Тогда нам нужна учебная выборка содержащая и не содержащая людей. Люди должны быть разные – высокие, толстые, в разных одеждах и позах. При обработке учебной выборки формируется классификатор содержащий описание признаков людей, который, при применении к новому изображению, с некоторой долей вероятности (проценту совпавших признаков) будет распознавать или не распознавать людей.

Сколько всего объектов для распознавания? Примерно это число существительных плюс число объектов, описываемых словосочетаниями, не включая абстрактные, не материальные сущности + .. – … Словом много их. На практике, нам не нужен доскональный анализ каждой букашки на изображении – в силу приземленности, нас интересует сугубо практичная информация, навроде представлен ли на изображении конкретный объект. Или, что несколько более обобщенно – относится ли изображение к заданному классу – содержит ли он объект(ы) определенного типа (пейзаж/таракашку/атомный ледокол). Класс (категория) содержит информацию о том, как мы можем взаимодействовать с объектом (кошку вполне можно погладить за ухом, от тигра надо тикать). С другой стороны то, как мы можем взаимодействовать с объектом – функции объекта – зависят от наблюдателя – в кошке при виде мышки проснется охотник, в женщине – паника.

В идеальном мире разделение по категориям было бы простым – либо объект входит в данную категорию, либо нет: на основе набора свойств общих для всех элементов из категории. Это так называемые жесткие идеальные категории. На практике не все так просто – если кто-то любит лакомиться кактусами, это еще не повод заносить их в класс “еда”. Потому принято использовать так называемые естественные категории (Natural Categories by Rosch). В них каждый класс определяется наилучшими примерами-прототипами и, при сравнении неизвестного класса, можем задать некоторую степень (вероятность) соответствия категории. Нечеткие правила гораздо более гибкие и больше подходят для реальных задач классификации.

В психологии (ну, вы помните про кучу смежных отраслей, да?) используется термин каноническая перспектива (“Когнитивная психология”, Роберт Солсо) – такой эталонный экземпляр класса, по которому для человека проще всего опознать предмет. Скажут вам класс “кошка”, а на ум как-то сам собой приходит какой-нибудь Барсик, с расцарапанной по весне разбойничей мордой. Одна из упрощенных моделей мышления человека – feed-forward architecture – когда нет априорной информации о наблюдаемой сцене (человек без понятия что ему должны показать). При этом не обязательна обратная связь – т.е. никто не уточнит что качан капусты на мяч футбольный смахивает весьма отдаленно, хотя формой схожи. Хороший классификатор должен обеспечивать эквивалентные возможности.

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

Основные методы категоризация изображений:
Knn – метод ближайших соседей
и методы на основе машинного обучения
random forest – случайные леса
SVM – метод опорных векторов
boosting
neural networks – нейронные сети

Внимание – далее все тоже самое только оно расписано чуть более подробно с использованием разнузданной лексики из теории вероятности.

У всех объектов заданного класса есть некоторые схожие признаки. Распределение этих признаков (пусть неизвестное, пусть сложное) – одинаковое для всех всех объектов внутри класса. Имея некоторый конечный набор данных мы сможем оценить вероятностные характеристики – построить правила – некоторую функцию. Функция эта будет получать на вход характеристики важные для ответа на вопрос “Является ли эта штука объектом класса А?” – т.е. это классическая для тервера вероятность чего-то при условии таком-то. Пока, для упрощения, считаем что характеристики вычисляются на основе взаиморасположения особых точек.

Разновидности классификаций:

1) бинарная классификация – рассматриваем 2 класса

2) многоклассовая классификация – классов больше двух

3) регрессия – классов вообще нет, есть различные значения функции (определение возраста, веса)

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

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

Общая схема обучения (Features -> Coding -> Spatial pooling):
Для каждого изображения
– вычисляем признаки изображения (например по-пиксельно)
– разбиваем их на несколько категорий-кластеров (для усиления влияния на непосвященных можно воспользоваться термином “квантование признаков”, в случае неравномерного распределения признаков – в большинстве случае – лучше использовать адаптивное квантование с помощью K-средних)
– определяем область для вычисления (например, с помощью пространственной пирамиды – изображения разбиваем на области, и вычисляем признаки отдельно для каждой области, причем берем несколько уровней разделения – на 4 на 16 и т.п. частей)
– вычисляем признаки – агрегируем (гистограммы, мешок слов)
Используем один из методов категоризации на полученном наборе мешков слов, для формирования классификатора.

Гистограмму для описания распределения признаков можно строить по регулярной сетке или с помощью кластеризации (адаптивно). Используются различные подходы к ее вычислению: гистограммы цветов/градиентов/разреженных визуальных слов/ плотных визуальных слов. Каждый вид признаков можно рассчитывать по всему изображению, а можно по отдельной области. Часто используется пирамида разбиений из трех уровней (1+4+16 гистограммы).

Для сравнения гистограмм используются: пересечение гистограммы (histogram intersection), расстояние Манхэтена, L1 distance, расстояние хи-квадрат и т.п.

составляем лицо медведя на основе визуальных "слов" из словаря

составляем лицо медведя на основе визуальных “слов” из словаря

Один из метод агрегирования – мешок слов. Принимаем часто повторяющийся фрагмент изображения за визуальное слово. В конкретном изображении может встречать ровно один раз, несколько или ни одного раза. На их основе составляем словарь – базовый набор из фрагментов которые часто повторяются в коллекции изображений. Часто используется совместно и разреженная и плотная версия представления слов (Dense words PhowGray PhowColor – попросту говоря с перекрытиями или без). При построении словаря актуальной становится проблема золотой середины – чтобы слов было не слишком много (опять переобучение), но и не слишком мало (когда словами нельзя описать все признаки) – методы решения – использование деревьев словарей, хеширования.

Оценка качества работы классификатора

Эмпирический риск – отражает уровень ошибки тренировки – средняя вероятность ошибки, цель обучения классификатора – минимизация эмпирического риска. Во время тренировки руководствуемся правилом бритвы Окама (в науке это правда называется “Принцип структурной минимизации риска”) – и выбираем наиболее простую модель из тех, что достаточно точно описывают объект-категорию.

Для проверки качества можно использовать метод скользящего контроля (Cross validation)

Различают ошибки первого и второго рода – ошибки классифицированные и пропущенные. Их любят отображать на ROC-кривой – отражающей зависимость чувствительности и ошбки второго рода (ROC – receiver operating characteristic).

Если попробовать схематично описать процесс тренировки то получатся как то так: разделяем доступную нам выборку данных на несколько частей. Поочередно используем одну часть для проверки работы классификатора – контроля, а остальные для тренировки. Каждый вид объекта – прецедент – будет присутствовать минимум один раз в контрольный выборке, однако обучающие выборки будут сильно перекрываться и оценка может быть смещена. Альтернативный вариант – обучить на каждую часть свой классификатор и с помощью кросс-валидации выбрать лучший.

Виды классификаторов
1) Линейный классификатор.
Обладая достаточно развитым абстрактным мышлением можно представить себе множество признаков как набор точек в пространстве. Классификатор при таком представлении будет гиперплоскостью (линейной функцией) разделяющий множество признаков. Нас интересует какая гиперплоскость лучше – какой классификатор лучше подойдет для задачи категоризации объекта по признакам. Сухим языком эта задача формулируется как поиск гиперплоскости, максимизирующую отступ между положительными и отрицательными примерами (можно также учитывать влияние шума – добавив параметр минимизации доли признаков ошибочно отнесенных к “не своей” группе). На этот вопрос можно ответить с помощью метода опорных векторов (SVM – support vector machine).

2) Не-линейные.
Да где вы видели в реальном мире ситуацию, когда применимо линейное разделение? Однако уж больно подкупает кажущаяся простота линейного подхода. И был придуман простой способ избежать ужасов хитровыдуманных функций. Исходное пространство параметров отображается на многомерное пространство признаков (feature space), где обучающаяся выборка будет линейно разделима. (представьте что у вас на листке – двухмерном пространстве – есть набор из взаимнопересекающихся фигур, которые на этом листке никак не разделяются, но если вы перенесете этот же набор в трехмерное пространство все получится). Для упрощения вычислений, вычисляется ядровая функция – kernel trick, если она неотрицательно определена (Mercer’s condition) – тогда мы можем построить нелинейную решающую функцию в исходном пространстве.

Простейший пример ядра это полиномиальное.
1 выбрать признаки для изображения \мешок слов
2 выбрать ядро для этого вектор признака
3 вычслить матрицу значений ядра для каждой пары примеров из обучающей выборки
4 матрицу грузим в библиотеку SVM для получения весов и опорных векторов
5 во время вывода вычислить значения ядра для тест образца и каждого опорного вектора
и взять взвешенную сумму для получения значений решающей функции.

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

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

2 comments

  1. Samore

    Былобы хорошо если бы Вы раставили бы ссылки на литературу. Я понимаю что это именно ваше мнение но может есть у вас какая то литература что сподвигла Вас на написание этой заметки. Былобы интересно

  2. Артём

    Весьма интересно и познавательно! “т.е. будем получать ответы вида – на картинке собачка, а не соседский тузик пакостит в моем палисаднике” – посмеялся вдоволь 😀

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>