Я разработчик учебной программы Программа машинного обучения Nanodegree в Udacity. Учитывая наше обещание студентам, что они всегда будут учиться наиболее ценным и передовым навыкам, я обязан всегда искать способы обновить наш контент. В конце концов, мы не сможем обучить самым современным и трансформирующим технологиям со статическим содержанием, которое никогда не меняется! Машинное обучение - это захватывающая и постоянно меняющаяся область, и наша программа должна отражать это, если мы хотим выполнить свои обязательства перед учениками. Итак, я трачу МНОГО своего времени на изучение и изучение новых возможностей для внедрения новейших навыков, тенденций и технологий в наши классы, а прямо сейчас я работаю над чем-то действительно интересным для предстоящего запуска.

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

В своей статье 1948 года Математическая теория коммуникации Клод Шеннон представил революционное понятие информационной энтропии.

Это сообщение в блоге представляет собой более подробную версию этого видео:

Энтропия в физике

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

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

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

Энтропия и знания

Чтобы ввести понятие энтропии в вероятности, мы будем использовать пример на протяжении всей статьи. Допустим, у нас есть 3 ведра по 4 мяча в каждом. Шары имеют следующие цвета:

  1. Ведро 1: 4 красных шара
  2. Ведро 2: 3 красных шара и 1 синий шар.
  3. Ведро 3: 2 красных шара и 2 синих шара.

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

  1. В первом ведре мы точно будем знать, что выходящий мяч красный.
  2. Во втором сегменте мы знаем с 75% уверенностью, что мяч красный, и с 25% уверенностью, что он синий.
  3. В третьей корзине мы знаем с 50% уверенностью, что мяч красный, и с такой же уверенностью, что он синий.

Поэтому имеет смысл сказать, что Bucket 1 дает нам наибольшее количество «знаний» о том, какой шар мы будем рисовать (потому что мы точно знаем, что он красный), что Bucket 2 дает нам некоторые знания, а Bucket 3 дает нам наименьшее количество знаний. Ну, энтропия в некотором роде противоположна знанию. Итак, мы скажем, что Ведро 1 имеет наименьшее количество энтропии, Ведро 2 имеет среднюю энтропию, а Ведро 3 имеет наибольшее количество энтропии.

Но нам нужна формула для энтропии, поэтому, чтобы найти эту формулу, мы будем использовать вероятность.

Энтропия и вероятность

Итак, теперь вопрос в том, как составить формулу, которая дает нам низкое число для ведра с 4 красными шариками, высокое число для ведра с 2 красными и 2 синих шариками и среднее число для ведра с 3. красный и 1 синий шарики? Что ж, в качестве первой попытки вспомним определение энтропии: если молекулы имеют много возможных перегруппировок, то система имеет высокую энтропию, а если у них очень мало перегруппировок, то система имеет низкую энтропию. Итак, первая попытка - подсчитать количество перестановок этих шаров. В этом случае у нас есть 1 возможная перестановка для Bucket 1, 4 для Bucket 2 и 6 для Bucket 3, это число определяется биномиальным коэффициентом.

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

Энтропия и интересное игровое шоу

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

В этой игре нам снова предоставляется выбор из трех ведер. Правила следующие:

  1. Выбираем одно из трех ведер.
  2. Нам показывают шары в ведре в определенном порядке. Затем шары возвращаются в ведро.
  3. Затем мы вынимаем из ведра по одному мячу, записываем цвет и возвращаем мяч обратно в ведро.
  4. Если записанные цвета образуют ту же последовательность, что и последовательность шаров, которую нам показали в начале, то мы выигрываем 1 000 000 долларов. Если нет, то проиграем.

Это может показаться сложным, но на самом деле это очень просто. Допустим, мы выбрали ведро 2, в котором есть 3 красных шара и 1 синий шар. Шарики в ведре показаны в определенном порядке, например, в этом точном порядке: красный, красный, красный, синий. Теперь давайте попробуем нарисовать шары, чтобы получить последовательность: красный, красный, красный и синий. Какова вероятность этого? Хорошо…

  1. Для того, чтобы первый шар был красным, вероятность равна 3/4 или 0,75.
  2. Если второй шар окажется красным, вероятность снова равна 3/4. (Помните, что мы кладем первый шар обратно в ведро, посмотрев на его цвет.)
  3. Если третий шар окажется красным, вероятность снова равна 3/4.
  4. Четвертый шар станет синим с вероятностью 1/4 или 0,25.

Поскольку это независимые события, вероятность того, что 4 из них произойдут, составляет (3/4) * (3/4) * (3/4) * (1/4) = 27/256, или 0,105. Это маловероятно. На рисунках ниже мы видим вероятность выигрыша, если выберем каждую из трех корзин.

Для наглядности следующие три рисунка показывают вероятности выигрыша с каждым из ведер. Для Bucket 1 вероятность равна 1, для Bucket 2 вероятность равна 0,105, а для Bucket 3 вероятность равна 0,0625.

Или, как показано в следующей таблице:

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

  1. 1.0 для ведра 1
  2. 0,105 для ковша 2
  3. 0,0625 для ковша 3

Чтобы построить формулу энтропии, нам нужно обратное, некоторую меру, которая дает нам низкое число для сегмента 1, среднее значение для сегмента 2 и высокое число для сегмента 3. Нет проблем, здесь логарифмы придет, чтобы спасти нашу жизнь.

Превращение продуктов в суммы

