Współpracujący naukowcy z laboratoriów badań nad sztuczną inteligencją oraz systemów informacyjnych i decyzyjnych uniwersytetu technicznego MIT w Stanach opracowali algorytm, dzięki któremu wybór podzbiorów zróżnicowanych danych jest znacznie efektywniejszy.
Kiedy zbiory gromadzonych danych są zbyt duże, czasami jedynym sposobem, by wykorzystać je w praktyce jest wydzielenie mniejszych podzbiorów i praca z nimi, zamiast obróbki i przetwarzania całego, dużego zbioru.
Podzbiory te muszą zachowywać pewne cechy całego zbioru, jednak najbardziej użyteczną właściwością, istotną w wielu aplikacjach, jest zróżnicowanie danych. Jeżeli na przykład wykorzystuje się dane do uczenia maszyny, wybrane podzbiory muszą reprezentować pełne spektrum zdarzeń, z jakimi musi sobie poradzić takie urządzenie w trakcie eksploatacji.
Współpracujący naukowcy z laboratoriów badań nad sztuczną inteligencją (Computer Science and Artificial Intelligence Laboratory – CSAIL) oraz systemów informacyjnych i decyzyjnych (Laboratory for Information and Decision Systems) uniwersytetu technicznego MIT opracowali algorytm, dzięki któremu wybór zróżnicowanych podzbiorów danych jest znacznie efektywniejszy.
Podczas gdy wcześniejsze algorytmy wyboru podzbiorów opierały się na ilości punktów danych w całym zbiorze, nowy zależy od ilości punktów danych
w podzbiorze. Oznacza to, że jeżeli celem jest przesianie zbioru danych z milionem punktów danych tak, by miał on ich tysiąc, nowy algorytm będzie miliard razy szybszy niż poprzednie.
“Naszą intencją było selekcjonowanie zróżnicowanych podzbiorów,” mówi Stefanie Jegelka, adiunkt w X-Window Consortium na Wydziale Inżynierii Elektrycznej i Komputerowej (Department of Electrical Engineering and Computer Science) MIT i jednocześnie współautorka nowego algorytmu.
“Dlaczego jest to tak istotne i ważne z praktycznego punku widzenia? Najlepiej zrozumieć to na przykładzie. Jeżeli komuś chce się polecić książki lub filmy, to zwykle staramy się zaproponować zróżnicowany zestaw, a nie dziesięć tytułów będących wariacją na ten sam temat,” mówi Stephanie. „Albo jeśli na przykład wyszukujesz w Internecie znaczenia słowa Washington – ma ono wiele znaczeń i pewnie będziesz chciał pokazać kilka różnych. Jeszcze inny przykład. Masz duży zbiór danych i chcesz w nim wyszukać zdjęcia lub dane medyczne – prawdopodobnie chcesz swego rodzaju wyciągu z danych, prezentującego cały ich przekrój.”
„Inną aplikacją, w której wykorzystujemy taki sposób postępowania jest uczenie się. Jeśli masz do czynienia z dużym zbiorem danych, najchętniej wybierasz małą część, której możesz się dobrze nauczyć,” mówi Stephanie.
Mały równy dużemu
Przy tradycyjnym podejściu, w celu wyodrębnienia zróżnicowanego podzbioru z dużego zbioru danych, pierwszym krokiem jest stworzenie macierzy podobieństwa – dużej tabeli pozycjonującej każdy punkt zbioru względem wszystkich pozostałych. W takiej macierzy, przecięcie wiersza reprezentującego jedną pozycję danych z kolumną reprezentującą inną pozycję, zawiera punkty podobne według standardowego pomiaru.
Jest wiele standardowych metod wyodrębniania zróżnicowanych zbiorów, ale wszystkie one bazują na operacjach wykonywanych na macierzy jako całości. Przy zbiorze z milionem punktów, daje to macierz podobieństwa milion na milion – oznacza to bardzo długi okres czasu potrzebny na przetworzenie danych.
Dla odmiany, algorytm stworzony przez naukowców z MIT rozpoczyna pracę
z małym podzbiorem danych, wybranym losowo. Następnie algorytm bierze jeden punkt należący do tego podzbioru oraz jeden spoza niego i losowo wykonuje jedną z trzech operacji: zamiana punktów, dodanie punktu do podzbioru lub usunięcie punktu z podzbioru.
Prawdopodobieństwo wyboru jednej z tych operacji zależy zarówno od liczebności zbioru jak i podzbioru danych, więc algorytm zmienia się nieco przy każdej operacji dodania lub odjęcia. Jednak algorytm nie musi wykonać operacji, którą wybrał.
Decyzja o wykonaniu operacji ma charakter probabilistyczny, a w tym przypadku zależy od zwiększania się zróżnicowania, w wyniku tej właśnie decyzji. Co więcej, decyzja o dodaniu lub odjęciu zależy również od stosunku wielkości podzbioru w stosunku do oryginalnego zbioru. W rezultacie, wraz ze wzrostem liczebności podzbioru, coraz trudniej dodać do niego nowy punkt, o ile operacja ta nie zwiększy zróżnicowania.
Proces powtarza się, dopóki zróżnicowanie podzbioru nie odzwierciedla zróżnicowania całego zbioru. Ponieważ jednak zróżnicowanie całego zbioru nie jest obliczane, pytanie brzmi, jak określić, jaka ilość powtórzeń jest potrzebna. Naukowcy twierdzą, że ich badania są jednocześnie odpowiedzią na to pytanie, jak i dowodem, że mają rację.
Źródło: Massachusetts Institute of Technology (MIT)/CFE Media
