Odległość Levenshteina w służbie Wirtualnego Asystenta

29.05.2020 | Michał Dądela

Wstęp

W 2015 roku, pracując na 1 linii wsparcia informatycznego zaobserwowaliśmy, że bardzo wiele zgłoszeń od użytkowników dotyczy tematów opisanych w różnych bazach wiedzy, dla których nie były dostępne skuteczne mechanizmy wyszukiwania. W tym czasie na rynku polskim wystartowały małe startupy, które proponowały rozwiązania chatbotowe w języku polskim. Na tamten moment było to raczej niespotykaną funkcjonalnością. Spodobało nam się rozwiązanie małej firmy i zdecydowaliśmy się na wdrożenie Wirtualnego Asystenta. Główną jego zaletą jest dostępność – 24/7 dla każdego pracownika naszej organizacji. Wybrane rozwiązanie okazało się sukcesem i spotkało się z bardzo pozytywnym przyjęciem - głównie ze względu na jego skuteczność.

Od 2016 roku obserwujemy znaczący wzrost wolumenu interakcji z wirtualnym asystentem. Od samego początku naszą ambicją było uzyskanie jak największej skuteczności i pewności, że udzielone odpowiedzi są w każdym przypadku adekwatne do zadanego pytania. W tym celu koniecznością stała się analiza historii konwersacji, w wyniku której zauważyliśmy, że nie każdy przypadek, w którym bot odpowiada na zadane pytanie jest odpowiedzią oczekiwaną przez pytającego. Przykładowo, na zadane pytanie: „zmiana PIN do karty SIM” bot udzielał odpowiedzi o sposobie zmiany PIN do karty płatniczej. W statystykach systemu udzielona odpowiedź była klasyfikowana jako poprawna, mimo że użytkownik nie o to pytał. Zgodnie z naszym głównym założeniem, oczekiwana jest sytuacja, w której bot informuje o tym, że nie zna odpowiedzi niż wprowadza pytającego w błąd.

Wszystkie te czynniki wymuszają na nas ciągłe monitorowanie historii rozmów. Po dwóch latach pracy i ciągłym wzroście wolumenu zapytań do asystenta, zderzyliśmy się z sytuacją, w której, ze względu na skalę, nie byliśmy w stanie w rozsądnym czasie potwierdzić poprawności udzielanych przez bota odpowiedzi. Jeden inżynier bazy wiedzy jest w stanie zweryfikować ok. 500 pytań dziennie. Przy rosnącym wolumenie (obecnie 3000 unikalnych pytań dziennie) konieczne byłoby zwiększenie zatrudnienia w zespole. Zadaliśmy sobie pytanie: czy w przyszłości czeka nas zwiększenie FTE czy więcej AI?

Dzięki AI możemy zautomatyzować powtarzalne zadania – zaoszczędzony czas pozwala nam w tym czasie skupić się na ciekawych, rozwojowych tematach i ciągle poszerzać zagadnienia, które są obejmowane bazą wiedzy chatbota. Zdajemy sobie sprawę z tego, że w najbliższej przyszłości nie uda nam się całkowicie wyeliminować czynnika ludzkiego. Nawet najlepsze algorytmy uczenia maszynowego i przetwarzania języka naturalnego aktualnie nie są w stanie same utrzymywać, rozwijać i kontrolować bazy wiedzy.

Podejmując próby wdrożenia algorytmów AI główną przeszkodą dla nas było to, że obecnie nie ma tak skutecznych rozwiązań do analizy języka polskiego jakie są dla języka angielskiego. Wynika to z faktu, że język angielski jest dużo bardziej popularny i z tego powodu jest dostępna większa liczba materiałów i rozwiązań gotowych do zaimplementowania. Dodatkową trudnością jest złożoność form i odmian w języku polskim.

Literówki, nieszczęsne literówki...

Podczas codziennej analizy historii konwersacji zaobserwowaliśmy, że bardzo wielu użytkowników robi literówki podczas wpisywania pytań do Wirtualnego Asystenta. Dostarczany przez producenta silnik aplikacji nie radzi sobie w tych przypadkach zbyt dobrze.

Podjęliśmy się stworzenia mechanizmu, który potrafiłby poprawiać tego typu błędy i dostarczać do silnika aplikacji frazy w poprawnej formie. Korpus modułu sprawdzania pisowni, który nazwaliśmy spellchecker składa się z bazy słów języka polskiego (słownictwo ogólne) oraz słów używanych w treściach artykułów w bazie wiedzy (słownictwo specjalistyczne).

Mechanizm sprawdzania pisowni w pierwszej fazie działania rozbija wpisaną przez użytkownika frazę na pojedyncze słowa, aby następnie przeanalizować każde z osobna. Do określenia najbardziej podobnego słowa do zadanego przez użytkownika wykorzystujemy algorytm obliczania odległości Levenshtein’a. Wyznacza on najmniejszą konieczną liczbę operacji zmian jednego ciągu tekstowego, aby stał się on identyczny z drugim. Takimi operacjami może być wstawienie, usunięcie lub podmiana któregoś znaku.

Za przykład posłuży nam fraza "departamnt". Tego słowa nie ma w słowniku, więc algorytm przystępuje do wyszukania słów, które znajdują się w najbliższej odległości Levenshteina. Najbliższym słowem jest słowo "departament", dla którego odległość wynosi 1, ponieważ należy wstawić jedną literę. W przypadku, gdyby nie znalazł słowa lub słów, dla których minimalna odległość jest mniejsza od 4 wówczas spellchecker zwróciłby słowo nie zmienione, ponieważ stwierdziłby, że nie jest w stanie określić poprawnej formy.

Kalibracja

Podczas testów pierwszych wersji modułu, opartych wyłącznie o algorytm Levenshteina, doszliśmy do wniosków, że rozwiązanie to charakteryzuje wysoki poziom skuteczności, jednak nie gwarantuje ono oczekiwanego rezultatu dla wszystkich przypadków. Jednym z pierwszych wniosków było to, że nie warto podejmować analizy słów krótszych niż 3 znaki, ponieważ są to na ogół skróty, a wyniki często są błędne. Z podobnych przyczyn nie warto też podejmować analizy słów, które w treści zawierają liczby, ponieważ zwykle są to nazwy systemów lub ich funkcji.

Po odfiltrowaniu takich przypadków pozostały nam jeszcze do rozwiązania przypadki, w których wynik stanowiło kilka słów o tej samej minimalnej odległości Levenshteina i należało podjąć decyzję, które z nich ma najwyższe prawdopodobieństwo bycia słowem oczekiwanym.

Opracowaliśmy trzy kroki, które mają na celu wyznaczenie słowa o najwyższym podobieństwie do zadanej frazy. W pierwszym kroku algorytm wylicza ile liter słowa wpisanego przez użytkownika oraz słowa wyznaczonego przez algorytm jest wspólnych i zostawia tylko te, dla których ta liczba jest najwyższa. Jeśli nadal nie ma unikalnego "zwycięzcy", wówczas wylicza dopasowanie według najmniejszej ilości nadmiarowych liter jednego ciągu względem drugiego. Jeśli to nie dało jednoznacznego unikalnego słowa, wówczas sprawdza, między którymi jest najmniejsza różnica pod względem długości ciągu. Do ostatniego kroku dochodzi bardzo rzadko, ponieważ na ogół poprzednie operacje dają pozytywny wynik. W większości przypadków, wszystkie te kroki pozwalają na wyznaczenie unikalnego ciągu, który z najwyższym prawdopodobieństwem jest ciągiem oczekiwanym.

Kolejnym wyzwaniem było radzenie sobie z polskimi literami. Przykładowo, dla wpisanego słowa "pozyczka", chcieliśmy, aby silnik otrzymał poprawione słowo "pożyczka". Aby moduł umożliwiał obsługę tego typu przypadków, wszystkie działania algorytmu opierają się na słowach sprowadzonych do formy bez polskich znaków. W ostatnim kroku algorytm sprawdza, czy dla słowa bez polskich znaków jest w stanie znaleźć odpowiednik z polskimi literami. Jeśli tak jest, zwraca go.

Po przeprowadzeniu testów i uzyskaniu satysfakcjonujących wyników, usługę wystawiliśmy, jako serwis REST, z którym front aplikacji komunikuje się przed zadaniem pytania do silnika. Rozwiązanie to pozwala nam na utrzymanie wysokiej skuteczności odpowiedzi Asystenta bez konieczności wprowadzania słów z literówkami, jako słów kluczowych w bazie wiedzy.

Podsumowanie

O skali potrzeby, z jaką się zmierzyliśmy stanowi fakt, że na chwilę obecną spellchecker poprawia około 10 tysięcy słów miesięcznie. Warto jednak pamiętać, że jak przy większości tego typu rozwiązań, warto monitorować wyniki pracy tego narzędzia. W naszej branży ciągle pojawiają się nowe nazwy usług, promocji itd., które muszą być wprowadzane do bazy słów specjalistycznych. Pozostawienie takiego narzędzia bez opieki w ciągle zmieniającym się otoczeniu mogłoby spowodować spadek, jakości wyników jego pracy i w konsekwencji tego spadek skuteczności odpowiedzi Wirtualnego Asystenta.

Gdy poradziliśmy sobie z literówkami, wydawało się, że można zmierzyć się z dalszą automatyzacją przeglądu konwersacji. W kolejnym artykule przybliżamy mechanizmy, które z powodzeniem wdrażamy w automatyzacji monitoringu przeglądu konwersacji z Wirtualnym Asystentem.