Egy kis kategóriaelmélet

Egy ideje pár barátommal kategóriaelmélettel foglalkozunk hobbiból. Az elmúlt hetek során pár nagyon jó forrást ismertem meg, ezek úgy gondolom az olvasók számára sem haszontalanok.

Dominic Verity előadása remek áttekintést nyújt, különösen Haskell programozóknak ajánlom.

An Introduction to Category Theory - FP-Syd talk from Alex Mason on Vimeo.

Conceptual Mathematics

Ez a kötet egy igazi gyöngyszem! Kb józan paraszti ésszel és némi középiskolai matekkal felvértezve bárki elsajátíthatja belőle a kategóriaelmélet alapjait.

Category Theory

Awodey könyve ma a standard tankönyv filozófus és nyelvész körökben, de a matematikusok sem vetik meg. Talán kicsit túl sok a gyakorlati emberek számára, de ezt ellensúlyozza hogy olvasmányos (már amennyire egy kategóriaelmélet könyv az lehet).

Oxford Quantum Talks Archive

Remek kis előadások a szakma legjobbjaitól! Bob Coecke Lambek vs Lambek előadása olvasóinknak kötelező :D

Matematika felnőtteknek

Keith Delvin Mathematics: Making the Invisible Visible kurzusa az iTunes-ból kitört és immár elérhető a youtube-on is! Sokunk közös élménye az unalmas iskolai matematika óra. Delvin előadásai viszont kifejezetten szórakoztatóak és alkalmasak arra, hogy motiválják a matek-fóbiában szenvedőket.

Often described as the science of patterns, mathematics is arguably humanity's most penetrating mental framework for uncovering the hidden patterns that lie behind everything we see, feel, and experience. Galileo described mathematics as the language in which the laws of the universe are written. Intended to give a broad overview of the field, these five illustrated lectures look at counting and arithmetic, shape and geometry, motion and calculus, and chance and probability, and end with a mind-stretching trip to infinity.

A többi videó megtekinthető itt.

FP és termékfejlesztés

Két remek példa arra, hogy nem csak az általam imádott Prismatic esetében jó húzás egy funkcionális nyelv mellett letenni a garast.

1) Machine Learning at Unfold

Az Unfold Clojure-t használ. Ellenben a Prismatic-kel nem mennek el a "99% pure Clojure" irányba, hanem kihasználják a Java interop nyújtotta lehetőségeket. Így kipróbálhatnak minden elérhető eljárást és rögtön akár production módba kapcsolhatnak. Ez az igazi rapid prototyping! A többit a video jobban elmeséli, én annyi megjegyzést fűzök ehhez, hogy egy idő után a legtöbb Clojure shop a fontos részeket úgyis megírja magának.

2) Running a Startup on Haskell

Bryan O'Sullivan neve a Real World Haskell kapcsán biztos sokak számára ismerős. Ebben a videóban a MailRank-kel kapcsolatos tapasztalatairól beszél, no meg úgy általában a Haskell-ről, különös tekintettel ipari alkalmazására :D. Valamit csak tudnak, hiszen a Facebook tavaly meg is vette a céget egy tipikus acqui-hire keretében.

Prismatic

A Prismatic tkp. remek példa több dologra is. Mi a keresés jövője? Van valami igazán izgalmas felhasználása az NLP-nek és az ML-nek? Lehet egy terméket teljesen egy funkcionális nyelvre alapozni? A perszonalizációval együtt járó filter bubble jelensége ellen tehetünk valamit?

A Prismatic első ránézésre egy a sok hírolvasó eszköz közül ami a közösségi oldalon megjelenő híreket aggragálja. De nem egészen erről van szó! A Prismatic saját magát "discovery engine"-nek hívja és a hírek tálalását csak az első lépésnek tartja. A közösségi médiában megjelenő tartalmakat tkp. arra használják, hogy kitalálják a felhasználó ízlését és azt hogy milyen filtert épít maga köré. Sajnos arról nem lehet sokat megtudni miképp is működik ez az újdonságot behozó elem, de aki már eltöltött pár órát a Prismatic-en, az tapasztalatból tudja hogy egész jól működik.

