Entwicklung künstlicher neuronaler Netze zur Lösung von NP-Problemen

10

Ich habe kürzlich einen wirklich interessanten Blogeintrag aus dem Google Research Blog gelesen, in dem es um neuronale Netze geht. Grundsätzlich nutzen sie diese neuronalen Netze zur Lösung verschiedener Probleme wie der Bilderkennung. Sie verwenden genetische Algorithmen, um die Gewichte der Axone zu "entwickeln".

Im Grunde ist meine Idee die folgende. Wenn ich ein Programm schreiben sollte, das Zahlen erkennt, würde ich nicht wissen, wie ich anfangen soll (ich könnte eine vage Idee haben, aber mein Punkt ist: Es ist weder trivial noch einfach.), Aber durch die Verwendung eines neuronalen Netzwerks muss ich nicht. Durch die Schaffung des richtigen Kontexts für die Entwicklung des neuronalen Netzwerks findet mein neuronales Netzwerk "den richtigen Algorithmus". Unten habe ich einen wirklich interessanten Teil des Artikels zitiert, in dem erklärt wird, wie jede Ebene eine andere Rolle bei der Bilderkennung spielt.

Eine der Herausforderungen neuronaler Netze besteht darin, zu verstehen, was genau auf jeder Ebene vor sich geht. Wir wissen, dass nach dem Training jede Ebene nach und nach Merkmale des Bildes auf immer höherer Ebene extrahiert, bis die letzte Ebene im Wesentlichen eine Entscheidung darüber trifft, was das Bild zeigt. Beispielsweise sucht die erste Ebene möglicherweise nach Kanten oder Ecken. Zwischenebenen interpretieren die Grundmerkmale, um nach Gesamtformen oder -komponenten wie einer Tür oder einem Blatt zu suchen. Die letzten paar Schichten setzen diese zu vollständigen Interpretationen zusammen - diese Neuronen werden als Reaktion auf sehr komplexe Dinge wie ganze Gebäude oder Bäume aktiviert.

Meine Frage lautet also im Grunde: Könnten wir nicht genetische Algorithmen + neuronale Netze verwenden, um jedes NP-Problem zu lösen? Wir schaffen einfach den richtigen evolutionären Kontext und lassen "Natur" eine Lösung finden.

Inceptionismus: Tiefer in neuronale Netze vordringen

EDIT: Ich weiß, dass wir in vielen Fällen Brute-Force verwenden oder eine nicht effiziente Lösung finden können. Deshalb versuche ich, die Entwicklung künstlicher neuronaler Netze hervorzuheben . Wie ich in einem Kommentar sagte: Bei ausreichender Zeit und einer angemessenen Mutationsrate könnten wir die optimale Lösung finden (oder zumindest denke ich das).

Konzept

NMO
quelle
1
Wir müssen nicht. Wir können einfach Brute-Force anwenden. Was genau ist dein Ziel?
Pål GD
2
Ich bin kein Experte für neuronale Netze, daher weiß ich nicht, ob sie trainiert werden können, um NP-Probleme richtig zu lösen. Aber ich glaube nicht, dass Sie die richtige Frage stellen. Es ist normalerweise nicht schwierig, einen Algorithmus zu finden, der ein in NP enthaltenes Problem löst. Überprüfen Sie einfach jede mögliche Lösung. Es ist jedoch eine andere Geschichte, einen Algorithmus zu finden, der ein NP-hartes Problem in der Polynomzeit löst, und seine Existenz ist höchst unwahrscheinlich. Da neuronale Netze von einer Abrichtmaschine simuliert werden können, benötigen sie immer noch Superpolynomzeit, es sei denn, P = NP, und sie sind keine große Hilfe.
Dennis Kraft
Ja, neuronale Netze wurden gegen NP-Komplettprobleme eingesetzt, z. B. Travelling Salesman und viele andere, und es gibt Forschung / Literatur zu diesem Thema. Sie können einige nützliche Eigenschaften haben, aber sie kommen nicht von zeitlichen Einschränkungen der Komplexitätstheorie weg, wie DK betont.
vzn
Mein Punkt ist: Mit einer angemessenen Mutationsrate und ausreichender Zeit könnten wir (zumindest theoretisch) die optimale Lösung finden. (Oder zumindest ein lokales Maximum) Bild: Konzept
NMO
2
Genetische Algorithmen (und der Rest der "KI" -Techniken) sind im Wesentlichen randomisiert. Nein, es ist nicht besser als "alle möglichen Lösungen ausprobieren", meistens viel schlimmer (da es keine Garantie gibt, den gleichen weggeworfenen Fall nicht noch einmal zu überprüfen). Sicher, sie finden "anständige" Lösungen. Aber wir wollen das Beste finden .
vonbrand

Antworten:

21

