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

Идентификация Борна (и не только Борна)

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

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

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

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




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

Поставим последнюю задачу из примера чуть более формально и героически её решим, позвав на помощь arxiv.org, Python и Keras. Фотографии лица — матрицы из . По двум лицам мы хотим знать вероятность их принадлежности одному человеку. Вероятность — вещественное число от 0 до 1. Значит, мы ищем функцию . Так как на дворе уже 2017 год, искать мы её будем методами машинного обучения. Обучающим множеством, однако, у нас будет не множество пар из определения, а множество фотографий лиц разных людей с метками, кому какое принадлежит — прямо как для задачи классификации. Множества эти эквивалентны, однако со вторым проще работать.

Превосходство Борна

Что важнее всего в решении задач машинного обучения? Думаете, умение искать ответ? Нет, главное — умение этот ответ верифицировать. Функция , возвращающая случайные числа из интервала является вполне корректным решением поставленной задачи, однако на практике она бесполезна. Как это узнать, не прибегая к методу «на глаз»? В задаче классификации мы можем посмотреть accuracy на валидационном множестве — долю правильно классифицированных примеров. Для задачи идентификации такая метрика не применима. Так как же объективно оценить пригодность решения нашей задачи?

Давайте введём понятие target-попытки и imposter-попытки. Первым мы назовём объект для которого известно, что , т.е. объект обладает требуемым свойством с вероятностью 1 (в нашей задаче — пара лиц , принадлежащих одному человеку), а вторым, соответственно, объект такой, что . Соответственно, рассмотрим множества и , которые вместе будут являться нашим валидационным множеством: . Соображения по его выбору абсолютно стандартны, как и для любой задачи машинного обучения — оно должно быть репрезентативно, т.е. отражать всю требуемую вариативность и иметь достаточный размер. Например, если ваша система распознавания лиц предполагает работу в условиях разного освещения, эти условия должны быть представлены в валидационном множестве (как и в обучающем, конечно).

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

Так она выглядит для :


Согласитесь, толку от такого идентификатора немного — в половине случаев он будет угадывать ответ, а в половине — ошибаться.

Такое распределение нам уже больше подходит:


Для target-попыток такая функция будет скорее уверена в их правильности, чем нет.

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


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

Допустим, нашей системе на вход подаётся пара изображений. Она может посчитать для них вероятность того, что это target-попытка. Но требуется от неё однозначный ответ: один и тот же это человек или нет, пускать его на секретный объект или нет. Давайте зададимся некоторым порогом и если , будем отвечать отрицательно, иначе — положительно. Если , система никогда никого не узнает, а если , то любых двух человек станет считать одинаковыми. По графику видно, что наши распределения не разделимы и нельзя подобрать так, чтобы добиться идеальной работы в обоих случаях. Что будет, например, если в примере выше установить ?


В скольких случаях наша система будет ошибаться при target-попытках? Легко посчитать: — количество target-попыток, которые будут неверно классифицированы как imposter-попытки. Аналогично и для последних. А теперь дадим им имена и сделаем не абсолютными, а относительными:

• FRR (False Rejection Rate) — доля неправильно отклонённых target-попыток.
• FAR (False Acceptance Rate) — доля неправильно принятых imposter-попыток.

Давайте теперь зададимся некоторым шагом и посчитаем с ним значения FRR и FAR для точек из интервала и отобразим их на одном графике:


Теперь для любого выбранного расстояния можно сказать, какая доля target-попыток будет отклоняться и какая доля imposter-попыток приниматься. И наоборот, можно выбирать исходя из задачи. Например, для верификации на охраняемом объекте, где важно не пропустить чужака, по понятным причинам требуется , обеспечивающий минимально возможный FAR. Если же вы хотите, чтобы компьютер вас узнавал и желал доброго утра, а по квартире обычно ходите только вы, можно остановиться на низком FRR и достаточно высоком FAR — не случится ничего плохого, если компьютер поздоровается с кем-то, назвав его вашим именем.

Обратите внимание на точку пересечения графиков. Значение в ней называется EER (Equal Error Rate).


Если мы выберем , значения FAR и FRR окажутся равны. EER — тот самый объективный критерий, к которому мы шли. Он позволяет оценить качество идентификации в целом: это средняя ошибка на нашем валидационном множестве. Ещё можно смотреть на FAR при фиксированном FRR и наоборот, но чаще всего в качестве метрики используют именно EER.

В примере выше EER = 0.067. Значит, в среднем 6.7% всех target-попыток будет отклоняться и 6.7% всех imposter-попыток — приниматься.

