Machine Learning w wydaniu praktycznym – Quora competition

Internal Project to inicjatywa polegająca na realizowaniu dodatkowo finansowanych projektów, poza godzinami pracy. W ramach wewnętrznego programu wspierane są technologiczne i rozwojowe pomysły pracowników Apollogic. Projekt naszego zespołu Big Data został zatytułowany “Quora Competition”.

Inicjatywa zakładała udział w konkursie Data Science, realizowaliśmy go w trzyosobowej drużynie Big Data w składzie:

Adam Maciaszek

Arkadiusz Rusin

Mikołaj Kęsy

W pierwszej części artykułu pokazaliśmy:

Ogólne informacje dotyczące tematyki konkursu
Przebieg zawodów
Nasze wyniki

Tym razem przybliżymy jedno z zagadnień technicznych, z jakim mieliśmy okazję się zmierzyć

Machine Learning

Komputery, jako maszyny obliczeniowe bardzo efektywnie zoptymalizowały proces analiz danych, wypierając tym samym tradycyjną kartkę papieru i długopis. Obecnie przyrost informacji, możliwość składowania olbrzymich wolumenów danych wysunęły maszyny na pierwsze miejsce w kontekście eksplorowania setek petabajtów informacji.

Współcześnie proces składowania danych charakteryzuje się jednym z największych współczynników wzrostu, a prognozy jakie stawiają eksperci wskazują, że proces ten będzie się stale nasilał, a całkowity rozmiar danych elektronicznych składowanych na świecie w roku 2020 ma przekroczyć 44ZB (w 2004 roku było to jedynie 4.4ZB źródło).

W tym dynamicznym nasilaniu się zróżnicowanych i gigantycznych wolumenów danych, jednym z głównych problemów inżynierów, z którymi muszą się zmierzyć, to sposób ich przechowywania i zarządzania danymi.

Z drugiej strony, opinie ekspertów wskazują, że dane będą jednym z najcenniejszych zasobów, jakimi w przyszłości będzie mógł dysponować człowiek. Jeśli pomyślimy o danych elektronicznych jak o innym cennym surowcu, jakim jest choćby złoto, to przychodzi nam na myśl obraz ciężko pracujących górników, szukających złota w petagramach bezużytecznej ziemi. Ten trop nakierowuje nas także, na ideę wydobywania cennych informacji z petabajtów bezwartościowych danych składowanych na różnorodnych dyskach pamięci.

Po połączeniu dwóch światów specjalistów zajmujących się z jednej strony eksploracją danych, a z drugiej ich zarządzaniem, powstaje nowa, interdyscyplinarna dziedzina, zwana Machine Learning (Uczenie Maszynowe). Zajmują się nią specjaliści z zakresów Data Science i Big Data.

Dynamiczny wzrost wytwarzanych danych to konsekwencja silnie rosnącego trendu, jaki narzuca nam bardzo prężnie rozwijający się rynek IoT (Internet Rzeczy) – otaczające nas maszyny, generują olbrzymie wolumeny danych, ale wzrost ich wytwarzania jest także konsekwencją działania człowieka.

To właśnie człowiekowi zawdzięczamy generowanie różnorodnych rodzajów informacji, takich jak treści tekstowe, graficzne czy video, do których w szczególny sposób przyczynił się rozwój Internetu, a wraz z nim powstanie portali społecznościowych.

Obecnie człowiek nie jest już w stanie przetworzyć w skończonym czasie materiału, jaki sam wygenerował, dlatego potrzebuje do tego potężnych maszyn obliczeniowych. Tylko one są w stanie objąć skalę tego zadania.

Niestety współczesne komputery są w stanie posługiwać się jedynie w większości danymi numerycznymi, wykonując na nich różnorodne operacje. W momencie, gdy mamy do czynienia z danymi tekstowymi, zachodzi potrzeba symulacji rozróżniania poszczególnych słów w warstwie leksykalnej, bądź budowania grup słów o wysokiej relacji jednoznaczności.

