Идеальное обнаружение рака легких в конкурсе ML на 1 миллион долларов с помощью хитроумного взлома - как это было сделано

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

THE BATTLE GROUND - ЧАША НАУКИ ДАННЫХ 2017

Я участвовал в 2017 Data Science Bowl, соревновании по машинному обучению Kaggle, организованном Бузом Алленом для раннего выявления рака легких на основе компьютерной томографии пациентов. Цель заключалась в том, чтобы определить, будет ли у пациента диагностирован рак легких в течение 6 месяцев с момента проведения компьютерной томографии. Общий призовой фонд составлял 1 миллион долларов; конкуренты были мотивированы использовать всевозможные тактики, чтобы получить хоть какое-то преимущество. Всего в соревнованиях приняли участие 1972 команды. Хотя с момента закрытия этого конкурса прошло больше года, я хотел поделиться с вами самым интересным, что произошло в этом конкурсе, по крайней мере, на мой взгляд.

НАСТРОЙКА СОРЕВНОВАНИЙ

Это соревнование состояло из двух этапов:
* На этапе 1 участники тренировали свои модели, используя официальный обучающий набор из около 1400 компьютерных томографов (и, возможно, любой внешний общедоступный набор данных), и отправляли свои прогнозы рака легких на общедоступный набор тестов. , и получить их счет обратно из системы. Набор общедоступных тестов состоял из компьютерной томографии 198 пациентов, результаты диагностики рака которых были известны организатору соревнований, но неизвестны участникам. Лучший результат каждого участника публикуется в общедоступной таблице лидеров (это обычно называется общедоступным счетом LB в Kaggle). Это способ определить, насколько хорошо он справляется с другими участниками во время соревнования. К концу Этапа 1 участники должны были представить свои модели и заморозить код для входа в Этап 2.
* Этап 2 длился одну неделю. Ранее нераскрытые метки для общедоступного набора тестов на Этапе 1 были показаны всем участникам на Этапе 2. Кроме того, частный набор тестов (КТ-сканирование без меток наземной достоверности) для Этапа 2 был доступен для составления прогнозов. Участникам было разрешено не более двух разных заявок, чьи оценки не будут раскрыты до конца Этапа 2. Оценки Этапа 1 просто игнорировались, и результаты Этапа 2 определяли окончательное положение. Участникам было разрешено переобучить свои модели, обрабатывая общедоступный тестовый набор Этапа 1 как дополнительные обучающие данные перед выполнением вывода на частном тестовом наборе Этапа 2, при условии отсутствия изменений в их моделях или гиперпараметрах (включая график скорости обучения и количество эпох для обучения. и т. д.) (если такие изменения не были автоматизированы в замороженном коде).

Некоторое преимущество получают конкуренты, которые смогли добыть достоверную информацию для набора тестовых данных Этапа 1, находясь еще на Этапе 1. Они могут использовать добытые наземные истины на тестовом наборе и использовать их в качестве дополнительных обучающих данных (~ 14% Более того, по сравнению с официальным обучающим набором) для настройки их гиперпараметров, обучения огромного количества моделей для объединения, настройки более надежных результатов локальной проверки, определения оптимальных графиков обучения и т. д. на этих дополнительных «обучающих» данных до им нужно было отправить и заморозить код в конце этапа 1. Также определенно существует фактор «хорошего самочувствия», позволяющий победить других конкурентов во время этапа 1, даже если он напрямую не влияет на итоговую репутацию.

ПРОИСХОДИТ НЕВОЗМОЖНОЕ

Вскоре после запуска конкурса произошла удивительная вещь.

В то время как лучшие участники в то время набирали меньше 0,5 (чем меньше баллов, тем лучше), был один джентльмен по имени Олег Тротт, который имел * идеальный балл * 0,00000 на общедоступном наборе тестов после того, как только после 16 представлений в течение 6 дней ( в этом конкурсе допускалось максимум 3 заявки в день.)

Это казалось невозможным.
Резидент-рентгенолог, который также участвовал в конкурсе, сообщил, что его ручное обследование показало около 0,30–0,38 на различных подмножествах.
Метод грубой силы для определения одной целевой метки для каждой заявки потребовалось бы не менее 66 дней (198 лейблов с 3 отправками в день).

ОБЪЯВЛЕНИЕ

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

