Našeptávač: šikovný rádce, který má na práci 50 milisekund

Co je našeptávač a k čemu slouží

Na našeptávač uživatel narazí, když začne psát svůj dotaz do hledacího pole. Jde o nabídku dotazů, které může prokliknutím rovnou vyhledat, aniž by musel pokračovat v psaní.

Jeho cílem je usnadnit zadávání dotazu tím, že se snaží „uhádnout“ dotaz, který chce uživatel položit, a nabídnout ho k vyhledání na jedno kliknutí. Šetří tak čas a energii potřebnou na zadání dotazu.

Druhou důležitou funkcí našeptávače je navádění na výsledky hledání, u kterých předpokládáme vyšší informační kvalitu. Celkově vzato víme, že uživatelé, kteří svůj dotaz položí pomocí našeptávače, jsou s výsledky hledání spokojenější než ti, kteří dotazy zadají ručně.

Třetím základním úkolem našeptávače je lidem při hledání poradit. Ne vždy totiž uživatel ví přesně, co hledá, nebo potřebuje poradit s gramatikou. Tuto funkci plníme jak prací s překlepy a zajištěním rozmanitosti „našeptaných” dotazů, tak obsáhlou databází čítající miliony dotazů.

Jak našeptávač funguje

V první řadě rychle. Aby byla funkce našeptávání člověku při psaní k užitku, musí se nabízené dotazy měnit stejně rychle, jako uživatel píše. Ve špičkách musí  server, který našeptávač obstarává, umět odpovědět až 2500krát za sekundu a v 95 % případů se tak musí stát do 130 ms. Průměrně odpovídáme do 50 ms, tedy stejně rychle, jako trvá mrknutí oka.

Největší část prostředků je ale vynaložena na to, aby se objevovaly v danou chvíli pro daného uživatele a v daném kontextu co nejužitečnější dotazy. V ideálním případě, kdyby uměl našeptávač číst myšlenky, dařilo by se vždy nabídnout k prokliknutí přesně ten dotaz, který se chystá člověk zadat. Bohužel, nebo bohudík, zatím tyto technologie nemáme, a tak si musíme vystačit s tím, co nám nabídne strojové učení na základě dostupných dat.

Abychom co nejlépe poznali, jaký dotaz se snaží uživatel zadat, řídíme se informacemi, které pro každý dotaz máme k dispozici. Je to například: jak často dotaz lidé hledají, jestli se dotaz vztahuje ke konkrétnímu místu, jaká je poloha uživatele, jaké jsou poslední dotazy, které hledal, a řada dalších.

Tím ale práce nekončí. Pokud bychom uživateli přímočaře nabídli dotazy, které mají jen nejvyšší skóre, pravděpodobně bychom dostali na písmeno „f” dotaz „facebook” na šest způsobů. Například „facebook přihlášení”, „facebook přihlásit”, „facebook login” a podobně. To by asi pro naše uživatele moc užitku neneslo, jelikož by celý našeptávač byl v podstatě obsazený dotazy o stejném významu, a tedy stejném nebo velmi podobném výsledku hledání. Abychom tomuto zamezili, dotazy tzv. clustrujeme. To znamená, že podobné dotazy dáváme do skupinek a z každé skupinky vybereme jen jednoho zástupce, který má nejvyšší skóre, a to třeba „facebook přihlášení”. Tím je zajištěno, že uživateli nabídneme významově rozmanité dotazy a máme větší šanci, že trefíme, co uživatel skutečně hledá.

Další způsob, jakým se snažíme navést uživatele na výsledek, se kterým bude spokojený, je zobrazování obrázku a popisku u dotazů, pro které víme, že máme kvalitní odpověď.

Autor: Michal Veselý

Techničtější pohled

Co vše se tedy během zmíněných 50 milisekund stane?

Jak jsme viděli výše, základní fungování našeptávače se dá popsat poměrně jednoduše: „Na tento rozepsaný dotaz (tj. pár písmen, tzv. „prefix”) vraťme šest dotazů s nejvyšším skóre.” Skutečnost je ale o něco komplikovanější, jak je vidět na poměrně hodně zjednodušeném diagramu níže. Diagram se dá rozdělit na dvě hlavní části: tvorba databáze dotazů na jedné straně a jejich výdej na druhé.

Autor: Michal Veselý

Tvorba databáze uživatelských dotazů

