Machine Learning w Ceneo

Autorzy tekstu: zespół developerski Ceneo.pl.

Wprowadzenie

W naszym serwisie Ceneo.pl użytkownicy mają możliwość wyszukiwania produktów, porównywania ich cen w różnych sklepach internetowych oraz zapoznania się z opiniami o produktach i sprzedawcach przed dokonaniem zakupu.

Z portalu korzysta 7 mln unikalnych użytkowników generując ponad 30 mln wizyt miesięcznie. Mają oni dostęp do bazy 10 milionów aktywnych produktów, które zawierają łącznie 45 milionów ofert z 6 000 polskich i zagranicznych sklepów. Baza łącznie zawiera 40 milionów produktów, które potencjalnie mogą pojawić się w ofercie sklepów.

Dziennie napływa ze sklepów średnio 100 tysięcy nowych ofert, dla których należy znaleźć pasujący produkt lub utworzyć nowy. Proces ten nazywamy integracją ofert.

Ewentualne błędy w realizacji tego zadania sprawiają, że nie jesteśmy w stanie dostarczyć użytkownikowi prawdziwych informacji. Tym samym uniemożliwiamy mu dokonanie najlepszego wyboru. Jeśli oferta trafi do niewłaściwego produktu, to porównanie jej ceny z innymi ofertami nie ma sensu. Jeśli dla oferty zostanie utworzony nowy produkt, gdy właściwy już istnieje, to niemożliwe będzie jej porównanie.

Jednym ze sposobów na łączenie oferty z produktem jest grupowanie po kodzie kreskowym (EAN). To unikalny identyfikator produktu. Niestety, ta metoda jest niewystarczająca z prostego powodu: nie wszystkie oferty posiadają uzupełniony kod EAN. W takiej sytuacji zostaje nam porównanie innych cech ofert, a w szczególności ich nazw.

Porównując nazwy ofert należy określić, które słowa są istotne i decydują o tym, że dana oferta odpowiada (lub też nie) danemu produktowi. Można próbować robić to ręcznie, ale jest to zadanie bardzo czasochłonne, narażone na błędy i przy naszej skali praktycznie niewykonalne.

Chcąc zautomatyzować i maksymalnie uprościć ten proces postanowiliśmy wykorzystać do tego celu Machine Learning.

Machine Learning

Uczenie maszynowe to zbiór algorytmów i technik umożliwiających znajdowanie i rozpoznawanie wzorców ukrytych w danych. Mają one zastosowanie w dziedzinach, w których rozwiązanie danego problemu wymaga analizy ogromnej ilości danych oraz wyciągania na ich podstawie wniosków. Dysponując odpowiednią próbką przykładowych danych (zbiorem treningowym) jesteśmy w stanie „nauczyć” komputer rozpoznawać skomplikowane wzorce i na ich podstawie podejmować właściwe decyzje.

Przykłady zastosowania uczenia maszynowego to: filtrowanie spamu, rozpoznawanie tekstu (OCR), rozpoznawanie mowy, diagnostyka chorób, itd.

Wśród technik uczenia maszynowego możemy wyróżnić dwie podstawowe grupy:

Uczenie nadzorowane (supervised) – polega na dostarczeniu do algorytmu uczącego przykładów posiadających przypisane etykiety. Na bazie tych danych tworzony jest model, który dla nowych, nieznanych wcześniej dla algorytmu danych wejściowych, powinien zwrócić odpowiednią etykietę. Przykładem uczenia nadzorowanego jest klasyfikacja.

Uczenie nienadzorowane (unsupervised) – w tym podejściu dane nie posiadają żadnych etykiet, a celem tej techniki jest rozpoznanie regularności w nich oraz przypisanie ich do odpowiednich grup, których liczba może być z góry określona lub wyznaczona w trakcie procesu uczenia. Przykładem jest analiza skupień (grupowanie).

Decyzja o wyborze odpowiedniego sposobu zależy od rozwiązywanego problemu oraz danych, którymi dysponujemy. W przypadku łączenia ofert z produktami postanowiliśmy użyć uczenia nadzorowanego. Posiadamy dużą bazę już istniejących ofert i mogą one posłużyć jako zbiór treningowy.