Nein. Diese Richtung ist aus zwei Gründen unwahrscheinlich:

  1. Die meisten Informatiker glauben, dass P NP. Unter der Annahme von P NP bedeutet dies, dass es keinen Polynom-Zeit-Algorithmus gibt, um ein NP-vollständiges Problem zu lösen . Wenn Sie möchten, dass Ihr neuronales Netzwerk das Problem in angemessener Zeit löst, kann es nicht zu groß sein, und daher ist das neuronale Netzwerk selbst ein Polynom-Zeit-Algorithmus. Daraus folgt, dass neuronale Netze bei P NP kein NP-vollständiges Problem effizient lösen können.

  2. Neuronale Netze sind keine "Magie". Sie sind eine Möglichkeit, Muster zu finden. Bei einigen Problemen, bei denen genügend starke Muster gefunden werden können und die Muster aus einer angemessenen Anzahl von Beispielen gelernt werden können, können sie wirksam sein. Aber sie sind kein magischer Feenstaub. Nur weil Sie ein neuronales Netzwerk einrichten können, bedeutet dies nicht, dass die Backpropagation unbedingt einen guten Weg findet, um Ihr Problem zu lösen. Es kann sein, dass keine Muster gefunden werden können, dass die Muster nur mit einer nicht durchführbaren Anzahl von Beispielen entdeckt werden können oder dass Muster existieren, aber das Trainingsverfahren für neuronale Netze sie nicht finden kann.

Neuronale Netze sind nur eine andere Form des maschinellen Lernens. Wir könnten die gleichen Bemerkungen zu SVMs oder zufälligen Wäldern oder zur linearen Regression für jede andere Form des maschinellen Lernens machen. Neuronale Netze sind keine magische Silberkugel, die alle Probleme des maschinellen Lernens löst. Sie sind ungefähr so ​​effektiv wie andere Methoden des maschinellen Lernens oder für einige Arten von Problemen vielleicht ein bisschen effektiver, aber sie sind keine Magie.

Manchmal stoße ich auf Leute, die nur wenig über neuronale Netze gehört haben, und sie gehen weg und denken, dass neuronale Netze die Antwort auf alles sind - vielleicht weil sie gehört haben, dass "Ihr Gehirn auch neuronale Netze verwendet", oder sie haben einige sehr gesehen coole Anwendung (Spracherkennung oder so). Aber lass dich nicht täuschen. Glaube dem Hype nicht. Neuronale Netze sind eine nützliche Technik, aber sie werden es Computern nicht ermöglichen, NP-vollständige Probleme zu lösen oder den Turing-Test zu bestehen, alle unsere Jobs wegzunehmen und Menschen durch Computer zu ersetzen. Jedenfalls nicht so bald. Das ist nur Science Fiction.

DW
quelle
1
Wirklich gute Antwort. Genetische Algorithmen + Neuronale Netze scheinen sehr leistungsfähig zu sein, aber vielleicht reicht es nicht aus, jedes np-Problem zu lösen. Ich stelle mir vor, diese neuronalen Netze + genetischen Algorithmen in freier Wildbahn zu lassen und nach diesen p-Lösungen zu suchen. Wie kleine Späher haha.
NMO
1
Es kann auch erwähnenswert sein, dass neuronale Netze in der Regel eine gewisse Wahrscheinlichkeit bieten, die richtige Antwort zu finden, und keine Garantie. Wenn Sie Ihre Problemanforderungen lockern, um nicht optimale Lösungen zu ermöglichen, gibt es sehr oft praktische Lösungen für NP-vollständige Probleme, trotz ihrer Unlösbarkeit im schlimmsten Fall.
Dan Bryant
9

Es scheint, dass andere informative / hilfreiche Antworten Ihre Frage nicht genau verstehen und ein wenig zu viel hineinlesen. Sie haben nicht gefragt, ob neuronale Netze andere Methoden übertreffen würden , sondern nur, ob sie auf NP-Komplettprobleme angewendet werden können. Die Antwort lautet ja, mit einigem Erfolg, und dies ist seit Jahrzehnten bekannt, und es gibt eine Vielzahl von Forschungsarbeiten dazu, und es geht weiter. Dies hat mit der Flexibilität des maschinellen Lernens zu tun. Beachten Sie, dass selbst wenn sie keine genauen oder optimalen Lösungen finden, die Lösungen, die sie haben, andere wünschenswerte Eigenschaften haben können. Einige Beispielpapiere:

vzn
quelle
4

Neuronale Netze lösen NP-vollständige Probleme nicht wirklich. Was sie tun ist , um Probleme zu lösen , die bemerkenswert nahe an NP-vollständige Probleme sind.

Ein großes Merkmal neuronaler Netze ist, dass sie nicht jedes Mal die "richtige" Antwort finden müssen. Sie dürfen "falsch" sein. Zum Beispiel könnten Sie ein Problem beim Verpacken von Behältern lösen und zu einer Lösung kommen, die 1% von der idealen Lösung abweicht, und mit dieser Antwort vollkommen zufrieden sein.

