Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion
Dieses Paper schlägt einen zweiseitigen Nearest-Neighbor-Algorithmus für die Matrixvervollständigung unter latenten nichtlinearen Faktormodellen mit geringer Glattheit und hoher Fehlstellenrate vor und beweist, dass dieser minimax-optimale Fehlerraten erreicht, die sich an die Glattheit der zugrunde liegenden Funktion anpassen und die Performance eines Oracles selbst bei deterministischen fehlenden Einträgen erreichen.
Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen
Im digitalen Zeitalter sind wir ständig von riesigen Gittern aus Informationen umgeben, von den Filmen, die ein Streaming-Dienst empfiehlt, bis hin zu den täglichen Schritten, die eine Gesundheits-App erfasst. Diese Gitter sind selten vollständig; Nutzer überspringen Bewertungen, Sensoren versagen bei der Datenerfassung, und Menschen erscheinen einfach nicht zu jedem geplanten Termin. Die Herausforderung für Wissenschaftler besteht darin, diese fehlenden Teile genau zu ergänzen, ohne falsche Informationen zu erfinden. Dieses Problem, bekannt als Matrix Completion (Matrix-Vervollständigung), beruht auf der Idee, dass verborgene Muster die Daten, die wir sehen, mit den Daten verbinden, die wir nicht sehen. Wenn eine Person Actionfilme mag und gleichzeitig dazu neigt, Science-Fiction zu genießen, kann ein System diese Verbindung nutzen, um zu erraten, was sie über einen neuen Film denken könnte, den sie noch nicht gesehen hat. Die Realität der Daten ist jedoch oft unordentlich. Die fehlenden Informationen sind oft nicht zufällig; ein Nutzer könnte eine Bewertung nur deshalb ausgelassen haben, weil er den Film so sehr nicht mochte, dass er sich nicht einmal die Mühe machte, oder ein Sensor könnte nur unter spezifischen Bedingungen ausfallen. Darüber hinaus sind die Beziehungen zwischen Nutzern und Objekten oft komplex und nicht-linear, was bedeutet, dass einfache, geradlinige Regeln das vollständige Bild nicht erfassen können.
Ein Team von Forschern der Cornell University und der University of Pennsylvania hat eine neue Methode entwickelt, um dieses schwierige Rätsel zu lösen, insbesondere wenn die Daten auf eine verzerrte Weise fehlen und die zugrunde liegenden Muster komplex sind. Sie konzentrierten sich auf eine Technik namens „Nearest Neighbors“ (Nächste-Nachbarn-Verfahren), die funktioniert, indem sie ähnliche Zeilen und Spalten in einem Datengitter findet, um Vorhersagen zu treffen. Obwohl dieser Ansatz bereits untersucht wurde, gingen frühere Theorien oft davon aus, dass die Daten zufällig fehlen oder dass die Beziehungen zwischen den Datenpunkten glatt und einfach sind. Die Forscher fragten sich, ob diese Methode auch dann noch funktionieren kann, wenn die Daten fehlen, weil sie genau diese Werte enthalten, und wenn die Verbindungen zwischen Nutzern und Objekten eher zackig und unregelmäßig als glatt sind.
Um dies zu beantworten, analysierte das Team einen zweiseitigen Nearest-Neighbor-Algorithmus. Stellen Sie sich ein Gitter vor, in dem die Zeilen Personen repräsentieren und die Spalten Momente in der Zeit oder spezifische Ereignisse. Der Algorithmus sucht nach Menschen, die sich ähnlich verhalten wie die betreffende Person, und er sucht auch nach Momenten, die dem betreffenden Moment ähnlich sind. Indem er die bekannten Ergebnisse ähnlicher Menschen und ähnlicher Momente mittelt, schätzt die Methode den fehlenden Wert. Die Forscher bewiesen mathematisch, dass dieser Ansatz sich an die Komplexität der Daten anpasst. Wenn die verborgenen Muster sehr rau und unregelmäßig sind, passt der Algorithmus seine Suche an, um das richtige Maß an Ähnlichkeit zu finden. Wenn die Muster glatter sind, verfeinert er seine Suche entsprechend. Entscheidend ist, dass sie zeigten, dass diese Methode genauso gut abschneidet wie ein perfektes, allwissendes System, das bereits über die verborgenen Faktoren verfügt, die die Daten antreiben, obwohl der Algorithmus selbst diese Faktoren nicht kennt.
Die Studie zeigte auch, dass die Methode robust bleibt, selbst wenn ein erheblicher Teil der Daten auf deterministische Weise fehlt. In einem Szenario beispielsweise, in dem zwanzig Prozent der Daten garantiert fehlen, weil eine spezifische Regel gilt – etwa dass ein Nutzer niemals eine Benachrichtigung erhält, wenn er nicht verfügbar ist –, funktioniert der Algorithmus dennoch erfolgreich. Er bricht nicht zusammen, wenn das Fehlen nicht zufällig ist, sondern an die zugrunde liegende Struktur des Systems gebunden ist. Die Forscher validierten diese theoretischen Erkenntnisse durch umfangreiche Computersimulationen, bei denen sie die Methode gegen verschiedene andere Techniken testeten. In diesen Tests schnitt ihr zweiseitiger Ansatz konsistent besser ab als Standardmethoden; er wies eine stetige Abnahme der Fehlerraten auf, während andere Methoden Schwierigkeiten hatten oder sich nicht verbesserten.
Um zu sehen, wie dies in der realen Welt funktioniert, wandte das Team seine Methode auf Daten aus einer mobilen Gesundheitsstudie namens HeartSteps an. Diese Studie umfasste siebenunddreißig Teilnehmer, die Benachrichtigungen auf ihre Telefone erhielten, um sie zum Gehen zu ermutigen. Das Ziel war es, zu schätzen, wie viele Schritte eine Person gemacht hätte, wenn sie eine bestimmte Art von Benachrichtigung erhalten hätte, selbst wenn diese Benachrichtigung tatsächlich nicht gesendet wurde. Da die Teilnehmer nicht zu jedem Zeitpunkt verfügbar waren und Benachrichtigungen nur mit einer gewissen Wahrscheinlichkeit gesendet wurden, waren die Daten unvollständig und verzerrt. Die Forscher behandelten die Nutzer als Zeilen und die Entscheidungszeiten als Spalten und erstellten so ein Gitter mit fehlenden Einträgen. Als sie ihre Methode mit anderen verglichen, lieferte der zweiseitige Nearest-Neighbor-Ansatz die genauesten Schätzungen mit den geringsten Fehlern und den konsistentesten Ergebnissen. Er navigierte erfolgreich durch die fehlenden Daten, um die wahrscheinlichen Ergebnisse der Interventionen aufzudecken.
Die Bedeutung dieser Arbeit liegt in ihrer Fähigkeit, mit der unordentlichen Realität menschlichen Verhaltens und von Sensordaten umzugehen. Indem sie bewiesen, dass eine relativ einfache, adaptive Suchstrategie die Leistung eines idealen Systems mit vollem Wissen erreichen kann, haben die Forscher ein leistungsstarkes Werkzeug für Bereiche bereitgestellt, die von Empfehlungsmaschinen bis hin zu medizinischen Studien reichen. Sie zeigten, dass wir selbst dann, wenn Daten nicht zufällig fehlen und die Beziehungen komplex sind, nicht die verborgenen Ursachen kennen müssen, um genaue Vorhersagen zu treffen. Wir müssen lediglich nach den Nachbarn in beide Richtungen suchen – über die Menschen hinweg und über die Zeit hinweg – und die Muster entstehen lassen. Dieser Befund legt nahe, dass in einer Welt unvollständiger Informationen die richtige Art der Mittelung die Wahrheit offenbaren kann, ohne dass man zuerst das gesamte Geheimnis lösen muss.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.