13.05.2015 - 15:15

Predhodnih godina mašinsko učenje je dalo prilično dobre rezultate u olakšavanju određenih poslova, predviđanju događaja i donelo velike uštede u različitim oblastima. Računare je danas moguće naučiti da rade prilično veliki broj poslova gotovo podjednako efikasno kao i čovek. Iako smo i dalje prilično daleko od jake mašinske inteligencije, koja bi bila uporediva sa čovekovom, mnogi poslovi se mogu delegirati mašinama, bez bojazni da će ih ona to raditi gore od čoveka.

Tipovi mašinskog učenja

Generalno algoritmi mašinskog učenja se dele na supervizovane i nesupervizovane.

Supervizovanim algoritmima su potrebni pokazni primeri, takozvani trening skup. U trening skupu se nalaze podaci sa rešenjem ili izlazom. Na osnovu ovih podataka, algoritam je sposoban da kreira model, po kome će se izlazni podaci generisati i koji će na najbolji mogući način da oslikaju mapiranje podataka i očekivanih izlaza iz trening skupa.

Nesupervizovani algoritmi ne koriste trening skup podatke, već su sposobni da na osnovu određenog skupa podataka donesu određene zaključke i kreiraju model. Na primer, ukoliko na koordinatnom sistemu postoje određene grupe tačaka, ovi algoritmi će biti sposobni da ih prepoznaju. Za određene probleme su sjajni, međutim, za neke druge probleme je neophodno koristiti supervizovano učenje.

Polu-supervizovano učenje je zapravo kombinacija supervizovanog i nesupervizovanog učenja. Neki autori ove algoritme izdvajaju kao treću grupu, ali oni su samo kombinacija pomenutih. Često se koriste kada je trening skup mali. U tom slučaju se na malom trening setu kreira model, da bi se posle propustili ostali podaci kroz algoritam. Ukoliko je algoritam dovoljno siguran da je tačno predvideo neke izlaze, ti podaci se dodaju trening skupu, pa se algoritam trenira na proširenom trening skupu iznova. I ovo se ponavlja, dok se ne dobije zadovoljavajuće velik trening skup i zadovoljavajuće precizan model.

Takođe, ovde je interesantno napomenuti da algoritmi mašinskog učenja nisu novi, iako je u poslednje vreme došlo do određenih poboljašanja. Međutim, najčešće korišćeni algoritmi, koji su zapravo oni koji donose i najbolje rezultate postoje preko 50 godina. Tako Naive Bayes je zasnovan na Bayesovoj teoremi, koja je publikovana u današnjem obliku 1812. godine, dok je sam algoritam iz 1960ih. Warren McCulloch i Walter Pitts su 1943. napravili računarski model neuralnih mreža. Jedan od najkorišćenijih algoritama za klasivikaciju je support vector machines (SVM), koje se pojavio 1963. godine u radu koji su napisali ruski naučnici Vladimir N. Vapnik i Alexey Ya. Chervonenkis. Međutim, algoritam je stigao na zapad, tek 1992. godine, nekoliko godina nakon pada Berlinskog zida.  

Problemi koje mašinsko učenje rešava

Osnovni problem koji mašinsko učenje pokušava da reši je da na osnovu podataka nauči ishod koji bi i čovek dao. Kada govorimo o supervizovanom učenju, onda trening skup nazivamo istorijskom podacima, dok je za nove podatke potrebno predvideti ishod. Tako imamo problem predikcije. Kod predikcije postoje dve vrste – klasifikacija i regresija. Klasifikacija se odnosi na diskretnu predikciju, odnosno klasifikovanje podataka u definisan, konačan broj klasa. Regresija se, sa druge strane, odnosi na kontinualno predviđanje. Kod regresije, algoritam uči i predviđa kako će se funkcija ponašati u budućnosti, na osnovu istorijskih podataka. Generalno, ostali problemi, koje mašinsko učenje može da reši, poput grupisanja, mogu se svesti na klasifikaciju ili regresiju.

Primer klasifikacije teksta

Kako bi približili rad sa mašinskim učenjem, uradićemo jedan relativno prost primer. Kreiraćemo klasifikator za vesti na srpskom jeziku. Kreiraćemo crawler uz pomoć Scrapy frameworka, koji će prikupiti vesti sa sajta B92. Naš klasifikator će imati tri klase – informacione(politika i dešavanja), sportske i tehničke vesti. Napravićemo trening skup od po 100 tekstova iz svake kategorije i napraviti SVM model uz pomoć Weka radnog okruženja. Na kraju ćemo pokušati da malo poboljšamo preciznost predviđanja.

Prikupljanje podataka

Kako bismo napravili trening skup, napisaćemo jednostavan crawler, koji će da prikupi članke članke. Crawler ima to svojstvo da kad skine članak, može da prati sve linkove na toj stranici i tako na nađe nove članke, dok ne pokupi sve. Naravno, on se može i ograničiti na određeni domen i da adresa sadrži određeni tekst.

Za crawler sam koristio Scrapy framework, koji omogućava jednostavno pravljenje crawlera u programskom jeziku Python. Može se instalirati uz pomoć pip menadžera paketa. Da bi se instalirao, potrebno je pokrenuti komandu „pip install scrapy“. Nakon toga se može kreirati projekat, tako što se u komandnoj liniji unese komanda „scrapy startproject crawler“. Scrapy će napraviti folder crawler sa određenom folderskom strukturom. Nakon toga u folder spiders, koji je kreirala predhodna komanda, se mogu dodati moduli, koji će definisati logiku našeg crawlera. Taj fajl kod nas izgleda na sledeći način:

import scrapy

from scrapy.contrib.spiders import CrawlSpider, Rule

from scrapy.contrib.linkextractors import LinkExtractor

from scrapy import log

from scrapy.tests.mockserver import Follow


class B92InfoSpider(CrawlSpider):

    name = "b92info"

    allowed_domains = ["b92.net"]

    start_urls = [

        "http://www.b92.net/info/",             

    ]  

    rules = (

        # Extract links matching 'item.php' and parse them with the spider's method parse_item

        Rule(LinkExtractor(allow=('info/vesti/', )),

callback='parse_item',follow=True),

    )

    def parse_item(self, response):

        log.msg("URL:"+response.url, level=log.DEBUG)

       filename = "files_b92_info/"+(response.url.split("/")[-1]+"_crawled.html").replace("?","")

       .replace("=","")

        with open(filename, 'wb') as f:

            f.write(response.body)

Definiše se klasa koja je izvedena od CrawlSpidera (postoje I druge klase, ali nama je ova neophodna, jer omogućava praćenje linkova sa svake stranice). Klasa mora imati ime, koje je bitno za pokretanje. Takođe treba definisati koji domeni su dozvoljeni I sa koje adrese se kreće. Nakon toga definišemo pravila. Naše pravilo govori da će se pratiti linkovi koji sadrže info/vesti, da će se sa svih stranica koje su crawlovane pratiti dalje linkovi, dok se svi ne iscrpe (follow=True), kao I da će se izvršiti funkcija parse_item prilikom parsiranja stranice. U parse item, samo čuvamo sadržaj stranice na lokalnom hard disku u određenom direktorijumu. Slično smo napravili i crawlere za sport i technopolis deo sajta b92. Samo se argument pravila malo razlikuje. Crawler se pokreće komandom “scrapy crawl b92info”.

Nakon što su datoteke sa vestima prikupljene, potrebno ih je iz HTML oblika pretvoriti u tekstualne datoteke. S obzirom da se tekstovi vesti na sajtu B92 nalaze u div tagu sa klasom article-text, to možemo uraditi na sledeći način:

from bs4 import BeautifulSoup

from os import listdir

from os.path import isfile, join

mypath = "selected_info/"

onlyfiles = [ f for f in listdir(mypath) if isfile(join(mypath,f)) ]

for file in onlyfiles:

    file_object = open(mypath+file, "r")

    sdata = file_object.read()

    soup = BeautifulSoup(sdata)

    mydivs = soup.findAll("div", { "class" : "article-text" })

    with open("b92_info_txt/"+file.split("/")[-1]+".txt", 'wb') as f:

        if mydivs != None and len(mydivs)>0:

            f.write(mydivs[0].text.encode("utf8"))

print "Done!"

Ovako spremljeni dokumenti se već mogu iskoristiti za učenje. Međutim, uradio sam još nekoliko transformacija, poput čišćenja javascript koda i pretvaranje srpskih karaktera (č,ć,š,đ,š) u kombinacije ascii karaktera (cx,cy,sx,dx,sx), radi izbegavanja problema sa enkodingom.

Klasifikacija

Ovako dobijene datoteke su dovoljne za započinjanje procesa mašinskog učenja. Za mašinsko učenje ćemo koristiti Weka radno okruženje. Weka je radno okruženje razvijeno na Univerzitetu Waikato sa Novog Zelanda. Ovo radno okruženje, inače razvijeno u programskom jeziku Java, sadrži veliku kolekciju algoritama za mašinsko učenje, kao i alata, filtera i biblioteka neophodnih u procesu mašinskog učenja. S obzirom da koristimo Weka radno okruženje, prvo moramo pretvoriti podatke u ulaz, koji Weka može da razume. Za učenje Weka koristi .arff fajl, koji sadrži podatke o svojstvima, kao i podatke. S obzirom da su naši podaci trenutno u 3 direktorijuma i mnogo datoteka unutar tih direktorijuma, ovo može biti prilično naporno ručno konvertovati u .arff fajl, ali Weka već sadrži skriptu, koja od ovakve kolekcije može da napravi odgovarajući ulaz. U komandnu liniju je potrebno uneti nešto ovako:

Ovo će unutar folder b29_unstemmed gde se nalaze direktorijumi info, sport i tehno napraviti train.arff fajl, koji će služiti kao ulaz.

Nakon ovoga u Weka exploreru ćemo otvoriti kreirani fajl. Na žalost, sa podacima u trenutnom obliku ne može se mnogo uraditi, pa ih je potrebno dodatno obraditi. Trenutno, ulaz u algoritam čini tekst vesti i njegova klasa. Mi želimo da kao svojstva algoritam prihvata vektor reči, pa ćemo tekstove pretvoriti u vektore reči uz pomoć StringToWordVector filtera. Takođe, sve reči ćemo normalizovati u mala slova tokom pretvaranja i iskoristiti opciju TFTransform (Term Frequency) i IDFTransform (Inverse Document Frequency). Poslednje dve opcije će nam dati podatak o tome koliko je termin bitan u određenom dokumentu.

Nakon što smo primenili filter, možemo preći na karticu classify. Kao algoritam za klasifikaciju ćemo izabrati SMO (Sequential Minimal Optimization). Ovo je zapravo Support Vector Machines (SVM) algoritam sa primenom određenog načina na koji se rešava problem kvadratičnog programiranja. Izabraćemo Polinomijalni kernel. Kernel kod SVM algoritma služi za mapiranje iz mnogodimenzionog prostora u dvodimenzijalnu ravan. Svaka reč se u shvata kao vektor u mnogodimenzionom prostoru. Kada je sve ovo spremno možemo kliknuti na dugme Start. Izlaz izgleda na sledeći način:

Za ovu evaluaciju je korišćena 10-fold cross validation. Ovaj metod podeli trening skup na 10 skupova. Nakon toga trenira na 9, dok jedan koristi za testiranje. Ovaj proces se ponovi 10 puta, tako da se svaki od skupova iskoristi za testiranje. Što se mera tiče, skoncentrisaćemo se na Precision, Recall, F-Measure i Confusion Matrix.

Konfuziona matrica pokazuje koliko  dokumenata iz koje klase je kako klasifikovano. Pa tako možemo videti da iz info klase svi dokumenti su pravilno klasifikovani. Od sportskih vesti jedna vest je klaifikovana kao vest iz tehno klase, itd.

Precision je mera koja pokazuje odnos ispravno klasifikovanih dokumentata u određenoj klasi i dokumenata klasifikovanih kao ta klasa. (P = TP/(TP+FP), TP – ispravno pozitivno klasifikovani, FP – neispravno pozitivni)

Recall je odnos ispravno klasifikovanih i ukupnog broja dokumenata u toj klasi. ( R=TP/(TP+FN) TP – ispravno pozitivni, FN – neispravno negativni).

F-measure je kombinacija Precision i Recall-a. Ova mera daje ukupnu sliku koliko je algoritam precizan. Računa se kao F= 2*R*P/(P+R).

