Schlecht konditionierte Kovarianzmatrix in der GP-Regression zur Bayes'schen Optimierung

12

Hintergrund und Problem

Ich verwende Gaußsche Prozesse (GP) zur Regression und anschließenden Bayes'schen Optimierung (BO). Für die Regression verwende ich das gpml- Paket für MATLAB mit mehreren benutzerdefinierten Modifikationen, aber das Problem ist allgemein.

Es ist eine bekannte Tatsache, dass, wenn zwei Trainingseingaben im Eingaberaum zu nahe beieinander liegen, die Kovarianzmatrix möglicherweise nicht positiv eindeutig wird (auf dieser Site gibt es mehrere Fragen dazu). Infolgedessen kann die Cholesky-Zerlegung der Kovarianzmatrix, die für verschiedene GP-Berechnungen erforderlich ist, aufgrund eines numerischen Fehlers fehlschlagen. Dies ist mir in mehreren Fällen passiert, als ich BO mit den von mir verwendeten Zielfunktionen ausführte, und ich möchte es beheben.

Vorgeschlagene Lösungen

AFAIK, die Standardlösung zur Linderung von Fehlkonditionierungen, besteht darin, der Diagonale der Kovarianzmatrix eine Kante oder ein Nugget hinzuzufügen. Für die GP-Regression bedeutet dies das Hinzufügen (oder Erhöhen, falls bereits vorhanden) von Beobachtungsrauschen.

So weit, ist es gut. Ich habe den Code für die exakte Inferenz von gpml so modifiziert , dass ich bei jedem Fehlschlagen der Cholesky-Zerlegung versuche, die Kovarianzmatrix auf die nächste symmetrische positive definite (SPD) -Matrix in der Frobenius-Norm zu fixieren, inspiriert von diesem MATLAB-Code von John d'Errico. Das Grundprinzip besteht darin, Eingriffe in die ursprüngliche Matrix so gering wie möglich zu halten.

Diese Problemumgehung macht den Job, aber ich habe festgestellt, dass die Leistung von BO für einige Funktionen erheblich reduziert ist - möglicherweise immer dann, wenn der Algorithmus in einen Bereich hineinzoomen muss (z. B. weil er sich dem Minimum nähert oder weil die Länge skaliert des Problems werden ungleichmäßig klein). Dieses Verhalten ist sinnvoll, da ich das Rauschen effektiv erhöhe, wenn zwei Eingangspunkte zu nahe kommen, aber es ist natürlich nicht ideal. Alternativ könnte ich auch nur problematische Punkte entfernen, aber manchmal müssen die Eingabepunkte nahe beieinander liegen.

Frage

Ich denke nicht, dass numerische Probleme mit der Cholesky-Faktorisierung der Kovarianzmatrizen von GP ein neues Problem sind, aber zu meiner Überraschung konnte ich bis jetzt nicht viele Lösungen finden, abgesehen davon, das Rauschen zu erhöhen oder Punkte zu entfernen, die zu nahe beieinander liegen. Andererseits ist es wahr, dass sich einige meiner Funktionen ziemlich schlecht verhalten, so dass meine Situation vielleicht nicht so typisch ist.

Irgendwelche Vorschläge / Verweise, die hier nützlich sein könnten?

lacerbi
quelle
Sie könnten versuchen, die Einträge der Kovarianzmatrix zu bilden sowie deren Cholesky-Faktorisierung mit höherer Genauigkeit zu berechnen oder zu aktualisieren, beispielsweise mit Quad-Genauigkeit oder sogar mit höherer Genauigkeit. Abgesehen von dem Aufwand können die Berechnungen um Größenordnungen langsamer sein. Es gibt beliebige Präzisions-Add-Ons für MATLAB. Ich sage nicht, dass dies ideal ist, aber es kann eine Option sein. Ich weiß nicht, wie gut sie mit gpml spielen, aber wenn Sie den gpml-Quellcode (m-Dateien) ändern können, können Sie es vielleicht tun.
Mark L. Stone
Haben Sie versucht, der Diagonale der Kovarianzmatrix einen kleinen Jitter hinzuzufügen?
Zen
@ MarkL.Stone Danke für den Vorschlag. Leider muss der Trainingscode schnell sein, sodass hochpräzise Zahlen für meine Anwendung wahrscheinlich keine gute Wahl sind.
Lacerbi
2
Diese Frage ist wirklich interessant. Wenn Sie den Nugget-Effekt zu Ihrer Covaraince-Matrix hinzufügen, z. B. , optimieren Sie Sigma in Ihrer Wahrscheinlichkeit, oder es wird angegeben. Ich habe festgestellt, dass die Optimierung des Nugget-Effekts das Messrauschen erfasst und dem Gaußschen Prozess hilftσ2Iσ
Wis
1
Ich optimiere normalerweise. In einigen Fällen habe ich versucht, darüber hinwegzukommen, aber keine große Verbesserung für die Optimierung erzielt (ich nehme an, dass der hintere Teil sehr eng war).
Lacerbi

Antworten:

7

