бритва Оккама

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

Что такое бритва Оккама?
Бритва Оккама - это закон бережливости, который обычно формулируется как (по словам Уильяма) «Множественность никогда не должна допускаться без необходимости». С другой стороны, как эвристику, это можно рассматривать как то, что при наличии нескольких гипотез для решения проблемы предпочтение следует отдавать более простой. Неясно, кому можно окончательно приписать этот принцип, но предпочтение Вильгельма Оккама (ок. 1287–1347) простоте хорошо задокументировано. Отсюда этот принцип получил название «бритва Оккама». Это часто означает отсечение или исключение других возможностей или объяснений, поэтому к названию принципа добавляется слово «бритва». Следует отметить, что эти объяснения или гипотезы должны приводить к одному и тому же результату.

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

• Исследования похожи на это, где результаты показали, что дошкольники чувствительны к более простым объяснениям в первые годы обучения и развития.
• Предпочтение более простого подхода и объяснений для достижения одной и той же цели наблюдается в различных аспектах науки; например, принцип экономии применяется к пониманию эволюции.
• В теологии, онтологии, эпистемологии и т. Д. Этот взгляд на экономию используется для вывода различных заключений.
• Варианты бритвы Оккама используются в Knowledge Discovery.

Бритва Оккама как индуктивный уклон в машинном обучении.

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

• Индуктивное смещение (или присущее алгоритму смещение) - это предположения, которые делает алгоритм обучения для формирования гипотезы или обобщения за пределами набора обучающих примеров с целью классификации ненаблюдаемых данных.
• Бритва Оккама - один из простейших примеров индуктивного смещения. Это предполагает предпочтение более простой гипотезы, которая лучше всего соответствует данным. Хотя бритву можно использовать для опровержения других гипотез, для этого может потребоваться соответствующее обоснование. Ниже приводится анализ того, как этот принцип применим в обучении дереву решений.
• Алгоритмы обучения дерева решений следуют стратегии поиска для поиска в пространстве гипотез гипотезы, которая наилучшим образом соответствует обучающим данным. Например, алгоритм ID3 использует стратегию от простого к сложному, начиная с пустого дерева и добавляя узлы, руководствуясь эвристикой получения информации, для построения дерева решений, согласованного с обучающими примерами.
  Информационный прирост каждого атрибута (который еще не включен в дерево) вычисляется, чтобы сделать вывод, какой атрибут следует рассматривать как следующий узел. Получение информации - суть алгоритма ID3. Он дает количественную меру информации, которую атрибут может предоставить о целевой переменной, т. Е. При условии, что доступна только информация об этом атрибуте, насколько эффективно мы можем сделать вывод о целевой переменной. Его можно определить как:

  

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

  

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

• Следовательно, начиная с пустого узла, алгоритм переходит к более сложным деревьям решений и останавливается, когда дерева достаточно для классификации обучающих примеров.
• В этом примере возникает вопрос. Влияет ли устранение сложных гипотез на классификацию ненаблюдаемых случаев? Проще говоря, имеет ли преимущество предпочтение более простой гипотезы? Если два дерева решений имеют несколько разные ошибки обучения, но одинаковые ошибки проверки, то очевидно, что будет выбрано более простое дерево из двух. Поскольку более высокая ошибка проверки приводит к переобучению данных. Сложные деревья часто имеют почти нулевую ошибку обучения, но ошибки проверки могут быть высокими. Этот сценарий дает логическую причину предпочтения более простых деревьев. Кроме того, более простая гипотеза может оказаться эффективной в условиях ограниченных ресурсов.
• Что такое переоснащение? Рассмотрим две гипотезы а и б. Пусть «a» идеально подходит для обучающих примеров, в то время как гипотеза «b» имеет небольшую ошибку обучения. Если по всему набору данных (т. Е. Включая невидимые экземпляры), если гипотеза «b» работает лучше, то говорят, что «a» превышает обучающие данные. Чтобы лучше проиллюстрировать проблему чрезмерной подгонки, рассмотрите рисунок ниже.

  

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

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

Примечание. Дополнительные сведения об обучении дерева решений см. В книге Тома М. Митчелла «Машинное обучение».