Wenn Sie die Anforderung entfernen, jedes Mal 100% richtig zu sein, funktionieren andere Lösungsansätze sehr gut. Zum Beispiel müssen viele Routenplanungsalgorithmen (a la Google Maps) NP-vollständig sein, aber es ist ziemlich trivial, einen Algorithmus zu finden, der in 99,9% der Fälle einen Pfad innerhalb von 1% des Optimums findet. Es wird versucht, die Ergebnisse in den letzten 0,1% der Fälle festzuhalten, die dazu führen, dass NP-vollständige Bemühungen so unglaublich teuer werden.

Wenn wir versuchen, NP-vollständige Gleichungen im wirklichen Leben zu verwenden, brauchen wir nicht oft die eigentliche Antwort. Wir fühlen uns oft sehr wohl mit einer "engen" Antwort, obwohl wir oft keinen Wortlaut haben, um zu erklären, welche "enge" Metrik wir verwenden. Dies sind die Situationen, in denen ein neuronales Netzwerk die eigentliche Frage beantworten kann, die Sie stellen wollten, anstatt das von Ihnen gestellte NP-vollständige Problem tatsächlich lösen zu müssen.

Cort Ammon
quelle
1

Es ist bekannt, dass neuronale Netze zur universellen Funktionsnäherung fähig sind. Dies erfordert jedoch, dass sie auf das Problem (Optimierung) trainiert werden, das an und für sich ein NP-vollständiges Problem darstellt. Aus diesem Grund verfügen Sie über Evolutionstraining und SGD mit Backpropagation und so weiter.

Obwohl es unwahrscheinlich ist, dass sie NP-vollständige Probleme lösen, können sie trainiert werden, um eine Funktion, die das Problem modelliert, auf einen beliebigen Grad an Genauigkeit zu approximieren. Auch wenn Sie ein NP-vollständiges Problem mithilfe eines neuronalen Netzwerks optimal lösen, können Sie nicht beweisen, dass die gefundene Lösung tatsächlich das globale Optimum ist, ohne die Lösung brutal zu erzwingen (dies ist natürlich für fast jedes Praktikum nicht möglich Anwendungsfall neuronaler Netze).

Ihre Visualisierung ist insofern genau, als evolutionäre Algorithmen (siehe, wie der saubere Algorithmus verhindert, dass eine einzelne Spezies die Population mit einer anfänglich hochleistungsfähigen Struktur durch gemeinsame Fitness übernimmt) weniger geeignet sind als SGD und andere Techniken des maschinellen Lernens lokale Optima, aber sie liefern keinen Beweis dafür, dass die Lösung, die sie finden, tatsächlich die global optimale Lösung ist.

nickw
quelle
Könnten Sie Ihrer Antwort einige Verweise hinzufügen? Versuchen Sie auch, die Formatierung zu verbessern (verwenden Sie beispielsweise NP, SGD, Backpropagation usw. und fügen Sie möglicherweise einige Zeilenumbrüche hinzu).
Yuval Filmus
In Ordnung, einige Änderungen vorgenommen, lassen Sie mich wissen, ob ich irgendwo weiter in die Tiefe gehen sollte
am
Ich denke, Sie sollten Ihre Behauptung begründen, dass "evolutionäre Algorithmen ... weniger geeignet sind als SGD und andere Techniken des maschinellen Lernens, um in lokalen Optima gefangen zu sein". Ich denke nicht, dass das richtig ist, besonders für die spezielle Aufgabe, neuronale Netze zu trainieren.
DW
Diese Antwort hat einige Verwirrung über die Definition der NP-Vollständigkeit. Im Gegensatz zu dem, was Sie behaupten, wenn wir ein NP-vollständiges Problem lösen, wir können prüfen , ob wir die richtige Lösung. Es gibt einen Unterschied zwischen einem NP-vollständigen Suchproblem und einem NP-harten Optimierungsproblem. Bei ersteren können wir zwar effizient prüfen, ob die Lösung korrekt ist, bei letzteren sind wir möglicherweise nicht in der Lage.
DW
Ich habe mich qualifiziert, dass wir nicht überprüfen konnten, ob es die optimale Lösung ist, ohne die wirklich optimale Lösung zuerst brutal zu erzwingen. Ist das nicht korrekt? Ich habe meine Argumentation begründet, dass die Neuroevolution mit dem referenzierten Link zum ordentlichen Algorithmus und der gemeinsamen Fitness weniger dazu neigt, in lokalen Optima stecken zu bleiben Framework kann helfen, dies zu lindern Ich würde nicht gutschreiben, dass als Abneigung SGD besitzt, stecken zu bleiben.
Nickw