jump to navigation

The Advisor czyli koniec bibliografii 08/31/2012

Posted by Mikołaj Morzy in konferencja, nauka, sieci społeczne.
9 Komentarzy

W trakcie tegorocznej konferencji ASONAM wysłuchałem ciekawej prezentacji pt. „Fast Recommendation on Bibliographic Networks” wygłoszonej przez Onura Kucuktunca z Ohio State University. Idea polega na przyspieszeniu algorytmu rekomendującego artykuły naukowe na podstawie historycznej bazy bibliograficznej. Główny algorytm rekomendacyjny to losowy spacer z restartem (RWR, ang. random walk with restart), autorzy niestety nie podają źródła dla bazy danych cytatów. Idea algorytmu jest prosta: rozpoczynając od wskazanego artykułu naukowego A podążaj losowo do artykułów cytujących artykuł A lub prac cytowanych przez A. W zależności od dodatkowego parametru algorytmu losowy spacer może mieć preferencję do prac starszych lub nowszych. Unikanie pułapki zapętlenia odbywa się przez losowy przeskok do innego artykułu. Z czysto naukowego punktu widzenia interesujące są zaproponowane optymalizacje: po pierwsze autorzy sugerują przeorganizowanie macierzy sąsiedztwa opisującej graf cytowań w taki sposób, aby losowy spacer unikał cache misses, czyli żeby kolejne bloki danych wymagane przez algorytm znajdowały się już w pamięci podręcznej (tzw. lokalność odwołań do pamięci). Po drugie, autorzy wprowadzają do algorytmu z pozoru niewielkie poprawki, które ponad sześciokrotnie redukują liczbę aktualizacji pozycji w macierzy sąsiedztwa. W efekcie uzyskują ogromne przyspieszenie działania algorytmu.

A teraz najciekwasze.

Algorytm został zaimplementowany w prototypowym systemie theadvisor, dostępnym w postaci usługi webowej. System przyjmuje na wejście plik Bibtex lub RIS z częściową bibliografią, a w odpowiedzi wyrzuca rekomendowaną listę pozycji literaturowych. Podane na wejście pozycje stanowią ziarno (ang. seed) od którego algorytm rekomendacyjny zaczyna przeszukiwanie bazy danych bibliograficznych. Nie posiadając plliku Bibtex lub RIS można także podać nazwisko autora lub nazwę obszaru (oczywiście kosztem trafności rekomendacji). Jakby tego było mało, theadvisor wyświetla rekomendowaną listę prac oraz dostarcza wizualizacji powiązań między publikacjami.

Załóżmy, że pracuję nad artykułem dotyczącym ewolucji sieci społecznościowych w czasie. Rozpocząłem od zdefiniowania prac „Graphs over time: densification laws, shrinking diameters and possible explanations” i „Graph evolution: Densification and shrinking diameters” Leskoveca, Kleinberga i Faloutsosa jako moich głównych inspiracji. Następnie ustawiam suwak „I want papers to be more…” pośrodku między opcjami „traditional” i „recent” i klikam na przycisk „Start the search with the selected papers”.  Odpowiedź theadvisor jest następująca:

Relevant Citations

  1. Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos:
    On Power-law Relationships of the Internet Topology.
    SIGCOMM, pp.251-262, 1999. [dblp] [citeseer] [pdf] [google]
  2. Hongwu Ma, An-Ping Zeng:
    The Connectivity Structure, Giant Strong Component and Centrality of Metabolic Networks.
    Bioinformatics, 19(11):1423-1430, 2003. [dblp] [arXiv] [citeseer] [pdf] [google]
  3. Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
    The Web as a Graph: Measurements, Models, and Methods.
    COCOON, pp.1-17, 1999. [dblp] [citeseer] [pdf] [google]
  4. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan D. Sivakumar, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal:
    Stochastic Models for the Web Graph
    [citeseer] [pdf] [google]
  5. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
    Trawling the Web for Emerging Cyber-Communities.
    Computer Networks, 31(11-16):1481-1493, 1999. [dblp] [citeseer] [pdf] [google]
  6. Michael Mitzenmacher:
    A Brief History of Generative Models for Power Law and Lognormal Distributions.
    Internet Mathematics, 1(2), 2003. [dblp] [citeseer] [pdf] [google]
  7. P. Erdős, A Rényi:
    On the Evolution of Random Graphs
    1960. [citeseer] [pdf] [google]
  8. Jon M. Kleinberg:
    Authoritative Sources in a Hyperlinked Environment.
    J. ACM, 46(5):604-632, 1999. [dblp] [citeseer] [pdf] [google]
  9. Fan R. K. Chung, Linyuan Lu, Van H. Vu:
    The Spectra of Random Graphs with Given Expected Degrees.
    Internet Mathematics, 1(3), 2003. [dblp] [citeseer] [pdf] [google]
  10. Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos:
    R-MAT: A Recursive Model for Graph Mining.
    SDM, 2004. [dblp] [citeseer] [pdf] [google]

A na dodatek jeszcze to:

Visualization of bibliographic database

Wiele wskazuje na to, że przez najbliższy czas kompilowanie referencji do artykułów stanie się dużo łatwiejsze. Cały prototyp jest dostępny pod adresem theadvisor.osu.edu

Reklamy

ASONAM 2012, dzień 2 08/28/2012

Posted by Mikołaj Morzy in konferencja, nauka, sieci społeczne.
14 Komentarzy

Hagia Sophia in IstanbulDrugi dzień konferencji rozpoczął wykład zaproszony wygłoszony przez Barry’ego Wellmana z Uniwersytetu w Toronto. Wellman dopiero co opublikował książkę „Networked. The New Social Operating System„, którą już zamówiłem i po przeczytaniu zamieszczę tu krótką recenzję (powinna być ciekawa, bo Wellman jest socjologiem z głęboką znajomością Internetu, ale w przeciwieństwie do większości informatyków potrafi umiejscowić Internet w szerszym kontekście ludzkiej działalności lub porównać zmiany społeczne spowodowane przez usieciowienie z wcześniejszymi etapami rozwoju ludzkich społeczeństw). Wykład, zatytułowany „The New Social Operating System”, był w dużej mierze streszczeniem książki. Prawdę powiedziawszy, Wellman na scienie mnie rozczarował. Wykład był niemrawy i nie przedstawił niczego rzeczywiście nowego (w przeciwieństwie do wczorajszego wystąpienia Ulrika Brandesa). Wellman omawiał ogólne zmiany społeczne (emancypacja kobiet, większe usieciowienie społeczeństw, gwałtowne zwiększenie się liczby miękkich więzów, spadek znaczenia tradycyjnych ograniczeń w kontaktach międzyludzkich, takich jak etniczność, płeć, religia, orientacja seksualna). Kilkakrotnie powtórzył, że twierdzenie jakoby tradycyjne więzy międzyludzkie ulegały erozji w wyniku korzystania z Internetu (na pewno kojarzycie współczesne Kassandry rozpaczające nad tym że ludzie ze sobą nie rozmawiają bo wolą się „polubić” na Facebooku) jest kompletną bzdurą nie popartą żadnymi badaniami. Jest dokładnie odwrotnie, badania jednoznacznie wskazują że osoby aktywnie korzystające z internetu i udzielające się w sieciach społecznościowych zdecydowanie bardziej się socjalizują w świecie rzeczywistym. „The more is the more”.

Póżniej zaczęły się regularne sesje. John Lee z Uniwersytetu Filipin przedstawił ciekawą pracę pt. „Link Prediction in a Modified Heterogeneous Bibliographic Network„. Sama metoda nie jest może specjalnie odkrywcza, ale artykuł zawiera bardzo staranny przegląd wcześniejszych prac w obszarze predykcji odnośników. Rozczarowało mnie jednak to, że w pracy Lee rozważa jedynie grafy (tzn. jeśli kiedykolwiek osoby A i B napiszą wspólnie pracę, między A i B powstaje krawędź w grafie). Bardziej interesowałoby mnie gdyby graf był hipergrafem, tzn. żeby każda współpraca między A i B tworzyła nową krawędź. Taka niewielka zmiana niestety powoduje zdecydowany wzrost trudności w predykcji. Ciekawa była też praca prezentowana przez Marco Pellegriniego pt. „Fast exact computation of betweenness centrality in social networks„. To bardzo elegancki artykuł prezentujący metodę polepszenia algorytmu Brandesa wyznaczania miary pośrednictwa, która z kolei jest używana w wielu bardziej złożonych algorytmach, np. w algorytmie Girvan-Newmana partycjonowania grafu.