Так как же это было сделано? Вы можете посмотреть Объяснение Олега здесь. Его объяснения краткие и сопровождаются кодом, который он использовал. Когда я впервые прочитал это, в нем определенно было какое-то волшебство, которого я не понимал, что привело меня к более глубокому анализу.

ОБЗОР МЕТОДА НА ВЫСОКОМ УРОВНЕ

Файл представления на этапе 1 состоял из 198 пар идентификаторов сканирования и прогнозов о степени достоверности диагноза рака, например:

идентификатор, рак

026470d51482c93efc18b9803159c960,0.2037569618639993 031b7ec4fe96a3b035a8196264a8c8c3,0.34115835466290567

03bd22ed5858039af223c04993e9eb22,0.11568318622008714 06a90409e4fcea3e634748b967993531,0.15048923567505673

07b1defcfae5873ee1f03c90255eb170,0.30526565977678183 ...

В зависимости от того, насколько хороши ваши прогнозы, вы получите некоторый результат от системы, скажем, 0,55213. Если вы отправите разные значения прогноза, оценка может увеличиться или снизиться.

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

Вот что сделал Олег.

  • Установите значения прогноза для 15 из 198 образцов на значения ниже, а для всех 183 других - на 0,5:
    [4.994803e-01, 4.989605e-01, 4.979210e-01, 4.958421e-01, 4.916848e-01 ,
    4.833741e-01, 4.667850e-01, 4.338618e-01, 3.699983e-01, 2.564604e-01,
    1.063198e-01, 1.395599e-02, 2.002820e-04, 4.012894 e-08, 1.610332e-15]
  • Отправьте этот файл, чтобы получить счет обратно из Kaggle
  • Основываясь на этой оценке, можно вычислить точную метку истинности для 15 образцов. Например, оценка 0,67220 будет означать, что 15 ярлыков - это [1 1 0 0 0 1 0 0 0 0 0 0 0 0 0], а оценка 0,91589 означает, что [0 0 1 1 0 0 1 1 0 1 0 1 1 0 1]
  • Повторите поочередно для остальных образцов (отправьте те же значения прогноза, что и выше, но для другого набора из 15), пока не будут вычислены все 198 меток.

Как это вообще работает? Читать дальше…

ПОДРОБНЕЕ О МЕТОДЕ

Осторожно! Остальная часть сообщения немного сложна с математикой!

Для каждого прогноза, сделанного для выборки, оценка (или потеря - эти два термина могут использоваться взаимозаменяемо) вычисляется по потерям журнала:

где y_i - метка истинности (0 или 1), а p_i - прогноз (от 0 до 1) для образца i .

Написано по-другому:

Если истинная истинность равна 1, а прогноз равен 1 (или если истинная истинность равна 0, а прогноз равен 0), то потеря выборки равна 0. Если истинная истинность равна 0, а прогноз равен 1 (или если наземная истина равно 1 и прогноз равен 0), то потеря бесконечна; быть абсолютно уверенным и неправым наказывать бесконечно. Однако в этом соревновании значения прогнозов были автоматически принудительно установлены в диапазоне [10 ^ -15, 1–10 ^ –15] для оценки баллов, поэтому максимальный убыток, который можно понести на выборке, составляет -ln (10 ^ -15 ), что составляет около 34,53878. С другой стороны, минимальная потеря составляет -ln (1–10 ^ -15), что составляет около 9,99201e-16 (в основном 0.)

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

В результате получается диапазон от 0,00000 до 34,53877.

Если сделать прогноз на 0,5 для всех образцов (в основном говоря, что это 50% рака или «Я понятия не имею»), мы получим 0,69314 (-ln 0,5).

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

Если мы игнорируем десятичные разряды, это эквивалентно тому, что система выставляет оценку от 0 до 3 453 877 на основе представленных вами прогнозов; может быть 3 453 878 различных оценок, которые система могла бы выдать на основе различных представленных прогнозов.

В терминах теории информации это означает, что оценка потенциально может «выдать» 21,7 бита информации, поскольку log2 3 453 878 ~ = 21,7.

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

Я говорю «теоретически», потому что есть практические проблемы, такие как побочные эффекты математики с плавающей запятой, такие как недо / переполнение, округление, а также возможность придумать идеальное кодирование.

Мы знаем, что отправка прогноза 0,5 дает оценку -ln 0,5 по выборке, независимо от базовой метки истинности (которая равна 0 или 1), поскольку мы можем извлечь только до 21 бит информации, мы можем «нацелить» на извлечение не более 21 метки, установив прогнозирование всех других нецелевых выборок на 0,5, потому что мы уже знаем точную потерю, которую эти выборки будут вносить. Затем мы можем сосредоточиться на добыче целевых меток. С этого момента я буду называть это количество целевых меток, которые мы пытаемся извлечь для каждой отправки, как T, а общее количество выборок - как N (например, T = 21 и N = 198). При T целевых метках для извлечения общее убыток можно переписать как:

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

Обратите внимание, что каждое предсказание p_i может быть любым действительным числом от 0 до 1. Установка предсказания на 0,5 не дает никакой информации, поскольку оно дает константу -ln 0,5 независимо от основной метки истинности.

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

  • -ln 0.1 ~ = 2.30259, если наземная метка истинности равна 1
  • -ln 0.9 ~ = 0.10536, если метка истинности равна 0

Для всех остальных это -ln 0,5 ~ = 0,69314

Если бы мы представили этот набор прогнозов, общая оценка была бы:

(-ln 0,1 + -ln 0,5 * 197) / 198 ~ = 0,70128, если наземная метка истинности равна 1

(-ln 0,9 + -ln 0,5 * 197) / 198 ~ = 0,69018, если метка истинности равна 0

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

Чтобы извлечь несколько целевых меток для каждой отправки, мы хотим установить прогнозы для каждой целевой выборки по-разному, чтобы мы могли однозначно определять их точные метки по результирующей оценке. Мы можем сделать это, установив значения прогноза для T целевых выборок так, чтобы каждая возможная комбинация оценок 2 ^ T (например, при T = 21 это было бы 2097152 различных комбинаций) была бы уникальной.

Поскольку система выдает баллы до 5-го знака после запятой, мы хотим, чтобы общий балл для каждой двоичной комбинации был разделен на 0,00001, чтобы равномерно заполнить пространство баллов, начиная с 0,00000 до 20,97151 (при T = 21). Придумать такое эффективное идеальное кодирование на практике может оказаться невозможным, хотя мы можем подойти достаточно близко. Олег использовал Т = 15. Я считаю, что он установил T = 15, чтобы он был достаточно большим, чтобы получить небольшое количество представлений, но достаточно безопасным, чтобы оставить достаточно большой запас для побочных эффектов вычисления с плавающей запятой / оценки (иначе он бы потратил больше представлений, пытаясь найти оптимальное T, чем используя консервативное число.) Я экспериментировал со значениями T больше 15, которые работали так же хорошо.

Какие значения предсказания p_i’s мы можем установить, чтобы сделать все оценки уникальными? Вот что использовал Олег:

где i идет от 1 до T, что соответствует каждой из T целевых объектов, которые необходимо извлечь, N - общее количество выборок в отправке, а epsilon - коэффициент масштабирования для управления степенью детализации и диапазоном результирующих оценок. .

Также Олег утверждал, что:

Приложив немного математики и игнорируя усечение во время ввода-вывода и ошибки округления на сервере, вы сможете показать, что при использовании выражения sigmoid потери равныconst + epsilon * X, где X - это целое число, двоичное представление которого равно 15 этикетки.

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

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

А пока давайте для простоты забудем про N и epsilon в функции кодирования для p_i; мы вернемся к ним позже. Тогда у нас остается:

где i находится в диапазоне от 1 до T. Обратите внимание, что мы используем степень двойки * -1. Это сделано для того, чтобы вынудить потерю выборки для случая y_i = 1 быть больше, чем когда y_i = 0. Это необходимо для арифметической точности, чтобы следовать стандартному соглашению о двоичном кодировании, где 0,0,0, .., 0 принимает наименьшее значение и 1 , 1,1,…, 1 принимает наивысшее значение.

Рассмотрим случай, когда i = 1:

Потери для целевого образца 1 составляют:

Для случая y_1 = 0 мы использовали тот факт, что -ln (1-sigmoid (-1)) = - ln (sigmoid (1)), потому что 1-sigmoid (x) = sigmoid (-x). Доказательство можно найти в конце этого поста.

Точно так же потери для целевого образца 2 составляют:

В общем, для любого целевого образца i потеря составляет:

Давайте немного упростим обозначения и вывод, введя функцию softplus.

softplus (x) = -ln (сигмоид (-x)) = ln (1 + e ^ x)

У Softplus есть одно изящное свойство:

softplus (x) - softplus (-x) = x

Это Уравнение 3.41 из книги И. Гудфеллоу Deep Learning. Чтобы понять, почему это так, см. Доказательство внизу этого сообщения.

Если переписать потерю сэмпла в терминах softplus:

В чем разница между потерей выборки, когда метка истинности равна 1, и 0 для любого заданного образца i?

Таким образом, разница в потерях выборки колеблется от 1, 2, 4, 8,… до 2 ^ (T-1) в зависимости от того, какой это образец.

Мы фокусируемся на разнице потерь от метки, равной 1 против 0 для каждого образца i, потому что, в отличие от стандартного двоичного кодирования, метка (или «бит»), равная 0, на самом деле вносит свой вклад в общую сумма softplus (-2 ^ i-1). Это фактически добавляет константу к потерям. Потеря цели минимальна, когда все метки наземной достоверности цели равны нулю. Назовем эту константу Z (для всех нулей)

Точно так же потеря цели максимальна, когда все метки истинности цели равны 1. Мы можем назвать это О (для всех).

Для всего, что находится «между» Z и O (т. Е. Любой комбинации единиц и нулей для T выборок), метка sample i, равная 1, положительно смещает Z на 2 ^ i-1. Это означает, что все потери будут уникальными на основе каждой комбинации наземных меток истинности, как при стандартном двоичном кодировании.

С помощью вышеизложенного мы можем кодировать прогнозы и отображать точные метки истинности на основе оценки. Но есть пара больших проблем. sigmoid (-2 * i) для i ›9 вызывает потерю значимости, и выражение оценивается как ноль. Кроме того, диапазон оценки намного больше, чем максимальная оценка -ln 10 ^ -15 ~ = 34,53878 (этот максимум обусловлен усечением прогнозов отдельных выборок, выполняемых системой оценки, как упоминалось ранее). Кроме того, степень детализации оценки, основанной на этом, составляет 1 (никакие две оценки отдельно друг от друга не меньше чем на 1.) Мы можем сделать это ближе к 1e-5, что является точностью оценки, выставляемой системой, чтобы уменьшить диапазон оценки до соответствовать. Все вышеперечисленные проблемы решаются путем масштабирования прогнозов на эпсилон, как показано в исходной формуле кодирования. Олег установил эпсилон на 1.05e-5. Использование 1.05e-5 вместо 1e-5 позволяет избежать любых потенциальных проблем с математической точностью / округлением с плавающей запятой. И давайте не будем забывать, что общий балл - это среднее значение всех проигрышей в выборке. Таким образом, нам нужно противостоять тому факту, что ко всем потерям образца применяется коэффициент 1 / N. Это причина, по которой коэффициент N появляется в функции кодирования.

Вернемся к утверждению Олега о том, что:

потеря равна const + epsilon * X, где X - это целое число, двоичное представление которого - 15 меток

Упомянутый const - это Z, как определено выше, а термин epsilon * X возникает из-за того, что оценка монотонно увеличивается по мере увеличения X и размера шага в соседние оценки - эпсилон.

Я надеюсь, что это пролило свет на гениальную технику Олега для получения идеального результата на этапе 1 Data Science Bowl 2017. Похоже, что более поздние соревнования, проводимые на Kaggle, хорошо осведомлены об этой уязвимости и значительно ограничили точность оценок. доступны для конкурентов, хотя насчет других платформ я не уверен.

Извините, если некоторые части кажутся изрезанными, но я хотел сделать ошибку, сделав это более очевидным (по крайней мере, для меня!). Надеюсь, вам понравилась эта статья так же, как и мне, написав ее!

ПРИЛОЖЕНИЕ

Докажите, что 1-сигмовидный (x) = сигмовидный (-x)

Вы можете увидеть, почему это так, визуально, поскольку сигмовидная и 1-сигмоидальная симметрия относительно оси y (x = 0) и y = 0,5:

Докажите, что softplus (x) - softplus (-x) = x