Aplikace algoritmu pozitivní selekce pro doporučení vhodného psího plemene

Aplikace algoritmu pozitivní selekce pro doporučení vhodného psího plemene Martina Husáková Univerzita Hradec Králové, Fakulta informatiky a managementu Hradecká 1249/6, 50003 Hradec Králové [email protected]

Abstrakt Algoritmus pozitivní selekce je základním selekčním algoritmem využívaným v umělých imunitních systémech. Slouží k nalezení takových prvků umělého imunitního systému, které jsou schopné detekovat jeho vlastní prvky. Tento postup je v příspěvku využit k doporučení vhodného psího plemene a implementován v multiagentovém modelovacím prostředí NetLogo.

1

Úvod

Biologie je oblastí, která v současné době výraznou a významnou měrou přispívá k řešení problémů v počítačové vědě. Tato skutečnost je patrná zejména ve výpočetní inteligenci, jejíž hlavní doménou je práce s neurčitými, nejistými a nepřesnými informacemi. Hlavními podoblastmi výpočtové inteligence, mající biologický základ, jsou genetické algoritmy (GA) a umělé neuronové sítě (UNS). K těmto předním reprezentantům začíná zaujímat své jisté postavení i paradigma beroucí si inspiraci z fungování biologického imunitního systému (BIS), tzv. umělé imunitní systémy (UIS). UIS poskytuje výpočetní inteligenci možnost pracovat s principy BIS, přičemž se v něm často promítají rysy jak GA tak UNS. V porovnání s GA a UNS se jedná o oblast poměrně mladou. Počátky jejího vzniku se datují k roku 1986, kdy J. D. Farmer spolu s dalšími napsal pojednání o adaptaci a strojovém učení založeném na imunitním síťovém modelu [10]. Od té doby bylo napsáno mnoho publikací, magisterských a doktorských prací [4], realizováno několik konferencí, z nichž nejznámější ICARIS je pořádána od roku 2002 [9]. I když od první zmínky o vztahu mezi výpočetní inteligencí a imunitním systémem uběhlo více než 20 let, nedá se říci, že by nebylo možné v této oblasti bádat dále. Vědci se stále aktivně zabývají [13]: • zlepšením a rozšířením UIS, • tvorbou nových UIS, • hledáním nových aplikačních oblastí, • upřesněním nebo rozšířením frameworku podle kterého se budou UIS vytvářet.

Současný vývoj UIS nesměřuje ani tak k vytvoření plnohodnotného BIS, ale k reprezentaci jeho vybraných mechanismů pro řešení určitých typů problemů efektivním způsobem. Snahou je například zabudovat určité principy imunitní ochrany a obrany do již existujících systemů [12]. Cílem tohoto příspěvku je, kromě teoretického seznámení s BIS a UIS, ukázat praktické využití jednoho základního algoritmu využívaného v UIS, tzv. algoritmu pozitivní selekce. Ten je zde využit k roztřídění vybraných plemen psů z FCI standardu [11] na ta, která jsou vhodná pro jeho potenciálního majitele a na ta, která nejsou. O požadovaném plemeni lze pak říci, nakolik je podobné kterému ze standardu FCI.

2

Biologický imunitní systém

2.1 Vlastnosti Biologický imunitní systém je komplexním systémem, který je nezbytný pro přežití jakéhokoliv organismu. Jeho úkolem je identifkovat, lokalizovat a patřičně reagovat na částice, které mohou být pro organismus nebezpečné. Tyto částice nazýváme antigeny. Antigenem je cokoliv co může vyvolat imunitní reakci. Rozdělujeme je na antigeny nevlastní (non-self) a vlastní (self). Do první skupiny spadají mikroorganismy způsobující různá onemocnění (viry, bakterie, houby, paraziti) a v druhé jsou prvky, které organismus považuje za svoji součást. BIS může některé vlastní buňky vyhodnotit jako nepřátele, útočit proti nim a to v důsledku tzv. autoimunitních onemocnění. Pokud ale BIS funguje správně, dokáže biologický systém udržet v rovnováze, rozpoznat a reagovat na nebezpečí, učit se a pamatovat si elementy, které ohrožovaly organismus v minulosti [3]. Na BIS se lze dívat z různých úhlů pohledu. Jedním z nich je specifičnost, podle které má BIS vrozenou (VIm) a adaptivní imunitu (AIm) [3], [17]. VIm je nespecifická, neadaptabilní, ale přitom cílenější než AIm - její buňky jsou okamžitě připraveny k boji, aniž by vyžadovaly určitou předchozí zkušenost s nepřítelem. K jejím součástem patří různé mechanické bariéry, např.

