Alai

W 2004 roku Microsoft Research i zespół Microsoft Web Search rozpoczęły wspólne działania mające na celu poprawę trafności naszych wyników wyszukiwania w sieci. W ciągu następnych kilku lat trwały intensywne prace, które zaowocowały opracowaniem trzech generacji algorytmów rankingowych do wyszukiwania w sieci, których kulminacją są zespoły drzew wspomaganych, używane obecnie w wyszukiwarce Bing. Pierwszy z tych algorytmów rankingowych nazwaliśmy RankNet. Ostatnio papier RankNet, który został opublikowany w International Conference on Machine Learning (ICML) w 2005 roku, wygrał nagrodę ICML „Test of Time”, nagrodę przyznawaną co roku temu pojedynczemu papierowi przedstawionemu na konferencji dziesięć lat wcześniej, który został oceniony jako mający największy ogólny wpływ akademicki w ciągu tych lat. Jest to wielki zaszczyt, ale także okazja, aby spojrzeć wstecz i ocenić nasz postęp w ciągu ostatniej dekady. W tym artykule, chciałbym opowiedzieć tę historię.

Wyszukiwanie w sieci działa zasadniczo biorąc zapytanie użytkownika i oceniając znaczenie każdego zindeksowanego dokumentu do niego. Nie każda strona internetowa jest w indeksie, ale indeks mimo to zawiera setki miliardów dokumentów, przechowywanych w specjalnej strukturze danych, aby szybko wyszukiwać. Ponieważ najlepsze wyniki muszą być przedstawione użytkownikowi w ciągu kilkuset milisekund, wymaga to niezwykle wydajnego procesu filtrowania i tworzenia rankingu. Opisane tutaj rankingi działają na (wciąż dużym) podzbiorze dokumentów, wybranym za pomocą tego szybkiego procesu wstępnego filtrowania. Zasadniczo, rankinger działa na podstawie listy liczb, z których każda mierzy jakość dopasowania zapytanie/dokument w jeden szczególny sposób (na przykład, liczba binarna reprezentująca czy zapytanie zawiera słowo w tytule dokumentu czy nie). Następnie rankinger mapuje tę listę liczb do pojedynczej miary trafności, która jest następnie używana do uszeregowania wszystkich dokumentów dla danego zapytania. Uporządkowana lista liczb, które rankinger mapuje do pojedynczego wyniku, nazywana jest wektorem cech.

Tak więc, gdy jest używany w trybie runtime, dla danego zapytania, rankinger bierze wektor cech dla każdej pary zapytanie/dokument i mapuje go do liczby, która oddaje istotność tego dokumentu dla zapytania. RankNet jest modelem sieci neuronowej typu feedforward. Zanim będzie mógł być użyty, jego parametry muszą być nauczone przy użyciu dużej ilości oznaczonych danych, zwanych zbiorem treningowym. Zbiór treningowy składa się z dużej liczby par zapytanie/dokument, gdzie dla każdej pary, liczba oceniająca jakość relewancji dokumentu do zapytania jest przypisywana przez ludzkich ekspertów. O ile etykietowanie danych jest zadaniem powolnym i wymagającym udziału człowieka, o tyle trening sieci na danych etykietowanych jest w pełni zautomatyzowany i dość szybki. System użyty przez Microsoft w 2004 roku do trenowania rankera nosił nazwę The Flying Dutchman. Stwierdziliśmy, że podczas gdy The Flying Dutchman potrzebował kilku dni i klastra, aby stworzyć wytrenowany model, RankNet był w stanie stworzyć model rankingowy w zaledwie kilka godzin przy użyciu tylko jednej maszyny. RankNet dał również znacznie lepszą trafność niż poprzednio używany ranker, ponieważ sieci neuronowe mogą modelować bardzo szeroki zakres możliwych mapowań, podczas gdy poprzedni system był ograniczony tylko do mapowań liniowych.

