Поиск по сайту Поиск

Стэнфордский курс: лекция 2. Классификация изображений

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

Ссылка на предыдущую лекцию

Несколько слов о классификации

Как же работает классификация? Когда ваша система получает входное изображение, ей уже известен фиксированный набор категорий или меток. Это могут быть любые объекты: «кошка», «собака», «самолёт», «грузовик» и так далее. Компьютер должен посмотреть на изображение и назначить ему одну из меток. 


Классификация

Со стороны задача выглядит несложной, поскольку большая часть нашей зрительной системы запрограммирована на распознавание объектов. Но для машины это не так-то просто.

Проблема классификации

Когда компьютер смотрит на изображение, то не видит целостное представление кошки или любого другого объекта. Он видит лишь гигантскую сетку чисел. Например, если размер изображения 800 на 600 и каждый пиксель представлен тремя числами для красного, зелёного и синего каналов, то получится сетка из 800х600х3 = 1,440,000 чисел. Очень трудно выделить из них какой-то конкретный предмет, представленный на фотографии. 

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

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

Пытаемся решить проблему

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

Но явные наборы правил работают не очень хорошо: любое отклонение может всё сломать, а для новых объектов придётся создавать новые условия. Поэтому такой подход не является масштабируемым.

Подход, основанный на данных

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

Итак, вместо одной функции, которая просто распознаёт объект на входном изображении, мы получили две: первая называется «обучение» — это процесс обработки изображений и создания модели. Вторая функция — «прогноз» — распознаёт новые фотографии. Вместе они составляют основу для свёрточных нейронных сетей и глубокого обучения в целом. 

Метод ближайшего соседа

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

Возьмём набор данных CIFAR-10, содержащий 10 различных классов и около 50000 обучающих и 10000 тестовых образцов. 

Так на нём работает классификатор ближайшего соседа:

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

Как это работает? 

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

Реализация метода ближайшего соседа на Python:

Если в обучающем наборе содержится N примеров, то обучение всегда будет выполняться за постоянное время O(1), а прогнозирование — за линейное время O(N), поскольку тестовое изображение сравнивается с каждым обучающим образцом. «О» здесь означает временную сложность алгоритма

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

Что именно делает алгоритм ближайшего соседа? На рисунке ниже показаны так называемые области принятия решений классификатора. 

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

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

Метод k-ближайших соседей

Вместо того, чтобы искать одно похожее изображение, мы будем искать k ближайших соседей в соответствии с метрикой расстояния. После этого проведём голосование по каждому соседу и спрогнозируем метку согласно большинству голосов. Здесь показан тот же набор точек с числом соседей k=1, k=3 и k=5.

Можно увидеть, что жёлтая точка внутри зелёного кластера больше не создаёт область вокруг себя, а граница между красным и синим классами становится более гладкой. Как правило, для классификации используется значение k > 1. Белые регионы здесь означают области, в которых не найдено ни одного ближайшего соседа.

Евклидово расстояние

Расстояние L2 (евклидово) тоже часто используется в задачах классификации. Оно выглядит как корень из суммы квадратов разности между цветами пикселей:

Метрики расстояния делают разные предположения об ожидаемой геометрии или топологии пространства. На рисунке видно, что L1 формирует квадратную область, тогда как L2 создаёт окружность. При повороте системы координат евклидово расстояние не изменится, а манхэттенское выдаст уже другой результат. Этот пространственный эффект важно учитывать и выбирать метрику в соответствии с исходной задачей. 

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

Гиперпараметры

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

Разберёмся, что такое «лучше всего». 

Идея 1. Подобрать такие параметры, которые дадут самую высокую точность на обучающих данных.

И это очень плохая идея. Никогда не делайте так. В случае с методом ближайших соседей при k=1 достигается почти идеальная точность во время обучения, но с тестовыми данными алгоритм справляется крайне плохо. Это явление называется «переобучение».

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

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

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

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

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

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

После перекрёстной проверки вы получите график, который выглядит примерно так:

На оси X показано значение k (число соседей), а на оси Y — точность классификатора. По графику можно оценить эффективность модели в зависимости от гиперпараметров, В этом случае наибольшая точность достигается при k≈7.

Теперь я могу классифицировать изображения с котиками?

К сожалению, нет. На самом деле метод k-ближайших соседей никогда не применяется к фотографиям, потому что:

— очень медленно работает с тестовыми данными

— метрика расстояний между цветами пикселей не говорит о сходстве изображений.

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

Ещё одна проблема — так называемое «проклятие размерности», связанное с экспоненциальным возрастанием количества данных из-за увеличения размерности пространства.

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

Линейная классификация

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

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

Вернёмся к набору данных CIFAR-10. Чтобы классифицировать изображения, мы создадим простую параметрическую модель из двух компонент. Первая — входные данные, обычно обозначающиеся как X, и вторая — набор параметров или весов W. Теперь запишем некоторую функцию, которая принимает данные X и параметры W, а затем выдаёт 10 чисел, описывающих оценки для каждой из 10 категорий в CIFAR-10.