A cég blogja is mutatja, mennyire átgondoltan halad a termékfejlesztés. Tulajdonképpen talán a Prismatic az egyetlen cél, ahol holisztikusan koncentrálnak egy adott problémára. Nagyon erős vizióval rendelkeznek arról hogyan is kell az ML és az NLP eredményeit felhasználni egy termékben és arról hogyan is néz ki az alkalmazott kutatás. Az alapoktól egészen a mutatós svájci designt idéző webes megjelenésig átgondoltak mindent (itt és itt érdemes erről olvasni). Érdemes megnézni TC Founder Stories alapítóval készített interjúját.

Ma a legtöbb kereső rendszer az ún term-document matrix megoldáson alapul. A Prismatic az ún topik modellekre szavaz ellenben (bővebben erről itt). Ezek nagyon hasonlóak a címkéző, vagy tagelő megoldásokhoz, de sokkal pontosabban működnek és írják le egy-egy dokumentum látens szemantikáját. A topik modellek a keresésben - több technikai probléma megoldásán túl - lehetővé teszik hogy "csoportosítsák" a találatokat és egyfajta összefoglalót adjanak tartalmukról. Így kerülhető el a duplikációk és a hasonló hírek szűrése, ill. kereshetők hasonló tartalmak. Habár a topik modellek már egy évtizede megjelentek, a Prismatic egyike az első ipari alkalmazóknak.

A "filozófia" mellett természetesen a fejlesztésben is jólátgondolt elveik vannak. Elsőre talán furcsa, hogy a Clojure-t választották, de ez még érthető is (plána, nekem, aki szeretem a Clojure nyelvet). Ami sokkal meglepőbb hogy nem igazán használnak Java cuccokat, inkább maguk írnak meg mindent amire szükségük van. Clojure körökben idézetté vált az "avoid large, monolithic frameworks" mottó (de persze inkább keresünk egy wrapper-t, vagy írunk magunk, semhogy a Prismatic-et követve saját numerikus könyvtárat dobjunk össze :D), ami az abstraction principle-re utal. Ezt az architektúrára is átvitték, a technikai részletek iránt érdeklődőknek ajánlom a High Scalability-n megjelent részletes írást erről.

Úgy tűnik, működőképes ez a szigorúan termékközpontú fejlesztés. Jó lenne látni több kezdeményezést, ami ennyire fókuszáltan és tudatosan vezet be a piacra egy alapvetően elméleti megoldást.

Kategóriaelmélet és jQuery

A kategóriaelméletet a közkedvelt meghatározás szerint "general abstract nonsense". Ez persze korántsem jelenti azt, hogy nem lehet gyakorlatias dolgokra használni eredményeit. Pl. John Bender egészen zseniálisan alkalmazta az ún. loop fusion technikát a jQuery-ben. De hogy kerül a csizma az asztalra? Bender working paper-je így foglalja össze:

The jQuery JavaScript library, used on more than 55% of Alexa’s top 10,000 websites makes the manipulation of HTML documents easy and intuitive through fluent method chaining and an intuitive API design. An unfortunate side effect of these user friendly features is that they often incur an otherwise unnecessary performance overhead. While JavaScript execution in desktop browsers has become fast enough to hide much of the problem, the growing complexity of HTML documents and the ubiquity of web enabled mobile devices continue to make performance an important concern when developing JavaScript applications. We address this issue by proposing a category theoretic view of the relationship between jQuery and the Document Object Model. From that view we derive a set of alterations to the jQuery library and demonstrate the performance benefits that result. Additionally we show how the second functor law suggests a set of JavaScript functions and jQuery methods that can be optimized using loop fusion.

 

Az alábbi videón teljesen érthető formában fejti ki vizsgálódásainak lényegét Bender. Érdemes a lejátszás előtt és után is elolvasni rövid posztját.

 

Könyvismertető: Digital_Humanities (ingyenes e-könyv)

A digitális bölcsészet iránt még csak érdeklődők és a területen otthonosan mozgók számára is hasznos kiadvány a Digital_Humanities, mely elektronikus verziója ingyen letölthető. 

• Peter Lunenfeld, Anne Burdick, Johanna Drucker, Todd Presner, Jeffrey Schnapp: Digital_Humanities
• MIT Press, 2012
• 153 oldal
• Open Access Edition (pdf)

Az MIT Press beharangozója remekül összefoglalja miről olvashatunk:

Digital_Humanities is a compact, game-changing report on the state of contemporary knowledge production. Answering the question, “What is digital humanities?,” it provides an in-depth examination of an emerging field. This collaboratively authored and visually compelling volume explores methodologies and techniques unfamiliar to traditional modes of humanistic inquiry--including geospatial analysis, data mining, corpus linguistics, visualization, and simulation--to show their relevance for contemporary culture.
Included are chapters on the basics, on emerging methods and genres, and on the social life of the digital humanities, along with “case studies,” “provocations,” and “advisories.” These persuasively crafted interventions offer a descriptive toolkit for anyone involved in the design, production, oversight, and review of digital projects. The authors argue that the digital humanities offers a revitalization of the liberal arts tradition in the electronically inflected, design-driven, multimedia language of the twenty-first century.

Nagyon kellemesen olvasható a kötet, bölcsészeknek inspirációt ad a technológia elsajátításához, IT felől érkezőknek pedig megmutatja mi mindenre lehet/lehetne használni a technológiát.

Try R - ingyenes statisztikai programozás kurzus

Sokak számára nehéz időt találni a Coursera kurzusainak követésére, vagy nem rendelkeznek kellő alapokkal ahhoz hogy belevágjanak egybe. Habár a Udacity remek munkát végzett és rövid részekre oszt egy-egy leckét és saját tempójában haladhat a tanuló ezeken végig, még így is sok időt kell invesztálni egy kurzus elvégzésébe. A Try R nem kínál királyi utat a statisztikai programozás iránt érdeklődőknek, de elvégzésével biztos alapokra tehet szert bárki, ami a további kurzusoknál nagyon jól jöhet. A tananyag hét "fejezetre" van tagolva, az első három az R nyelv alapjaiba nyújt bevezetést, a harmadik a klasszikus leíró statisztikával foglalkozik, majd az alapvető adatstruktúrákkal ismerkedhet meg az olvasó, az utolsó fejezetben pedig haladóbb témákba is belekóstolhat a tanuló. A gamification divatnak megfelelően "badges" gyűjtést folytat az aki végigmegy az egyes leckéken, amiről én nem tudom eldönteni hogy nettó poén, vagy tényleg inspiráló dolog. A c<>de school és az O'Reilly nagyon jó mukát végzett, most már nincs mentség és ha valaki meg akarja tanulni a statisztikai programozás alapjait, csak az elhatározás hiánya állhat útjába.

Mire jó a funkcionális programozás

Sokan úgy vannak a funkcionális programozással mint a big data-val; ízlelgetik, próbálgatják és foglalkoznak vele, mert mindenki más is ezt teszi. Alapvetően három dolog fokozta fel a paradigma iránti érdeklődést 1) a MapReduce-t a funkcionális paradigma ihlette 2) a statisztikai programozás és a gépi tanulás terén népszerű R nyelv és a mostanában különösen startupok körében elterjedt Clojure sikere 3) a párhuzamos feldolgozás elterjedése. A posztban megpróbálom körüljárni hogy tényleg jobb-e a funkcionális paradigma és hogy milyen feladatokra érdemes funkcionális nyelvet választani.

Az első kérdésre - ti. hogy jobbak-e a funkcionális nyelvek - a válasz egész egyszerűen az hogy nem. Bővebben; se nem jobbak, se nem rosszabbak mint pl. az OO nyelvek. Ennek oka, hogy a jelenlegi Neumann-architektúrán Turing-ekvivalensek. Ezen nincs értelme vitatkozni, mivel bizonyított tény, hogy amit az egyik paradigmában meg tudunk oldani, azt a másikban is elérhetjük. Más lapra tartozik, hogy Backus híres Can Programming Be Liberated from the Neumann Style? esszéjében megmutatta, hogy a jövőben más lesz a helyzet, de erre már harminc éve várunk és még jó ideig várnunk kell.

Peter Naur Programming as Theory Building esszéje más oldalról közelíti meg a dolgot. Naur szerint a programozó munkája során externalizálja (külsővé teszi) és mások által használhatóvá teszi tudását. De miből áll ez a tudás? Egyrészt a programozó jártas kell hogy legyen a számítástudományban, másrészt jó adag általános intelligenciával is rendelkeznie kell hogy megértse a kapott feladatait. Elvben egy jó programozó mindent meg tud oldani, gyakorlatban specializálódás ment végbe a szakmában, ami továbbra is tart és csak fokozódni fog.

Aria Haghighi nem rég írt az ACM blogján arról, hogy miért hagyta ott rendkívül ígéretes akadémiai karrierjét és lett a Prismatic társalapítója. Haghighi saját bevallása szerint nem akarta életét egy egy részterület apró kis problémájának szentelni. Habár az NLP-ben szeretjük azt hinni hogy majd egyszer eljutunk a teljességhez, vagy a közelébe kerülünk, igazából a tudomány logikáját követve részterületek alakultak ki, mely kutatói elvannak a saját kis problémáikkal. Ez hatással van arra, hogy miképp jelenik meg az NLP az alkalmazott területeken. Egy termék fejlesztése során ha felmerülnek számítógépes nyelvészeti kérdések, akkor a fejlesztők egy palettáról válogatják össze a megoldásokat. Így az NLP a mellékes featur-ökbe szivárog be. Haghighi O'Reilly Radar-on megjelent írásában megjegyzi, hogy az igazán érdekes problémákra nincs ilyen "leemelhető" válasz. Ha tényleg szeretnénk megoldani egy kérdést és a termékünket erre szánjuk, akkor holisztikusan kell gondolkodnunk!

Naur tézisét szerintem a legtöbben elfogadják. Adjuk ehhez hozzá Haghighi gondolatait is. Az NLP (és a gépi tanulás, továbbá valamennyi kutatás-vezérelt terület) esetében is azon van a hangsúly hogy a fejlesztő tudását szoftverbe tudja "önteni", s ha jó terméket akarunk, akkor a lehető legjobb szerszámot kell megtalálnuk ehhez. Az erősen formalizált tudományok esetében a legjobb szerszám egy funkcionális programozási nyelv, mivel ezek segítségével egy ismerős nyelven lehet kifejezni a formális elméleteket.

A párhuzamos feldolgozás terén valóban izgalmas dolgok történnek a funkcionális paradigmában. De itt is sokkal inkább arról van szó, hogy megfelelő absztrakciós eszköz áll egyes fejlesztők rendelkezésére. Pankratius és tsai alapos összehasonlító kísérlet során arra jutottak hogy

Contrary to popular belief, the functional style does not lead to bad performance. Average Scala run-times are comparable to Java, lowest run-times are sometimes better, but Java scales better on parallel hardware. We confirm with statistical significance Scala’s claim that Scala code is more compact than Java code, but clearly refute other claims of Scala on lower programming effort and lower debugging effort.

A megállapítás sokkal inkább az ún. generalista programozókra vonatkozik, akik egy software shopban készítenek a "beeső" ügyfeleknek különféle alkalmazásokat. Ilyenkor egy jó szaki dolga, hogy ügyfelével konzultálva a lehető legjobb szolgáltatást tudja nyújtani. Ilyen környezetben nem jár előnyökkel egy funkcionális nyelv használata.

A kutatás-intenzív termékfejlesztés során azonban a funkcionális nyelvek használata megkönnyíti a kutatók és a fejlesztők dolgát. A kutatóknak nem kell ún. throw away prototípusokkal bíbelődniük kedvenc nyelvükben, a fejlesztők nem kapnak agyvérzést amikor a prototípusok alapján kell valódi termékké formálniuk az ötleteket. Rövidül a fejlesztés idő, olcsóbbá válik a hibázás (ami a kutatás része) és csökken a kockázat (érdemes Paul deGrendis Clojure-powered Startups előadását megnézni a témában erről).