Что точнее/быстрее - нейросети или обычные алгоритмы?

[Sonic86]

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

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

Если да, то следует ли отсюда, что AlphaZero в процессе обучения научилась некоему детерминированному алгоритму игры в шахматы, который лучше существующих и неизвестен человечеству.
Если нет, то как вообще возможно, что нейросеть обыграла детерминированный алгоритм?!

(сумбурная мотивация второго вопроса)

Т.е. насколько я понимаю, нейросеть вообще по своему построению в принципе - это вложение некоторого простого, но длинного, м.б. громоздкого по структуре, алгоритма в эдакий такой большой количественный параметризатор алгоритмов, т.е. она по определению должна работать медленнее. (Когда булевы переменные заменяют целыми, прога работает медленнее. Любая нейросеть, вычисляющая XOR или любую другу функцию, которую вычисляет конечный автомат, она тоже должна выполнять бОльшее число вычислений, чем обычный алгоритм (конечно, за счет параллельности общее время работы м.б. сильно меньше, но это - другой вопрос)). (Есть еще куча других примеров: вложение логических операций в арифметические - это есть, но никто так не решает логические задачи. Есть вложение задач булева линейного программирования в ЦЛП, а последних - в ЗЛП. Это работает, но вроде как неизвестно почему. Есть арифметизация доказательств (как в теореме Геделя) - тоже так можно доказывать, но так никто не делает, ибо это неэффективно. Если я запускаю эмуляцию ОС или ЯП в другой ОС на другом ЯП, то эмуляция будет работать медленнее. И с нейросетями д.б. аналогично)

[Dmitriy40]

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

[mihaild]

Sonic86 в сообщении #1275771 писал(а):

Верно ли, что $A$ будет решать эту задачу за указанное время либо быстрее, либо точнее, чем $N$?

Очевидно, что зависит от $A$ и $N$. Например, простейший алгоритм "выдать константу" будет, скорее всего, работать быстрее, чем любая нейросеть.

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

Тут скорее нужен вопрос - есть ли области, где "классические методы" конкурируют с нейросетями? Во всём, что мне сходу приходит в голову, нейросети либо безнадежно проигрывают (какой-нибудь поиск пути в графе), либо выигрывают с гигантским отрывом (компьютерное зрение).

[Legioner93]

mihaild в сообщении #1275804 писал(а):

Тут скорее нужен вопрос - есть ли области, где "классические методы" конкурируют с нейросетями? Во всём, что мне сходу приходит в голову, нейросети либо безнадежно проигрывают (какой-нибудь поиск пути в графе), либо выигрывают с гигантским отрывом (компьютерное зрение).

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

[alesha_popovich]

mihaild в сообщении #1275804 писал(а):

Во всём, что мне сходу приходит в голову, нейросети либо безнадежно проигрывают (какой-нибудь поиск пути в графе), либо выигрывают с гигантским отрывом (компьютерное зрение).

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

Sonic86 в сообщении #1275771 писал(а):

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

А почему бы нет, что в этом такого удивительного? Например, в упомянутом компьютерном зрении нейросети вполне обучаются алгоритму (распознавания, на самом деле - аппроксимации некоторой функции), который неизвестен человечеству. Иначе, нейросети в этой области никому не были бы нужны. Они для того и создавались.

[mihaild]

Legioner93 в сообщении #1275947 писал(а):

то по непрерывности получаем, что

А кто сказал, что "применимость нейросетей" непрерывна?)

Ну и можно ли придумать непрерывный путь от распознавания котиков до решения 3SAT? (может быть и можно, но я не могу)

[Sonic86]

Dmitriy40 в сообщении #1275773 писал(а):

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

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

mihaild в сообщении #1275804 писал(а):

Тут скорее нужен вопрос - есть ли области, где "классические методы" конкурируют с нейросетями? Во всём, что мне сходу приходит в голову, нейросети либо безнадежно проигрывают (какой-нибудь поиск пути в графе), либо выигрывают с гигантским отрывом (компьютерное зрение).

Ну вот шахматы появились например.

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

[Dmitriy40]

Sonic86 в сообщении #1276108 писал(а):

К сожалению, я не уловил аналогии

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

[Sonic86]

Dmitriy40 в сообщении #1276116 писал(а):

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

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

[Dmitriy40]

Выскажу предположение. Может быть из-за изначального акцента на неформализуемость критерия оценки? В ГА мы можем на каждой стадии оценивать эффективность алгоритма, для этого есть чёткий (детерминированный) критерий, именно по нему отбираются выживающие экземпляры. В НС такого критерия изначально нет, мы предоставляем его выработку самой НС, в процессе обучения, мы лишь указываем что хотим получить от этого "чёрного ящика", а как именно - не волнует.
Человек не смог полностью формализовать критерии сравнения лиц или выбора лучшего хода в шахматах, потому в частности и ГА тут человеку не соперники, а НС справилась лучше, не идеально, но лучше. Думаю этим надо гордиться, что мы смогли придумать и создать такой совершенный механизм себе в помощь (как к примеру и радиотехнику), а не комплексовать что породили дьявола.

[mustitz]

Победа AlphaZero над Stockfish нелёгкая и, честно говоря, под вопросом. В целом нужен матч, в котором бы команда Stockfish сама бы настроила железо как считает нужным.

Опять же, проведём мысленный эксперимент. Если таблицы Налимова, где каждой позиции прописана оценка: ничья или сколько ходов до мата. Эти таблицы есть для семи фигур включительно. Там есть достаточно интересные варианты вроде мата в 517 ходов. Ну или другие экзотические выигрыши с учётом правила 50 ходов. И тут как минимум, играть лучше, чем программа по таблицам, невозможно в принципе. Сможет ли нейросеть добиться безошибной игры в этом классе позиций? Не знаю, не уверен...

[grizzly]

mustitz в сообщении #1278612 писал(а):

Победа AlphaZero над Stockfish нелёгкая и, честно говоря, под вопросом.

Даже если бы AlphaZero проиграла 40:60. Вопрос ведь не в счёте -- счёт сам по себе ничего особого кроме маркетинга не значит. Испытана принципиально новая технология разработки ИИ. Вряд ли кто-то скажет, что это испытание не прошло успешно.

[mustitz]

grizzly в сообщении #1278615 писал(а):

Даже если бы AlphaZero проиграла 40:60. Вопрос ведь не в счёте -- счёт сам по себе ничего особого кроме маркетинга не значит. Испытана принципиально новая технология разработки ИИ. Вряд ли кто-то скажет, что это испытание не прошло успешно.

Ну... До этого эта технология была испытана в AlphaGo Zero. И это куда более яркий результат.

Во-вторых, я бы не назвал это принципиально новой технологией разработки ИИ. И до AlphaZero существовало много программ, которые использовали Монте-Карло перебор. И до AlphaZero были попытки использования нейросетей для оценки/выбора хода. Это использовалось ранее в том же жирафе. Принципиальная новизна больше в том, сколько FLOPS-ов было вбухано в обучение.

[grizzly]

mustitz в сообщении #1278638 писал(а):

Во-вторых, я бы не назвал это принципиально новой технологией разработки ИИ. И до AlphaZero существовало много программ, которые использовали Монте-Карло перебор. И до AlphaZero были попытки использования нейросетей для оценки/выбора хода.

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

Я бы задал вопрос следующим образом. Сколько человеко-часов работы программистов нужно потратить, чтобы создать сейчас алгоритм игры в какие-то из типа-шахмат (с другими фигурами или досками, например), которые сколько-то известны (см. википедию), но алгоритмы которых не были разработаны? Интересует ответ на этот вопрос для технологий разработки Stockfish и AlphaZero, при прочих равных (но чтобы уровень игры был существенно выше человеческого). Ответьте, пожалуйста, на этот вопрос.

Я не специалист, поэтому пока готов принять на веру Ваш ответ. Если разница будет менее чем в 10 раз, тогда соглашусь -- это не принципиально.

mustitz в сообщении #1278638 писал(а):

Принципиальная новизна больше в том, сколько FLOPS-ов было вбухано в обучение.

Я попытаюсь сказать то же другими словами: если бы AlphaZero обучалась не 4 часа, а 400 и использовала на пару порядков FLOPS-ов меньше, то этот результат никого бы не удивил. Поправьте меня, пожалуйста, если я исказил Вашу мысль.

-- 25.12.2017, 18:51 --

mustitz в сообщении #1278638 писал(а):

До этого эта технология была испытана в AlphaGo Zero.

Да, соглашусь, что можно рассматривать это как генеральную репетицию.

[mustitz]

grizzly в сообщении #1278644 писал(а):

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

Человек это животное?

grizzly в сообщении #1278644 писал(а):

Я бы задал вопрос следующим образом. Сколько человеко-часов работы программистов нужно потратить, чтобы создать сейчас алгоритм игры в какие-то из типа-шахмат (с другими фигурами или досками, например), которые сколько-то известны (см. википедию), но алгоритмы которых не были разработаны? Интересует ответ на этот вопрос для технологий разработки Stockfish и AlphaZero, при прочих равных (но чтобы уровень игры был существенно выше человеческого). Ответьте, пожалуйста, на этот вопрос.

Это очень общий вопрос, который зависит от игры. Если брать StarCraft, то боты пока что не в состоянии конкурировать с человеком. Если брать счётные игры с хорошей оценкой (типа шахмат), то alpha-beta + эвристики могут на одном уровне и Монте-Карло и даже быть предпочтительнее. Опять же, последние несколько лет Stockfish развивается исключительно играя матчи с самим собой и другими движками. Человек не в состоянии охватить нюансы оценочной функции для миллиона позиций. Кто знает, какой бы силы получился Alpha-Beta движок, если бы ресурсы на его обучение выделил Google?

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

Stockfish в шахматах... Это 4000 коммитов в мастере на сегодня, будет ориентировочно считать по коммиту в день, итого десять человеко-лет. Но это очень грубая оценка... Тут нужен эксперимент...