jump to navigation

Eksploracja danych i muzyka (part 7) 12/11/2015

Posted by Mikołaj Morzy in eksploracja danych, muzyka.
add a comment

Zupełnie nie wiem, co o tym myśleć. Generalnie, co do zasady, informatycy nie powinni śpiewać… A piosenki o zjawisku przeuczenia w uczeniu maszynowym to nie jest gotowy materiał na hit. Niemniej jednak grupa związana z kursem uczenia maszynowego na Udacity popełniła poniższe dzieło.

Eksploracja danych i muzyka (part 5) 07/17/2013

Posted by Mikołaj Morzy in eksploracja danych, muzyka.
2 komentarze

Vienna TagCzy słyszeliście kiedyś o firmie Acxiom? Zatrudnia ponad 6000 osób i w 2012 roku osiągnęła dochód ponad $1.15 miliarda. I jest nazywana „jedną z największych firm o których nigdy nie słyszeliście”. Ta korporacja zajmuje się analizowaniem monstrualnych wolumenów danych i dostarczaniu raportów na potrzeby marketingu. Ich bazy danych zawierają nieskończone ilości danych demograficznych wykorzystywanych do personalizacji reklam, przeprowadzania wąsko celowanych akcji reklamowych czy do marketingu wielokanałowego. Acxiom sprzedaje swoje usługi przede wszystkim firmom zajmującym się handlem detalicznym, ale także firmom z branży telekomunikacyjnej, finansowej, rozrywkowej, mediom, firmom farmaceutycznym, producentom samochodów a nawet instytucjom rządowym. Ta jedna firma zgarnia 12% całego amerykańskiego rynku marketingu bezpośredniego.

Zgaduję, że nigdy też nie słyszeliście o Cynthii Yih Shih, działającej pod pseudonimem Vienna Teng. To amerykańska piosenkarka piosenkarka i pianistka tajskiego pochodzenia. Dla nas ważne jest to, że Cynthia ukończyła informatykę na Stanfordzie i przez jakiś czas pracowała jako programistka dla Cisco. Ostatnio analizowała bardzo dużą bazę danych profili klientów, wykorzystując do tego wnioski płynące ze słynnej już analizy danych przeprowadzonej przez Nate’a Silvera w trakcie kampanii prezydenckiej Baracka Obamy (jeśli ktoś nie wie o co chodzi, powinien szybko się zapoznać z blogiem Nate’a Five Thirty-Eight). Efektem jej prac jest „The Hymn of Acxiom”, niemal gregoriański chorał o utracie prywatności i stopniu ingerencji agencji analitycznych w nasze prywatne życia.

Vienna Teng, „The Hymn of Acxiom”

somebody hears you. you know that. you know that.
somebody hears you. you know that inside.
someone is learning the colors of all your moods, to
(say just the right thing and) show that you’re understood.
here you’re known.

leave your life open. you don’t have. you don’t have.
leave your life open. you don’t have to hide.
someone is gathering every crumb you drop, these
(mindless decisions and) moments you long forgot.
keep them all.

let our formulas find your soul.
we’ll divine your artesian source (in your mind),
marshal feed and force (our machines will)
to design you a perfect love—
or (better still) a perfect lust.
o how glorious, glorious: a brand new need is born.

now we possess you. you’ll own that. you’ll own that.
now we possess you. you’ll own that in time.
now we will build you an endlessly upward world,
(reach in your pocket) embrace you for all you’re worth.

is that wrong?
isn’t this what you want?
amen.

Parę użytecznych rzeczy na temat eksploracji danych 03/17/2013

Posted by Mikołaj Morzy in eksploracja danych, teoria.
2 komentarze

