Warum die automatische Filterung von Abfragen präziser sein muss

In einem früheren Blogbeitrag habe ich das Konzept der „automatischen Filterung von Suchanfragen“ vorgestellt. Dabei handelt es sich um den…

In einem früheren Blogbeitrag habe ich das Konzept der „automatischen Filterung von Suchanfragen“ vorgestellt. Dabei handelt es sich um den Prozess der Verwendung von Metainformationen (Informationen über Informationen), die von einer Suchmaschine indiziert wurden, um daraus zu schließen, was der Benutzer zu finden versucht. Viele der Informationen, die für die Facettensuche verwendet werden, können auch auf diese Weise genutzt werden. Indem wir dieses Wissen jedoch im Voraus oder zur „Abfragezeit“ nutzen, können wir Fragen sofort und viel präziser beantworten, als wir es ohne diese Techniken könnten. Ein Wort zur „Präzision“: Präzision bedeutet, dass es weniger „falsch-positive“ Antworten gibt. Das sind unbeabsichtigte Antworten, die sich in eine Ergebnismenge einschleichen, weil sie einige Wörter mit den besten Antworten gemeinsam haben.

Suchanwendungen mit gut abgestimmter Relevanz bringen die besten Ergebnisse an die Spitze der Ergebnisliste, aber es ist üblich, dass auch andere Antworten, die wir „Rauschtreffer“ nennen, zurückkommen. Im vorigen Beitrag habe ich erklärt, warum die Suchmaschine bei der Verwendung mehrerer Begriffe oft „das Falsche tut“ und warum dies für die Benutzer frustrierend ist – sie fügen ihrer Anfrage mehr Informationen hinzu, um sie weniger mehrdeutig zu machen, und die Antworten belohnen diese zusätzliche Mühe oft nicht – in vielen Fällen hat die Antwort mehr Rauschtreffer, einfach weil die Anfrage mehr Wörter enthält. Die Lösung, die ich erörtert habe, besteht darin, ein gewisses semantisches Bewusstsein in den Suchprozess einzubauen, denn die Art und Weise, wie Wörter in Sätzen verwendet werden, ist bedeutungsvoll, und wir brauchen Möglichkeiten, um die Absicht des Benutzers anhand dieser Muster zu erkennen. Der traditionelle Weg, dies zu tun, ist die Verwendung von Natural Language Processing oder NLP, um die Benutzeranfrage zu analysieren. Dies kann gut funktionieren, wenn die Abfragen so gesprochen oder geschrieben werden, als ob die Person eine andere Person fragen würde, wie z.B. „Wo finde ich Restaurants in Cleveland, die Sushi servieren?“ Natürlich ist dieses Szenario – das auf die Anfänge der KI zurückgeht – viel wichtiger geworden, seit wir mit unseren Handys sprechen können. Bei Suchanwendungen wie Google, die nach dem Paradigma „Kästchen und eine Taste“ funktionieren, bestehen die Benutzeranfragen in der Regel aus einem Wort oder kurzen Sätzen wie „Sushi-Restaurants in Cleveland“. Diese sind oft das, was Linguisten als „Substantivphrasen“ bezeichnen. Sie bestehen aus einem Wort, das eine Person, einen Ort oder eine Sache bezeichnet (also das, was oder wen sie finden wollen) – z.B. „Restaurant“ und „Cleveland“ und einigen Wörtern, die ihre Anfrage präzisieren, indem sie die Eigenschaften der Sache, die sie finden wollen, einschränken – in diesem Fall „Sushi“.

Mit anderen Worten, aus dieser Anfrage geht klar hervor, dass der Benutzer nicht an irgendeinem Restaurant interessiert ist – er möchte diejenigen finden, die rohen Fisch auf einem Reisbällchen oder in Seetang eingewickelte Gemüse- und Meeresfrüchtedinger servieren. Die Suchmaschine macht oft das Falsche, weil sie nicht weiß, wie sie diese Begriffe kombinieren soll – und verwendet in der Regel den falschen logischen oder booleschen Operator – ODER, wenn die Absicht des Benutzers als UND interpretiert werden sollte. Es hat sich herausgestellt, dass unsere Suchindizes in vielen Fällen den Unterschied zwischen mexikanischen Restaurants (die in der Regel kein Sushi servieren) und japanischen Restaurants (die in der Regel Sushi servieren) kennen, und zwar aufgrund der Metadaten, die wir für die facettierte Suche eingegeben haben (Lustige Geschichte: Nachdem ich diesen Artikel veröffentlicht hatte, stieß ich auf ein mexikanisches Restaurant in Toms River, New Jersey, das Sushi serviert – aber die meisten tun es trotzdem nicht!) Das Ziel der automatischen Filterung von Suchanfragen besteht darin, das vorhandene Wissen zu nutzen, um die Frage sofort zu beantworten, und nicht darauf zu warten, dass der Benutzer die Facetten „aufschlüsselt“. Wenn der Benutzer keine präzise Anfrage stellt (z.B. einfach nur „Restaurants“), können wir die Facettierung immer noch verwenden, aber in diesem Fall wäre es gut, wenn wir gleich zur Sache kommen könnten.

Wie Sie sehen werden, können wir das tun. Der vorherige Beitrag enthielt eine Lösung, die ich eine „einfache“ Kategorieextraktionskomponente nannte. Sie funktioniert, indem sie prüft, ob einzelne Token in der Abfrage mit Feldwerten im Suchindex übereinstimmen (unter Verwendung einer coolen Lucene-Funktion, mit der wir den „uninvertierten“ Index nach allen Werten durchsuchen können, die in einem Feld indiziert wurden). Wenn es beispielsweise das Token „rot“ sieht und feststellt, dass „rot“ einer der Werte eines Feldes „Farbe“ ist, würde es daraus schließen, dass der Benutzer nach Dingen gesucht hat, die in „Farbe“ „rot“ sind, und die Abfrage auf diese Weise einschränken. Die Lösung funktioniert in einer begrenzten Anzahl von Fällen gut, aber es gibt eine Reihe von Problemen, die sie in einer Produktionsumgebung weniger nützlich machen. Sie leistet gute Arbeit in Fällen, in denen der Begriff „rot“ verwendet wird, um eine Sache zu qualifizieren oder genauer zu spezifizieren – wie z.B. „rotes Sofa“. Es funktioniert nicht so gut in Fällen, in denen der Begriff „rot“ nicht als Qualifizierungsmerkmal verwendet wird – z.B. wenn er Teil eines Marken- oder Produktnamens ist, wie „Red Baron Pizza“ oder „Johnny Walker Red Label“ (toller Scotch, aber „Black Label“ ist noch besser, vielleicht werde ich eines Tages reich genug sein, um mir „Blue Label“ leisten zu können – aber ich schweife ab …). Es ist interessant festzustellen, dass die Hauptschwächen des einfachen Extraktors darauf zurückzuführen sind, dass er jeweils einzelne Token isoliert von den Token um sie herum betrachtet.

Es stellt sich heraus, dass dies das gleiche Problem ist, das die Algorithmen der Kernsuchmaschine haben – d.h. es ist ein „Wortsack“-Ansatz, der – warten Sie es ab – den semantischen Kontext nicht berücksichtigt semantischen Kontext. Die Lösung besteht darin, nach Wortmustern zu suchen, die mit Mustern von Inhaltsattributen übereinstimmen. Dies bewirkt eine viel bessere Arbeit bei der Disambiguierung. Wir können den gleichen Codierungstrick wie bisher verwenden (aktualisiert für die API-Änderungen, die in Solr 5.0 eingeführt wurden), aber wir müssen den Kontext und die Verwendung berücksichtigen – so viel wie möglich, ohne dass wir ein komplettes NLP einführen müssen, das viel Text zum Verarbeiten benötigt. Im Gegensatz dazu kann dieser Ansatz funktionieren, wenn wir nur strukturierte Metadaten haben.

Suchen vs. Navigieren

Ein kleiner historischer Hintergrund. Bei modernen Suchanwendungen gibt es im Grunde zwei Arten von Benutzeraktivitäten, die miteinander vermischt werden: Suchen und Navigieren. Ersteres beinhaltet die Eingabe in ein Feld und letzteres das Klicken auf Facettenlinks. Früher gab es noch eine dritte Benutzerschnittstelle, das so genannte „erweiterte“ Suchformular, in dem die Benutzer aus einer Reihe von Metadatenfeldern auswählen, einen Wert eingeben und ihre logischen Kombinationsoperatoren auswählen konnten – eine Schnittstelle, die sich ideal für eine präzise Suche bei umfangreichen Metadaten eignet. Das Problem ist nur, dass niemand sie benutzen will. Nicht, dass die Menschen diese Schnittstelle jemals gemocht hätten (außer denen mit einem Master of Library Science), aber Google hat auch viel getan, um diese Schnittstelle zu einer historischen Referenz zu degradieren. Google hat immer noch das gleiche Problem mit den Rauschtreffern, aber es hat sich den Ruf erworben, die besten Ergebnisse an die Spitze zu bringen (und das tun sie in der Regel auch) – und sie vermeiden auch Facetten (sie haben sie jetzt irgendwie unten auf der Suchseite als verwandte Suchen). Die Benutzer können ihre Suchanfrage auch mit Anführungszeichen, booleschen Ausdrücken oder Vorzeichen versehen, aber glauben Sie mir, das tun sie auch nicht (normalerweise jedenfalls). Das bedeutet, dass das kleine Suchfeld – ob Sie es lieben oder hassen – unser Haupteinstiegspunkt ist, d.h. wir müssen uns damit befassen, denn das ist es, was die Benutzer wollen – einfach etwas eingeben und dann die „richtige“ Antwort zurückbekommen. (Wenn die mangelnde Benutzerfreundlichkeit oder die einfache Freude an Google der erweiterten Suche nicht den Garaus gemacht hat, dann wird es die Umstellung auf mobile Geräte mit Sicherheit tun).

Ein wenig Solr/Lucene-Technologie – String-Felder, Textfelder und „Freitext“-Suche:

Wenn es in Solr um Textdaten geht, werden diese beiden Benutzeraktivitäten normalerweise von zwei verschiedenen Arten von Indexfeldern verarbeitet: String und Text. String-Felder werden nicht analysiert (tokenisiert) und die Suche nach ihnen erfordert eine genaue Übereinstimmung mit einem Wert, der in einem Feld indiziert ist. Dieser Wert kann ein Wort oder eine Phrase sein. Mit anderen Worten: Sie müssen die Syntax <field>:<value> in der Abfrage verwenden (und die Syntax „value here“ in Anführungszeichen, wenn die Abfrage mehrere Begriffe enthält) – etwas, womit Power-User gut zurechtkommen, was wir aber nicht von einem Durchschnittsanwender erwarten können. String-Felder sind jedoch sehr gut für die facettierte Navigation geeignet. Textfelder hingegen werden analysiert (tokenisiert und gefiltert) und können mit „Freitext“-Abfragen durchsucht werden – unser kleiner Kasten also. Das Problem dabei ist, dass durch die Tokenisierung ein Textstrom in einen Strom von Token (Wörtern) umgewandelt wird. Wir behalten zwar Positionsinformationen bei, so dass wir nach Phrasen suchen können, aber wir wissen nicht von vornherein, wo sich diese Phrasen befinden. Textfelder können auch facettiert werden (eigentlich kann jedes Feld in Solr ein Facettenfeld sein), aber in diesem Fall basieren die Facetten auf einzelnen Token, die in der Regel nicht sehr nützlich sind. Wir haben also zwei grundlegende Feldtypen für Textdaten, einen für die Suche und einen für die Navigation. Bei dem schwieriger zu durchsuchenden Typ wissen wir genau, wo sich die Phrasen befinden, aber bei dem leichter zu durchsuchenden Typ wissen wir das normalerweise nicht. Ein klassisches Kompromiss-Szenario. Da String-Felder schwerer zu durchsuchen sind (zumindest im Google-Paradigma, das die Benutzer lieben), machen wir sie durchsuchbar, indem wir ihre Daten (mit der Solr-Direktive „copyField“) in ein Textfeld kopieren, das standardmäßig „text“ heißt. Das funktioniert, aber dabei gehen Informationen darüber verloren, welche Werte als Phrasen gedacht sind und welche nicht. Und nicht nur das, wir haben auch den Kontext verloren, für den diese Werte stehen (die Stringfelder, aus denen sie stammen). Obwohl wir diese Stringfelder besser durchsuchbar gemacht haben, mussten wir sie in einen „Wortsack“-Mixer packen. Aber die Informationen befinden sich immer noch irgendwo im Suchindex, wir brauchen nur eine Möglichkeit, sie zur „Abfragezeit“ wieder zu finden. Dann können wir beides haben: unseren Kuchen UND ihn essen!

Substantivische Ausdrücke und die Hierarchie der Metadaten

Wenn wir über Dinge sprechen, gibt es bestimmte Attribute, die beschreiben, was das Ding ist (Typattribute) und andere, die die Eigenschaften oder Merkmale des Dings beschreiben. In einer strukturierten Datenbank oder einem Suchindex werden diese beiden Arten von Attributen auf die gleiche Weise gespeichert – als Feld/Wert-Paare. Es gibt jedoch natürliche oder semantische Beziehungen zwischen diesen Feldern, die die Datenbank oder die Suchmaschine nicht verstehen kann, wir aber schon. Das heißt, in den Beziehungen zwischen unseren Metadatenfeldern sind Substantivphrasen versteckt, die spezifischere Dinge beschreiben. Alles, was wir tun müssen, ist, sie auszugraben. Wenn ich z.B. eine Datenbank mit lokalen Geschäften habe, kann ich ein „Was“-Feld wie „Geschäftstyp“ haben, das Werte wie „Restaurant“, „Eisenwarenladen“, „Drogerie“, „Tankstelle“ und so weiter enthält. Innerhalb einiger dieser Geschäftstypen, wie z.B. „Restaurant“, kann es verfeinernde Informationen geben, wie z.B. die Art des Restaurants („Mexikanisch“, „Chinesisch“, „Italienisch“, usw.) oder die Marke/Franchise („Exxon“, „Sunoco“, „Hess“, „Rite-Aid“, „CVS“, „Walgreens“, usw.) für Tankstellen und Drogerien. Diese Felder bilden eine natürliche Hierarchie von Metadaten, in der einige Attribute die Menge der Dinge verfeinern oder einschränken, die durch breitere Feldtypen gekennzeichnet sind.

Wiederherstellung des Kontexts: Identifizierung von Feldnamensmustern, um relevante Phrasenmuster zu finden

Jetzt ist es also an der Zeit, Humpty Dumpty wieder zusammenzusetzen. Mit Solr/Lucene ist es wahrscheinlich, dass die Informationen, die wir benötigen, um präzise Antworten auf präzise Fragen zu geben, im Suchindex vorhanden sind. Wenn wir Unterbegriffe in einer Abfrage identifizieren können, die auf ein Metadatenfeld im Index verweisen oder dieses abbilden, können wir die entsprechende Metadatenabbildung im Namen des Benutzers hinzufügen. Wir sind dann in der Lage, Fragen wie „Wo befindet sich der nächstgelegene Tru Value Eisenwarenladen?“ zu beantworten, da wir die Phrase „Tru Value“ als Geschäftsname und „Eisenwarenladen“ als eine bestimmte Art von Geschäft identifizieren können. Unter der Annahme, dass diese Informationen in Form von Metadatenfeldern im Index enthalten sind, besteht das Parsen der Abfrage darin, diese Metadatenwerte zu erkennen und sie mit ihren Quellfeldern zu verknüpfen. Mit etwas zusätzlicher NLP-Magie lassen sich auch andere Aspekte der Frage ableiten, wie z.B. „wo ist das nächste“, was z.B. die Hinzufügung eines Filters für räumliche Nähe auslösen sollte.

Die Suchkomponente Query AutoFiltering Search