Jak dotąd wszystko dobrze, ale czy mogliśmy to zrobić lepiej? Odpowiedź brzmi: tak, ale aby zobaczyć dlaczego, muszę wyjaśnić, jak RankNet jest szkolony. Dla każdego zapytania w zestawie szkoleniowym, dla każdej pary dokumentów do rankingu dla tego zapytania, RankNet jest pokazany dwa wektory cech, a następnie dostosowuje swoje parametry trochę, przy użyciu metody zwanej Stochastic Gradient Descent (SGD), tak, że dostosowane wyniki wyjściowe dla dwóch cech poruszają się we właściwym kierunku – to znaczy, wynik dla bardziej istotnego dokumentu wzrasta, a że mniej, spada. Oznacza to jednak, że RankNet będzie ciężko pracował, aby podnieść wysoko punktowane dokumenty, które są bardzo nisko w rankingu, a także aby obniżyć wysoko punktowane, ale mniej istotne dokumenty. Wydając swoje zasoby w ten sposób, nie poświęca tyle uwagi, ile powinien, tylko kilku najwyższym linkom, które są pokazywane użytkownikowi. W rzeczywistości, w tamtym czasie, naszą metryką oceny był wynik zwany NDCG, który daje pojedynczą liczbę oceniającą ogólną jakość rankingu, z dużo większym naciskiem na kilka najlepszych wyników, które są pokazywane użytkownikowi. NDCG jest więc bardziej naturalną miarą dla wyszukiwania w sieci niż błąd parami. Postawiło to przed nami wyzwanie: SGD sprowadza się do wyszukiwania w przestrzeni ciągłej, natomiast NDCG jest zasadniczo miarą dyskretną, w której wartość zmienia się tylko wtedy, gdy co najmniej dwa dokumenty zmieniają pozycję na liście rankingowej. Wystarczająco małe zmiany w punktacji modelu nie dają żadnych zmian w NDCG, a ponieważ SGD działa poprzez eksplorację małych zmian w punktacji, trudno sobie wyobrazić, jak zoptymalizować NDCG za pomocą SGD.

Znaleźliśmy odpowiedź na tę zagadkę, którą nazwaliśmy LambdaRank. Sztuczka polegała na zauważeniu, że cała procedura szkolenia dla sieci neuronowej potrzebuje tylko gradientów funkcji kosztu, a nie samej funkcji kosztu. Możesz myśleć o tych gradientach jak o małych strzałkach dołączonych do każdego dokumentu na liście rankingowej, wskazujących kierunek, w którym chcielibyśmy, aby te dokumenty się poruszały. LambdaRank po prostu wziął gradienty RankNet, o których wiedzieliśmy, że działają dobrze, i przeskalował je przez zmianę w NDCG znalezioną przez zamianę każdej pary dokumentów. Stwierdziliśmy, że to szkolenie wygenerowało modele ze znacznie poprawioną trafnością (mierzoną przez NDCG) i miało dodatkowy bonus w postaci odkrycia kolejnej sztuczki, która poprawiła ogólną szybkość szkolenia (zarówno dla RankNetu, jak i LambdaRanku). Ponadto, co zaskakujące, znaleźliśmy empiryczne dowody (zobacz również ten artykuł), że procedura szkolenia faktycznie optymalizuje NDCG, mimo że metoda, choć intuicyjna i rozsądna, nie daje takiej gwarancji.

Jak dotąd tak dobrze, ale znowu, czy mogliśmy to zrobić lepiej? Odpowiedź znów brzmiała Tak. Wiedzieliśmy o klasie modeli zwanych boosted tree ensembles, które były znane z tworzenia bardzo silnych klasyfikatorów wieloklasowych. Co się stanie, jeśli potraktujemy problem rankingu jako problem klasyfikacji wieloklasowej, z jedną klasą dla każdego z pięciu poziomów istotności zidentyfikowanych w zbiorze treningowym? Stwierdziliśmy, że daje to lepsze wyniki niż LambdaRank (szczególnie w przypadku klasyfikacji rzędowej wieloklasowej). Drzewa boostowane mają tę dodatkową zaletę, że mogą łatwo obsługiwać cechy kategoryczne i inne rodzaje cech dyskretnych, które są gorzej przystosowane do sieci neuronowych. Wierzyliśmy, że te wyniki były spowodowane lepszym dopasowaniem tej klasy modeli do naszych danych, więc naturalnym pytaniem było, czy możemy połączyć modele drzew boostowanych z ideą LambdaRank, aby uzyskać to, co najlepsze z obu światów? Trening modelu drzew boostowanych może być również postrzegany jako forma SGD, więc odpowiedź brzmiała tak, w postaci modelu, który nazwaliśmy LambdaMART. LambdaMART miał dodatkową zaletę: trening modeli zespołów drzew może być bardzo znacząco przyspieszony w stosunku do odpowiednika w postaci sieci neuronowej (ta praca, prowadzona przez O. Dekela, nie jest jeszcze opublikowana). Dzięki temu możemy trenować z dużo większymi zestawami danych, co znów daje lepszą dokładność rankingów.