Klasyfikacja

Zadaniem klasyfikacji jest przypisanie obiektów o określonych cechach do pewnych, wcześniej zdefiniowanych grup (lub inaczej: klas). W naszym przypadku używamy klasyfikacji do tego, aby określić przynależność oferty do danego produktu.

Aby było to możliwe, konieczne jest najpierw nauczenie komputera rozpoznawania ofert i łączenia ich z produktami. W tym celu do algorytmu uczącego dostarczamy przykładowe oferty oznaczone jedną z etykiet:
1 – oznacza, że oferta należy do produktu
0 – oznacza, że oferta nie należy do produktu.
Zbiory te nazywamy odpowiednio pozytywnym i negatywnym.

Wynikiem procesu uczenia jest model klasyfikatora. Dla nowej oferty odpowie on 1, jeśli ta oferta pasuje do produktu. W przeciwnym wypadku zwróci 0.

Proces przeprowadzany jest w ten sam sposób dla wszystkich produktów.

Chcemy, aby system odpowiadał identyfikatorem produktu, więc konieczne jest zastosowanie jednej ze strategii używanych do budowy klasyfikatorów multi-class (czyli takich, które zwracają więcej wyników niż tylko binarne 1 i 0).

Możliwości są następujące:

One vs one – każdy model odpowiada za porównanie pary produktów. Odpytanie o wynik polega na dostarczeniu do wszystkich modeli danych nowej oferty, a klasa z największą liczbą odpowiedzi 1 traktowana jest jako wynik. Wadą tego podejścia jest duża liczba modeli.

One vs rest – dla każdej klasy uczony jest model, jako dane uczące oznaczone etykietą 1 (zbiór pozytywny) dostarczamy oferty należące do produktu, a wszystkie inne, nienależące do produktu, są oznaczone etykietą 0 (zbiór negatywny). Liczba modeli odpowiada liczbie klas. Wadą tego podejścia jest konieczność uczenia modelu z dużą liczbą przykładów negatywnych w zbiorze uczącym.

My zdecydowaliśmy się na one vs rest ze względu na mniejszą liczbę wynikowych modeli. Wprowadziliśmy jednak małą modyfikację polegającą na ograniczeniu zbioru negatywnych przykładów tylko do tych, które mają przynajmniej jedną wspólną cechę ze zbiorem pozytywnym. Dzięki temu uczenie trwa krócej.

Supported Vector Machines

Supported Vector Machines (SVM) – maszyna wektorów nośnych to rodzaj modelu, w którym w procesie uczącym wyznaczona zostaje hiperpłaszczyzna dzieląca przestrzeń na dwa obszary odpowiadające dwóm klasom problemu. Kryterium podziału zakłada, że przestrzeń pomiędzy pozytywnymi i negatywnymi próbkami, zwana marginesem, powinna być jak największa. Odpowiednio duży margines pozwala uniknąć błędów złej klasyfikacji.

O użyciu SVM w naszym rozwiązaniu zdecydowała duża szybkość uczenia oraz wysoka efektywność szczególnie w przypadku klasyfikacji tekstu.

Przebieg procesu uczenia maszynowego

Proces uczenia maszynowego składa się z kilku etapów:

I. Pozyskanie danych

Dane wykorzystywane w procesie uczenia pochodzą z bazy ofert. Oferty te wcześniej przeszły proces integracji i posiadają przypisany identyfikator produktu.

II. Przygotowanie danych

Machine learning uczy się z danych, dlatego bardzo ważne jest odpowiednie ich przygotowanie, zanim zostaną dostarczone do algorytmu. W naszym przypadku stosujemy w tym celu kilka technik:

1. Tokenizacja – nazwa oferty dzielona jest na pojedyncze słowa (tokeny).
2. Lowercasing – wszystkie duże litery zostają zamienione na małe.
3. Diacritics replacing – znaki diakrytyczne są zamieniane na ich odpowiedniki np. “ą” na “a”.
4. Stopwords filtering – wyrazy takie jak: “darmowa”, “dostawa”, “promocja” są usuwane, ponieważ są bez znaczenia i stanowią tylko zbędny szum.
5. Feature selection – jest to jeden z najważniejszych kroków, ponieważ ma on duży wpływ na jakość modelu. Polega on na wyborze tych cech, które najlepiej rozróżniają klasyfikowane obiekty. Jeśli pominiemy istotne cechy, to model będzie generował błędne wyniki. Jeśli dostarczymy za dużo cech, to możemy doprowadzić do przeuczenia modelu, czyli sytuacji, w której model odpowiada prawidłowo tylko dla przykładów użytych w trakcie trenowania lub wyciągnął błędne wnioski z danych i tym samym generuje błędne wyniki. Ograniczenie zbioru cech ma jeszcze jedną ważną zaletę: w znacznym stopniu skraca proces uczenia.

* – na etapie feature selection, oprócz cech z bieżącej oferty, wybierane są też cechy pochodzące z przykładów negatywnych.

III. Zastosowanie algorytmu uczącego

Wejściem do algorytmu uczącego są feature vectory oznaczone etykietami 1 lub 0. Przykład dla modelu „Apple iPhone 7 Plus 32GB Czarny” wygląda następująco:

Wektory reprezentujące zbiór pozytywny (czyli określającą przynależność do produktu „Apple iPhone 7 Plus 32GB Czarny”) oznaczone są etykietą 1:

Wektory reprezentujące zbiór negatywny oznaczone są etykietą 0:

IV. Cross-validation i wybór najlepszego modelu

W celu oceny jakości modelu stosujemy technikę cross-validation. Polega ona na podziale zbioru danych na dwa podzbiory: zbiór uczący oraz zbiór testowy, najczęściej w proporcjach 70%/30%. W procesie uczenia jest używany pierwszy zbiór, a procesie weryfikacji drugi. Na podstawie uzyskanych wyników takiego testu wyznaczamy tablicę błędów (confusion matrix). Dla klasyfikatora binarnego, tablica ta ma następującą postać:

Weźmy jako przykład klasyfikator binary dla produktu „Apple iPhone 7 Plus 32GB Czarny”. W teście używamy zbioru testowego zawierającego oferty oznaczone etykietą reprezentującą przynależność do produktu (1 – należy, 0 – nie należy). Klasyfikator może zwrócić 1 – należy, 0 – nie należy.

Możliwe są następujące przypadki:

• True positive (TP) – klasyfikator zwrócił 1 dla oferty oznaczonej etykietą 1
• False positive (FP) – klasyfikator zwrócił 1 dla oferty oznaczonej etykietą 0
• False negative (FN) – klasyfikator zwrócił 0 dla oferty oznaczonej etykietą 1
• True negative (TN) – klasyfikator zwrócił 0 dla oferty oznaczonej etykietą 0

W tablicy błędów umieszcza się wartość wyrażającą liczbę wystąpień danego przypadku na zbiorze testowym. Następnie można obliczyć:

• dokładność (precision) – wyraża stosunek liczby trafnie sklasyfikowanych ofert do liczby wszystkich sklasyfikowanych ofert.
  
• kompletność (recall) – wyraża stosunek liczby trafnie sklasyfikowanych ofert do liczby tych, które powinny zostać sklasyfikowane.
  

Częstą praktyką jest uczenie kilku modeli za pomocą różnych algorytmów i parametrów, a następnie wybór tego, który gwarantuje największą dokładność i kompletność.

Realizacja

Przy implementacji finalnego rozwiązania skorzystaliśmy z biblioteki open-source Accord.NET Framework (http://accord-framework.net) oferującej wiele gotowych i prostych w użyciu algorytmów machine learning napisanych w języku C#. Zaletą Accord.NET jest też bardzo dobra dokumentacja zawierająca masę praktycznych przykładów, które można użyć we własnych projektach.

W procesie uczenia bierze udział kilka milionów modeli, więc ważnym kryterium była dla nas efektywność i skalowalność projektowanego systemu. Aby osiągnąć zamierzone cele, zdecydowaliśmy się wykorzystać framework Microsoft Orleans (https://dotnet.github.io/orleans/). Orleans służy do budowania rozproszonych systemów w oparciu o koncepcję Actor Model. Podstawową jednostką w modelu aktorów jest Aktor, który w odpowiedzi na otrzymywane wiadomości wykonuje akcje. Akcją może być modyfikacja własnego stanu, utworzenie nowego aktora i/lub wysłanie wiadomości do innego aktora. Aktor wykonuje tylko jedną akcję na raz, a pozostałe oczekują w kolejce. Wszystko to sprawia, że komunikacja między aktorami jest całkowicie asynchroniczna, a ponieważ aktor robi tylko jedną rzecz na raz, to nie ma konieczności używania blokad.

Microsoft Orleans nie jest jednak czystym modelem aktorów jak np. Akka (http://getakka.net). Jego twórcy określają go bardziej jako Model Wirtualnych Aktorów. W Orleans aktorów nazywa się ziarnami (grain). Programista nie musi przejmować się cyklem życia ziarna. Może przyjąć, że ziarno cały czas żyje i jest dostępne na każde żądanie. Framework zapisze stan i offloaduje ziarno, jeśli przez dłuższy czas nie będzie używane, a w momencie, gdy pojawi się wiadomość dla tego ziarna, to z powrotem je wskrzesi.

Ziarna żyją wewnątrz Silosów. Silos to pojedyncza maszyna. W klastrze może znajdować się wiele silosów. Programista nie musi znać i dbać o lokalizację ziarna, do którego chce wysłać wiadomość. Wystarczy, że zna jego identyfikator, a framework zadba o to, aby wiadomość została dostarczona do adresata. Taki system bardzo dobrze się skaluje, ponieważ stan aplikacji jest rozproszony w ziarnach. Dodatkowo silosy można dodawać do Klastra dynamicznie. Dużą zaletą Orleans jest też to, że można go używać zarówno we własnej infrastrukturze jak i w chmurze (Azure).

Poniższy diagram prezentuje architekturę naszego rozwiązania w podejściu Actor Model.

Wyniki

Poniżej zaprezentowane zostały wyniki z wybranych kategorii. Przedstawiają one procentowe porównanie liczby ofert zintegrowanych za pomocą machine learning w stosunku do dwóch innych algorytmów używanych przez nas w procesie integracji: algorytmu EAN łączącego oferty posiadające ten sam kod kreskowy co produkt, oraz algorytmu Name łączącego oferty mające taką samą lub zbliżoną nazwę do nazwy produktu.

Uruchomienie projektu machine learning znacznie zwiększyło liczbę automatycznie integrowanych ofert i poprawiło jakość katalogu Ceneo.

Podsumowanie

W Ceneo pracujemy nad wieloma ciekawymi projektami. Jednym z takich projektów jest opisane właśnie wykorzystanie Machine Learning do integracji ofert sklepowych.

Zastosowanie Machine Learning dało nam zupełnie nowe możliwości rozwiązywania różnego rodzaju problemów, które do tej pory rozwiązane były w sposób mniej efektywny lub których zaadresowanie było wręcz niemożliwe.

Rozwiązania oparte o Machine Learning i Artificial Intelligence wkraczają coraz szerzej do naszego codziennego życia. Jest to obecnie jedno z najbardziej rozwojowych i przyszłościowych zagadnień. Jednocześnie wymaga posiadania ogromnej wiedzy z dziedziny matematyki, algorytmiki, programowania, analizy danych itp..

W Ceneo od lat korzystamy z innowacyjnych technologii, które przekładają się na dynamiczny rozwój naszej firmy.

Obserwacja, jak poprzez analizę danych i optymalizację algorytmów, nasze produkty stają się ze sprintu na sprint coraz lepsze i w bardziej efektywny sposób wspierają działania biznesu, napawa nas dumą i motywuje do dalszej pracy.