Устойчивость

Сортировка выбором

06.07.2020 02:17:13 |

Автор: admin

Всем привет. Эту статью я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.

Введение

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

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

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

Сортировка выбором

Одной из простейших сортировок является сортировка выбором.

Описание алгоритма

Сортировка массива выбором осуществляется так: массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы находим минимум в неотсортированной части массива и меняем местами этот минимум с первым элементом неотсортированной части массива. После чего мы увеличиваем длину отсортированной части массива на единицу. Пример осуществления одной итерации представлен ниже:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void choiseSortFunction(double A[], size_t N){    for(size_t tmp_min_index = 0; tmp_min_index < N;                                  tmp_min_index++) {        //ищем минимум        for(size_t k = tmp_min_index + 1; k < N; k++) {            if (A[k] < A[tmp_min_index]) {                double min_value = A[k];                A[k] = A[tmp_min_index];                A[tmp_min_index] = min_value;            }        }    }}

Анализ

Предлагаю проанализировать данный алгоритм. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. На первой итерации внешнего цикла имеют место (n 1) итераций внутреннего цикла. На второй итерации внешнего цикла (n 2) итерации внутреннего цикла. Продолжая это рассуждение и далее, мы приходим к следующему:

$display$

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

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

$display$

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

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

Двусторонняя сортировка выбором

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

Рекурсивная сортировка выбором

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

public static int findMin(int[] array, int index){    int min = index - 1;    if(index < array.length - 1) min = findMin(array, index + 1);    if(array[index] < array[min]) min = index;    return min;}  public static void selectionSort(int[] array){    selectionSort(array, 0);}  public static void selectionSort(int[] array, int left){    if (left < array.length - 1) {        swap(array, left, findMin(array, left));        selectionSort(array, left+1);    }}  public static void swap(int[] array, int index1, int index2) {    int temp = array[index1];    array[index1] = array[index2];    array[index2] = temp;}

Итоги

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

Если вы хотите подробнее узнать о курсе, приглашаю всех на бесплатный вебинар, который пройдет уже 10 июля.

Подробнее..

Категории: Программирование , Алгоритмы , Высокая производительность , Промышленное программирование , Блог компании otus. онлайн-образование , Собеседование , Сортировка , Структуры , Данных , Линейная , Квадратичная , Устойчивость , Поразрядная

Сортировка вставками

09.07.2020 12:23:49 |

Автор: admin

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.

Введение

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

Сортировка вставками

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

Описание алгоритма

Сортировка массива вставками осуществляется так: также как и в случае сортировки выбором массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы берем первый элемент неотсортированной части массива и осуществляем с ним следующую операцию: пока наш элемент строго меньше чем предыдущий меняем их местами. После чего увеличиваем длину отсортированной части массива на единицу. Таким образом путем последовательного перемещения изучаемого элемента мы добиваемся того, чтобы он встал на свое место. Пример осуществления одной итерации представлен ниже:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void insertionSortFunction(double array[], int size) {    int i, j, temp;    // i представляет длину отсортированной части массива, начинаем с 1, потому что один элемент сам по себе считается упорядоченным    for (i = 1; i < size; i++) {        temp = array[i];        for (j = i - 1; j >= 0; j--) {            if (array[j] < temp) {                break;            }              array[j + 1] = array[j];            array[j] = temp;        }    }}

Анализ

Предлагаю проанализировать данный алгоритм.

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

$display$

.

Со временем все несколько интереснее. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. Но количество итераций внутреннего цикла зависит от того, насколько хорошо упорядочены (или не упорядочены) элементы сортируемого массива. Для осуществления анализа необходимо посмотреть несколько случаев.

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

$display$

Таким образом, сортировка осуществляется за линейное время.

В худшем случае число итераций предполагается наибольшим, то есть break никогда не срабатывает. На первой итерации внешнего цикла осуществляется одна итерация внутреннего цикла. На второй итерации внешнего цикла осуществляется 2 итерации внутреннего цикла. Продолжая рассуждение дальше, можно прийти к тому, что на последней ((n 1) ой) итерации внешнего цикла выполниться (n 1) итерация внутреннего цикла. Получаем:

$display$

Для осуществления вычислений мы воспользовались свойствами О нотации и формулой суммы арифметической прогрессии.

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

. Предполагается, что i это номер итерации внешнего цикла. Теперь для подсчета асимптотики необходимо вычислить

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

.

Если подводить итоги, то асимптотика алгоритма по памяти

$display$

по времени в лучшем случае

$display$

и в среднем и в худшем случаях

$display$

Поэтому данную сортировку относят к классу квадратичных сортировок.

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

Итоги

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

$display$

упорядоченность объема данных.

Узнать о курсе подробнее.

Подробнее..

Быстрая сортировка

25.10.2020 18:16:57 |

Автор: admin

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: Три алгоритма поиска шаблона в тексте.

Введение

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

Быстрая сортировка

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

Описание алгоритма

Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r n, где по традиции n обозначает длину массива.

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

Реализация partiion'а:

partition(l, r):

pivot = a[random(l ... r - 1)]

m = l

for i = l ... r - 1:

if a[i] < pivot:

swap(a[i], a[m])

m++

return m

Пивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учатка, либо выбирать его каким-то умным образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition O(n), где n = r l длина участка.

Теперь используем partition для реализации сортировки:

Реализация partiion'а:

sort(l, r):

if r - l = 1:

return

m = partition(l, r)

sort(l, m)

sort(m, r)

Крайний случай массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.

Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?

При написании partition мы сделали допущение все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части (< pivot, = pivot, > pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.

Анализ

Предлагаю проанализировать данный алгоритм.

Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 a) * n, потому что пивот разделил элемент на доли.

В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).

В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n 1. То есть: T(n) =n + T(1) + T(n 1) = n + O(1) + T(n 1) = n + O(1) + (n 1 + O(1) + T(n 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.

В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).

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

Подробнее..

Исследование устойчивости сверточных нейросетей. Часть 1 Теория

12.08.2020 18:08:51 |

Автор: admin

Если Вам интересно разобраться, насколько современные (прежде всего, сверточные) нейросети устойчивы, насколько легко можно менять их выход небольшим искажением входных данных, а также возможно ли это делать на уровне реальных (физических) атрибутов объектов перед их съемкой на (фото)видеокамеру милости просим под кат!

Введение в сверточные нейронные сети

Начиная с 1943 года, когда впервые была предложена математическая формализация МакКалоком и Питтсом понятия искусственного нейрона, нейросети становились:

Объемнее (содержали больше параметров),
Глубже (содержали больше блоков вычислений),
Лучше! (более правильно решали поставленные перед ними задачи)

Image credit

arxiv.org/abs/1409.4842

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

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

Как сейчас соотносится качество распознавания человеком и СНС для известных баз данных?
Насколько устойчивы СНС по отношению к входным данным? Легко ли их сломать?

Прогресс в сверточных нейронных сетях

Для ответа на первый вопрос обратимся к двум популярным базам данных изображений ImageNet (1000-классовая база данных изображений) и Labeled Faces in the Wild (LFW) (база данных лиц).

Примеры изображений

ImageNet:

LFW:

Итак, классификация на ImageNet:

Top-5 ошибка (вероятность того, что правильный класс не будет в 5 наиболее вероятных) для человека: 5.1% (пруф в блоге Karpathy)
Top-5 ошибка для СНС: 2.0% (по крайней мере, по состоянию на конец прошлого года; сейчас, наверняка, уже ближе к проценту подбираются или даже меньше. В любом случае, можно сослаться для порядка на статью "Fixing the train-test resolution discrepancy")

А вот верификация (проверка, что пара фотографий принадлежат одному человеку) на LFW:

Ошибка верификации для человека: 2.47% (см. пруф в статье "Attribute and simile classifiers for face verification")
Ошибка верификации для СНС: 0.17% (классическая работа по распознаванию лиц "Arcface: Additive angular margin loss for deep face recognition")

Можно было бы после такого сделать такой вывод:

Image credit

spectrum.ieee.org

(Не)устойчивость сверточных нейронных сетей

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

Например, результат классификации с "панды" меняется на "гиббона" при внесении крайне незаметных возмущений:

Image credit

arxiv.org/pdf/1412.6572.pdf

Так вот, такие почти не заметные возмущения, которые меняют выход нейросети, называют состязательными примерами (или, зачастую, атаками на эту самую нейросеть); по-английски устойчивое выражение adversarial examples / attack.

Может показаться, ну, возможно, такие состязательные примеры существуют только для классификационных сетей (ну класс там перекинуть с правильного на неправильный). Однако быстро выяснили, что подобные проблемы наблюдаются и у сетей, которые детектируют объекты (обводят прямоугольником), и даже у сегментационных сетей (которые каждому пикселю изображения сопоставлют класс): для примера можно посмотреть работу "Adversarial examples for semantic segmentation and object detection".

Ну и напоследок, предвидя возражения в виде ну это все картинки, в нашем замечательном NLP такого не бывает! [NLP = Natural Language Processing], можно привести замечательный пример из статьи "Adversarial examples for evaluating reading comprehension systems", который относится прежде всего к так называемым вопросно-ответным системам, в которых исследуемой системе дают небольшой кусочек текста (несколько предложений), а затем задают простой вопрос на понимание этого куска.

Вот исходный текст:

Peyton Manning became the first quarterback ever to lead two different teams to multiple Super Bowls. He is also the oldest quarterback ever to play in a Super Bowl at age 39. The past record was held by John Elway, who led the Broncos to victory in Super Bowl XXXIII at age 38 and is currently Denvers Executive Vice President of Football Operations and General Manager.

Вопрос:

What is the name of the quarterback who was 38 in Super Bowl XXXIII?

Правильный (а в данном примере он совпадает и с выходом исследуемой модели) ответ: John Elway.

Если же последним предложением к тексту добавить вот этот кусок, совершенно не относящийся к вопросу:

Quarterback Jeff Dean had jersey number 37 in Champ Bowl XXXIV.

То ответ поменяется (станет неправильным внимание нейросети сбилось): Jeff Dean.

Откуда берется неустойчивость и способы борьбы с ней

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

Image credit

arxiv.org/pdf/1608.08967.pdf

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

Итак, мы знаем, что можно обмануть СНС путем небольшого пиксельного возмущения. Почему бы во время обучения для каждого обучающего примера не добавлять и всю его попиксельную окрестность (по некоторой норме, например, $\ell_{\infty}$ [про нормы чуть позже]). Ниже замечательная иллюстрация из статьи "Towards deep learning models resistant to adversarial attacks", где звездочками помечены пиксельные окрестности обучающих примеров, которые попали при изначальной разделяющей прямой в область соседнего класса поэтому нужно разделяющую кривую преобразовать так, чтобы эти звездочки попали в область своего класса:

Ну что ж, сказано сделано. Давайте произведем на коленке необходимые расчеты. Если предположить, что:

исходная картинка размера $100\times 100$ пикселей, 3 цвета RGB,
наш глаз не сильно различает колебания цвета пикселей в 2 градации (из 256): в каждой точке для каждого цвета можем позволить $\pm 1$ значение,

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

$2^{3\times 100\times 100} = 2^{30000} = (2^{10})^{3000} \approx (10^{3})^{3000} = 10^{9000}.$

Хочется заметить, что это значение гораздо больше числа атомов в видимой части Вселенной $(\approx 10^{80})$ , что разбивает на корню идею поправить дело с устойчивостью СНС простым методом в лоб.

Как видим, простой перебор пиксельной окрестности дело трудоемкое. Но ведь нам не нужна та окрестность обущающего примера, которая и так находится в правильной классификационной области! Нужно, наоборот, брать во внимание те точки из окрестности, которые попадают в неправильную область для классификации (по сути, эдакий hard mining обучающих примеров). И вот такой метод обучения с использованием дополнительных, наиболее сложных примеров из окрестности и называется состязательным обучением (adversarial training). В качестве матчасти можно обратиться к первоисточнику по состязательному обучению для СНС.

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

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

Обозначения: формальная часть

Введем парочку обозначений для более формального дальнейшего изложения:

Пусть $x\in B=[0,1]^{C\times M\times N}$ входная картинка $C\times M\times N$ , где $inline$ количество цветов (1 для черно-белой, 3 для цветной в формате RGB), $M\times N$ пространственные размерности (ширина, высота);
$y_{gt}$ правильный класс для входа $inline$ ;
$\theta$ параметры СНС-классификатора;
$L(\theta, x, y_{gt})$ функция потерь;
$inline$ выход классификатора (распознанный класс); при обучении мы добиваемся равенства $f(x) = y_{gt}$ ;
$r\in B=[0,1]^{C\times M\times N}$ аддитивная добавка ко входу $inline$ ;

Теперь можно формально определить цель состязательной атаки: поменять выход классификатора $inline$ на неправильный путем добавления минимального по некоторой норме (на практике используются $\ell_{0}, \ell_{1}, \ell_{2}\mbox{ и }\ell_{\infty}$ обозначим через $\ell_{p}$ ) возмущения $inline$ , а именно минимизировать $||r||_{p}$ так, чтобы:

$f(x) = y_{gt}$ (изначально правильно определяем класс),
$f(x+r) \neq y_{gt}$ (ломаем СНС с помощью возмущения r),
$x+r\in B$ (остаемся во множестве допустимых значений).

Замечание на полях. Похожим образом можно определить и такое понятие, как устойчивость классификатора найти такой класс возмущения $S(x,f)\subseteq B$ , при котором классификатор не меняет свой выход: $f(x+r) = f(x)\quad \forall r\in S(x, f)$ .

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

$\min_{\theta}\mathbb{E}_{(x,y_{gt})}[L(\theta, x, y_{gt})]$

В состязательном обучении мы сначала генерируем (например, каким-нибудь методом атаки) самый сложный пример из некоторой окрестности $\Delta$ входного примера (например, по $\ell_{p}$ -норме), а уже затем минимизируем по параметрам нейросети:

$\min_{\theta}\mathbb{E}_{(x,y_{gt})}[\max_{r\in\Delta}L(\theta, x+r, y_{gt})]$

Нормы l_p: напоминание

Напомним наиболее употребительные нормы $\ell_{p}$ для $x = (x_{1}, \dots, x_{n})\in\mathbb{R}^{n}$ :

$\ell_{2}$ : $||x||_{2} = \sqrt{\sum_{i=1}^{n}x_{i}^{2}}$ (обычная Евклидова норма);
$\ell_{1}$ : $||x||_{1} = \sum_{i=1}^{n}|x_{i}|$ (т.н. метрика городских кварталов);
$\ell_{\infty}$ : $||x||_{\infty} = \max_{i}|x_{i}|$ (максимум модуля; именно на основе данной метрики человеческий глаз воспринимает зрительную информацию);
$\ell_{0}$ : $||x||_{0} = \sum_{i=1}^{n}\mathbf{1}_{x_{i}\neq 0}$ (число ненулевых значений).

Замечание. Для $inline$ норма $\ell_{p}$ , для которой $||x||_{p} = \left(\sum_{i=1}^{n}|x_{i}|^{p}\right)^{1/p}$ , не является нормой.

Состязательные примеры в компьютерном зрении: история вопроса

Fooling images

Допустим, у нас есть классификатор, который выдает вероятности принадлежности входной картинки к 1 из N предобученных классов (например, N=1000 в случае с ImageNet). И, допустим (это не всегда так, но все же), на картинках, принадлежащих этим классам, вероятности выдаются более-менее осмысленно (хоть и бывают ошибки, конечно). Но что будет, если подадим на вход картинку, не принадлежащую этим N классам то есть, выражаясь математически, вне области определения? И хорошо, если на выходе будет равномерный вектор вида (1/N, ..., 1/N) типа сеть не понимает, что происходит.

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

Такие примеры назывались "обманными изображениями" (fooling images) и строились с помощью эволюционных алгоритмов:

За деталями любопытный читатель может обратиться к первоисточнику "Deep neural networks are easily fooled: High confidence predictions for unrecognizable images".

FGSM

В самом первом методе атаки СНС использовался квази-Ньютоновский метод минимизации с ограничением на память и на переменные L-BFGS-B но этот метод достаточно медленный, да и требует зачастую внешнего оптимизатора.

Поэтому практически сразу было предложено использовать линейную часть функции потерь в окрестности входной картинки $inline$ и идти по градиенту (см. первоисточник "Explaining and harnessing adversarial examples"):

$r = \epsilon\cdot sign(\nabla_{x}L(\theta, x, y_{t}))$

где $0 < \epsilon < 1$ некоторая константа, отвечающая за скорость движения, а $y_{t}\neq y_{gt}$ неправильный класс, в направлении которого мы подталкиваем (обманываем) смотреть СНС.

Такой метод получил название Fast Gradient Sign Method (по-русски "быстрый метод, основанный на знаке градиента", но звучит все равно не очень), или FGSM.

Напоминание: для оптимизации весов СНС применяется метод обратного распространения ошибок, где берется градиент по весам СНС, т.е. $\nabla_{\theta}L(\theta, x, y_{gt})$ .

Ну и в данной работе исследуется норма возмущения $\ell_{\infty}$ как наиболее близкая к тому, как устроено человеческое зрение (восприятие зрительной информации).

I-FGSM (PGD)

Часто линейная оценка окрестности функции достаточно грубая, и один шаг FGSM порой не приводит к хорошей атаке.

Для преодоления данной проблемы применяют итеративный метод Iterative FGSM, или I-FGSM, который позволяет двигаться в сторону границы классификатора более точно.

Если $\Pi_{B}$ проекция на $inline$ , то

$x^{n+1} = \Pi_{B}(x^{n} + \alpha\cdot sign(\nabla_{x}L(\theta, x, y_{gt}))), \quad x^{0}=x$

При этом если мы хотим, чтобы наше итоговое решение $x_{adv}$ отдалилось от исходного примера $inline$ не более чем на $\epsilon$ по норме $\ell_{\infty}$ , и мы можем сделать не более $inline$ шагов, то можно сразу вывести эмпирическое правило на скорость движения:

$\alpha = \frac{\epsilon}{n}$

Замечание 1. Но в целом метод I-FGSM гораздо более известен как метод спроектированного градиентного спуска Projected Gradient Descent, или PGD, хотя и появилось это название чуть ли не на год позже.

Замечание 2. Вообще, метод I-FGSM / PGD до сих пор является наиболее широкоприменяемым на практике как простой и при этом достаточно устойчивый (хотя и не такой быстрый, как простой FGSM).

MI-FGSM

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

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

Как следствие, работа "Boosting adversarial attacks with momentum" предлагает использовать сглаживание градиента в итеративном методе I-FGSM Momentum I-FGSM, или MI-FGSM.

Схема работы следующая:

$x^{n+1} = \Pi_{B}(x^{n} + \alpha\cdot sign(g^{t+1})), \quad x^{0}=x, g^{0} = 0$

где через g обозначен как раз сглаженный градиент:

$g^{n+1} = \mu\cdot g^{n} + \frac{\nabla_{x}L(\theta, x, y_{gt})}{||\nabla_{x}L(\theta, x, y_{gt})||_{1}}$

Ну и табличка сравнения последних трех методов, из которой видно, что MI-FGSM все-таки предпочтительнее использовать (чем больше циферки, тем выше успешность атаки):

One Pixel

До этого мы рассматривали состязательные атаки в цифровой области, когда можно менять вообще любой пиксель входного изображения. Тем не менее, есть методы (один из первых JSMA, но он не очень практичный и удобный), которые принимают во внимание не максимальную разность по яркости (по норме $\ell_{\infty}$ ), а максимальное количество пикселей, который можно поменять (по норме $\ell_{0}$ ).

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

В работе "One pixel attack for fooling deep neural networks" рассматривается предельный случай $\ell_{0}$ -атаки. Для этого авторы применяют эволюционный алгоритм (а именно, алгоритм дифференциальной эволюции) для поиска состязательных примеров:

Популяция состоит из 400 экземпляров, каждый из которых задается пятеркой чисел: две координаты и три канала цвета;
Генерация потомка линейная комбинация трех случайных родителей.

Ниже пример такой атаки на базе CIFAR-10, где исходная картинка собаки при изменении ровно одного пикселя становится поочередно любым из остальных 9 классов (самолет, ..., грузовик):

Краткие выводы по первой части

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

Ссылки

Введение на пальцах в тему состязательных атак, прочитанное в 2019 году на Фестивале науки в МГУ им. М. В. Ломоносова:
Чуть больше математики заключительная лекция курса "Современное компьютерное зрение", читаемого в рамках программы SHARE в МГУ им. М. В. Ломоносова для студентов и аспирантов факультетов механико-математического, физического, космических исследований и ВМиК.

Бонус: программа SHARE

В 2019 году в Huawei стартовала образовательная программа SHARE: Школа опережающего научного образования Хуавэй (School of Huawei Advanced Research Education).

Наша лаборатория Intelligent Systems and Data Science Technology Center проводит занятия в МГУ им. М. В. Ломоносова.

Основные факты по данной программе:

2 года длится обучение;
12 полносеместровых курсов в составе (планируем расширять нужно больше практических занятий, это то, чего просят студенты в своих отзывах на наши курсы);
2 главных направления в составе (на данный момент ведем переговоры о включении третьего про обучение с подкреплением):
Специализация "Компьютерное зрение и машинное обучение'';
Специализация "Большие данные и теория информации''.

В будущем будем наполнять содержимое сайта программы (пока только домен зарегистрировали, но работа идет полным ходом ;)

Трейлер следующей части

В следующий раз разберем:

Что такое физически реализуемая состязательная атака;
Основные методы генерации физических состязательных примеров;
Сбиваем с толку реальный детектор лиц;
Делаем больно лучшему открытому распознавателю лиц;
Рассматриваем методику защиты от физических состязательных атак.

Спасибо за внимание!

Подробнее..

Категории: Искусственный интеллект , Машинное обучение , Обработка изображений , Блог компании huawei , Устойчивость , Сверточные нейронные сети , Состязательные примеры

	Русский
	English

Устойчивость

Сортировка выбором

Введение

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

Сортировка выбором

Описание алгоритма

Реализация

Анализ

Двусторонняя сортировка выбором

Рекурсивная сортировка выбором

Итоги

Сортировка вставками

Введение

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

Сортировка вставками

Описание алгоритма

Реализация

Анализ

Итоги

Быстрая сортировка

Введение

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

Быстрая сортировка

Описание алгоритма

Анализ

Читать ещё:

Исследование устойчивости сверточных нейросетей. Часть 1 Теория

Введение в сверточные нейронные сети

Прогресс в сверточных нейронных сетях

(Не)устойчивость сверточных нейронных сетей

Откуда берется неустойчивость и способы борьбы с ней

Обозначения: формальная часть

Состязательные примеры в компьютерном зрении: история вопроса

Fooling images

FGSM

I-FGSM (PGD)

MI-FGSM

One Pixel

Краткие выводы по первой части

Ссылки

Бонус: программа SHARE

Трейлер следующей части

Спасибо за внимание!

Категории

Последние комментарии