Jak nasze rankingi wypadają na tle innych w branży? W 2010 r. firma Yahoo! zorganizowała konkurs learning to rank, którego celem było sprawdzenie, kto ma najlepszy algorytm rankingowy w wyszukiwarkach internetowych. Do udziału w wyzwaniu zarejestrowało się 1055 zespołów. Nasz zespół wygrał wyzwanie, używając zespołu modeli LambdaMART.

Patrząc wstecz na ostatnią dekadę, być może najbardziej znaczącą lekcją techniczną jest znaczenie szybkości szkolenia. Szybsze szkolenie pozwala zarówno na więcej eksperymentów, jak i na wykorzystanie większych zbiorów danych. Wierzę, że te dwa czynniki są w końcu ważniejsze niż stosowane algorytmy, o ile te ostatnie są wystarczająco wyrazistymi modelami dla danego zadania. Inną „lekcją życia”, jaką wyciągnąłem z tego doświadczenia, jest znaczenie wytrwałości, ale przede wszystkim znaczenie daru, jakim jest możliwość pracy ze wspaniałymi kolegami, w grupach produktowych, w Microsoft Research i w środowisku akademickim.

Chris Burges jest głównym badaczem i kierownikiem badań w Microsoft Research, gdzie pracuje od 2000 roku. Wcześniej pracował w AT&T Bell Labs, do którego dołączył w 1986 roku. Wcześniej był postdoktorantem w Departamencie Fizyki Teoretycznej MIT, do którego dołączył po uzyskaniu doktoratu z fizyki w Brandeis, po uzyskaniu dyplomu z wyróżnieniem pierwszej klasy z fizyki i matematyki w Oxfordzie. Jego zainteresowania obejmowały inżynierię systemów dużych sieci komunikacyjnych (AT&T wciąż używa jego algorytmów do routingu kilku kluczowych sieci), sieci neuronowe do rozpoznawania pisma ręcznego i druku maszynowego (pracował nad systemem używanym obecnie do odczytywania milionów czeków dziennie, a tak naprawdę jego długie zejście do uczenia maszynowego zostało zapoczątkowane przez szczególnie fajne demo sieci neuronowej rozpoznającej odręczne cyfry na początku lat 90-tych), maszyny wektorów podporowych (miał szczęście pracować z Vladimirem Vapnikiem, współtwórcą SVM, we wczesnych latach i napisał tutorial, który niektórym się spodobał), audio fingerprinting (jego praca jest obecnie używana w Xbox i Windows Media Player do identyfikacji muzyki), weryfikacja mówców, wyszukiwanie informacji i ranking (jego algorytm rankingowy jest obecnie używany przez Bing do wyszukiwania stron internetowych). Obecną pasją Chrisa jest opracowywanie nowych podejść do skalowalnego, możliwego do zastosowania w praktyce maszynowego rozumienia tekstu, które, choć jest szalenie ambitne, może nas czegoś nauczyć, o ile nie przestaniemy próbować. Chris był współprzewodniczącym programowym Neural Information Processing Systems 2012 oraz współprzewodniczącym generalnym NIPS 2013.

Więcej wiadomości na temat badań w dziedzinie informatyki można znaleźć na stronie ResearchNews.com.

.