Следующий прием - очень простой, но используемый очень широко, особенно в машинном обучении. Видите ли, товары никогда не бывают очень хорошими. Здесь у нас есть произведение 4 чисел, что неплохо, но представьте, если бы у нас был миллион точек данных. Как бы выглядело произведение миллиона малых вероятностей (от 0 до 1)? Это было бы смехотворно крошечное число. В общем, мы стараемся избегать продуктов, насколько это возможно. Что лучше продукта? Ну что ж, сумма! А как превратить продукты в суммы? Точно, используя функцию логарифм, так как следующая идентификация будет очень полезна:

Так что же нам делать? Итак, у нас есть произведение четырех вещей, мы берем логарифм и получаем сумму четырех вещей. В случае Bucket 2 (3 красных шара, 1 синий шар) мы имеем следующее:

И взяв логарифм (в данном случае мы возьмем логарифм и умножим его на -1, чтобы сделать результат положительным), мы получим:

Теперь, в качестве последнего шага, мы берем среднее значение для нормализации. Вот и все, это энтропия! Для сегмента 2 это 0,811:

Если мы посчитаем энтропию для Ведра 1 (4 красных шара), мы получим:

А для ведра 3 (2 красных шара, 2 синих шара) получаем:

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

Для любителей формулы общая формула выглядит следующим образом. Если в нашем ведре m красных шариков и n синих шариков, формула будет следующей:

Мультиклассовая энтропия

До сих пор мы имели дело с двумя классами: красным и синим. Чтобы связать энтропию с теорией информации, нам нужно рассмотреть энтропию с несколькими классами. Давайте переключимся на буквы, чтобы было понятнее. У нас есть следующие три корзины по 8 букв в каждой. В сегменте 1 есть буквы AAAAAAAA, в сегменте 2 - AAAABBCD, а в сегменте 3 - буквы AABBCCDD. Хотя легко увидеть, что у Bucket 1 наименьшее количество энтропии, разница между Bucket 2 и Bucket 3 не очевидна. Ниже мы увидим, что у ведра 3 самая высокая энтропия из трех, а у ведра 2 - средняя.

Формула энтропии очень легко обобщается на большее количество классов. Это общая формула:

Где имеется n классов, а p_i - это вероятность появления объекта из i-го класса. Для наших трех ведер у нас есть следующее:

В этом случае, поскольку у Bucket 1 есть только один класс (буква A), и вероятность его появления равна 1, то энтропия равна:

Для Bucket 2, поскольку у нас есть 4 класса (буквы A, B, C и D), и вероятность появления A составляет 4/8, для B - 2/8, для C - 1/8, а для D это 1/8, тогда энтропия равна:

И, наконец, для Bucket 3, поскольку у нас есть 4 класса (буквы A, B, C и D) и вероятность появления каждого равна 1/4, то энтропия равна:

Итак, мы вычислили энтропию для наших трех ведер.

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

Теория информации

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

Во-первых, давайте разберемся с легким делом. Если ведро - это 1-й сегмент, мы точно знаем, что это буква А. Итак, мы знаем, что для сегмента 1 нам нужно задать в среднем 0 вопросов, чтобы угадать, какую букву мы получили. Для большей избыточности представим это в формуле:

Теперь, для блоков 2 и 3, наивно можно было бы подумать, что 4 вопросов достаточно, чтобы узнать любую букву. А именно, следующих четырех вопросов будет достаточно:

  1. Это буква А?
  2. Буква А Б?
  3. Буква C?
  4. Буква D?

Итак, во-первых, четвертый вопрос является избыточным, поскольку если ответ на все предыдущие - «нет», то мы точно знаем, что это буква D. Так что трех вопросов достаточно. Можем ли мы сделать лучше, чем это? Что ж, наши вопросы не должны быть независимыми. Мы можем адаптировать наш вопрос 2, основываясь на ответе на вопрос 1, следующим образом:

  1. Буква А или Б?
  2. а) Если ответ на вопрос 1 «да»: буква А? Если ответ на вопрос 1 «нет»: буква C?

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

  1. «Да» и «Да»: буква А
  2. «Да» и «Нет»: буква B
  3. «Нет» и «Да»: буква C
  4. «Нет» и «Нет»: буква D

Это дерево вопросов можно увидеть на следующем изображении:

Теперь для Bucket 3 каждая буква появляется с вероятностью 1/4, так как есть 8 букв, по 2 каждой. Таким образом, среднее количество вопросов для выяснения буквы, извлеченной из ведра 2, равно 2, как гласит следующая формула:

Теперь давайте посмотрим на сегмент 1. Конечно, если мы будем использовать то же дерево вопросов, что и для сегмента 2, мы увидим, что среднее количество вопросов равно 2. Но мы можем сделать немного лучше. Собственно, воспользуемся первой попыткой. Сначала спрашивают, является ли буква A, затем B, затем C. Это следующее дерево:

В этом случае мы имеем следующее:

  1. Если буква А, мы выяснили это в 1 вопросе.
  2. Если буква B, мы выяснили это за 2 вопроса.
  3. Если буква C или D, мы выяснили это за 3 вопроса.

Теперь фокус в следующем. A появляется гораздо чаще, чем C и D, поэтому в среднем, возможно, у нас дела обстоят намного лучше. Насколько лучше? Вспомните, что в Bucket 2 есть буквы AAAABBCD, поэтому A появляется в 1/2 раза, B появляется в 1/4 времени, а C и D появляются каждые 1/8 времени. Итак, среднее количество вопросов:

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

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

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

Благодарности

  • Я хотел бы поблагодарить Тимоти Мэна за его разъяснение и подробное объяснение концепции энтропии в физике.
  • Также я хотел бы поблагодарить Гектора Плата за ценные исправления.

Предложения? Исправления? Напишите мне по адресу [email protected].

И если вам понравилось то, что вы видели, не стесняйтесь проверить наши программы Nanodegree на Udacity!