Um die oben dargelegte Idee umzusetzen, habe ich eine Solr-Suchkomponente namens QueryAutoFilteringComponent entwickelt. Suchkomponenten werden als Teil des Prozesses zur Bearbeitung von Suchanfragen ausgeführt. Neben der Ausführung einer Suche können sie auch andere Dinge tun, wie z.B. Rechtschreibprüfung oder Abfragevorschläge, die Menge der in einem Feld indizierten Begriffe oder die Begriffsvektoren (Begriffshäufigkeitsstatistiken) zurückgeben, um nur einige zu nennen. Die Schnittstelle SearchComponent definiert eine Reihe von Methoden, von denen eine – prepare( ) – von allen Komponenten in einer Suchhandler-Kette ausgeführt wird, bevor die Anfrage verarbeitet wird. Wenn Sie angeben, dass eine Nicht-Standard-Komponente in der Liste der „ersten Komponenten“ steht, wird sie ausgeführt, bevor die Abfrage von der nachgeschalteten QueryComponent an den Index gesendet wird. Dadurch haben diese frühen Komponenten die Möglichkeit, die Abfrage zu ändern, bevor sie von der Lucene-Engine ausgeführt (oder an andere Shards in der SolrCloud verteilt) wird. Die QueryAutoFilteringComponent erstellt ein Mapping von Termwerten auf die Indexfelder, die sie enthalten. Sie verwendet den Lucene UnivertedIndex und die Solr TermsComponent (im SolrCloud-Modus), um diese Zuordnung zu erstellen. Diese „umgekehrte“ Zuordnung von Termwert -> Indexfeld wird dann verwendet, um herauszufinden, ob ein Teilsatz innerhalb einer Abfrage einem bestimmten Indexfeld zugeordnet ist. Wenn dies der Fall ist, wird – je nach Konfiguration – eine Filterabfrage (fq) oder eine Boost-Abfrage (bq) aus diesem Feld:Wert-Paar erstellt und wenn das Ergebnis eine Filterabfrage sein soll, wird der Wert aus der ursprünglichen Abfrage entfernt. Das Ergebnis ist eine Reihe von Abfrageausdrücken für die Phrasen, die in der ursprünglichen Abfrage identifiziert wurden. Ein Beispiel soll dies noch deutlicher machen. Angenommen, wir haben die folgenden Datensätze indiziert:

Field:         color       product_type         brand

Record 1:      red         shoes
Record 2:      red         socks
Record 3:      brown       socks
Record 4:      green       socks                red lion
Record 5:      blue        socks                red lion
Record 6:      blue        socks                red dragon
Record 7:                  pizza                red baron
Record 8:                  whiskey              red label
Record 9:                  smoke detector       red light
Record 10:                 yeast                red star
Record 11:                 red wine             gallo
Record 12:                 red wine vinegar     heinz
Record 13:                 red grapes           dole
Record 14:                 red brick            acme
Record 15:                 red pepper           dole
Record 16:                 red pepper flakes    mccormick

Dieses Beispiel ist zugegebenermaßen etwas konstruiert, da der Begriff „rot“ absichtlich mehrdeutig ist – er kann als Farbwert oder als Teil einer marken- oder produkttypbezogenen Phrase auftreten. Mit dem OOTB Solr /select Handler bringt eine Suche nach „red lion socks“ also alle 16 Datensätze zurück. Mit der QueryAutoFilterComponent werden jedoch nur 2 Ergebnisse (4 und 5) für diese Abfrage zurückgegeben. Außerdem bringt die Suche nach „Rotwein“ nur einen Datensatz zurück (11), während die Suche nach „Rotweinessig“ nur den Datensatz 12 zurückbringt. Der Filter gleicht Begriffe mit Feldern ab und versucht, die längsten zusammenhängenden Phrasen zu finden, die den zugeordneten Feldwerten entsprechen. Bei der Abfrage „rote Löwensocken“ wird also zunächst festgestellt, dass „rot“ eine Farbe ist, aber dann wird festgestellt, dass „roter Löwe“ eine Marke ist, und dies wird die kürzere Übereinstimmung, die mit „rot“ beginnt, verdrängen. Ähnlich verhält es sich mit „Rotweinessig“: Zuerst wird „rot“ == Farbe gefunden, dann „Rotwein“ == Produkttyp, dann „Rotweinessig“ == Produkttyp und die letzte Übereinstimmung gewinnt, weil sie die längste zusammenhängende Übereinstimmung ist. Das funktioniert auch feldübergreifend. Wenn die Abfrage „blaue rote Löwensocken“ lautet, stellt das System fest, dass „blau“ eine Farbe ist, und dass „blau rot“ nichts ist. Es wird dann, wie zuvor, feststellen, dass „roter Löwe“ eine Marke ist, „rote Löwensocken“ ablehnen, was nichts bedeutet, und schließlich feststellen, dass „Socken“ ein Produkttyp ist. Aus diesen drei Feldübereinstimmungen wird eine Filter- (oder Boost-) Abfrage mit der entsprechenden Zuordnung von Feldname zu Feldwert konstruiert. Das Ergebnis von all dem ist eine Übersetzung der Solr-Abfrage:

q=blau rote Löwensocken

zu einer Filterabfrage:

fq=color:blue&fq=brand: „red lion“&fq=product_type:socks

Diese letzte Abfrage liefert nur 1 Ergebnis im Gegensatz zu 16 für den ungefilterten Fall. Mit anderen Worten: Wir haben die Genauigkeit von 6,25% auf 100% erhöht!

Groß-/Kleinschreibung und Synonymunterstützung hinzugefügt:

Eines der Probleme bei der Verwendung von Zeichenkettenfeldern als Quelle von Metadaten für Substantivphrasen ist, dass sie nicht analysiert werden (wie oben beschrieben). Dies schränkt die Menge der Benutzereingaben ein, die übereinstimmen können – ohne Änderungen muss der Benutzer genau das eingeben, was indiziert wird, einschließlich Groß- und Kleinschreibung und Pluralität. Um dieses Problem zu lösen, wurde der QueryAutoFilteringComponent Unterstützung für grundlegende Textanalysen wie Groß-/Kleinschreibung und Stemming (Singular/Plural) sowie Unterstützung für Synonyme hinzugefügt. Dies erhöht zwar die Komplexität des Codes etwas, ermöglicht es dem Filter aber, synonyme Ausdrücke in der Abfrage zu erkennen, wie z.B. „couch“ oder „lounge chair“, wenn „Sofa“ oder „Chaise Lounge“ indiziert wurden. Eine andere Sache, die auf Anwendungsebene hilfreich sein kann, ist die Entwicklung eines Suggestors für Typeahead- oder Autocomplete-Schnittstellen, der die Solr-Terms-Komponente und Facet-Maps verwendet, um einen Suggestor mit mehreren Feldern zu erstellen, der Benutzer zu präzisen und umsetzbaren Abfragen führt. Ich hoffe, dass ich in naher Zukunft einen Beitrag zu diesem Thema veröffentlichen kann.

Quellcode

Für diejenigen, die sich dafür interessieren, wie die Autofilter-Komponente funktioniert oder die sie in Ihrer Suchanwendung verwenden möchten, sind der Quellcode und die Design-Dokumentation auf github verfügbar. Die Komponente wurde auch bei Solr eingereicht(SOLR-7539, wenn Sie sie verfolgen möchten). Der Quellcode auf github liegt in zwei Versionen vor, von denen eine mit Solr 4.x kompiliert und ausgeführt werden kann und die andere die neue UninvertingReader API verwendet, die in Solr 5.0 und höher verwendet werden muss.

Schlussfolgerungen

Die Komponente QueryAutoFilteringComponent kann viel mehr als die einfache Implementierung, die im vorherigen Beitrag vorgestellt wurde. Wie im vorherigen Beispiel verwandelt sie eine Freiformabfrage in eine Reihe von Solr-Filterabfragen (fq) – wenn sie kann. Dadurch werden Ergebnisse eliminiert, die nicht mit den Werten der Metadatenfelder (oder ihren Synonymen) übereinstimmen, und es ist eine Möglichkeit, eine hohe Präzision zu erreichen. Eine andere Möglichkeit besteht darin, die „Boost-Abfrage“ oder bq anstelle von fq zu verwenden, um die präzisen Treffer an die Spitze zu bringen, andere Treffer aber in der Ergebnismenge zu belassen. Sobald kontextbezogene Phrasen identifiziert sind, können wir Dokumente boosten, die diese Phrasen in den identifizierten Feldern enthalten (eines der Henne-Ei-Probleme beim Boosting zur Abfragezeit besteht darin, zu wissen, welche Feld/Wert-Paare zu boosten sind). Der Boosting-Ansatz ist möglicherweise sinnvoller für herkömmliche Suchanwendungen, die auf Laptops oder Workstations betrachtet werden, während der Ansatz der Filterabfrage wahrscheinlich eher für mobile Anwendungen sinnvoll ist. Die Komponente enthält einen konfigurierbaren Parameter „boostFactor“, der, wenn er gesetzt ist, bewirkt, dass sie im Boost-Modus arbeitet, so dass Datensätze mit exakten Übereinstimmungen in identifizierten Feldern gegenüber Datensätzen mit zufälligen oder teilweisen Token-Treffern geboostet werden.