Ещё одним важным понятием является DET-кривая — зависимость FAR от FRR в логарифмическом масштабе. По её форме легко судить о качестве системы в целом, оценивать какое значение одного критерия можно получить при фиксированном втором, и, что самое главное, сравнивать системы.


ERR здесь — пересечение DET-кривой с прямой .

Наивная реализация на Python (можно более оптимально, если учесть, что FAR и FRR меняются только в точках из ):

import numpy as np

def calc_metrics(targets_scores, imposter_scores):
    min_score = np.minimum(np.min(targets_scores), np.min(imposter_scores))
    max_score = np.maximum(np.max(targets_scores), np.max(imposter_scores))

    n_tars = len(targets_scores)
    n_imps = len(imposter_scores)

    N = 100

    fars = np.zeros((N,))
    frrs = np.zeros((N,))
    dists = np.zeros((N,))

    mink = float('inf')
    eer = 0

    for i, dist in enumerate(np.linspace(min_score, max_score, N)):
        far = len(np.where(imposter_scores > dist)[0]) / n_imps
        frr = len(np.where(targets_scores < dist)[0]) / n_tars
        fars[i] = far
        frrs[i] = frr
        dists[i] = dist

        k = np.abs(far - frr)

        if k < mink:
            mink = k
            eer = (far + frr) / 2

    return eer, fars, frrs, dists

С контролем разобрались: теперь, какую бы функцию мы ни выбрали, можем посчитать для неё FAR, FRR и ERR на валидационном множестве и построить несколько наглядных графиков.

Важно: в задачах идентификации то, что мы выше называли валидационным множеством, принято называть development set (development-множество, devset). Будем придерживаться этого обозначения и в дальнейшем.

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

Подготовка базы

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

• Caltech Faces
• FEI Face Database
• Georgia Tech face database.

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

В полученной таким образом базе оказалось 277 субъектов и ~4000 изображений, в среднем по 14 изображений на человека. Возьмём 5-10% субъектов для development-множества, остальных используем для обучения. Система при обучении должна видеть лишь примеры из второго множества, а проверять её (считать EER) мы будем на первом.

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

Теперь данные необходимо предобработать. Для начала, выделить лица. Сами мы этим заниматься не будем, а используем библиотеку dlib.

import dlib
import numpy as np
from skimage import io

image = io.imread(image_path)
detector = dlib.get_frontal_face_detector()
face_rects = list(detector(image, 1))
face_rect = face_rects[0]

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

Формальная постановка нашей задачи подразумевает, что все лица должны быть одного размера. Удовлетворим это требование, заодно выровняв все лица так, чтобы ключевые точки (глаза, нос, губы) всегда находились в одном и том же месте изображения. Ясно, что такая мера может нам помочь безотносительно выбранного способа обучения и уж точно не навредит. Алгоритм прост:

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

Эталонное положение ключевых точек найдём в примерах к dlib (face_template.npy, скачать здесь).

face_template = np.load(face_template_path)

Для поиска ключевых точек на изображении лица опять-же воспользуемся dlib, используя уже обученную модель, которую можно найти там-же, в примерах (shape_predictor_68_face_landmarks.dat, скачать здесь).

predictor = dlib.shape_predictor(dlib_predictor_path)
points = predictor(image, face_rect)
landmarks = np.array(list(map(lambda p: [p.x, p.y], points.parts())))

Аффинное преобразование однозначно задаётся тремя точками:

INNER_EYES_AND_BOTTOM_LIP = [39, 42, 57]

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


Найдём его:

proper_landmarks = 227 * face_template[INNER_EYES_AND_BOTTOM_LIP]
current_landmarks = landmarks[INNER_EYES_AND_BOTTOM_LIP]

A = np.hstack([current_landmarks, np.ones((3, 1))]).astype(np.float64)
B = np.hstack([proper_landmarks, np.ones((3, 1))]).astype(np.float64)
T = np.linalg.solve(A, B).T

И применим к изображению с помощью библиотеки scipy-image:

import skimage.transform as tr

wrapped = tr.warp(
    image,
    tr.AffineTransform(T).inverse,
    output_shape=(227, 227),
    order=3,
    mode='constant',
    cval=0,
    clip=True,
    preserve_range=True
)

wrapped /= 255.0

Полный код препроцессинга, обёрнутый в удобный api, можно найти в файле preprocessing.py.

Финальным аккордом подготовки данных станет нормализация: посчитаем среднее и стандартное отклонение по базе обучения и нормируем каждое изображение на них. Не забудем и про development-множество. Код смотрите здесь.



Собранные, разделённые, выровненные и нормированные данные можно скачать здесь.

Ультиматум Борна

Данные нашли и подготовили, с методикой тестирования разобрались. Полдела сделано, осталось самое лёгкое — найти , решающую задачу с хорошим EER. Давайте сразу определимся, что EER = 10% нас вполне устроит для такой учебной задачи. На самом деле, такая система даже сможет быть использована в простых приложениях вроде поиска одинаковых лиц на двух фотографиях.

Монетка

Начнём поиски с того самого примера плохой функции . Для каждой пары фотографий из development-множества получим случайное значение, построим по ним DET-кривую и найдём EER.



C EER = 49.5% такой идентификатор не лучше монетки, которую бы мы подбрасывали при принятии каждого решения. Конечено, это понятно и без графиков, но наша цель — научиться решать задачи идентификации и уметь объективно оценивать любые решения, даже заведомо плохие. К тому же, будет от чего оттолкнуться.

Расстояние

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

Возьмём, например, косинусную дистанцию:



И проделаем все те же самые операции над development-множеством:

dev_x = np.load('data/dev_x.npy')
protocol = np.load('data/dev_protocol.npy')

dev_x = dev_x.mean(axis=3).reshape(dev_x.shape[0], -1)
dev_x /= np.linalg.norm(dev_x, axis=1)[:, np.newaxis]
scores = dev_x @ dev_x.T

tsc, isc = scores[protocol], scores[np.logical_not(protocol)]

eer, fars, frrs, dists = calc_metrics(tsc, isc)

Получим такую DET-кривую:


EER уменьшился на 16% и стал равен 34.18%. Лучше, но всё-ещё не применимо. Конечно, ведь мы до сих пор лишь подбирали функцию, никак не используя обучающее множество и методы машинного обучения. Однако, идея с расстоянием здравая: давайте его оставим и представим нашу функцию в виде


где — косинусная дистанция, а — некоторая функция, которую мы назовём embedder, а результаты её работы из пространства — embeddings. Она «встраивает» наши изображения в некоторое пространство другой (не обязательно меньшей) размерности, учитывая апостериорный опыт, добытый из обучающего множества.

CNN

Отлично, мы с вами только-что ещё сильнее упростили задачу. Осталось лишь найти хорошую функцию , все остальные части системы уже на месте. Не будем ходить вокруг да около — все мы знаем, что на текущий момент нет модели, лучше справляющейся с изображениями, чем CNN (Convolutional Neural Networks). Давайте построим конволюционную сеть какой-нибудь не очень сложной архитектуры, например такой:




И обучим её решать классическую задачу классификации на нашем обучающем множестве: определять, кому из 250 субъектов принадлежит фотография лица. Такую простую задачу решать умеют все, в keras для этого помимо приведённого выше кода понадобится ещё строчек 5-6. Скажу лишь, что для базы обучения, описанной в этой статье, жизненно необходимо применить аугментацию, иначе данных не хватит, чтобы достичь хороших результатов.

Спрашиваете, при чём здесь задача классификации и как нам поможет её решение? Правильно делаете! Чтобы описанные далее действия имели смысл, необходимо сделать очень важное предположение: если сеть научится хорошо решать задачу классификации в закрытом множестве, то на предпоследнем слое размерностью 256 будет сосредоточена вся важная информация об изображении лица, даже если субъекта не было в обучающем множестве.

Такая техника извлечения характеристик низкой размерности из последних слоёв обученной сети широко распространена и носит название bottleneck. Кстати, код для работы с bottleneck в keras находится по ссылке.

Сеть обучили, 256-мерные признаки из development-множества извлекли. Смотрим на DET-кривую:


Предположение оказалось верным, уменьшили EER ещё на 13%, достигнув результата 21.6%. В два раза лучше, чем подбрасывание монетки. А можно ещё лучше? Конечно, можно собрать базу побольше и повариативнее, построить более глубокую CNN, применить различные методы регуляризации… Но мы с вами рассматриваем концептуальные подходы, качественные. А количество всегда можно нарастить. Ещё один козырь в рукаве у меня всё-таки остался, но перед тем как выложить его на стол, придётся немного отвлечься.

Эволюция Борна

Ключ к улучшению наших результатов кроется в осознании того факта, что оптимизируя можно использовать информацию не только из обучающего множества, но и информацию о функции . Действительно, давайте зафиксируем и будем обучать исходя из априорного знания о том, как затем embedding-и будут использованы для получения score. Впервые такой подход предложили ребята из Google в работе FaceNet: A Unified Embedding for Face Recognition and Clustering.

Подход, предложенный ими, получил название TDE (Triplet Distance Embedding) и состоял в следующем: давайте построим как сеть из исходного пространства в пространство embedding-ов без необходимости решать промежуточную задачу классификации, зафиксируем как евклидово расстояние и учтём его в loss-функции. Каким образом? Вполне интуитивным: мы хотим, чтобы вектора одного субъекта были в целевом пространстве как можно ближе к друг другу и при этом, дальше от векторов других субъектов.



Обучать такую сеть было предложено с помощью троек , где (anchor) и (positive) принадлежат одному субъекту, а (negative) — другому. Для всех трёх векторов построим embedding-и , и . Заранее зададимся некоторым параметром . Будем считать, что тройка хорошая, если выполняется соотношение



которое означает, что для данного anchor-а между сферами, на которых лежит positive и negative имеется зазор . Если такое соотношение выполняется для всех возможных троек из обучающего множества, мы идеально разделили данные. А обучать сеть имеет смысл только на тех тройках, для которых это неравенство нарушается. Исходя из неравенства, можно построить loss-функцию для сети :


Используя такой подход, авторы уменьшили ошибку на 30% на датасетах Labeled Faces in the Wild и YouTube Faces DB, что, несомненно, очень круто. Однако, есть у подхода и проблемы:

• требуется очень много данных;
• медленное обучение;
• дополнительный параметр , который не ясно как выбирать;
• во многих случаях (в основном при малом количестве данных) проявляет себя хуже, чем softmax + bottleneck.

Тут на сцену выходит TPE (Triplet Probabilistic Embedding) — подход, описанный в работе Triplet Probabilistic Embedding for Face Verification and Clustering.

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



Оно проще исходного и легко интерпретируется: мы хотим, чтобы самый близкий к нам negative-пример лежал дальше, чем самый далёкий от нас positive-пример, но между ними не обязательно должен быть какой-либо зазор. Благодаря тому, что мы не прекращаем обновлять сеть, когда расстояние достигнуто, группы embedding-ов могут быть разнесены в пространстве ещё лучше.

Можем посчитать вероятность того, что триплет удовлетворяет приведённому неравенству:


Разделим на :


Будем максимизировать логарифм вероятности, поэтому loss-функция будет выглядеть следующим образом:


А в качестве функции авторы предлагают использовать не гигантскую CNN, а простую матрицу: и учить её на bottleneck признаках, уже полученных нами. Вот результаты, которых достигли авторы работы:


Как видно, такой подход работает лучше оригинального и имеет множество плюсов:

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

Этот подход мы с вами и используем. Нужно для этого всего 20 строчек кода:

def triplet_loss(y_true, y_pred):
    return -K.mean(K.log(K.sigmoid(y_pred)))


def triplet_merge(inputs):
    a, p, n = inputs

    return K.sum(a * (p - n), axis=1)


def triplet_merge_shape(input_shapes):
    return (input_shapes[0][0], 1)

a = Input(shape=(n_in,))
p = Input(shape=(n_in,))
n = Input(shape=(n_in,))

base_model = Sequential()
base_model.add(Dense(n_out, input_dim=n_in, bias=False, weights=[W_pca], activation='linear'))
base_model.add(Lambda(lambda x: K.l2_normalize(x, axis=1)))

a_emb = base_model(a)
p_emb = base_model(p)
n_emb = base_model(n)

e = merge([a_emb, p_emb, n_emb], mode=triplet_merge, output_shape=triplet_merge_shape)

model = Model(input=[a, p, n], output=e)
predict = Model(input=a, output=a_emb)
model.compile(loss=triplet_loss, optimizer='rmsprop')

Если вы захотите использовать TPE в своих проектах, не поленитесь прочитать оригинальные работы, так как я не осветил самый главный вопрос обучения триплетами — вопрос их отбора. Для нашей небольшой задачи хватит и случайного выбора, однако это скорее исключение, чем правило.

Обучим TPE на наших bottleneck-ах и взглянем на DET-кривую последний на сегодня раз:


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

Сравнение DET-кривых всех рассмотренных методов:


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


С приложением можно ознакомиться на GitHub.

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

Литература

• Различные задачи машинного обучения
• FaceNet: A Unified Embedding for Face Recognition and Clustering
• Triplet Probabilistic Embedding for Face Verification and Clustering