Vector Space Model

Do powyżej przedstawionego problemu najlepiej nadaje się wykorzystanie modelu VSM (Vector Space Model). Umożliwia on przetransformowanie surowego tekstu do jego wektorowej reprezentacji. Każdy “dokument”, w zależności od poziomu granulacji, z jakim mamy do czynienia w naszym problemie, jest reprezentowany jako N-wymiarowy wektor, gdzie N jest liczbą wszystkich pojęć (potocznie zwanych “słów kluczowych”), znajdujących się w analizowanym zbiorze. Warto zatrzymać się w tym punkcie i uściślić pojęcia “dokument” oraz “słowa kluczowe”.

W zależności od złożoności problemu z jakim musimy się zmierzyć w naszej analizie możemy wyszczególnić różnorodne poziomy granulacji, w obrębie których będziemy budować nasz wektor:

Słowo
Zdanie
Dokument (zbiór zdań)
Kolekcja (zbiór dokumentów)

W analizie tekstu można także rozróżnić wiele różnorodnych jednostek będących poszczególnym poziomem leksykalnej reprezentacji tekstu:

Znaki:

n-gramowe “zlepki” liter
sekwencje liter

Słowa:

termy, czyli znormalizowane słowa, będące efektem działania takich metod jak stemming (wydobywania korzenia danego słowa, poprzez wykonanie operacji obcięcia prefiksu, bądź postfiksu. Metoda obcięcia jest zdefiniowana przez zbiór różnorodnych reguł, prowadzących do automatycznego wydobywania korzenia słowa), czy też lemmatyzacji (wydobywania fundamentalnego słowa dla danej części mowy). Termy jednoznacznie reprezentują daną klasę słowa,
“stop-words” reprezentujące najczęściej spotykane słowa w tekstach, między innymi takie jak: “the”, “a”. Często są to słowa, które nie niosą żadnej wartościowej treści

Zdania:

zbiór słów tworzący semantyczne i syntaktyczne znaczenie
n-gramowe zbiory słów

Części mowy

Warto mieć powyższą listę poziomów leksykalnych na uwadze, gdyż takie podejście do analizy tekstu umożliwia stworzenie różnorodnych modeli wektorowych, z których każdy z nich może dostarczyć innej, ale równie ciekawej, odpowiedzi na nasz problem.

W dalszej części artykułu dla uproszczenia zostało zastosowane sformułowanie “dokument d” odnoszące się do poziomu reprezentującego wektor oraz “słowa w” odzwierciedlającego elementy wektora. Dlatego korzystanie z powyższego nazewnictwa pozwala na następujący opis naszego modelu: “Każdy dokument d_i (i=1,…,M gdzie M oznacza liczbę analizowanych dokumentów) reprezentowany jest przez wektor N słów w_j (j=1,…,N gdzie N oznacza liczbę unikalnych słów).

Na powyższym rysunku możemy zaobserwować dwa oddzielne dokumenty reprezentowane przez dwa wektory d_1 oraz d_2. Każdy z tych wektorów składa się z 3 elementów, które w naszej analizie identyfikują 3 unikalne słowa.

Waga słów

Kolejnym problem to ustalenie wag poszczególnych słów. Analizując zbiory tekstowe należy sobie zadać pytanie: “Które współdzielone słowa są istotne dla podobieństwa tekstów?” Jest to w gruncie fundamentalne pytanie, które każdy analityk powinien sobie zadać. Możemy wyróżnić kilka sposobów określenia wag słów:

waga TF (term frequency), czyli inaczej mówiąc częstotliwość występowania słów. W tym przypadku interesuje nas wychwycenie słów, które często występują w zdaniu, a tym samym mogą być dla nas bardzo istotne. Sposobów obliczenia wagi TF jest naprawdę wiele. Można przykładowo zastosować mapy bitowe, które obejmują jedynie wystąpienie danego słowa w tekście. Dlatego każde słowo ma taką samą wagę o ile występuje w tekście (1 - gdy słowo występuje w zdaniu, 0 - gdy brakuje danego słowa w zdaniu). Możemy także rozróżniać wagi poprzez liczebność występowania danego słowa w zdaniu c(w, s). Zaproponowanych zostało wiele metod reprezentacji wag TF, można choćby wykorzystać funkcję logarytmiczną, która rośnie zdecydowanie wolniej od wspomnianej wcześniej funkcji liniowej reprezentującej częstotliwość słów.

Niestety funkcja logarytmiczna, podobnie jak liniowa, nie gwarantuje możliwości ograniczenia funkcji odgórnie, przez co dążą one do nieskończoności wraz ze wzrostem częstotliwości występowania słów. Problem ten zaczyna być istotny momencie występowania bardzo licznej grupy słów w dokumencie, które przejmują zdecydowanie większą część wagi wektora.

Do takich słów należą szczególnie wspomniane wcześniej słowa z grupy “stop words”. To zjawisko sprawia, że rzadkie słowa, które mogą mieć szczególne znaczenie w analizowanym dokumencie zostaną dyskryminowane. Aby uniknąć tego problemu, można zastosować transformację BM25, dla której można ograniczyć wartości wag TF górną granicą dla y = (k+1). Natomiast gdy wartość k będzie bardzo duża, powyższa transformacja sprawi, że funkcja ta będzie zbliżona do funkcji liniowej.

waga IDF (Inverse Document Frequency) reprezentuje siłę dyskryminacji tekstów przez dane słowo. Oznacza to, że jeśli w analizowanym tekście znajdują się słowa, które równie często występują w innych tekstach, to może to oznaczać, że słowa te mogą nie mieć istotnego wpływu na analizowane zdanie. Do tych słów należą między innymi “stop words”.
TF-IDF jest to waga odzwierciedlająca iloczyn częstotliwości występowania słów oraz siłę dyskryminacji danego słowa w obrębie zbioru tekstów. Miara ta szczególnie mocno wyróżnia słowa rzadkie w obrębie całego zbioru dokumentów będące jednocześnie częstymi słowami w obrębie analizowanego dokumentu.

Mając już wygenerowane odpowiednie wektory słów, przedstawiające odpowiednio analizowane dokumenty, łatwo sobie wyobrazić, że każdy taki dokument jest scharakteryzowany przez punkt w przestrzeni wielowymiarowej.

W zawodach, w których braliśmy udział, najważniejszym zadaniem było porównanie dwóch pytań i określenie czy są one unikalne, czy są duplikatami.

Dlatego należało wyznaczyć funkcję podobieństwa, która opisałaby stopień podobieństwa dwóch wektorów. W przypadku jedno- lub dwuwymiarowej przestrzeni, intuicyjnym wydaje się zastosowanie miary euklidesowej. Niestety, w momencie, gdy mamy do czynienia z analizą tekstu, każdy wektor reprezentowany jest przez kilkadziesiąt do kilku tysięcy elementów.

Jako jedną z miar które zastosowaliśmy w naszym rozwiązaniu była miara kosinusowa, która bazuje na iloczynie skalarnym dwóch wektorów i oblicza kąt między nimi. Jeżeli kąt ten jest zerowy, to analizowane wektory są sobie równe, a miara kosinusowa osiąga wtedy najwyższą wartość równą 1.

Za przykład może posłużyć kilka par pytań ze zbioru treningowego, który posłużył nam w zawodach do zbudowania klasyfikatora:

Question1	Question2
How do I become a data scientist in the data scientist team?	How can I become a data scientist?
What are the questions should not ask on Quora?	Which question should I ask on Quora?
What are the important algorithms in computer science?	What is the importance of algorithm in computer science?
Can I call you tonight?	Please, could you call me? PLEASE!

Biorąc udział w zawodach Kaggle mieliśmy do dyspozycji zbiór treningowych par pytań. Jednym z naszych podejść do analizy leksykalnej powyższych zdań było zbudowanie jednego dużego zbioru pytań.

Byliśmy dzięki temu w stanie wyznaczyć listę unikalnych elementów wektora. Dla powyższego przykładu 4 par pytań, usuwając stop-words, uzyskaliśmy 33 unikalne elementy, które posłużyły do opisów poszczególnych pytań. Poniżej zostały przedstawione fragmenty kodu generujące odpowiednio macierz częstości słów (TF), częstość występowania danych słów w obrębie zbioru dokumentów, macierz TF-IDF.

from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer

import pandas as pd

import numpy as np

df = pd.DataFrame({ 'q1' : ['How do I become a data scientist in the data scientist team',

                            'What are the questions should not ask on Quora?',

                             'What are the important algorithms in computer science',

                            'Can I call you tonight'], 

                     'q2' : ['How can I become a data scientist',

                            'Which question should I ask on Quora', 

                             'What is the importance of algorithm in computer science?',

                            'Please, could you call me? PLEASE'] })

np_list = np.concatenate((df.q1, df.q2))

Generowanie macierzy częstości słów TF, budowanej na podstawie zliczenia słów w danym pytaniu:

vect = CountVectorizer()
tf = pd.DataFrame(vect.fit_transform(np_list).toarray(), columns=vect.get_feature_names())

Generowanie wektora DF, który przedstawia wystąpienia poszczególnych słów w obrębie wszystkich pytań ze zbioru. Tutaj została wykorzystana funkcjonalność wagi TF dla map bitowych:

vect = CountVectorizer(binary=True)
df = vect.fit_transform(np_list).toarray().sum(axis=0)
df_result = pd.DataFrame(df.reshape(1, len(vect.get_feature_names())), columns=vect.get_feature_names())

Ostatnia tabela przedstawia użycie drugiego Vectorizera, który oblicza wagę TF-IDF:

vect = TfidfVectorizer()
tfidf = pd.DataFrame(vect.fit_transform(np_list).toarray(), columns=vect.get_feature_names())

Powyższe działania obliczają podstawowe modele wektorowe dla testowanych zdań. W końcowym etapie chcieliśmy porównać ze sobą wektory pytań dla poszczególnych par. W tym przypadku wykorzystaliśmy wektory TF-IDF, a za miarę podobieństwa posłużyła miara kosinusowa opisana w poniższym akapicie:

from scipy import spatial
df_1 = tfidf.iloc[:4, :]
df_2 = tfidf.iloc[4:, :]
result = []
for i in range(4):
 result.append(1-spatial.distance.cosine(np.array(df_1.iloc[i,:]), 
 np.array(df_2.iloc[i,:])))

Question1	Question2	TF-IDF cosine similarity
How do I become a data scientist in the data scientist team?	How can I become a data scientist?	0.712959832
What are the questions should not ask on Quora?	Which question should I ask on Quora?	0.504939411
What are the important algorithms in computer science?	What is the importance of algorithm in computer science?	0.462370678
Can I call you tonight?	Please, could you call me? PLEASE!	0.2928629354

Wykonanie poprawnej wektoryzacji i następnie wyciągnięcie miar podobieństwa między wybranymi parami pytań na podstawie otrzymanych wektorów miało duże znaczenie w procesie budowania konkursowego klasyfikatora. Ważnym etapem był także odpowiedni preprocessing, który stanowił fazę wstępną w naszym przepływie zadań. To właśnie na tym etapie mieliśmy duży wpływ na unikalne “słowa kluczowe” poszczególnych wektorów.

Największy wpływ na ostateczne wyniki w zawodach miały następujące czynności:

Wykorzystanie przeprocesowanych danych w fazie wektoryzacji i obliczenie cech podobieństwa między poszczególnymi parami pytań
Zastosowanie różnorodnych poziomów leksykalnych w obrębie elementów wektora
Wykorzystanie mechanizmu wykrywania synonimów
Rozszerzenie zbioru treningowego
Czyszczenie danych