Eine andere Möglichkeit besteht darin, die verursachenden Punkte im Wesentlichen zu mitteln. Wenn Sie beispielsweise 1000 Punkte und 50 Ursachenprobleme haben, können Sie die optimale Annäherung für niedrige Ränge unter Verwendung der ersten 950 Eigenwerte / Vektoren vornehmen. Dies ist jedoch nicht weit davon entfernt, die nahe beieinander liegenden Datenpunkte zu entfernen, was Sie lieber nicht tun würden. Beachten Sie jedoch, dass Sie mit dem Hinzufügen von Jitter die Freiheitsgrade verringern - dh, jeder Punkt beeinflusst Ihre Vorhersage weniger, sodass dies schlechter sein kann als die Verwendung von weniger Punkten.

Eine andere Möglichkeit (die ich persönlich für ordentlich halte) besteht darin, die beiden Punkte auf eine etwas intelligentere Art und Weise zu kombinieren. Sie können zum Beispiel 2 Punkte nehmen und zu einem kombinieren, aber auch eine Annäherung für den Gradienten bestimmen. Um Gradienteninformationen aufzunehmen, müssen Sie lediglich und d x d x k ( x , x ) aus Ihrem Kernel ermitteln . Derivate haben normalerweise keine Korrelation mit ihrer Beobachtung, sodass Sie nicht auf Konditionierungsprobleme stoßen und lokale Informationen behalten.dxk(x,x)dxdxk(x,x)

Bearbeiten:

Basierend auf den Kommentaren dachte ich, ich würde erläutern, was ich damit meinte, abgeleitete Beobachtungen einzubeziehen. Wenn wir einen Gaußschen Kernel verwenden (als Beispiel),

kx,x=k(x,x)=σexp((xx)2l2)

seine Derivate sind,

kdx,x=dk(x,x)dx=2(xx)l2σexp((xx)2l2)

kdx,dx=d2k(x,x)dxdx=2l22(xx)l4σexp((xx)2l2)

{xi,yi;i=1,...,n}x1m1

Y=[m1,y1,,yn]

K=(kdx0,dx0kdx0,x0kdx0,xnkdx0,x0kx0,x0kx0,xnkdx0,xnkx0,xnkxn,xn)

Der Rest des GP ist wie gewohnt.

j__
quelle
Möchten Sie die Details zu Ihrer vorgeschlagenen Verwendung von ungefähren Gradienteninformationen erweitern?
Mark L. Stone
@j Danke - Ich dachte darüber nach, eine Annäherung mit niedrigem Rang zu machen, ich könnte es versuchen (ich habe es bisher vermieden, da ich möglicherweise große Teile des Codes neu schreiben muss). Bezüglich der Kombination von zwei Punkten zu einem hatte ich es in einer früheren Frage vorgeschlagen , aber ich dachte nicht daran, abgeleitete Informationen zu erhalten. Im Prinzip klingt es ordentlich, aber ich bin nicht sicher, wie ich es verwenden würde, da ich nur einige abgeleitete Beobachtungen (entsprechend den zusammengeführten Punkten) hätte, mit der Last, einen GP pro Eingabedimension hinzuzufügen.
Lacerbi
@j Danke für die zusätzliche Erklärung. Das sieht in der Tat sehr ordentlich aus. Haben Sie Referenzen für diesen Ansatz (oder etwas Ähnliches)?
Lacerbi
2
Sehen Sie sich die These von Mike Osborne auf Seite 67 an ( robots.ox.ac.uk/~mosb/public/pdf/136/full_thesis.pdf ) - er führt derivative und integrale Beobachtungen ein. Hoffe, es hilft :)
j__
4

Eine Lösung, die wir im Büro gefunden haben, besteht darin, die problematischen Punkte zu ändern. Dies kann in Form eines direkten Löschvorgangs oder eines komplexeren Vorgangs erfolgen. Die Beobachtung ist im Wesentlichen, dass nahegelegene Punkte hochgradig redundant sind: Tatsächlich sind sie so redundant, dass sie den Rang der Kovarianzmatrix verringern. Aus dem gleichen Grund trägt ein Punkt ohnehin nur wenig zu dem vorliegenden Problem bei. Entfernen Sie den einen oder anderen Punkt (oder führen Sie etwas anderes aus, indem Sie ihn mitteln oder einen Punkt vom anderen Punkt weg auf einen akzeptablen Mindestabstand "springen" lassen) nicht wirklich ändern Sie Ihre Lösung so viel.

Ich bin nicht sicher, wie ich beurteilen soll, an welchem ​​Punkt die beiden Punkte "zu nahe kommen". Möglicherweise könnte dies eine dem Benutzer überlassene Tuning-Option sein.

(Hoppla! Nachdem ich dies gepostet habe, habe ich hier Ihre Frage gefunden, die diese Antwort zu einer viel ausführlicheren Lösung weiterentwickelt. Ich hoffe, dass ich durch Verknüpfen meiner Antwort mit SEO helfen werde ...)

Sycorax sagt Reinstate Monica
quelle
Dies ist sehr hilfreich, können Sie bitte auch etwas Licht vergießen diese , wenn möglich.
GENIVI-LEARNER