jump to navigation

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

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

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

Konkurs „Executable Paper Grand Challenge” 12/26/2010

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

Logo of the Elsevier publishing companyRecenzowanie prac naukowych, w szczególności w informatyce, od lat obarczone jest poważną wadą. Recenzji podlega jedynie ostateczny wynik, czyli publikacja, natomiast nie ma możliwości oceny procesu naukowego, który do publikacji doprowadził. Nie można ocenić poprawności eksperymentu, nie można zweryfikować poprawności danych. Ba, nie wiadomo nawet, czy opisywane w publikacji eksperymenty w ogóle zostały przeprowadzone lub czy rzeczywiście dały takie wyniki, jakie zaprezentowano w publikacji. Czy mało jest nieuczciwych ludzi, którzy bezczelnie nakłamią lub nagną wyniki byle przejść przez sito recenzji? I trudno mieć pretensje do recenzentów, którzy wykonują swoją pracę społecznie, najczęściej nie jest to związane z jakimś wielkim prestiżem, a dodatkowo mają do wykonania po kilka-kilkanaście recenzji na pojedynczą konferencję.

Ciekawe rozwiązanie tego problemu zaprezentował Elsevier. Ogłosił konkurs „Executable Paper Grand Challenge” na propozycję prototypowego systemu wspomagającego pracę recenzentów, który umożliwiałby współdzielenie danych, programów, eksperymentów i wyników między autorami i recenzentami. Celem projektu ma być powstanie „wykonywalnego artykułu” (ang. executable paper), który będzie komatybilny z wieloma różnymi systemami operacyjnymi i będzie umożliwiał efektywną komunikację między recenzentem i autorem. W szczególności autorzy konkursu chcą, aby proponowane rozwiązania skupiały się na następujących czynnikach:

  • wykonywalność: tabele, wykresy czy równania muszą być wykonywalne, tj. recenzenci muszą mieć możliwość interaktywnej pracy z wymienionymi komponentami aby walidować poprawność wyników i z łatwością eksplorować przestrzeń rozwiązań (aby sprawdzić, czy np. autor nie publikuje tylko niewielkiego zakresu pozytywnych wyników i nie ukrywa tych obszarów w przestrzeni rozwiązań, gdzie zaproponowany algorytm zawodzi.
  • kompatybilność: proponowana architektura systemu powinna być elastyczna i umożliwiać adaptację do dużego bogactwa środowisk programistycznych i systemowych.
  • walidacja: system powinien umożliwiać (przynajmniej częściową) walidację uzyskanych rozwiązań aby odciążać recenzentów. Przykładowo, automatyczna walidacja jest możliwa choćby przy statystycznej obróbce wyników, wyznaczaniu przedziałów ufności, wyznaczaniu błędów, itp.
  • prawa autorskie: idea powszechnego dostępu do danych jest na naszych oczach bardzo często naruszana, często na najlepszych konferencjach widzimy wyniki badań przeprowadzonych na zamkniętych zbiorach danych (np. od Google czy Yahoo!) niedostępnych recenzentom i reszcie społeczności. W proponowanej architekturze należy dążyć do otwarcia dostępu do danych, przy jednoczesnym zachowaniu praw autorskich i innych ograniczeń (wyobrażam sobie, że mogłyby w tym pomóc techniki anonimizacji danych, kontrolowane wprowadzanie szumu do danych, itp)
  • rozmiar: wiele eksperymentów jest prowadzonych na ogromnych wolumenach danych, proponowana architektura powinna umożliwiać współpracę i współdzielenie takich zbiorów danych w efektywny i wydajny sposób.
  • kontrola dostępu: w naturalny sposób architektura musi umożliwiać śledzenie wszelkich akcji podejmowanych na takich wykonywalnych publikacjach.
  • inne problemy: kradzież pomysłów i danych przez recenzentów, wirusy i trojany wprowadzane do danych, algorytmów i kodu, plagiaryzm, i potencjalnie sto innych problemów.

Pierwszą nagrodą w konkursie jest $10 000, drugie miejsce jest premiowane $5 000, trzecie miejsce jest warte $2 500. Dodatkowo, propozycje które dotrą na podium będą nagrodzone iPadem. Zwycięzcy zostaną wyłonieni w trakcie warsztatu odbywającego się w trakcie tegorocznej konferencji ICCS’2011 w Japonii (Elsevier zobowiązuje się wspomóc finansowo w podróży). Finaliści będą także zaproszeni do opublikowania swoich rozwiązań w Journal of Computational Science. Propozycje rozwiązań w postaci streszczenia (max. 2000 słów, trzeba się streszczać, bo ten post ma ok. 500 słów) należy składać do 15 stycznia. Szczegółowe reguły konkursu, zasady i sposób zgłaszania propozycji, skład komisji, itp. znajdują się na stronach konkursu.

Od dawna mam poważne obiekcje co do sposobu funkcjonowania współczesnej nauki, w szczególności do procesu recenzowania prac naukowych. Propozycja Elseviera bardzo mi się podoba, bo to dobry przykład kierunku, w którym nauka powinna iść. Polepszenie jakości recenzji naukowych jest warunkiem sine qua non polepszenia jakości publikacji naukowych i postępu naukowego i proponowany system bez wątpienia przyczyniłby się do poprawy jakości recenzji dla konferencji i czasopism.

Mapa eksploracji danych 11/27/2010

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

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

 

 

Parę słów o otwartej nauce 09/25/2010

Posted by Mikołaj Morzy in bazy danych, nauka, teoria.
2 comments

Wiele psów powieszono na współczesnym modelu uprawiania nauki. Takie sformułowania jak „wieża z kości słoniowej”, „korporacyjna sterylność”, „oderwanie od praktyki”, nie należą do rzadkości. Faktycznie, pomysł że będziemy na wzajem recenzować sobie prace, niektóre przyjmować, a inne odrzucać, a potem będziemy się parę razy do roku spotykać w najprzeróżniejszych miejscach na całym świecie i przez parę dni rozmawiać, słuchać się nawzajem, smacznie jeść, i za to wszystko zapłacą podatnicy, taki pomysł może wydawać się dziwny. A jeszcze dziwniejsze jest to, że znakomita większość napisanej przez nas treści jest praktycznie niedostępna, ponieważ zostaje umieszczona w płatnych, drogich czasopismach i można się do niej dostać jedynie przez specjalizowane portale, takie jak IEEE Computer Science Digital Library, SpringerLink lub ACM Digital Library. Sam fakt ograniczenia dostępności publikacji końcowej nie jest jeszcze taki straszny, bo w końcu można sobie pozwolić wydać parę dolarów na zakup artykułu. Ale jeśli zamknięte są dane, na których przeprowadzono eksperymenty, lub narzędzia potrzebne do powielenia tych eksperymentów, to podważamy najważniejszy komponent metody naukowej: możliwość niezależnego potwierdzenia lub obalenia doniesień naukowych. A bez tego komponentu nie ma mowy o prawdziwej nauce.

Od jakiegoś czasu wielką karierę robi pojęcie otwartej nauki (ang. open science) lub otwartych badań (ang. open research). Przykładowa inicjatywa promująca ideę otwartej nauki to Science Commons. Science Commons zajmuje się trzema najważniejszymi aspektami: (a) adnotacją danych i badań w taki sposób, aby w łatwy sposób mogły być ponownie wykorzystane przez innych naukowców, (b) ułatwieniem dostępu do materiałów badawczych poprzez opracowanie nowego typu licencji prawnej, oraz (c) opracowaniem specjalnego języka ułatwiającego integrację wyników badawczych osiąganych w przeszłości. W ramach inicjatywy Science Commons zdefiniowano główne cechy otwartej nauki w następujący sposób:

  • otwarty dostęp do literatury powstałej w ramach badań dofinansowanych: wszystkie wyniki badawcze, nawet w przypadku gdy badania były finansowane ze środków niepublicznych, powinny być całkowicie dostępne w Internecie, a licencja powinna umożliwiać swobodne pobieranie, wykorzystywanie, drukowanie, kopiowanie, cytowanie, linkowanie, indeksowanie i przetwarzanie wyników bez żadnych ograniczeń prawnych, technologicznych czy finansowych
  • otwarty dostęp do narzędzi wykorzystywanych w ramach badań dofinansowanych: jeśli w trakcie badań wykorzystano specjalne narzędzia, to narzędzia te powinny być dostępne w formie szczegółowych opisów (w formie cyfrowej) umożliwiających replikację przeprowadzonych badań, to samo dotyczy np. linii komórek wykorzystywanych w badaniach, narzędzi do analizy DNA, itp.
  • dane w domenie publicznej: wszystkie dane, bazy danych, zbiory i protokoły użyte w badaniach, także badaniach finansowanych ze środków niepublicznych, muszą znaleźć się w domenie publicznej, z możliwością kopiowania, reformatowania, dystrybuowania i włączania danych do nowych badań lub wykorzystania danych do weryfikacji poprawności przeprowadzonych eksperymentów
  • inwestycje w otwartą cyber-przestrzeń: infrastruktura umożliwiająca współwykorzystywanie i współdzielenie danych naukowych powinna być traktowana jako wspólne dobro, infrastruktura powinna być otwarta, darmowa, rozszerzalna i dostępna zarówno dla środwiska naukowego, jak i podatników

Innym przykładem inicjatywy promującej koncepcje otwartej nauki jest Public Library of Science. PLoS to inicjatywa utworzenia nowego modelu publikowania wyników naukowych. W chwili obecnej jest to siedem czasopism (PLoS One, PLoS Biology, PLoS Medicine, PLoS Genetics, PLoS Computational Biology, PLoS Neglected Tropical Diseases, PLoS Pathogens), do których dostęp jest całkowicie otwarty i darmowy (publikowanie w tych czasopismach jest płatne). Wszystkie czasopisma PLoS są recenzowane i mają wysokie współczynniki impact factor, przykładowo, na liście MNiSW PLoS Biology ma 30 punktów, PLoS Medicine ma 24 punkty, a PLoS Genetics i PLoS Computational Biology mają po 10 punktów.

Zasady działania Public Library of Science są sformułowane w postaci listy obejmującej: otwartość dostępu, doskonałość, naukowa uczciwość, uniwersalność publikacji, kooperacja, dostępność finansowa, zaangażowanie społeczności naukowej, międzynarodowość i udostępnienie nauki jako powszechnego i dostępnego zasobu publicznego. Warto się zaznajomić ze szczegółowym opisem tych zasad.

A wszystkie te dywagacje są wynikiem mejla, który dostałem. Zakończyła się 36 konferencja International Conference on Very Large Data Bases (VLDB’2010) i wszystkie artykuły prezentowane w trakcie tej konferencji są publicznie dostępne. Jeśli ktoś się zajmuje zawodowo bazami danych, to powinien natychmiast przejrzeć zawartość materiałów konferencyjnych.

Książka do pobrania (za darmo!) 08/04/2010

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

Od jakiegoś czasu stałem się wielkim fanem systemu R. Dziś z dużą radością natknąłem się na ciekawą pozycję: wprowadzenie do statystyki i probablistyki ilustrowane przykladami w R. Książka pod tytułem „Introduction to Probability and Statistics Using R” autorstwa G. Jay Kernsa obejmuje sobą następujące zagadnienia:

  • wprowadzenie do probabilistyki
  • wprowadzenie do języka R
  • formaty danych
  • teoria prawdopodobieństwa
  • rozkłady dyskretne i ciągłe
  • rozkłady wielu zmiennych
  • rozkłady próbek
  • estymacja i przedziały ufności
  • testowanie hipotez
  • regresja liniowa prosta i wielokrotna
  • metody bootstrap

A to wszystko bardzo bogato ilustrowane przykładami w R. I co więcej, całkowicie legalnie i za darmo do pobrania ze strony www.lulu.com! Sama książka także ma swoją stronę domową, z której możecie między innymi ściągnąć wtyczkę do R Commandera, popularnego GUI do systemu R, a także pobrać pełne źródła książki w Latexu i Lyxie.

Prawo Benforda 01/06/2010

Posted by Mikołaj Morzy in nauka, teoria.
2 comments

Prawo Benforda, zwane także prawem pierwszej cyfry (choć istnieje także alternatywne sformułowanie dotyczące drugiej najbardziej znaczącej cyfry), dotyczy rozkładu częstości występowania poszczególnych cyfr na najbardziej znaczącej pozycji w dużej kolekcji danych. Okazuje się, że cyfry nie są rozłożone jednostajnie, lecz zgodnie z rozkładem

P(d)=\log_{10}(1+\frac{1}{d})

gdzie d oznacza cyfrę z przedziału <1,9>. Prawo działa także dla liczb innych niż wyrażonych w systemie dziesiętnym, zmienia się tylko podstawa logarytmu.

Najciekawsze jest to, że prawo Benforda działa tylko wówczas, jeśli kolekcja danych jest generowana przez rzeczywisty proces, którym rządzi rozkład wykładniczy potęgowy (patrz komentarze).  Dotyczy to np. wielkości miast, długości rzek, rozmiarów populacji miast, cen w sklepach, itp. Dzieje się tak dlatego, że w przypadku rozkładów potęgowych otrzymujemy jednostajny rozkład cyfr po zlogarytmowaniu oryginalnych wartości, tzn. jest takie samo prawdopodobieństwo, że rzeka ma od 10 do 100 km długości, jak to, że rzeka ma od 100 do 1000 km długości. Rozkłady potęgowe są bardzo często spotykane w przyrodzie i naukach społecznych, toteż pole do stosowania prawa Benforda jest szerokie. Innym ważnym czynnikiem jest aby rozkład wartości był niezależny od skali, na jakiej jest mierzony (tzw. scale invariance). Tak się akurat składa, że tylko rozkłady potęgowe posiadają tę cechę, ponieważ mając dany rozkład potęgowy f(x)=ax^k jeśli przeskalujemy x o stałą c, otrzymamy f(cx)=a(cx)^k=c^kf(x)\propto f(x).

Prawo Benforda nie działa, jeśli kolekcja danych została spreparowana przy użyciu rozkładów losowych i pseudo-losowych, ponieważ rozkład najbardziej znaczącej cyfry staje się wówczas jednostajny. Okazuje się, że można ten fakt wykorzystać do zidentyfikowania, czy zbiór danych został sfałszowany. Zaproponowano wykorzystanie prawa Benforda do audytu sprawozdań finansowych, księgowości, wyników wyborów, itp. Dziś dowody na podstawie prawa Benforda są akceptowane jako dowody sądach amerykańskich. Całkiem niedawno prawo Benforda zostało wykorzystane do nadzorowania uczciwości przeprowadzania wyborów. W szczególności, dużo kontrowersji wzbudziły ostatnie wybory prezydenckie w Iranie. Walter Mebane wykorzystuje prawo Benforda do stwierdzenia, że prawdopodobnie wyniki zostały sfałszowane.

Z czystej ciekawości postanowiłem sprawdzić, czy prawo Benforda stosuje się do cen przedmiotów wystawianych w serwisie Allegro. Poniżej przedstawiam rozkład najbardziej znaczącej cyfry cen produktów wyliczony na podstawie próbki liczącej ponad 300 tysięcy przedmiotów (na osi odciętych najbardziej znacząca cyfra ceny, na osi rzędnych procent aukcji z daną ceną), zgodność jest uderzająca:

Dla uczciwości dodać należy, że Frank Benford sprawdził poprawność tego  prawa dla dużej liczby różnych zbiorów danych i opublikował wyniki swoich prac w 1935 roku, natomiast oryginalnym odkrywcą prawa był astronom Simon Newcomb w 1881 roku. Podobno odkrył je czytając tablice logarytmów i zauważając, że początkowe strony tablic (z logarytmami zaczynającymi się od cyfry 1) były dużo bardziej zużyte, niż inne strony. Swoją drogą, czytanie tablic logarytmów wygląda na dziwaczne hobby.

Jak zarobić $1 000 000 nie ruszając się sprzed biurka? 11/25/2009

Posted by Mikołaj Morzy in nauka, teoria.
1 comment so far

W zasadzie nawet nie 1 milion, ale 6 lub 7 milionów dolarów (7, jeśli bardzo się pospieszycie). Clay Mathematics Institute of Cambridge (Cambridge w stanie Massachusetts) wpadł na ciekawy pomysł świętowania nowego millennium. Zebrał trochę pieniędzy (rzeczone $7 000 000), wybrał siedem milenijnych problemów matematycznych i zaoferował okrągły $1 000 000 za rozwiązanie każdego z problemów. Oczywiście, wyraźnie widać tu wpływ Dawida Hilberta i jego słynnych 10 problemów matematyki, ogłoszonych w trakcie Międzynarodowego Kongresu Matematyków w Paryżu w 1900 roku. Hilbert później rozszerzył listę do 24, a następnie zmniejszył do 23 problemów. Jak pokazała historia, rozwiązanie wielu problemów z listy Hilberta popchnęło matematykę znacząco do przodu a konkurencja między naukowcami ścigającymi się w rozwiązywaniu kolejnych problemów zaowocowała wieloma nieoczekiwanymi rozwiązaniami (np. rezultatami prac podjętych w odpowiedzi na tezy Hilberta były dwa wielkie twierdzenia Goedla: twierdzenie o niezupełności i twierdzenie o niedowodliwości niesprzeczności). Z oryginalnej listy Hilberta na dzień dzisiejszy:

  • 10 problemów zostało definitywnie rozstrzygniętych,
  • 8 problemów zostało częściowo rozstrzygniętych lub rozwiązania są dyskusyjne (przede wszystkim ze względu na wielość interpretacji samego sformułowania problemu przez Hilberta),
  • 5 problemów do dziś nie zostało rozstrzygniętych (w tym najsłynniejszy problem, czyli Hipoteza Goldbacha: każda liczba parzysta większa niż 2 da się przedstawić jako suma dwóch liczb pierwszych).

Problemy podane przez CMIC to nowy zestaw (powtarza się tylko problem Hipotezy Riemanna). Nie muszę dodawać, że nie są to problemy z gatunku takich, które można zabrać ze sobą do toalety zamiast sudoku. Jako informatyka cieszy mnie, że na liście znalazł się także problem P != NP (o którym pisałem już wcześniej).

Pełna lista problemów jest następująca:

  1. hipoteza Bircha i Swinnerton-Dyera
  2. hipoteza Hodge’a
  3. równania Naviera-Stokesa
  4. problem P != NP
  5. hipoteza Pointcare’go (w zasadzie rozwiązana, ale trudny charakter Grigorija Perelmana uniemożliwia mu odebranie nagrody)
  6. hipoteza Riemanna
  7. pole Yanga-Millsa

Szczegółowe reguły i zasady konkursu są dostępne na stronach Clay Mathematics Institute.

Bardzo ciekawa konferencja 11/06/2009

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

W dniach 4-7 stycznia 2010 w Pekinie odbędzie się konferencja o nazwie The First Symposium on Innovations in Computer Science (ICS 2010). To jest bardzo ciekawy pomysł, który polega, z grubsza rzecz biorąc, na zebraniu artykułów typu position paper lub vision paper i zaprezentowaniu ich w jednym miejscu. Jak zauważają organizatorzy i pomysłodawcy konferencji, tego typu prace mają poważne trudności w przebiciu się podczas tradycyjnych konferencji. W cfp czytamy m.in.:

Innovations in Computer Science (ICS) is a new conference in theoretical computer science, broadly construed. ICS seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or cross-disciplinary areas, or introducing novel techniques or novel applications of known techniques). ICS welcomes all submissions whether they are aligned with the current TCS research directions or transcend these boundaries.