pokožka, hleny, slzy, sliny, žaludeční šťávy apod. Disponuje širokým spektrem imunitních buněk. Některé z nich poskytují na svém povrchu vzorky nepřátel jiným imunitním buňkám, které zajišťují AIm. AIm je specifická a namířena především k již jednou rozpoznaným nepřátelům. K hlavním imunitním buňkám v tomto případě patří B a T lymfocyty. Klíčovou funkcí B-lymfocytů je tvorba protilátek a schopnost přeměny na paměťové buňky s cílem urychlit aktuální imunitní odpověď při napadení stejným nebo velmi podobným nepřítelem z minulosti. T-lymfocyty protilátky netvoří. Přímo likvidují buňky napadené mikroorganismy nebo regulují funkce ostatních imunitních buněk [3], [5].

Obr. 2. Rozpoznávání antigenu B-lymfocyty

2.2 Princip funkce

3 BIS je postaven především na procesu rozpoznávání prvků organismu. B i T lymfocyty nesou na svém povrchu receptory schopné rozpoznat antigeny. Způsob rozpoznávání antigenů popíšeme na B-lymfocytech. Jak již bylo řečeno v podkapitole 2.1, hlavní funkcí B-lymfocytů je tvorba protilátek. Jedna B-buňka umí produkovat jen jeden specifický typ protilátky (obr. 1.), přitom antigen může mít na svém povrchu různé povrchové struktury, tzv. epitopy [5]. Jedná se o konkrétní oblasti antigenu, na které se mohou protilátky vázat.

Umělý imunitní systém

3.1 Vlastnosti, využití a reprezentace UIS je dynamický adaptivní systém, který v sobě implementuje principy a funkce BIS s cílem jejich použití k řešení problémů spojených s různými aplikačními oblastmi [13]. K těmto oblastem patří např.: • rozpoznávání vzorů a jejich klasifikace, • detekce chyb a anomálií, • učení, • optimalizace, • analýza dat. Většina modelů UIS využívá konceptu tzv. reprezentačního prostoru (prostoru tvarů) (RP), který byl představen roku 1979 A. S. Perelsonem a G. F. Osterem s cílem formálně popsat interakce odehrávající se mezi protilátkami a antigeny [5], [6]. Jedná se o obecný framework použitelný k reprezentaci abstraktních modelů imunitních buněk a molekul.

Obr. 1. B-lymfocyty s různými receptory Rozpoznávání je založené na tzv. komplementaritě mezi protilátkou (receptorem, detektorem) a epitopem. Tento princip odráží fakt, že rozpoznání (identifikaci) antigenu protilátkou se uskuteční tehdy, když do sebe obě částice zapadnou jako klíč do zámku. Tím se na sebe oba prvky naváží a B-buňka se aktivuje (obr. 2., upraven dle [5]). Poté dojde k množení těchto buněk (tvorbě klonů), které budou produkovat protilátky se stejnou specificitou, jako jejich rodičovské buňky. I T-lymfocyty se umí navázat na antigeny. Umožňují jim to právě povrchové receptory podobné protilátkám u B-buněk [5], [7].

Koncept pracuje s n-dimenzionálním prostorem obsahující protilátky (receptor, (r)) a antigeny (a), které jsou v tomto prostoru nejčastěji reprezentovány jako body. Každý receptor a antigen má vlastnosti obsažené v seznamu, který může nabývat celých čísel, reálných čísel, binárních hodnot, znaků, řetězců nebo jejich kombinaci. Receptor je dle tohoto konceptu charakterizován určitou afinitní prahovou (aktivační) hodnotou (e) určující do jaké vzdálenosti je ještě schopný receptor antigen rozpoznat (obr. 3.). K rozpoznání obou prvků dojde tehdy, když vzdálenost mezi receptorem (r) a antigenem (a) je menší než afinitní prahová (aktivační) hodnota (e), čili: d(r, a) < e [5], [12]. Větší vzdálenost ukazuje na větší rozdílnost porovnávaných prvků a naopak [12].

3.2

Obr. 3. Reprezentační prostor

3.1.1 Způsoby určování afinity Existují různé způsoby určování afinity (vzdálenosti, podobnosti). K nejznámějším patří: Euklidovská a Manhattanská vzdálenost využívající se u reálných hodnot a Hammingova vzdálenost nejpoužívanější u řetězců, znaků a binárních hodnot (obr. 4., upraven dle [5]). Výběr vhodné metody pro určování afinity závisí hlavně na doménové oblasti. Tyto a další typy měr jsou podrobně popsány např. v [7].

Obr. 4. Určování Hammingovy vzdálenosti

3.1.2 Komplementarita vs. podobnost Co mírně komplikuje pohled na způsob porovnávání receptorů a antigenů je skutečnost, že pro to existují dva možné způsoby. První je založen na komplementaritě tvarů, kdy k rozpoznání antigenu receptorem dojde tím spíš, čím rozdílnější tvary (povrchy) oba mají, viz. přirovnání obou k zámku a klíči v podkapitole 2.2. Tato cesta odpovídá rozpoznávání prvků v BIS, ale k implementaci UIS se příliš často nevyužívá [5], [7]. V praxi je hojněji zastoupena metoda založená na podobnosti tvarů, kdy k rozpoznání antigenu receptorem dojde tím spíš, čím více jsou si oba podobní. Druhé možnosti je využito v praktické aplikaci pro rozpoznávání plemen psů.

Modely umělých imunitních systémů

Modely UIS lze dělit na selekční a síťové [6]. Selekční modely jsou zaměřeny na rozpoznávání vlastních a nevlastních antigenů. Algoritmus negativní selekce vybírá jen ty T-lymfocyty, které jsou schopné rozpoznat nevlastní antigeny. Algoritmus pozitivní selekce, který je detailněji popsán v podkapitole 3.2.1, pracuje na opačném principu – extrahuje T-lymfocyty schopné detekovat vlastní prvky organismu. Klonální selekční algoritmus se zabývá tvorbou paměťových buněk, které jsou schopné uchovat si v sobě informaci o patogenu, který postihl organismus v minulosti s cílem jeho rychlejší eliminace v budoucnosti. Síťové modely, dělené na spojité a diskrétní, jsou založeny na teorii, ve které si BIS udržuje určitou síť vzájemně propojených Blymfocytů s cílem rozpoznávání antigenů. Síť je zde dynamickým systémem, který se udržuje na základě posilování a oslabování vazeb mezi B-lymfocyty [8].

3.2.1

Algoritmus pozitivní selekce

Pozitivní selekce v imunologii označuje proces bezreceptorových nebo poškozených odstranění lymfocytů B a T. Buňky, které projdou pozitivní selekcí přežijí a mohou hrát roli v imunitní odezvě [5]. Algoritmus pozitivní selekce (APS) slouží k vyčlenění jen těch prvků, které jsou schopné rozpoznat alespoň jednu buňku vlastního těla (self-prvek). Ty, které to nedokáží, jsou eliminovány. Vstupem pro APS je množina S obsahující self-prvky, výstupem je množina A s detektory určenými k rozpoznávání self-prvků. APS má fázi trénovací a testovací [5]. Trénovací fáze má následující kroky: • inicializace: náhodné vygenerování potenciálních detektorů (PD) do množiny P, • určení afinity: porovnání každého PD se self-prvkem z množiny S, • vyčlenění detektoru: jestliže je afinita PD větší než nebo rovna afinitní prahové hodnotě, pak je PD schopný self-prvek rozpoznat a stává se prvkem množiny A obsahující dostupný repertoár detektorů, jinak je PD odstraněn. Trénovací fáze se opakuje do té doby, dokud není splněno určité kritérium, např. dokud nemáme k dispozici dostatek detektorů v množině A. V testovací fázi ověřujeme typ nového příchozího prvku. Jestliže je alespoň jedním detektorem z množiny A rozpoznán, je nový prvek klasifikován jako self-prvek, jinak je prvkem nežádoucím.

APS spadá do kategorie učení založeného na instancích (instance-based learning), kde pracujeme s množinou trénovacích příkladů (self-prvky) [20]. Trénovací příklady slouží k získání podobných souvisejících instancí (detektorů), které jsou pak použity ke klasifikaci instance nové (nového příchozího prvku) [18].

4

Využití pozitivně selekčního algoritmu v kynologii

4.1

Program pro doporučování psích plemen

APS je použit v aplikaci, která má vybrat z různých psích plemen [1], [2], [11], [15], [19] (standardizovaných dle FCI) ta, která vyhovují parametrům zadaných uživatelem programu – budoucím majitelem psa. K implementaci bylo vybráno prostředí NetLogo, které se využívá k modelování a simulování sociálních, biologických a dalších jevů prostřednictvím agentů [16]. Model je členěn do několika procedur, které zajišťují funkčnost celého programu. Mezi hlavní patří: • inicializace modelu, • nalezení řešení, • výpis výsledků.

4.1.1

Inicializace modelu

Kromě nastavení počátečních hodnot k pomocným proměnným jsou inicializací vytvořeny dvě skupiny agentů. První je tvořena padesáti vybranými plemeny ze skupin FCI standardu (FCIPsi). Druhá množina je jednoprvková – obsahuje požadovaného psa (HledaniPsi). Každý agent množiny FCIPsi má určité vlastnosti, které ho charakterizují. Jejich výčet je uveden v tabulce 1. Co se týká datových typů, tak proměnná afinitaFCIPsa je celočíselná, porovnan a vyhovujiciPes jsou typu Boolean, ostatní proměnné nabývají řetězcové hodnoty (hodnot). Vlastnosti agenta množiny HledaniPsi nastavuje uživatel pomocí GUI aplikace (obr. 6.). Nastavitelné jsou vlastnosti: fyzickeRysy, vyuziti a vlastnosti. Tyto parametry jsou pak vstupními hodnotami pro proceduru určenou k nastavení rysů hledaného psího plemene.

4.1.2

Nalezení řešení

V podkapitole 3.2.1 byl charakterizován základní algoritmus pozitivní selekce. Tento algoritmus byl modifikován, resp. neformálně popsán M. Ebnerem a formálně T. Stiborem s tím, že roli detektorů mohou zastávat přímo self-prvky [20], [21], [22]. Výsledkem je skutečnost, že tento algoritmus je tvořen jen testovací fází. Trénovací fáze není uskutečněna.

Tato upravená verze APS byla využita i pro nalezení vhodných psů pro jeho budoucího majitele. Nalezení vyhovujícího psa spočívá v určení podobnosti mezi standardizovanými plemeny psů se psem požadovaným. Konkrétněji, hodnoty proměnných (tab. 1) fyzickeRysy, vyuziti a vlastnosti jednotlivých agentů množiny FCIPsi jsou porovnávány s hodnotami proměnných fyzickeRysy, vyuziti a vlastnosti agenta množiny HledaniPsi. Výsledkem porovnání je stanovení afinitní hodnoty pro daného psa z množiny FCIPsi. Při určování míry podobnosti mezi standardizovaným a požadovaným psem byla využita tzv. Hammingova vzdálenost (obr. 4.). Porovnávání rysů jednoho prvku z množiny FCIPsi s prvkem z množiny HledaniPsi je demonstrován na obrázku 5. Tab. 1. Atribut (proměnná) nazevPlemene cisloSkupinyFCI nazevSkupinyFCI detail fyzickeRysy vyuziti vlastnosti afinitaFCIPsa porovnan vyhovujiciPes

Vysvětlení atributu (proměnné) název plemene psa hodnota v rozsahu <1,10> název skupiny, do které psí plemeno patří detailnější informace o plemeni psa [velikost váha osrstění péče o srst] [lovec hlídač společník k dětem do bytu] [aktivita cvičitelnost agresivita] do jaké míry je FCIPes podobný požadavkům uživatele proměnná pro porovnávání dalšího psa s požadovaným výsledná role psa

Po určení afinity u každého agenta z množiny FCIPsi se rozhoduje o jeho vhodnosti pro potenciálního majitele. Jestliže je afinita agenta z množiny FCIPsi větší než nebo rovna prahové afinitě, pak je psí plemeno doporučeno, jinak doporučeno není. Prahovou afinitu lze v modelu předdefinovat a označuje minimální procento znaků, které musí být u porovnávaných prvků shodných, aby byl pes vybrán jako vhodné plemeno. Vyšší hodnotou prahu klademe přísnější požadavky na potenciální výsledek, protože požadujeme více shodných znaků mezi hledaným a standardizovaným psím plemenem. Nižší hodnota prahu naopak značí, že chceme méně shodných znaků mezi chtěným a standardizovaným psem. Různé nastavení prahové afinity dává odlišné výsledky. Opakovaným spouštěním modelu bylo zjištěno, že při nižší prahové afinitě je poskytnuto více výsledků než při prahu vyšším.

Dále se rozhoduje o roli hledaného psa. Jestliže existuje alespoň jeden agent (psí plemeno) z množiny FCIPsi, který je hledanému podobný, pak hledaný agent přechází do nové množiny FCIPodobniPsi (odpovídající množině se self-prvky). Pokud se s žádným agentem z množiny FCIPsi neidentifikuje, přechází do množiny FCINepodobniPsi (odpovídající množině s non-self prvky). Zde dochází k určitému odchýlení se od podstaty UIS, kdy nežádoucí prvek systému (pes, který není žádnému standardizovanému podobný) by z něj měl být odstraněn. Místo odstranění nežádoucího prvku bylo zvoleno jeho zařazení do jedné ze dvou množin, aby byla v modelu jasnější jeho povaha a odpovídala realitě.

tradičně zmiňována výzkumníky z oblasti UIS. Po stránce budoucnosti programu je nezbytné rozšířit množinu FCIPsi o další jedince, protože aktuální verze využívá jen 50 psích plemen. Ve skutečnosti je počet standardizovaných psů téměř desetinásobný.

Obr. 6. GUI aplikace v NetLogu

5

Obr. 5. Určování afinity psího plemene

4.1.3 Výpis výsledků Po nalezení řešení je možné uživateli zobrazit vyhovující psí plemena z FCI skupin dle relevantnosti, resp. od nejvíce vhodného po nejméně vhodného, spolu s počtem vyhovujících/nevyhovujících, jejich vlastnosti a detailnější popis (obr. 6.).

Závěr

Příspěvek se zabývá problematikou umělých imunitních systémů, především algoritmem pozitivní selekce, který slouží k nalezení takových prvků systému, které jsou schopné rozeznat jeho vlastní elementy. Zjednodušená varianta algoritmu pozitivní selekce byla použita k identifikaci vhodných plemen psů kategorizovaných do skupin dle FCI standardu vhodných pro jeho potenciálního majitele. Aplikace si klade za cíl zjednodušit mnohdy časově náročné vyhledávání vhodného psího plemene s pomocí aktuálně dostupných prostředků (internet, knihy, časopisy) a demonstrovat využití principů UIS k řešení určitého problému. Model byl z prostředí NetLogo exportován do podoby apletu, aby mohl být volně využíván [14].

4.1.4 Kritický pohled na aplikaci

Literatura Využitelnost APS k doporučení vhodného psího plemene je velmi jednoduchou ukázkou toho, jak APS funguje a co může řešit. Celá aplikace je postavena na porovnávání seznamů dvou skupin agentů (HledaniPsi a FCIPsi) a nastavení citlivosti v rozpoznávání pomocí prahové afinity. Jistě by výše uvedený problém mohl být řešitelný i jinými, jednoduššími cestami, aniž bychom museli použít algoritmus UIS. Nicméně k cílům zmíněných v kapitole 1 také patří snaha o nalezení zajímavé aplikační oblasti pro demonstraci APS, která není

[1]

D. Alderton. Psi. Osveta, 1996, angl. orig. A Dorling Kindersley Book. ISBN 80-88824-14-1.

[2]

Atlas plemen psů. pes.cz/atlas_index.php

[3]

J. Bartůňková, A. Šedivá, E. Hölzelová. Primární imunodeficience. Příručka pro pacienty a jejich rodiny. Ústav imunologie 2. LF UK a FN Motol.

URL:

http://cz-

Praha, 1999. http://www.tigis.cz/Knihy/imuno/ [4]

[5]

[6]

[7]

URL:

J. Brownlee: Artificial immune system thesis bibliography. Complex Intelligent Systems Laboratory. Technical Report 071110A. Melbourne, Australia, 2007. URL: http://www.ict.swin.edu.au/personal/jbrownlee/200 7/TR14-2007.pdf L. N. de Castro, J. Timmis: Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002, ISBN 1-85233-594-7. L. N. de Castro, J. I. Timmis. Artificial immune systems as a novel soft computing paradigm. Soft Computing 7, pp. 526 – 544, Springer-Verlag 2003. D. Dasgupta, L. F. Niño. Immunological Computation: Theory and Applications. CRC Press, 2009. ISBN: 978-1-4200-6545-9.

[8]

D. Dasgupta. Advances in Artificial Immune Systems. Computational Intelligence Magazine, IEEE, Volume 1, Issue 4, pp. 40 – 49, 2007.

[9]

Ch. Ehret: Introducing the Artificial Immune System Paradigm: How to apply the Immune System model to Computer Science. University of Fribough, 2006. URL:http://diuf.unifr.ch/tns/teaching/tnsseminar/20 06/2006.07.06_AIS.pdf

[10] J. D. Farmer, N. H. Packard, A. S. Perelson: The immune system, adaptation, and machine learning, The Elsevier Science Publishers B. V. Amsterdam, The Netherlands, 1986. URL: http://portal.acm.org/citation.cfm?id=25213 [11] Federation Cynologique URL: http://www.fci.be/

Internationale,

2008.

[12] D. Floreano, C. Mattiussi. Bio-Inspired Artificial Intelligence: Theories, Methods, and Technologies. The MIT Press, 2008, ISBN 978-0-262-06271-8. [13] E. Hart, J. Timmis: Application Areas of AIS: The Past, The Present and The Future, ICARIS. LNCS 3627, pp. 483-497, Springer-Verlag Berlin Heidelberg, 2005. [14] M. Husáková. Aplikace pro doporučení vhodného psího plemene z FCI standardu. URL: http://lide.uhk.cz/fim/ucitel/fshusam2/lekarnicky/zt 3/zt3_index.html

[15] Krmivo Brit Superpremium. http://www.krmivo-brit.cz/plemena-psu

URL:

[16] NetLogo Homepage. http://ccl.northwestern.edu/netlogo/

URL:

[17] D. Neuwirth: Umělé imunitní výpočetní systémy. Bakalářská práce, VUT Brno, 2007. URL: http://www.neuwirth.name/res/DavidNeuwirth_Bac helorThesis.pdf [18] S. Palu. Instance-Based Learning: A Java Implementation. URL: http://www.developer.com/java/article.php/10922_1 491641_1 [19] L. Smrčková, M. Smrček. Kapesní altas psů. Bratislava, Art Area, 1997. ISBN 80-88879-06-X. [20] T. Stibor, J. Timmis. Comments on Real-Valued Negative Selection vs. Real-Valued Positive Selection and One-Class SVM. Evolutionary Computation, 2007, CEC 2007, IEEE. ISBN: 978-1-4244-1339-3. [21] T. Stibor, J. Timmis, C. Eckert. A Comparative Study of Real-Valued Negative Selection to Statistical Anomaly Detection Techniques. LNCS Artificial Immune Systems. Springer, 2005. [22] T. Stibor, P. Mohr, J. Timmis. C. Eckert. Is negative selection appropriate for anomaly detection? Genetic And Evolutionary Computation Conference. Proceedings of the 2005 conference on Genetic and evolutionary computation, pp. 321 – 328. URL: http://www.sec.informatik.tudarmstadt.de/pages/staff/stibor/papers/gecco2005_c .pdf