Aby bylo z čeho „brát”, je potřeba dotazy sbírat. Našeptávač to dělá jednoduše, od uživatelů. V momentě, kdy člověk napíše dotaz, tak si ho uložíme do logů. Dotazy se ale často vyskytují s vlastnostmi, se kterými se špatně pracuje. Například s velkými a malými písmeny, diakritikou, chybnými znaky, obsahují NSFW výrazy a podobě. Jako první krok je tedy potřeba je prohnat normalizační magií, která je těchto neduhů zbaví, ale zároveň nás nepřipraví o cenné informace. Druhým krokem je ohodnocení bodovým skóre (suggest score) podle jejich hledanosti. Tyto operace se dějí ve druhém kroku v komponentě zvané Suggest Generátor.

Aby měl našeptávač co největší slovní zásobu, čerpáme kromě dotazů od uživatelů také z dalších zdrojů. Těmi jsou například služby jako Zboží.cz nebo Firmy.cz, Wikipedie a další. Třetím krokem v cestě dotazu je potom jejich sloučení a obohacení o další informace pomocí Global Suggest Jobu.Odtud se už čistá data, spojená ze všech zdrojů a ohodnocená suggest score, uloží do Elastic DB.

Jak je z popisu vidět, našeptávač ukládá pouze ty dotazy, které uživatel zadá ručně. Tuto výjimku porušuje pouze uživatelská historie, která se ukládá, i když je vybrána z nabídnutých dotazů (nášeptů) pro každého uživatele.

Suggest scóre je číslo, které reprezentuje, kolikrát byl dotaz hledaný. Abychom zohlednili změny chování lidí v čase, toto skóre se každý den o něco zmenší.

Výdej doporučených dotazů na napsaný prefix

Výdej je o kousek přímočařejší. Uživatelem napsaný prefix putuje do Elastic DB. Ten vrátí předvýběr všech vhodných kandidátů a „podá” je Suggest serveru. Jeho úkolem je potom z předvýběru vybrat finálních šest kandidátů s ohledem na všechny informace, které má o nášeptech a uživateli k dispozici. Jelikož složitost a množství informací a dat, se kterými je potřeba při výběru počítat, neustále roste, používáme zde strojové učení, jehož silnou stránkou je právě schopnost zohledňovat velké množství parametrů a lépe najít nejlepších šest nášeptů, než by to udělal člověk pomocí „tvrdých” pravidel.

Poloha uživatele

Informace o poloze je jednou z klíčových funkcí, která zlepšuje relevanci. Aby fungovala, je potřeba mít informaci o poloze k dotazům, které kandidují na zobrazení uživateli, a zároveň musíme znát polohu uživatele. Příkladem může být například dotaz „zoo liberec”, ke kterému jeho zpracováním na komponentě CQP (Central Query Processor) zjistíme, že „zoo liberec”se nachází v Liberci. Pokud se uživatel taktéž nachází v Liberci, je pravděpodobné, že se mu nášept zobrazí mnohem dříve, při menším počtu napsaných znaků než například jinému uživateli v Opavě.

Druhý typ využití polohy dotazu je v principu jednoduchá „hitparáda” popularity dotazů podle segmentů republiky. Například v zimě se na Vysočině lidé na prefix „jak” budou spíše ptát „jak efektivně odházet metr sněhu” a v Praze na stejný prefix „jak” to bude „jak neuklouznout na náledí”.

Pro oba tyto výpočty používáme mapu České republiky rozdělenou do oblastí podle počtu hledání, přičemž počty hledání víceméně odpovídají hustotě osídlení. Ve velkých městech jsou tedy oblasti menší než například na horách.

Autor: Michal Veselý

Zajímavá čísla

• průměrná doba odpovědi 50 ms
• 200 000 000 záznamů v historii uživatelů
• celková velikost databáze 500 GB

Technologie

• S3 (storage)
• Hadoop (framework)
• Spark (framework)
• Kafka (message broker)
• KafkaStreams (framework)
• Kotlin (jazyk)
• Scala (jazyk)
• Gradle (build system)
• Python (jazyk)
• Fastapi (framework)
• Elasticsearch (databáze)
• Redis (databáze/cache)

Autor: Michal Veselý

Co je nového a co plánujeme

Vylepšování našeptávače se často věnuje i seznamácké oddělení výzkumu. Za jejich pomoci se do systému povedlo zapojit strojové učení v podobě boostovaných lesů. Tím se usnadnilo přidávání nových funkcí našeptávače, což se děje často.

Z dílny výzkumu pochází i řešení, co dělat, když našeptávači „dojde dech” a neví, co by našeptal dál. V takovém případě se nedokončený dotaz doplní nejpravděpodobnějším dalším slovem, které se v češtině za napsaným slovem vyskytuje. Jsou to takzvané n-gramy a funkci jsme pojmenovali došeptávač. Je to slibná oblast pro další výzkum i vývoj, jelikož jednoduchým zvyšováním počtu slov n-gramu se nedá daleko dostat z důvodů náročnosti na výpočetní výkon.

Nedávno se také zkoumalo, jaké jsou možnosti personalizace našeptávače a v čem by pomohlo, pokud by pracoval s kontextem posledního zadaného dotazu uživatele. Aktuálně se snažíme zvýšit jeho slovní zásobu, aby dokázal pomáhat uživatelům ještě častěji a v ještě složitějších méně častých dotazech.

Různá řešení se porovnávají dvojím způsobem. Jednak na offline metrikách, tj. měřením úspěšnosti na fixovaném historickém vzorku dat, a později se u slibných přístupů analyzuje chování uživatelů na reálných datech v AB testech.

Strojové učení

Co umí, co ne a jaká jsou častá úskalí strojového učení?

Jak už bylo zmíněno, využití strojového učení v našeptávači spočívá v zapojení modelu, který na základě vstupních informací vybere a seřadí top N kandidátů, které se mají uživateli zobrazit. Velkým přínosem je, že model si určuje pravidla sám a optimálně dle dat. Zatímco manuálně určených pravidel je jen několik, model si může určit „neomezené“ množství pravidel. Zároveň, pokud se chování uživatelů/dat změní, stačí přeučit model a pravidla se aktualizují. Mírná nevýhoda je, že aktualizace lze provádět pouze na historických datech a nelze optimalizovat pro budoucí chování (například na Vánoce se uživatelé chovají jinak než v létě, víme to, ale je těžké na to model připravit).

Při zapojení modelu jsme se setkali s několika problémy. Jako první jsme řešili, na jakých datech vlastně takový model trénovat. Při tvorbě trénovacích dat jsme si úlohu mírně zjednodušili. Předpokládáme, že jakmile uživatel vidí našeptaný dotaz, který má na mysli, bude na něj klikat. Takto to ale ve světě nechodí, uživatel ke spokojenosti často vyžaduje návrh na prvním místě. Model je tím pádem limitován tím, že předpokládáme nějaké uživatelské chování, které má svá omezení. Krásný příklad byl problém, když se po nasazení náš model nechoval v provozním A/B testu tak dobře jako v offline metrikách. Přišli jsme na to, že v trénovacích datech nám chyběl příklad uživatelského chování „potvrzování si dotazu“, kdy si uživatel ručně napsal celý dotaz a na závěr na stejný dotaz klikl v našeptávači.

Aby se model správně naučil to chování, které po něm požadujeme, je potřeba mít dobře promyšlené a definované, jaký úkol má model vůbec řešit. Hledaný dotaz považujeme za „svatý grál" a snažíme se ho dostat na co nejvyšší pozici. Nejdříve jsme tedy k této úloze přistoupili jako ke klasifikaci, kde kandidáti mají label, který je stejný jako hledaný dotaz = 1 / je jiný = 0. Tento přístup se nám neosvědčil, dokonce model našeptával hůř než původní pravidlové řešení. Proto jsme se rozhodli jít cestou řadicího úkolu, který se nám zdál být vhodnější. Párový CatBoost model učený pomocí loss funkce PairLogit dosahoval dobrých výsledků na testovacích metrikách, přičemž páry byly tvořeny tak, aby vždy obsahovaly správný a nesprávný kandidát. Nejvíce se osvědčil rankovací XGBoost model učený na MAP (Mean Average Precision). Tento model se naučil nejen vytahovat správného kandidáta mezi top N, ale na rozdíl od párového Catboost modelu ho dával i na co nejvyšší pozici.

Další omezení je, že jeden z nejvýživnějších signálů modelu je popularita dotazu, s čímž souvisí, že jsme omezeni na dotazy zadávané uživateli a jakékoli externí zdroje budou přirozeně znevýhodněny. Mnoho autorů se snažilo od popularity dotazu oprostit, nicméně v našeptávání je stále nejdůležitější.

E​​konomika a proces vývoje produktu

Na začátku celého procesu stojí produktové zadání. To obvykle začíná hypotézou ve formě „Pokud bychom X, mohli bychom uživatelům lépe Y.”Hypotézu je potom dobré ověřit na datech. Tedy, najít taková čísla, která ji buď potvrzují, nebo vyvracejí. Toto ověření také pomůže udělat si představu, jak velkému množství uživatelů nová funkce pomůže.

Druhým krokem je návrh a detailnější popis funkcionality a sepsání do tzv. „ticketu”. Ten může obsahovat pouze textový popis nové funkce, nebo je k němu přidaná grafika návrhu nové funkce.

Pokud nová funkcionalita vyžaduje implementaci nové technologie, se kterou zatím vývoj nemá zkušenosti, je druhým krokem konzultace s výzkumným týmem. Ten principiálně funguje stejně jako vývojový tým, ale jejich agenda je vyzkoumat, jakou technologii a jak použít. To se může týkat všeho od návrhů algoritmů, přes vybírání správných modelů strojového učení a jejich naučení, po prozkoumávání exotických řešení a studium vědeckých prací. Poslední projekty, které jsme takto řešili, se týkaly hlavně zapojení strojového učení a nových signálů pro personalizaci, trendovost, překlepovost a další.

Zadání je dále konzultováno s vývojáři, kteří odhadnou jeho náročnost a snaží se domyslet všechny možné důsledky a problémové situace, které by mohly při implementaci nastat. Tyto problémy pak konzultujeme s produktovým manažerem a společně hledáme cestu, jak funkcionalitu implementovat co nejlépe.

Ve chvíli, kdy je projekt připravený, dochází na vlastní vývoj. Projekt si tedy přebírá vývojářský tým. Produktový manažer vystupuje jako jakási nápověda pro případy, kdy není jasné zadání. Zároveň se s ním diskutují komplikace v projektu a možnosti řešení. Celý vývoj probíhá podle SCRUM metodiky. Práci tedy rozpadáme a plánujeme na sprinty, denně si povídáme na stand-upech, co je u koho nového a kdo s čím potřebuje pomoci či poradit. To pomáhá udržet přehled nad tím, jak se projekt vyvíjí, projekty posouvat kupředu, a zároveň být dostatečně pružní, pokud je potřeba něco změnit nebo upravit.

Po vyvinutí následuje testování „v baráku” a poté testování na uživatelích. O tom je další kapitola A/B testování.

Všechny projekty jsou součástí většího celku, kterému se říká kvartální plán a cíl. Ten se, jak název napovídá, stanovuje kvartálně a slouží jako „zapíchnutý kolík”, nebo maják, podle kterého se v průběhu kvartálu produktové a vývojové týmy orientují.

Proces se dá shrnout do několika bodů:

1. Produktové zadání: uživatel je středem všeho
2. Diskuze s výzkumem
3. Diskuze s vývojem
4. Náklady, přínos, peníze nebo ušetřené náklady a poměr cena/výkon
5. Čas, synchronizace a plánování
6. Vývoj, standupy, SCRUM – potkáme se a popovídáme
7. Cíle a jejich plnění
8. Cesta minimálního produktu – osekávání, MVP, „Kdyby to zítra mělo být…”

A/B testování, aneb „Udělali jsme to, co jsme chtěli?”

Jak se říká: „Co neměříš, to neřídíš.“ Proto na našeptávači máme širokou a stále rostoucí sadu čísel (metrik), pomocí kterých umíme vyhodnotit, jestli a do jaké míry se celkově daří uživateli pomáhat a jestli nová funkce „dělá, co má”. Sledujeme například míru interakce s našeptávačem, kolik znaků uživatelům šetříme a mnoho dalších.

Kromě sledování postupného vývoje metrik v čase pro vyhodnocení přínosu nových funkcí a vylepšení používáme metodu A/B testování a automatizovaného vyhodnocování. Díky tomu jsme schopni vyvinutou funkci velmi rychle dostat mezi lidi na vyzkoušení a hned po testu vyhodnotit a rozhodnout o nasazení nebo dalších úpravách.

Máte-li metriky i schopnost je jednoduše porovnávat pro každou novou funkci, dalším logickým krokem je tento proces automatizovat a co nejrychleji zjišťovat, jestli nová funkce lidem při hledání pomáhá, nebo spíše škodí. Jelikož je ale potřeba pracovat se strojovým učením a s každou změnou model znovu „naučit”, vyvinuli jsme automatizovanou přeučovací pipeline, nebo chcete-li proces, který toto všechno zvládá „na jedno kliknutí”. Výsledkem tedy je, že vývojář nemusí trávit čas prací s modelem a přeučováním a může se místo toho věnovat zajímavějším implementačním úlohám. Práce se tím paralelizuje a významně (někdy i o dny až týdny) se zkracuje time-to-market.