Правильно работающая модель в примере выше выдаст наибольшую оценку для класса кошки.

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

Как же получить функцию, объединяющую в себе веса и данные? Самый простой способ — просто перемножить их. Это и будет линейный классификатор: fx,W=Wx.

Иногда в функцию добавляется элемент смещения b — это линейный вектор, размер которого равен числу классов (в нашем случае 10). Он не взаимодействует с обучающими данными и выдаёт независимые предположения для классов. Например, если в наборе гораздо больше изображений с кошками, чем с собаками, то соответствующие классу кошек элементы вектора смещения будут выше остальных. Функция классификатора со смещением имеет вид: fx,W=Wx+b.

Интерпретация линейного классификатора

Рассмотрим простое изображение 2х2. Линейный классификатор растягивает его в вектор-столбец с четырьмя элементами. Здесь мы используем три класса: «кошка», «собака» и «корабль», поэтому весовая матрица будет иметь размерность 4х3. Вектор смещения из трёх элементов создаёт независимые условия для каждой категории:

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

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

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

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

Но такое разделение между классами возможно далеко не всегда.

Проблемы 

Приведём примеры данных, на которых линейный классификатор потерпит неудачу.

Предположим, что у нас есть датасет с двумя классами, в тривиальном случае — «синий» и «красный». «Синий» означает нечётное количество пикселей на изображении, а «красный» — чётное. Если мы попробуем изобразить эти области принятия решений на плоскости, то получим следующую картину:

Видим, что синий и красный классы занимают противоположные квадранты, которые нельзя разделить одной прямой линией. Это называется проблемой паритета — когда два или более признаков равны по каким-либо параметрам. 

Ещё одна непростая задача — явление мультимодальности, встречающееся в неравномерно распределённых данных. Например, фотографии животных могут изображать их с разных сторон, как в примере шаблона для класса «лошадь»:

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

Несмотря на возникающие проблемы, линейная классификация — простой алгоритм, который легко интерпретировать и реализовать.

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

Следующие лекции (список будет дополняться по мере появления материалов):

Лекция 3. Функция потерь и оптимизация
Лекция 4. Введение в нейронные сети
Лекция 5. Свёрточные нейронные сети
Лекция 6. Обучение нейросетей, часть 1
Лекция 7. Обучение нейросетей, часть 2

С оригинальной лекцией можно ознакомиться на YouTube.

7 советов для работы с небольшими данными

7 советов для работы с небольшими данными

В современном мире считается, что Big Data — ключ к созданию успешных проектов машинного обучения. Но проблема в том, что...
Read More
Квантовые нейронные сети на процессорах будущего

Квантовые нейронные сети на процессорах будущего

Законы квантовой механики в теории позволяют создать новый тип вычислительных машин, способных решать сверхпроизводительные задачи, недоступные даже самым мощным современным...
Read More
Стэнфордский курс: лекция 7. Обучение нейросетей, часть 2

Стэнфордский курс: лекция 7. Обучение нейросетей, часть 2

В шестой лекции мы начали рассказывать про обучение нейросетей: выяснили, как выбрать функцию активации, подготавливать данные, настраивать параметры и следить...
Read More
Нейросеть распознаёт узор вязания по фото

Нейросеть распознаёт узор вязания по фото

Автоматизированным производством сегодня уже никого не удивишь. Но мы попробуем. Один из наиболее необычных примеров автоматических устройств — вязальные машины,...
Read More
Бариста, учитель и работник типографии: кем были сотрудники REG.RU до того, как стали айтишниками

Бариста, учитель и работник типографии: кем были сотрудники REG.RU до того, как стали айтишниками

Сегодня, 30 сентября, День Интернета в России. В честь этой даты мы расскажем семь историй о том, как сотрудники REG.RU...
Read More
Чек-лист, который заряжен на защиту домена

Чек-лист, который заряжен на защиту домена

Время от времени мы сталкиваемся со случаями, когда мошенники уводят домены наших клиентов. Происходит это по самым разным причинам: от...
Read More
Методы распознавания радужной оболочки глаз. Часть 1

Методы распознавания радужной оболочки глаз. Часть 1

Не так давно идентификация людей по радужной оболочке глаз казалась фантастической технологией, использующейся только для защиты суперсекретных военных и правительственных...
Read More
Стэнфордский курс: лекция 6. Обучение нейросетей, часть 1

Стэнфордский курс: лекция 6. Обучение нейросетей, часть 1

В прошлый раз мы обсудили историю возникновения свёрточных архитектур, а также узнали об их устройстве и широких возможностях применения. В...
Read More
Три слова, которые поймут только айтишники

Три слова, которые поймут только айтишники

Если вы не разработчик, но работаете в IT-компании, или в вашем окружении есть программисты, то, скорее всего, часто слышите странные...
Read More
Customer development: почему при выборе идеи нужно учитывать мнение клиентов

Customer development: почему при выборе идеи нужно учитывать мнение клиентов

Вместе с менеджером по продуктам REG.RU Никитой Атучиным разбираем, почему MVP — не всегда хорошее решение для старта бизнеса. Если вы...
Read More