Kao što iz rezultata možemo videti, algoritam klasifikuje dokumente prilično dobro. Sa F merom od 91.4%. Ovi rezultati mogu biti uporedivi sa čovekovim performansama u klasifikaciji dokumenata, s tom razlikom da će mašina klasifikovati nekoliko stotina članaka u sekundi.

Istrenirani model se može eksportovati u datoteku uz pomoć opcija koje se dobijaju desnim klikom na polje u sekciji result set. Ovako eksportovan model se kasnije može importovati u program koji će klasifikovati nove dokumente.

U programskom jeziku Java importovanje modela izgleda na sledeći način. Prvo je potrebno kreirati klasifikator:

InputMappedClassifier classifier = new InputMappedClassifier() ;

InputMappedClassifier mapira svojstva klasifikatora iz modela u novi klasifikator. Svojstva modela u našem slučaju su reči. Drugi klasifikatori bi mogli imati problem ukoliko bi se pojavila neka nova reč, dok će ovaj to znati da obradi. Dalje je potrebno učitati model:

classifier.setModelPath(ClassifierPath);

Nakon ovoga se može klasifikovati, s tim što sve transformacije koje su urađene na ulaznom tekstu, moraju se uraditi i na novim tekstovima. Pa je tako potrebno tekst pretvoriti u vektor reči. Sama klasifikacija se može uraditi uz pomoć metode klasifikatora classifyInstance.

Poboljšanje

Jedna tehnika koja može poboljšati preciznost algoritma mašinskog učenja, kada je jezik u pitanju je steming. Steming (Stemming) predstavlja heuristični proces otklanjanja krajeva reči u nadi da će se to postići u većini slučajeva korektno, a ponekad obuhvata i otklanjanje derivacionih afiksa. Cilj steminga je dobiti za sve fleksije reči sa istim značenjem najmanji zajednički sadržalac. Dokumente ćemo propustiti kroz stemer za srpski jezik. Na žalost ne postoji mnogo resursa za jezičku obradu srpskog, tako da sam svojevremeno za potrebe master rada razvio jednu varijantu stemera, čija implementacija za Python se može naći na GitHubu (https://github.com/nikolamilosevic86/SerbianStemmer). Nakon stemovanja svih članaka ponovićemo proces iz predhodnog dela. Rezultati su malo bolji: 

F mera se u ovom slučaju poboljšala za 0.8% na 92.2%. S obzirom da je preciznost algoritma već i pre bila jako visoka, teško je očekivati velika poboljšanja, ali ipak je stemer doneo određeni benefit.

Zaključak

Kao što je naš primer pokazao već na relativno malom skupu podataka je moguće dobiti prilično dobru preciznost uz pomoć SVM algoritma. Kod mašinskog učenja često veći skupovi trening podataka mogu da poboljšaju performanse predviđanja. Međutim, preciznost od 92.2% se može smatrati prilično blizu performansama čoveka. Još ako uzmemo u obzir brzinu kojom će mašina obraditi tekstove, ovo svakako se može smatrati velikim ubrzanjem.

Kao što je ranije pomenuto, još uvek smo daleko od generalne veštačke inteligencije. Ali mašine sasvim dobro mogu da uče da rade neke jednostavne zadatke i na taj način nam ubrzaju rad. Istraživanja se rade i na generalnoj veštačkoj inteligenciji i određeni pomaci se dešavaju, pa samim tim će biti interesantno videti šta nam budućnost donosi. 

BACK END

Dodaj novi komentar

Plain text

  • HTML tagovi nisu dozvoljeni
  • Web i email adrese automatski postaju linkovi
  • Redovi i paragrafi se prelamaju automatski.
NAPOMENA:
IT-KONEKT zadržava pravo izbora i skraćivanja komentara koji će biti objavljeni na veb sajtu.
Neće biti objavljivani komentari koji sadrže govor mržnje, pretnje, uvrede i psovke.
Očekujemo da tekstovi budu pravopisno i gramatički ispravni.
Komentari objavljeni na ovom veb sajtu predstavljaju privatno mišljenje njihovih autora a ne zvaničan stav IT-KONEKT tima.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.