Pedro DomingosNa ubiegłorocznej konferencji CACM’2012 opublikowany został bardzo ciekawy artykuł Pedro Domingosa z University of Washington. Artykuł nosi tytuł „A Few Useful Things to Know about Machine Learning”  i postaram się go pokrótce streścić, żeby zachęcić do lektury.
Domingos zaczyna od zdefiniowania dziedziny uczenia maszynowego jako *uczenia programów na podstawie danych*. Nie jest to definicja wzbudzająca jakieś kontrowersje, choć interesujące jest przeniesienie nacisku z poszukiwania wzorców na znajdowanie programów. W swoim artykule koncentruje się przede wszystkim na problemie klasyfikacji i regresji, pomijając inne obszary (poszukiwanie asocjacji, analiza skupień, poszukiwanie wartości odstających). Dla niego proces uczenia się jest kombinacją trzech czynników: reprezentacji, oceny i optymalizacji. Reprezentacja to wybór sposobu, w jaki model będzie opisywany. Jest to o tyle istotne, że wybor konkretnej reprezentacji pośrednio definiuje zbiór wszystkich klasyfikatorów których dany model może się nauczyć. Jeśli dany klasyfikator nie mieści się w przestrzeni hipotez konkretnego modelu, taki klasyfikator po prostu nie może zostać wygenerowany. Oprócz wyboru reprezentacji dla modelu krok ten obejmuje sobą także wybór cech danych jakie będą podlegały uczeniu. Drugim czynnikiem jest ocena, czyli wybór funkcji wykorzystywanej do porównywania nauczonych klasyfikatorów. Trzeci czynnik, optymalizacja, to proces wyszukania w przestrzeni dostępnych klasyfikatorów tego klasyfikatora, który maksymalizuje funkcję wykorzystywaną do oceny. Taki podział algorytmów uczących na trzy niezależne czynniki jest o tyle interesujący, że pozwala dostrzec możliwości użycia kombinacji które nie są typowe.

  • reprezentacja: kNN, SVM, naiwny klasyfikator Bayesa, regresja logistyczna, drzewa decyzyjne, klasyfikator regułowy, sieć neuronowa, sieć Bayesowska
  • ocena: dokładność, precyzja i zwrot, błąd kwadratowy, prawdopodobieństwo a posteriori, Information Gain, Dywergencja KL
  • optymalizacja: algorytm zachłanny, beam search, B&B, metody gradientowe, Quasi-Newton, programowanie liniowe, programowanie kwadratowe

Jak się okazuje, można powiązać większość z wyżej przedstawionych konkretyzacji i uzyskać nowy model uczenia. Przykładowo, wybieramy kNN z miarą błędu kwadratowego i zachłannym poszukiwaniem najlepszej wartości parametru k. Nie każde połączenie ma tyle samo sensu, ale wiele z nich generuje egzotyczne algorytmy uczące.

Domingos kładzie bardzo duży nacisk na kwestię generalizacji. Przypomina o fundamentalnych zasadach testowania modeli i przestrzega przed nadmiernym optymizmem przy testowaniu na zbiorze uczącym. Zwraca też uwagę na interesujący aspekt uczenia maszynowego: w przeciwieństwie do innych problemów optymalizacyjnych w przypadku uczenia klasyfikatora nie dysponujemy funkcją którą próbujemy optymalizować, w związku z czym posługujemy się wyznaczonym błędem na zbiorze uczącym jako zastępstem rzeczywistego błędu.

Interesujące jest też nawiązanie do słynnego twierdzenia Davida Wolperta o braku darmowego lunchu w wyszukiwaniu i optymalizacji. Domingos pokazuje to na prostym przykładzie: niech zbiór danych jest opisany za pomocą 100 zmiennych binarnych. Dysponuję w moim zbiorze uczącym milionem etykietowanych przypadków. Milion to przecież bardzo dużo, w zupełności wystarczy żeby generalizować nauczony model, prawda? Niestety, nie… Przy 100 zmiennych i 1 000 000 rekordów przestrzeń wyszukiwania nadal zawiera 2^{100} - 10^{6} przypadków, dla których nie znam wartości zmiennej zależnej! Jeśli nie posiadam dodatkowej wiedzy eksperckiej, wówczas żaden algorytm eksploracji danych nie jest w stanie przebić zwykłego losowego rzucania monetą. Oczywiście powyższe to najgorszy z możliwych scenariuszy, w rzeczywistości funkcje których próbujemy się nauczyć nie są rozłożone jednostajnie w przestrzeni wszystkich możliwych 2^{100} funkcji. Korzystając z założenia o tym, że podobne przypadki należą do podobnych klas lub dodatkowej wiedzy o zależnościach między atrybutami możemy bardzo znacząco ograniczyć przestrzeń wyszukiwania. Ten indukcyjny proces uzyskiwana użytecznej wiedzy z niewielkiej ilości wiedzy początkowej stanowi sedno całej dziedziny uczenia maszynowego. Jak pisze Domingos:

[…] induction is a knowledge lever: it turns a small amount of input knowledge into a large amount of output knowledge. Induction is a vastly more powerful leveer than decuction, requiring much less input knowledge to produce useful results, but it still needs more than zero input knowledge to work.

Bardzo podobało mi się także proste i czytelne wytłumaczenie zjawiska przetrenowania modelu (ang. overfitting) zarówno pod kątem wariancji, jak i systematycznej tendencyjności (ang. bias) za pomocą jednego rysunku:

bias-varianceDomingos sporo miejsca poświęca też przekleństwu wymiarowości (ang. curse of dimensionality). Nawet, jeśli jesteśmy świadomi problemu, umyka on naszemu intuicyjnemu rozumieniu. Przykładowo, jeśli funkcja której próbujemy się nauczyć to f(x)=x_1 \wedge x_2, to zadanie jest proste. Teraz dodajmy 98 niezwiązanych z funkcją celu zmiennych x_3, \ldots, x_{100} i okaże się, że szum informacyjny dodatkowych wymiarów całkowicie przykrywa funkcję celu. Może rozwiązaniem jest zwiększenie zbioru danych? Próżne nadzieje, w przypadku 100 wymiarów binarnych (a przecież trudno jeszcze tu mówić o wielkiej liczbie wymiarów) i monstrualnym zbiorze danych liczącym bilion rekordów, nadal pokrywamy zaledwie 10^{-18} część przestrzeni… Ogromna liczba wymiarów fatalnie też wpływa na wszystkie metody bazujące na odległości między przypadkami, ponieważ każdy kolejny wymiar zwiększa liczbę przypadków położonych w tej samej odległości od danego przypadku, sprowadzając metody najbliższych sąsiadów do losowego wyboru sąsiadów.
Pozostałe problemy opisywane przez Domingosa dotyczą użyteczności teoretycznych granic błędów, znaczenia metod ekstrakcji atrybutów, przydatności ogromnych wolumenów danych (mimo wszystko), oraz dominacji metod wykorzystujących łączenie wielu modeli (ang. ensembles). Cały artykuł jest napisany bardzo czytelnie i przystępnie, dla początkujących adeptek i adeptów eksploracji danych będzie to dobre wprowadzenie i zbudowanie solidnych podstaw „filozoficznych”, ale i osoby doświadczone mogą ze zdumieniem odkryć dla siebie nowe aspekty eksploracji danych.

Na koniec, jako zachęta, lista tytułów sekcji:

  • Learning = Representation+Evaluation+Optimization
  • It’s Generalization That Counts
  • Data Alone Is Not Enough
  • Overfitting Has Many Faces
  • Intuition Fails in High Dimensions
  • Theoretical Guarantees Are Not What They Seem
  • Feature Engineering Is the Key
  • More Data Beats a Cleverer Algorithm
  • Learn Many Models, Not Just One
  • Simplicity Does Not Imply Accuracy
  • Representable Does Not Imply Learnable
  • Correlation Does Not Imply Causation

Domingos, P. (2012). A few useful things to know about machine learning Communications of the ACM, 55 (10) DOI: 10.1145/2347736.2347755

Wywiad z Jiawei Hanem 01/05/2012

Posted by Mikołaj Morzy in eksploracja danych, nauka.
add a comment