Jest to pierwsza edycja tej konferencji i mam nadzieję, że będzie udana. Lista streszczeń artykułów przyjętych do prezentacji wygląda bardzo obiecująco! A najfajniejsze w tym wszystkim jest to, że znakomita większość artykułów prezentowanych na tej konferencji jest publicznie dostępna (podziękowania dla Shivy Kintali’ego za zebranie wszystkich linków). Szkoda tylko, że materiały konferencyjne są publikowane w lokalnym zeszycie a konferencja odbywa się tak daleko. I że w przyszłym roku też odbędzie się w Pekinie.

Wszystkie najlepsze rzeczy w życiu są za darmo 10/31/2009

Posted by Mikołaj Morzy in eksploracja danych, nauka, teoria, zbiór danych.
2 comments

eslNa przykład książka „The Elements of Statistical Learning” autorstwa Trevora Hastie, Roberta Tibshirani i Jerome Friedmana. To już druga edycja książki wydanej przez Springera w serii „Springer Series on Statistics„. Na ponad 700 stronach książka opisuje m.in.: uczenie nadzorowane, regresję liniową, klasyfikację liniową i regresję logitową, metody wygładzania, metody oceny modeli, wnioskowanie bayesowskie, metody bootstrap, algorytm EM, różne algorytmy indukcji drzew, techniki boosting, sieci neuronowe, rodzinę algorytmów SVM, metody k-najbliższych sąsiadów, odkrywanie reguł asocjacyjnych, metody analizy skupień, wybór cech przy użyciu metod PCA i ICA, algorytmy Random Forest, metody uczenia Ensemble oraz eksplorację danych wielowymiarowych. A najlepsze jest to, że książkę tę można (legalnie, bez targania z osiołka) mieć za darmo.

Książka jest dostępna na stronie domowej Roberta Tibshirani na Stanfordzie. Ale to nie wszystko! Wraz z książką można pobrać:

Chapeaux bas dla wydawcy, że pozwolił umieścić tę książkę w sieci. Książka już trafiła na moją listę lektur polecanych studentom.

Czy można udowodnić, że P != NP? 10/09/2009

Posted by Mikołaj Morzy in nauka, teoria.
1 comment so far

acm_logoW najnowszym numerze Communications of the ACM Lance Fortnow z Northwestern University McCormick School of Engineering prezentuje artykuł pt. „The Status of the P Versus NP Problem„. Pokazuje w nim sposoby, na jakie informatycy i matematycy próbowali „ugryźć” najsłynniejszy problem informatyki. Artykuł jest świetnie napisany i stanowi doskonałe wprowadzenie do tego fascynującego tematu. Najbardziej spodobał mi się fragment, w którym autor przedstawia potencjalne konsekwencje dowodu na to, że P=NP. Oczywiście, przestałaby natychmiast działać współczesna kryptografia, oparta głównie na infrastrukturze klucza publicznego i założeniu, że faktoryzacja ogromnych liczb na jest bardzo trudna. Ale oprócz tego czekałby nas nowy wspaniały świat:

Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I’m just scratching the surface. Learning becomes easy by using the principle of Occam’s razor—we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of  eather and earthquakes and other natural phenomenon.

I jeszcze jedno zdanie na zachętę:

A person who proves P = NP would walk home from the Clay Institute not with $1 million  check but with seven (actually six since the Poincaré Conjecture appears solved).  Don’t get your hopes up. Complexity theorists generally believe P ≠ NP and such a beautiful world cannot exist.

Artykuł jest też dostępny jako plik pdf. A jeśli artykuł Wam się podoba, koniecznie odwiedzcie blog Lance’a Fortnowa: Computational Complexity.

%d bloggers like this: