Nebezpečná umělá inteligence od OpenAI?

17. 02 201919. 02 2019Jiří Materna

Americká nezisková společnost OpenAI před několika dny na svém blogu zveřejnila článek, ve kterém píše o tom, že vyvinula nový jazykový model, který je tak dobrý, že raději nezveřejní ani natrénovaný model, ani zdrojové kódy. Pro řadu médií (včetně některých seriózních českých) takové zprávy fungují jako červený hadr na býka a okamžitě tak začaly vznikat články o tom, že byla vyvinutá průlomová umělá inteligence, která je tak nebezpečná, že se musí držet pod pokličkou. Rád bych uvedl věci na pravou míru.

V první řadě je třeba přiznat, že OpenAI se v článku nedopustila žádného faulu a důvody, kvůli kterým nechtějí zveřejnit zdrojové kódy, znějí rozumně. Je však evidentní, že autoři dobře tušili, jak budou média reagovat a jde tak z jejich strany o promyšlený marketingový tah. O tom svědčí i poslední věta článku, která končí slovy „we’re hiring“.

A s čím tedy vědci z OpenAI přišli? Byl vytvořen zřejmě velmi dobrý jazykový model. Jazykovým modelem se rozumí nástroj, který na základě libovolné posloupnosti slov umí určit pravděpodobnosti možných slov, která by mohla následovat. Pro příklad uveďme posloupnost dvou slov

máma mele

Úkolem jazykového modelu je doplnit následující slovo posloupnosti. To může být teoreticky jakékoliv slovo, ale jistě každý tuší, že některá slova budou pravděpodobnější než jiná. Pravděpodobnosti následujících slov mohou vypadat například následovně:

slovo	pravděpodobnost
maso	0,6
kávu	0,1
koření	0,1
Emu	0,01
Ostatní slova	0,19

Pokud díky jazykovému modelu známe pravděpodobnosti následujících slov, můžeme je vyžít pro generování úplně nových textů. Postup je následující:

První slovo zvolíme sami, nebo ho vybere nějakým náhodným způsobem.
Pravděpodobnosti pro následující slovo nám už určuje jazykový model. Slovo tedy vybereme náhodně s ohledem na tyto pravděpodobnosti. Je možné si to představit tak, že vezmeme hrací kostku, která nemá 6 stěn, ale tolik stěn, kolik různých slov máme k dispozici. Na každou stěnu takové kostky vlepíme závaží, jehož hmotnost bude odpovídat pravděpodobnosti daného slova.
Onou hrací kostkou si hodíme a zapíšeme si slovo, které nám padlo. Tím nám vznikne posloupnost o jedno slovo delší. Na jejím základě podle jazykového modelu upravíme pravděpodobnosti pro následující slovo a celý postup opakujeme od bodu 2.

Klíčem k úspěchu a k vytvoření smysluplné posloupnosti slov je tedy kvalitní jazykový model. Na to existují už lety prověřené postupy. Nejprve potřebujeme dostatečně velkou kolekci textových souborů, která slouží jako vzorové texty. V oboru strojového učení se takovému datovému souboru říká trénovací data. Pokud se v těchto trénovacích datech bude po slovech máma mele vyskytovat maso častěji, než jiná slova, budeme chtít, aby jazykový model posloupnosti máma mele maso přiřadil velkou pravděpodobnost.

Na druhou stranu ale nechceme, ale si jazykový model jen zapamatoval časté posloupnosti. Chceme, aby byl schopný zobecňovat i na posloupnosti, které se v trénovacích datech nevyskytly. K tomu slouží algoritmy strojového učení.

Podle článku OpenAI byly pro strojové učení použity „staré známé“ algoritmy (velmi podobné například tomu, který byl sloužit pro generování básní), jen trénovací data a kapacita paměti modelu byla o mnoho řádů větší než dříve. To bylo umožněno díky velmi výkonné výpočetní infrastruktuře, která běžným smrtelníkům mimo špičková AI centra není dostupná.

V čem tedy spočívá nebezpečí takového modelu? V žádném případě se nejedná o nějakou formu samostatně uvažující umělé inteligence. Stále jsou to jen náhodné procesy a statistiky počítané z trénovacích dat. Díky jejich složitosti je však možné generovat texty, které jsou velice podobné textům psaným lidmi. Zneužít je lze například pro strojové generování fake news nebo komentářů v diskuzích. S pomocí těchto přístupů je možné vygenerovat libovolné množství různorodého textu, které nebude stát víc než trochu elektrické energie.

Přitom texty nemusí být jen bezduchým blábolením. Zaměření textů je vždy dáno trénovacími daty. Pokud se pro trénování použijí ideově zabarvené propagandistické texty, výsledek bude k nerozeznání od lidmi psaného obsahu na některých fake news serverech.

Sami autoři článku píší, že replikace jejich výsledků nebude velký problém. Přestože byly zveřejněny pouze zdrojové kódy menšího modelu, použité principy jsou ve vědecké komunitě dobře známy a jeho rozšíření je pro znalého člověka snadné. Jediným zásadním omezením je obrovská výpočetní náročnost. Ta se však týká jen procesu vytváření modelu. Jakmile model někdo vytvoří a zveřejní, jeho použití už je velmi snadné i s využitím řádově menšího výpočetního výkonu. Navíc z Moorova zákona víme, že výpočetní výkon počítačů roste v čase přibližně exponenciálně a nebude tedy trvat dlouho, než si takový generátor bude moci každý z nás natrénovat na svém mobilu.

Ze strany OpenAI tedy o žádný velký průlom nejde. Navíc by bylo naivní si myslet, že už se takovýmito generovanými texty náš mediální prosto dávno neplní. Jen se tím autoři těchto generátorů textů veřejně nechlubí.

Proč a kdy fungují slovní analogie v algoritmech word2vec

13. 08 2017Jiří Materna

Od publikování prvního algoritmu Tomáše Mikolova, převádějícího slova na vektory se zajímavými vlastnostmi (psal jsem o něm zde), uběhlo již několik let. Stále se však lidé snaží více či méně uspokojivě vysvětlit, jak je možné, že "kings – king + queen = queens". Před časem napsal podobný text na svém blogu Piotr Migdal. Článek je inspirativní, ale obsahuje řadu nepodložených tvrzení a předpokladů. Rád bych zde prezentoval alternativní zdůvodnění vycházející ze stejných myšlenek, které však bude preciznější.

Jedním z hlavním přínosů většiny takzvaných word embedding algoritmů (cbow, skipgram, glove, atd.) je schopnost projektovat lexikální jednotky (nejčastěji slova) do vektorového prostoru, ve kterém morfologické, syntaktické i některé sémantické vlastnosti těchto slov zachovávají lineární závislosti. Znamená to, že když například vektor slova king odečteme od vektoru slova kings, dostaneme vektor, který lze významově chápat jako vektor přechodu od singuláru k plurálu. Pokud tento vektor přičteme k libovolnému substantivu v singuláru, dostaneme se v daném vektorovém prostoru velmi blízko k vektoru stejného slova v plurálu. Tuto vlastnost ilustruje známý obrázek převzatý z původního článku T. Mikolova.

Obrázek 1: Vektorová reprezentace slov. Zdroj: T. Mikolovov et al. : Linguistic Regularities in Continuous Space Word Representations, NAACL 2013.

Tohoto fenoménu lze využít k hledání slovních analogií. Mohli bychom se ptát na slovo W, pro které platí: king se má ke kings jako queen k W. V obecnosti bychom chtěli ukázat, že pokud se slovo a má ke slovu A stejně jako slovo b ke slovu B, potom přibližně platí v_a – v_A = v_b – v_B, kde v_x je vektor reprezentující slovo x, získaný některým z algoritmů word2vec (viz Obr. 1).

Word2vec je zobecňující pojmenování pro metody převodu slova na jeho vektorovou reprezentaci. Pro účely tohoto textu se zaměřme konkrétně na nejznámější algoritmus Skip-gram s negativním samplováním.

Abychom mohli dané tvrzení dokázat, je třeba se nejdříve vypořádat s vágní definicí vztahu “mít se stejně k”. To většina literatury zanedbává a spokojuje se jen s intuicí. Pro větší přehlednost budeme v následujícím textu tučnou kurzívou označovat lexikální jednotky, kurzívou jejich vlastnosti a tučně zápis lexikální jednotky v korpusu.

Vyjděme z Firthova pohledu na lexikální význam. Jeho známý citát „You shall know a word by the company it keeps“ lze, volně přeloženo, chápat tak, že význam slova je dán slovy, která se s ním často pojí. Podle jeho tvrzení tedy platí, že dvě slova mají podobný význam tehdy, když se v textech často vyskytují ve stejných kontextech. Jedná se o v praxi často využívaný pohled na lexikální sémantiku.

Význam slova a lze ve Firthově pojetí formalizovat jako soubor pravděpodobností SEM(a) = 〈P(w | a): w ∈ L〉, které vyjadřují pravděpodobnost výskytu slova w blízko slova a v jazyce L. Ten nechť je reprezentovaný dostatečné velkým jazykovým korpusem. Blízkost je určena nějakou maximální vzdáleností v textu (měřeno počtem slov, která je oddělují).

Dalším důležitým poznatkem je Fregeho princip kompozicionality, který nám říká, že význam složitějšího lexikálního výrazu je dán významem dílčích jednotek a způsobem jejich kombinace. Tento princip se dá vztáhnout i na význam slov – slovo je nositelem souboru dílčích významů, která dohromady dávají význam celého slova. Například slovo queen lze zjednodušeně chápat jako anglické substantivum označující osobu, která má současně vlastnosti být panovníkem s královským titulem a být ženského pohlaví.

Vycházejíce z předchozích dvou formulací můžeme tedy význam slova queen definovat pomocí pravděpodobností〈P(w_i | je panovník ∧ je ženského pohlaví )〉, v obecnosti jako 〈P(w_i | a₁, a₂, … a_n)〉.

Nyní již lze zadefinovat slovní analogie: a se má k A stejně jako b k B tehdy, když existují vlastnosti a₁... a_n, b₁... b_n, c a d takové, že

SEM(a) =〈P(w_i | a₁, a₂, … a_n, c)〉

SEM(A) =〈P(w_i | a₁, a₂, … a_n, d)〉

SEM(b) =〈P(w_i | b₁, b₂, … b_m, c)〉

SEM(B) =〈P(w_i | b₁, b₂, … b_m, d)〉.

Pokud budou platit následující statistické nezávislosti výskytů vlastností slov v korpusu

P(a₁, a₂, … a_n) ⊥ P(c)

P(a₁, a₂, … a_n) ⊥ P(d)

P(b₁, b₂, … b_m) ⊥ P(c)

P(b₁, b₂, … b_m) ⊥ P(d)

Dostaneme pro všechna w_i

$\dfrac{P(\mathbf{w_i} | \mathbf{a})}{P(\mathbf{w_i} | \mathbf{A})} = \dfrac{P(\mathbf{w_i} | \mathbf{b})}{P(\mathbf{w_i} | \mathbf{B})}$

neboť

$\dfrac{P(\mathbf{w_i} | \mathbf{a})}{P(\mathbf{w_i} | \mathbf{A})} = \dfrac{P(\mathbf{w_i} | a_1 \dots a_n, c)}{P(\mathbf{w_i} | a_1 \dots a_n, d)} = \dfrac{P(\mathbf{w_i}, a_1 \dots a_n, c)P(a_1 \dots a_n, d)}{P(\mathbf{w_i}, a_1 \dots a_n, d)P(a_1 \dots a_n, c)} =$

$=\dfrac{P(a_1 \dots a_n, c | \mathbf{w_i})P(\mathbf{w_i})P(a_1 \dots a_n)P(d)}{P(a_1 \dots a_n, d | \mathbf{w_i})P(\mathbf{w_i})P(a_1 \dots a_n)P(c)} = \dfrac{P(a_1 \dots a_n | \mathbf{w_i})P( c | \mathbf{w_i})P(d)}{P(a_1 \dots a_n | \mathbf{w_i})P( d | \mathbf{w_i})P(c)} =$

$= \dfrac{P( c | \mathbf{w_i})P(d)}{P( d | \mathbf{w_i})P(c)} = \dfrac{P(\mathbf{w_i}|P(b_1 \dots b_m, c)}{P(\mathbf{w_i}|P(b_1 \dots b_m, d)} = \dfrac{P(\mathbf{w_i} | \mathbf{b})}{P(\mathbf{w_i} | \mathbf{B})}$ .

Nyní již lze analogie snadno zdůvodnit

$\dfrac{P(\mathbf{w_i} | \mathbf{a})}{P(\mathbf{w_i} | \mathbf{A})} = \dfrac{P(\mathbf{w_i} | \mathbf{b})}{P(\mathbf{w_i} | \mathbf{B})}$

$\mbox{log} \Bigg( \dfrac{P(\mathbf{w_i} | \mathbf{a})}{P(\mathbf{w_i})} \cdot \dfrac{P(\mathbf{w_i})}{P(\mathbf{w_i} | \mathbf{A})} \Bigg) = \mbox{log} \Bigg( \dfrac{P(\mathbf{w_i} | \mathbf{b})}{P(\mathbf{w_i})} \cdot \dfrac{P(\mathbf{w_i})}{P(\mathbf{w_i} | \mathbf{B})} \Bigg)$

$\mbox{log} \dfrac{P(\mathbf{w_i} | \mathbf{a})}{P(\mathbf{w_i})}-\mbox{log} \dfrac{P(\mathbf{w_i} | \mathbf{A})}{P(\mathbf{w_i})}=\mbox{log} \dfrac{P(\mathbf{w_i} | \mathbf{b})}{P(\mathbf{w_i})}-\mbox{log} \dfrac{P(\mathbf{w_i} | \mathbf{B})}{P(\mathbf{w_i})}$

Přičemž z definice pointwise mutual information platí

$\mbox{PMI}(\mathbf{w_i},\mathbf{a}) -\mbox{PMI}(\mathbf{w_i},\mathbf{A}) =\mbox{PMI}(\mathbf{w_i},\mathbf{b}) -\mbox{PMI}(\mathbf{w_i},\mathbf{B})$ .

Teď využijeme výsledek práce Levy & Yoav Goldberg, 2014, kde bylo ukázáno, že algoritmus Skip-gram s negativním samplováním aproximuje rozklad matice slov a kontextů, kde jednotlivé buňky matice odpovídají (až na konstatní posuv) pointwise mutual information. Autoři Arora & kol., 2015 sice ukazují, že aproximace se blíží skutečnosti jen u vektorů vysoké dimenze a navrhují vlastní důkaz, pro potřeby tohoto článku nám však tvrzení stačí:

$\mbox{PMI}(\mathbf{w},\mathbf{a}) \approx v_\mathbf{w} \cdot v_\mathbf{a}$ .

Odsud již dostaneme kýženou lineární závislost vektorů, odpovídající slovním analogiím:

$v_\mathbf{a} - v_\mathbf{A} = v_\mathbf{b} - v_\mathbf{B}$ .

Problémem důkazu je předpoklad nezávislosti výskytu jevů v korpusu, který samozřejmě ve většině případů neplatí. To je něco, čím se žádný ze mně známých důkazů analogií v algoritmech word2vec kvůli vágní nebo chybějící definici významu slov nezabýval. Je možné, že existuje silnější důkaz, který předpoklad nezávislosti jevů nepotřebuje. Druhou možností je, že slovní analogie fungují přesně jen v případě statisticky nezávislých jevů. Ani pro jedno však nemám zdůvodnění, a proto nechávám otázku otevřenou pro případné zájemce z řad čtenářů.

Pro tuto chvíli však nechme stranou exaktní důkazy a podívejme na několik příkladů analogií napočítaných algoritmem skip-gram na korpusu českého internetu.

+ slovo	- slovo	+ slovo	nejbližší slovo výsledku	kosinová podobnost
královna	král	řidič	řidička	0.785
			Řidička	0.682
			cyklistka	0.625
rybářka	rybář	ošetřovatel	ošetřovatelka	0.692
			Ošetřovatelka	0.619
			canisterapeutka	0.605
královna	kozel	řidič	řidička	0.609
			čtyřiadvacetiletá	0.532
			dvaadvacetiletá	0.511
rybářka	kozel	ošetřovatel	krotitelka	0.574
			ošetřovatelka	0.547
			pasačka	0.541

V tabulce jsou vždy uvedena tři slova, která slouží jako dotaz a ke každému dotazu 3 nejbližší slova nalezená v prostoru spolu s kosinovou podobností. U prvního příkladu, kde je dotazem v(královna) – v(král) + v(řidič) vidíme, že analogie krásně fungují a dvě nejbližší nalezená slova jsou řidička a Řidička. Ve druhém příkladu byla záměrně použita slova, pro která předpoklad nezávislosti výrazněji neplatí. Vlastnost být rybářem a být muž, spolu jistě pozitivně korelují. Podobně jako vlastnosti být ošetřovatel a být žena. Přestože kosinová podobnost nejbližšího kandidáta je nižší než v předchozím případě, stále je výsledkem správná odpověď ošetřovatelka. Třetí příklad je extrémnější. Dotazem je zde v(královna) – v(kozel) + v(řidič) a výsledkem stále řidička, i když už s výrazně nižší kosinovou podobností. Tento výsledek je trochu zarážející a neodpovídá naší intuici. Zdá se, že vlastnost být mužem a být ženou je natolik dominantní, že převáží všechny ostatní. Teprve poslední příklad, který kombinuje extrémy předchozích ukázek, dopadne jinak. Na dotaz v(rybářka) – v(kozel) + v(ošetřovatel) najdeme jako nejbližší slovo krotitelka.

Těchto pár příkladů samozřejmě vůbec nic nedokazuje. Je z nich však vidět, že hledání analogií pomocí word2vec přístupů je velmi odolné vůči šumu. Může tedy dobře fungovat i v případě, že by byl pro přesný důkaz požadavek nezávislosti jevů nutný. Navíc nepřesností, které do procesu hledání analogií vstupují, je mnoho (velikost a zaměření korpusu, velikost reprezentujících vektorů, apod.) a je jen otázkou, jak velkou chybu jednotlivě způsobují. Velká odolnost vůči nim je podle mého názoru zajištěna velkou řídkostí vektorového prostoru, ve kterém analogie hledáme. Pro dotaz v(královna) – v(kozel) + v(řidič) najdeme jako odpověď slovo řidička jednoduše proto, že se v blízkosti žádné jiné slovo nenachází.

Konvergence algoritmu k-means

15. 06 201612. 08 2017Jiří Materna

U pohovorů na pozici výzkumníka v Seznamu se ptávám na principy vybraných algoritmů strojového učení, mezi které patří i k-means pro shlukování. Po tom, co algoritmus dáme dohromady, následuje otázka, zda je zaručené, že algoritmus vždy skončí. Tušil jsem, že se dají najít extrémní případy, kdy algoritmus může začít nekonečně dlouho kmitat mezi několika stejně dobrými řešeními, a tak jsem požadoval drobné doplnění ukončovací podmínky (například detekci cyklu), která by ukončení garantovala.

Nedávno jsem však narazil na uchazeče, který byl skálopevně přesvědčený, že standardně definovaný k-means skončí za všech okolností a přísnější kritérium není potřeba. Vzhledem k tomu, že jsem žádný protipříklad připravený neměl, zkusil jsem nejprve zahledat na internetu. A ejhle. Internet je plný „důkazů“ toho, že k-means konverguje. Tvrdí to dokonce i Wikipedie! Nezbylo mi tedy nic jiného, než ten protipříklad vymyslet. Tady je.

Algoritmus k-means

K-means patří do skupiny takzvaných algoritmů strojového učení bez učitele. Jeho cílem je nalezení k shluků daných bodů, kde shlukem rozumíme skupinu bodů, které jsou si navzájem blízko (ve smyslu nějaké metriky). Typickým příkladem použití může být analýza zákazníků internetového obchodu, které chceme podle zájmů a chování roztřídit do předem neznámých kategorií.

Vstupem algoritmu je množina m bodů, které jsou definované souřadnicemi v n-rozměrném prostoru, a číslo k, určující požadovaný počet shluků. Všechny shluky jsou reprezentované svými středy a každý bod potom náleží do shluku, jehož střed je mu nejblíže. Souřadnice středů se určují iterativním způsobem založeným na EM algoritmu. Zde uvádím jeho neformální zápis (zájemci o preciznější definici si ho můžou nastudovat na příklad na Wikipedii):

Pro každý shluk zvol náhodně souřadnice jeho středu (typicky se volí totožně se souřadnicemi náhodně vybraných různých bodů).
Každý bod přiřaď středu, ke kterému leží nejblíže.
Urči nové souřadnice středů jako průměr souřadnic všech bodů, které náleží do daného shluku.
Opakuj od bodu 2, dokud se shlukování neustálí.

Princip algoritmu je ilustrovaný obrázkem 1.

Obrázek 1: Algoritmus k-means.

Není obtížné dokázat, že tento iterativní algoritmus neustále zmenšuje chybu, definovanou jako součet vzdáleností všech bodů od středů svých shluků, a spěje tak k nějakému lokálně-optimálnímu řešení. Co však, pokud dojde k tomu, že má jeden bod stejně daleko ke středům dvou nebo více různých shluků? V takovém případě je možné náhodně vybrat libovolný z nich a v tom je kámen úrazu.

Protipříklady

Začněme velmi jednoduchým příkladem. Mějme pouze dva body, které leží přesně na sobě, a hledejme 2 shluky. Pokud budou jejich středy inicializovány do stejného místa jako shlukované body, máme problém, neboť v kroku 2 algoritmu bude mít každý bod stejně daleko ke dvěma středům, a může si tak vybrat odlišný od toho z předchozí iterace. Tím se změní shlukování a algoritmus tak pokračuje dál. Takto je možné kmitat mezi čtyřmi řešeními libovolně dlouho a algoritmus nemusí nikdy skončit.

Dalo by se namítnout, že se v tomto jednoduchém příkladu oba shluky překrývají a nemuseli bychom je tedy považovat za různá řešení. Lze však vymyslet i netriviální příklady.

Mějme 10 bodů v trojrozměrném prostoru, které leží na vrcholech a v polovinách středů hran pomyslného pravidelného čtyřstěnu, a hledejme 6 shluků, jejichž středy A, B, C, D, E, F jsou inicializovány do středů hran, jak je ilustrováno na obrázku 2.

Obrázek 2: Protipříklad.

V takovém případě jsou vždy body na vrcholech stejně daleko od tří různých středů a je možné je tedy přiřadit třem různým shlukům. Existují tři různá shlukování, mezi kterými může algoritmus kmitat, aniž by zkonvergoval. Tato různá řešení jsou znázorněna na obrázku 3.

Obrázek 3: Tři různá řešení.

Klasický algoritmus k-means tedy v extrémních případech konvergovat nemusí. Opatření, která jeho skončení zajistí jsou však snadná. Nejjednodušším z nich je determinizace výběru shluku v případě, že máme více možností. Shluky si můžeme očíslovat a místo náhodného výběru vybírat například vždy ten s nejnižším identifikátorem. Jinou možností je detekovat kmitání nebo změnit ukončovací podmínku algoritmu a zastavit v případě, že už se chyba shlukování nezmenšuje. Nic takového však standardní definice algoritmu neuvádějí a tvrzení, že k-means vždy konverguje je tedy nesprávné.