Jaiwei Han's pictureJiawei Han to jedna z najbardziej znanych osób w świecie eksploracji danych. Jest ACM Fellow i IEEE Fellow, jest laureatem nagrody McDowella, a z jego książki korzystają wszyscy uczący eksploracji na całym świecie. W DBLP jest w tej chwili 527 jego publikacji! W samym 2011 roku napisał 62 prace indeksowane przez DBPL, co daje trochę ponad 5 publikacji miesięcznie (nie zdziwiłbym się, gdyby funkcjonowała tam prosta zasada: muszę być dopisany do każdej publikacji powstającej na moim wydziale). Oczywiście taka „produktywność” naukowa jest śmieszna, skoro jest wpisany jako autor 6 prac przyjętych np. na zeszłoroczny ASONAM.Wystarczy wspomnieć, że aktualna wartość indeksu Hirscha raportowana przez Publish or Perish dla Hana wynosi 101… chociaż musi to być jakiś błąd PoP, bo na oficjalnej liście ludzi o najwyższym indeksie Hirscha Han jest na dość odległej pozycji.

Ale nie da się ukryć, że wpływ Hana na eksplorację danych był ogromny, a jego propozycje, takie jak algorytm Prefix-Span, FP-Growth lub Graph-OLAP weszły na stałe do kanonu eksploracji danych. Tym chętniej zajrzałem do najnowszego numeru SIGMOD Record (December 2011 Vol. 40, No. 4) żeby przeczytać wywiad z Hanem. Niestety, rozczarowanie jest srogie. Albo moje oczekiwania były zbyt wysokie, albo Han nie był w formie, ale wywiad wydaje mi się nudny jak flaki z olejem. Z kronikarskiego obowiązku podaję jednak link. A w samym numerze najciekawsze artykuły to przegląd prac dotyczących przetwarzania równoległego na MapReduce i praca dotycząca przetwarzania i wizualizacji tweetów.

Krzyżówka z eksploracji danych (druga) 06/02/2011

Posted by Mikołaj Morzy in eksploracja danych, humor, zagadki.
add a comment

Dwa lata temu donosiłem o pierwszej na świecie krzyżówce poświęconej eksploracji danych. Nieocenione KDNuggets dostarcza nam kolejnej porcji wysoce hermetycznej rozrywki (bo, przyznajmy uczciwie, ile osób potrafi powiedzieć, jakie hasło kryje się za opisami „Review of data to establish patterns and conclusions and recommendations” lub „Sum of squared errors of prediction, abbr.„)

Mi rozwiązanie nowej krzyżówki zajęło 11 minut. Dobrej zabawy!

Konkursy, konkursy, konkursy 06/02/2011

Posted by Mikołaj Morzy in eksploracja danych, konkurs, nauka.
add a comment

Logo of the TunedIt websiteDziś o dwóch konkursach organizowanych na platformie TunedIt. Pierwszy konkurs zorganizowała kanadyjska firma FIND Technologies, konkurs dotyczy rozpoznawania substancji na podstawie ich własności elektro-magnetycznych. Firma produkuje czujniki, które w sposób całkowicie pasywny, analizując jedynie własności elektryczne i magnetyczne dowolnego materiału, określa rodzaj substancji. Okazuje się, że każda substancja posiada swoje „odciski palców”. Firma pracuje nad algorytmem, który będzie w stanie szybko i precyzyjnie określać, jakie substancje są zawarte w próbce materiału. Ponieważ budowa takiego algorytmu wykracza poza kompetencje FIND Technologies, kierownictwo firmy postanowiło pójść w crowdsourcing. Reguły są proste: zmienna celu przyjmuje trzy wartości, zbiory uczący i testowy zawierają po 1500 próbek, główna wygrana zostanie przyznana za osiągnięcie progu 95% dokładności klasyfikacji. Dodatkowo, uczestnicy konkursu dysponują pomocniczym zbiorem testowym składającym się z 500 instancji, na którym mogą sprawdzać swoje modele. Konkurs będzie trwał pół roku. Główna wygrana wynosi 45 000$, dodatkowo uczestnicy dostają po 1000$ za osiągnięcie progów 50%, 60%, 70%, 80% i 90% dokładności. Szczegóły konkursu, formularz rejestracyjny i zbiory danych do pobrania na głównej stronie konkursu: http://tunedit.org/challenge/material-classification

Drugi konkurs dotyczy rekomendacji wideo na portalu VideoLectures.net. Ten konkurs, ogłoszony jako VL.net Challenge na ECML/PKDD’2011, potrwa jeszcze jedynie 36 dni. Co prawda nagroda jest dużo skromniejsza (5500 EUR), ale za to wygrany zespół będzie się prezentował na jednej z wiodących światowych konferencji poświęconych eksploracji danych. W przypadku tego konkursu celem jest opracowanie modelu, który będzie rekomendował sekwencje wykładów i prezentacji na podstawie historii interakcji użytkownika z portalem VideoLectures.net. Konkurs podzielony jest na trzy części:

  • problem zimnego startu: rekomendowanie wideo dla osób nie posiadających praktycznie żadnej wcześniejszej historii (ew. rekomendowanie powiązanych wideo dla nowych nagrań)
  • problem rekomendacji dla trójek: budowanie rankingu powiązanych wideo dla trójek nagrań występujących często w sekwencjach użytkowników
  • konkurs na najlepszy przepływ (ang. workflow) rekomendacyjny zaimplementowany w Rapid Minerze (osoba która wygra ten konkurs pojedzie na RCOMM’2012, coroczną konferencję użytkowników Rapid Minera)

Szczególnie serdecznie chciałem zachęcić do udziału w tym drugim konkursie, ponieważ jego wyniki zostaną wykorzystane w projekcie e-Lico, w którym mam przyjemność brać udział. Pamiętajcie (drogie studentki i drodzy studenci), że takie konkursy to najfajniejszy sposób na rozpoczęcie swojej przygody z prawdziwą dorosłą nauką.

Nowe czasopismo poświęcone eksploracji danych 02/03/2011

Posted by Mikołaj Morzy in eksploracja danych, nauka.
add a comment

Właśnie ukazał się pierwszy numer nowego czasopisma poświęconego w całości problemom eksploracji danych. Czasopismo nazywa się „Data Mining and Knowledge Discovery” i ukazuje się w serii Wiley Interdisciplinary Reviews wydawanej przez John Wiley & Sons. Głównym edytorem jest Witold Pedrycz z University of Alberta (oraz Instytutu Badań Systemowych PAN), który w otwierającym artykule przedstawia ideologię czasopisma, zakres tematyczny, oraz typy artykułów, które będą przyjmowane (overview, advanced review, focus, opinions).

Oczywiście, póki co jest to zupełna świeżynka, ale wydawnictwo przyzwoite, seria ciekawa, więc na pewno warto sobie zanotować to czasopismo. No i pierwszy numer jest do pobrania z sieci za darmo.

Lista konferencji z dziedziny eksploracji danych 01/06/2011

Posted by Mikołaj Morzy in eksploracja danych, nauka.
add a comment

KDNuggets przynosi zestawienie topowych konferencji w dziedzinie eksploracji danych. Przyznam szczerze, że mój osobisty ranking był nieco inny, ale ten opublikowany przez KDNuggets jest poparty twardymi liczbami.

lp. nazwa publikacje cytowania pub/cyt
1 KDD – Knowledge Discovery and Data Mining 4140 10223 2.47
2 ICDE – International Conference on Data Engineering 7028 8370 1.19
3 ICDM – IEEE International Conference on Data Mining 3414 2463 0.72
4 CIKM – International Conference on Information and Knowledge Management 4452 2242 0.50
5 SDM – SIAM International Conference on Data Mining 1432 1256 0.88
6 ECML/PKDD – Principles of Data Mining and Knowledge Discovery 2062 1129 0.55
7 PAKDD – Pacific-Asia Conference on Knowledge Discovery and Data Mining 2526 711 0.28
8 DMKD – Research Issues on Data Mining and Knowledge Discovery , (SIGMOD Workshop, 1996-2004) 212 637 3.00
9 DASFAA – Database Systems for Advanced Applications 2232 364 0.16
10 DaWaK – Data Warehousing and Knowledge Discovery 1010 330 0.33

Pełną listę konferencji dotyczących eksploracji danych można sprawdzić tutaj.

Ngram Viewer: eksploracja ewolucji języka w czasie 01/06/2011

Posted by Mikołaj Morzy in dataset, eksploracja danych, nauka, Uncategorized, zbiór danych.
1 comment so far

Google Labs logoGoogle nie przestaje zadziwiać. Właśnie natknąłem się na Google Ngram Viewer, aplikację umożliwiającą śledzenie częstotliwości występowania zlepków słów we wszystkich książkach dostępnych przez Google Books. Na wstępie uwaga: przyzwyczailiśmy się (przynajmniej w eksploracji danych) używać terminu n-gram do określania sekwencji następujących po sobie n znaków, np. słowo eksploracja może być podzielona na bi-gramy: ek-ks-kp-pl-lo-or-ra-ac-cj-ja. Moje pierwsze wrażenie było takie, że Google używa tego terminu niepoprawnie (wg. nich jest to sekwencja n słów występujących w tekście). Jednak krótki rzut oka do Wikipedii pokazuje, że ich użycie jest prawidłowe:

An n-gram is a subsequence of n items from a given sequence. The items in question can be phonemes, syllables, letters, words or base pairs according to the application.

Do dyspozycji są zbiory danych z książek opublikowanych w Anglii, Stanach Zjednoczonych, można też ograniczyć analizę do książek w językach: chińskim, niemieckim, hiszpańskim, francuskim, hebrajskim i rosyjskim. Dane są dostępne zarówno przez interfejs Google’a, jak i w formacie do pobrania i samodzielnego przetwarzania (dane są dostępne na licencji Creative Commons 3.0). Jeśli zechcecie wykorzystać ten korpus danych, to powinniście w referencjach umieścić pracę

Jean-Baptiste Michel*, Yuan Kui Shen, Aviva Presser Aiden, Adrian Veres, Matthew K. Gray, William Brockman, The Google Books Team, Joseph P. Pickett, Dale Hoiberg, Dan Clancy, Peter Norvig, Jon Orwant, Steven Pinker, Martin A. Nowak, and Erez Lieberman Aiden. Quantitative Analysis of Culture Using Millions of Digitized Books. Science (ta publikacja nie jest dostępna za darmo ze strony czasopisma Science, ale jeśli ktoś przez przypadek kliknie tutaj…)

I zupełnie na marginesie: oto jak można połączyć naukę z marketingiem. Przy okazji pracy nad Ngram Viewer ekipa z Google (przy współpracy z młodymi ludźmi z Harvardu i MIT) ukuła nowy termin: culturomics. Prawda, że zgrabne i chwytliwe?

Mapa eksploracji danych 11/27/2010

Posted by Mikołaj Morzy in eksploracja danych, nauka, teoria.
5 komentarzy

Doskonała sprawa! Na AnalyticBridge dr Sayad opublikował doskonałe wprowadzenie do eksploracji danych. Jest to bardzo czytelna mapa całej domeny z podziałem na poszczególne etapy procesu odkrywania wiedzy (przygotowanie danych, eksploracja danych, modelowanie, ocena, wdrożenie), przy czym każdy fragment mapy jest „klikalny” i prowadzi do krótkiego, prostego opisu fragmentu dyscypliny. Absolutny hit dla osób rozpoczynających swoją przygodę z eksploracją danych i próbujących się połapać w gąszczu nazw metod, algorytmów i pojęć.

 

Mapa eksploracji danych z wyjaśnieniami

Mapa eksploracji danych

 

 

%d blogerów lubi to: