Развивающиеся искусственные нейронные сети для решения задач NP

10

Недавно я прочитал действительно интересную запись в блоге Google Research Blog, рассказывающую о нейронной сети. В основном они используют эту нейронную сеть для решения различных задач, таких как распознавание изображений. Они используют генетические алгоритмы, чтобы «развить» веса аксонов.

В общем, моя идея заключается в следующем. Если бы я должен был написать программу, которая распознает числа, я бы не знал, с чего начать (у меня могла бы быть какая-то смутная идея, но моя точка зрения такова: это не тривиально и не просто), но при использовании нейронной сети мне это не нужно. Создавая правильный контекст для развития нейронной сети, моя нейронная сеть «найдет правильный алгоритм». Ниже я процитировал действительно интересную часть статьи, где объясняется, как каждый слой играет различную роль в процессе распознавания изображений.

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

Итак, в основном мой вопрос заключается в следующем: не могли бы мы использовать генетические алгоритмы + нейронные сети для решения каждой проблемы NP? Мы просто создаем правильный эволюционный контекст и оставляем «природе» найти решение.

Inceptionism: углубляясь в нейронные сети

РЕДАКТИРОВАТЬ: Я знаю, что мы можем использовать Brute-Force или найти неэффективное решение во многих случаях. Вот почему я пытаюсь выделить развивающиеся искусственные нейронные сети. Как я сказал в комментарии: учитывая достаточное время и соответствующую частоту мутаций, мы могли бы найти оптимальное решение (или, по крайней мере, так я думаю).

концепция

НМО
источник
1
Мы не должны. Мы можем просто использовать грубую силу. Какова ваша цель, именно?
Пол GD
2
Я не эксперт по нейронным сетям, поэтому я не знаю, можно ли их обучить правильно решать проблемы NP. Но я не думаю, что вы задаете правильный вопрос. Придумать алгоритм, который решает проблему, содержащуюся в NP, обычно не сложно, просто проверьте каждое возможное решение. Однако найти алгоритм, который решает NP-трудную задачу за полиномиальное время, - это совсем другая история, и его существование маловероятно. Поскольку нейронные сети могут быть смоделированы с помощью проверочной машины, им все еще нужно супер полиномиальное время, если только P = NP, и они не окажут особой помощи.
Деннис Крафт,
да, нейронные сети использовались против комплексных проблем NP, например, Traveling Salesman и многих других, и есть исследования / литература по этой теме. они могут иметь некоторые полезные свойства, но они не уходят от временных ограничений теории сложности, как указывает Д. К.
ВЗН
Моя точка зрения такова: используя подходящую частоту мутаций и достаточное количество времени, мы могли бы (хотя бы теоретически) найти оптимальное решение. (Или хотя бы локальный максимум) Изображение: Концепция
NMO
2
Генетические алгоритмы (и остальная часть техники "ИИ") по существу рандомизированы, "попробуйте образец пространства решений" с добавлением некоторых умов (эвристик), чтобы сделать его не полностью случайным. Нет, это не лучше, чем «попробовать все возможные решения», в большинстве случаев гораздо хуже (так как нет гарантии, что мы не будем проверять тот же сброшенный случай снова). Конечно, они находят «приличные» решения. Но мы хотим найти лучшее .
vonbrand

Ответы:

21

Нет. Это направление вряд ли будет полезным по двум причинам:

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

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

Иногда я сталкиваюсь с людьми, которые слышали лишь немного о нейронных сетях, и они уходят, думая, что нейронные сети - это ответ на все вопросы - возможно, потому, что они слышали, что «ваш мозг тоже использует нейронные сети», или они видели очень классное приложение (распознавание голоса или что-то). Но не обманывайтесь. Не верьте обману. Нейронные сети - полезный метод, но они не позволят компьютерам решать проблемы, связанные с NP, или проходить тест Тьюринга, забирать все наши задания и заменять людей компьютерами. Во всяком случае, не в ближайшее время. Это просто научная фантастика.

DW
источник
1
Действительно хороший ответ. Генетические алгоритмы + нейронные сети кажутся очень мощными, но, возможно, этого недостаточно для решения каждой проблемы NP. Я представляю, как оставить эти нейронные сети + генетические алгоритмы в дикой природе в поисках этих решений. Как маленькие разведчики, ха-ха.
NMO
1
Также стоит отметить, что нейронные сети обычно предоставляют некоторую вероятность найти правильный ответ, а не гарантию. Когда вы ослабляете свои требования к задачам, чтобы позволить неоптимальные решения, очень часто есть практические решения для NP-полных задач, несмотря на их труднопреодолимость в худшем случае.
Дэн Брайант
9

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

ВЗН
источник
4

Нейронные сети на самом деле не решают NP-полных задач. То, что они делают , это решают проблемы, которые удивительно близки к NP-завершенным задачам.

Одна большая особенность нейронных сетей состоит в том, что они не обязаны каждый раз находить «правильный» ответ. Им позволено быть «неправильными». Например, вы, возможно, решаете проблему упаковки в мусорное ведро и находите решение, которое на 1% меньше идеального, и полностью удовлетворяетесь этим ответом.

Если вы устраняете требование быть на 100% правильным каждый раз, другие подходы к решению проблем работают очень хорошо. Например, многие алгоритмы планирования маршрута (например, Google Maps) должны быть NP-полными, но довольно просто найти алгоритм, который находит путь в пределах 1% от оптимального 99,9% времени. Он пытается определить результаты в тех последних 0,1% случаев, которые делают попытки завершить NP настолько дорогими.

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

Корт Аммон
источник
1

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

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

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

nickw
источник
Не могли бы вы добавить ссылки на ваш ответ? Также попробуйте улучшить форматирование (например, используйте NP, SGD, обратное распространение и т. Д. И, возможно, добавьте несколько разрывов строк).
Юваль
Хорошо, внес некоторые изменения, дайте мне знать, если я должен углубиться куда-либо
nickw
Я думаю, что вы должны обосновать свое утверждение о том, что «эволюционные алгоритмы ... менее пригодны, чем SGD и другие методы машинного обучения, которые должны быть включены в локальные оптимумы». Я не думаю, что это правильно, особенно для конкретной задачи обучения нейронных сетей.
DW
Этот ответ имеет некоторую путаницу относительно определения NP-полноты. Вопреки тому, что вы утверждаете, если мы решаем NP-полную проблему, мы можем проверить, есть ли у нас правильное решение. Существует разница между NP-полной проблемой поиска и NP-сложной задачей оптимизации; для первого мы действительно можем эффективно проверить, является ли решение правильным, но для второго мы не сможем.
DW
Я действительно утверждал, что мы не можем проверить, что это оптимальное решение, не прибегая к грубому принуждению к действительно оптимальному решению, не так ли? Я обосновал свои соображения о том, что нейроэволюция менее склонна застрять в локальных оптимумах с помощью ссылки на аккуратный алгоритм и общую пригодность, я думаю, склонность градиентных спусков к зависанию в локальных оптимумах довольно очевидна, и хотя настройка гиперпараметра Фреймворк может помочь облегчить это, я бы не стал полагать, что sgd как противник обладает способностью застрять.
Nickw