Ciekawą prezentację pokazał Yongli Ren z Deakin University. Praca zatytułowana „Learning Rating Patterns for Top-N Recommendations” dotyczyła drogiego memu sercu tematu odkrywania wzorców na potrzeby systemów rekomendacyjnych. Autorzy eksperymentowali na zbiorze danych Netflix i wyszukiwali konkretnych wzorców sekwencyjnych wskazujących na zmianę preferencji użytkownika w miarę upływu czasu. Muszę przeczytać cały artykuł żeby dobrze uchwycić ideę algorytmu, ale wyniki i opis wyglądały obiecująco. Bardzo ciekawie wypała prezentacja Onura Kucuktunca „Fast Recommendation on Bibliographic Networks„. Generalnie dużo było prac dotyczących badań nad sieciami naukowymi, co mnie szczególnie interesuje ze względu na to, nad czym aktualnie pracuję. Grupa Kucuktunca z Ohio State University przygotowała algorytm na sterydach, wykorzystujący specjalne struktury w pamięci operacyjnej oraz permutacje macierzy sąsiedztwa w celu maksymalnego przyspieszenia algorytmu typu RandomWalk na sieci bibliograficznej. Co ciekawe, ich artykuł został zaimplementowany w prototypie, któremu poświęcę osobną notkę.

Znajomość angielskiego pomaga (w pracy naukowej) 08/27/2012

Posted by Mikołaj Morzy in humor.
3 Komentarze

Dlaczego warto znać angielski gdy się człowiek zabiera za pracę naukową? Bo wówczas łatwiej uniknąć kompromitujących wpadek w przygotowywanych publikacjach. Nieoceniony w tropieniu takich perełek Marek Wojciechowski przesyła poniższe dwa przykłady

[1] Tzong-Wann Kao, Shi-Jinn Horng, Yue-Li Wang, Horng-Ren Tsai, „Designig Efficient Parallel Algorithms on CRAP„, IEEE Transactions on Parallel and Distributed Systems, Volume 6 Issue 5, May 1995, Pages 554-560

[2] Lei Zhang, Guoyou Wang, Wentao Wang, „A New Fuzzy ART Neural Network Based on Dual Competition and Resonance Technique„, Lecture Notes in Computer Science, 2006, Volume 3971, Advances in Neural Networks – ISNN 2006, Pages 792-797

W pierwszym przypadku streszczenie artykułu wyjaśnia, że CRAP to

„A cross-bridge reconfigurable array of processors is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm […]”

W drugim przypadku streszczenie artykułu nie tylko nie pomaga, ale wręcz pogarsza sprawę. Ostatnie zdanie streszczenia jasno mówi że

„[…] Experimental results have shown that compared with the original FART, this algorithm has a better segmentation and antinoise performance.”

ASONAM 2012, dzień 1 08/27/2012

Posted by Mikołaj Morzy in konferencja, nauka.
5 Komentarzy

Widok Istambułu znad Złotego RoguDziś zaczęła się konferencja ASONAM 2012. Konferencja odbywa się w przepięknym Istambule i potrwa trzy dni. Jest to kolejna edycja konferencji która wcześniej gościła na Tajwanie i w Danii. W niedzielę odbyło się parę warsztatów, dziś wystartowała główna konferencja. Poniżej umieszczam na gorąco swoje pierwsze wrażenia.

Gianni Costa i Riccardo Ortale prezentują artykuł „A Bayesian Hierarchical Approach for Exploratory Analysis of Communities and Roles in Social Networks„. W artykule prezentują model, który jest w stanie jednocześnie przypisywać aktorów sieci do wspólnot, a następnie przypisywać aktorom role na podstawie wspólnoty, do ktorej aktor należy. Metoda wykorzystuje wnioskowanie bayesowskie a do konstrukcji zbioru testowego przeprowadza próbkowanie Gibbsa w ramach LDA (Latent Dirichlet Allocation). Wyniki wyglądają obiecująco, mimo dużego obciążenia obliczeniowego narzuconego przez LDA (w szczególności LDA-G, metodę LDA przystosowaną specjalnie do grafów). Swoje wyniki weryfikują na dobrze znanych publicznych zbiorach danych Enron i Small World. Richard Oentaryo pokazuje jak można przewidzieć zjawisko porzucania usługodawcy przez klientów sieci społecznościowej w artykule „Collective Churn Prediction in Social Network„. Jak się okazuje, można z dość dużym prawdopodobieństwem (około 50%) przewidzieć, kiedy dana osoba rozważa porzucenie sieci społecznościowej (to akurat przykład sieci typu chat na Tajwanie). Bardzo ciekawą prezentację przedstawił James Lanagan. W pracy pt. „Knowing a Good Show When You See One” przedstawił wyniki analizy forów internetowych ze strony Television Without Pity w których sprawdził intensywność dyskusji po emisji odcinków popularnych seriali (Breaking Bad, Dexter, Office, itp.) Dzięki analize trendów pojawiajacych się w konwersacjach widzów James jest w stanie dokonać grupowania wypowiedzi (wykorzystuje algorytm k-średnich i indeks Hartigana do znalezienia właściwej liczby klastrów). Nie do końca wiem, jakie zastosowanie ma ta metoda, ale brzmi bardzo ciekawie.

Wykład zaproszony zaprezentował Ulrik Brandes z Universitaet Konstanz. Wykład był zatytułowany „A Network Science Manifesto” i był absolutnie fantastyczny. Brandes poddał w wątpliwość większość prawd objawionych w obszarze analizy sieci społecznościowych i zmasakrował nawet najbardziej podstawowe definicje podawane np. przez A-L. Barabasiego czy D. Wattsa. Główna teza Brandesa to konieczność zdefiniowania od nowa nauki o sieciach i oderwania się od ścisłego powiązania nauki o sieciach od teorii grafów. Jego definicja, z którą się całkowicie zgadzam, jest następująca:

Network science is the study of collecting, managing, analyzing, interpreting and presenting data on incidence structures.

Brandes twierdzi, że najważniejszymi, podstawowymi strukturami w naukach o sieciach są struktury incydencji (sąsiedztwa). Sprawa abstrakcji badanego zjawiska do postaci sieci jest najtrudniejszym i najważniejszym zadaniem (którego nie mogą podjąć się naukowcy od sieci, do tego potrzebna jest wiedza dziedzinowa). Posiadając sieciową abstrakcję zjawiska dopiero przystępujemy do wyboru reprezentacji i tu mamy do wyboru wiele sposobów: graf, wektor, algebra relacji, itp. W trakcie procesu abstrakcji zjawiska do sieci tracimy wiele informacji, które Brandes nazywa głęboką strukturą danych, której badanie powinno być podstawowym badaniem. W dodatku, jak twierdzi Brandes, nie istnieje jedna uniwersalna teoria sieci i jej poszukiwanie jest stratą czasu, a prezentowane w literaturze propozycje nazywa wsiami potiomkinowskimi. Głównym hasłem manifestu jest zatem powrót do podstaw i zdefiniowanie sposobów abstrakcji i reprezentacji zjawisk. Przyznaję szczerze, że te pomysły od dawna chodziły mi po głowie, nawet w zeszłym roku napisałem na ten temat artykuł z propozycją algebry dla sieci społecznościowych, ale artykuł był przygotowany na kolanie i został z hukiem odrzucony. Po dzisiejszym wykładzie mam zamiar do niego powrócić.

Po przerwie na lunch najbardziej podobała mi się prezentacja Davida Skillicorna pt. „Global Similarity in Social Network with Typed Edges„. Skillicorn przedstawił bardzo elegancką metodę łączenia informacji w sieciach wielomodalnych, w których niektórzy aktorzy funkcjonują jako łączniki między poszczególnymi poziomami sieci. Metoda została przetestowana na sławnym zbiorze Padgetta zawierającym informacje o rodzinach w renesansowej Florencji. W tej samej sesji miałem przyjemność prezentować artykuł napisany wspólnie z Pawłem Lubarskim pt. „Measuring the Importance of Users in a Social Network Based on Email Communication Patterns„. Zamieszczam też przygotowaną na tę okazję prezentację.

Teraz trwa panel dyskusyjny nt. przyszłości całej dziedziny analizy i eksploracji sieci społecznościowych. Prawdę powiedziawszy, niezbyt odkrywczy…

Jutro zamieszczę relację z kolejnego dnia. Gdy tylko artykuły z konferencji ukażą się online, mam zamiar zaktualizować notkę i dodać odnośniki do tych prac.

Eksploracja danych i muzyka (part 4) 08/26/2012

Posted by Mikołaj Morzy in humor, muzyka.
4 Komentarze

Tim Minchin

Wracamy do gry. Po długim milczeniu, w obliczu nowego semestru i nowego grantu i po wielu przemyśleniach postanowiłem dać sobie po raz ostatni szansę. Jeśli uda mi się wypracować sensowny sposób pracy nad blogiem i utrzymywać zadowalającą regularność, może uda się zbudować nową jakość (tym bardziej że lista rzeczy do opisania jest baaaardzo długa).

Zaczynam od czegoś lekkiego. W naszym cyklu „Eksploracja danych i muzyka” mieliśmy już drzewa decyzyjne, zespół złożony z profesorów, oraz punk-rock. Teraz przedstawiam Wam mojego ukochanego Tima Minchina oraz najbardziej statystycznie poprawną piosenkę o miłości.


Tim Minchin, If I didn’t have You

Yeah, yeah
If I didn’t have youIf I didn’t have you to hold me tight
(If I didn’t have you)
If I didn’t have you to lie with at night
(When I’m feeling blue)
If I didn’t have you to share my sights
(Share my sights)
And to kiss me and dry my tears when I cry

Well I really think that I would…
Have somebody else

(If I didn’t have you)
If I didn’t have you, someone else would do

Your love is one in a million
(One in a million)
You couldn’t buy it at any price
(Can’t buy love)
But of the 9.999 hundred thousand other loves
Statistically, some of them would be equally nice
(Equally nice)
Or maybe not as nice but, say, smarter than you
Or dumber but better at sport or tracing
I’m just saying
(I really think that I would)
Probably
(Have somebody else)

Yeah

(If I didn’t have you)
If I didn’t have you someone else would do
(Someone else would surely do)

If I were a rich man
Diddle-diddle-diddle-diddle-diddle-diddle-diddle-ee
I guess I would be with a surgeon or a model
Or a rellie of the Royals or a Kennedy
Or a nymphomonical exhibitionist heiress to a large chain of hotels
If I were a rich man, maybe I would fiddle
Fiddle-diddle-diddle with the rich man girls

I’m not saying that I’d not love you if I was wealthy or handsome
But realistically there’s lots of fish in the sea
And if I had a different rod I would concievably land some
Even though I am fiscally consistantly pitiable
And considerably less Brad Pitt than Brad Pitiful
Am I really so poor and ugly that you reckon only you could possibly love me?
And I
(Really think that I would)
Probably
(Have somebody else)

(If I didn’t have you)
If I didn’t have you, someone else would do
(Someone else would surely do)

And look, I’m not undervaluing what we’ve got when I say
That given the role chaos inevitably plays in the inherently flawed notion of „fate”
It’s obtuse to deduce that I’ve found my soulmate at the age of seventeen
It’s just mathematically unlikely that at a university in Perth
I happened to stumble on the one girl on Earth specifically designed for me
And if I may conjecture a further objection, love is nothing to do with destined perfection
The connection is strengthened, the affection simply grows over time
Like a flower
Or a mushroom
Or a guinea pig
Or a vine
Or a sponge
Or bigotry
… or a banana

And love is made more powerful by the ongoing drama of shared experience
And the synergy of a kind of symbiotic empathy or… something

So I trust it would go without saying
That I would feel really very sad
If tomorrow you were to fall off something high
Or catch something bad
But I’m just saying
I don’t think you’re special
I-I mean, I think your special
But you fall within a bell curve
I mean, I’m just saying I
(Really think that I would)
Probably
(Have somebody else)

I think you are unique and beautiful
(Unique and beaut)
You make me happy just by being around
(Being around)
But objectively, you would have to agree that baby when I found you
Options were relatively thin on the ground
(Thin on the ground)
You’re lovely but there must be girls as lovely as you
And maybe more open to spanking or table tennis
I’m just saying
(Really think that I would)
Probably
(Have somebody else)

I mean I reckon it’s pretty likely that if, for example
My first girlfriend, Jackie, hadn’t dumped me
After I kissed Winston’s ex-girlfriend Neah at Steph’s party back in 1993
And our variables would probably have been altered by the absence of that event
To have meant the advent of a tangential narrative in which we don’t meet
Which is to say there exists a theoretical hypothetical parallel life
Where what is is not as it is and I am not your husband and you are not my wife

And I am a stuntman living in LA
Married to a small, blonde Portuguese skier
Who, when she’s not training
Does abstract painting
Practices yoga
And brews her own beer
And really like making home movies
And suffers neck down alopecia

But with all my heart and all my mind, I know one thing is true
I have just one life and just one love and, my love, that love is you
And if it wasn’t for you, darling you

(Really think that I would)
Probably
(Have somebody else)

(If I didn’t have you)
If I didn’t have you someone else would surely do

%d blogerów lubi to: