Honnan tudjuk, hogy egy IR-rendszer jól teljesít? Elvégzünk egy kísérletet, amelyben a rendszer kap egy lekérdezéshalmazt, az eredményhalmazokat pedig pontozzuk az emberi relevanciamegítélés szerint. Tradicionálisan két mértéket használunk a pontozásra: a felidézést (recall) és pontosságot (precision). Ezeket egy példán keresztül fogjuk bemutatni. Képzeljük el, hogy egy IR-rendszer visszaadott egy eredményhalmazt egy olyan lekérdezésre, amelyre tudjuk, hogy egy 100 dokumentumot tartalmazó korpuszból mely dokumentumok relevánsak, és melyek nem. Az egyes kategóriákba tartozó dokumentumok számát az alábbi táblázat adja meg:

A pontosság az eredményhalmaz dokumentumai közül a ténylegesen relevánsak arányát méri. A példánkban a pontosság 30/(30 + 10) = 0,75. A hamis pozitív arány 1 – 0,75 = 0,25. A felidézés a gyűjtemény releváns dokumentumaiból az eredményhalmazban megjelenő hányadát méri. A példánkban a felidézés 30/(30 + 20) = 0,60. A hamis negatív arány 1 – 0,60 = 0,40. Egy nagyon nagy dokumentumgyűjteményben, mint például a világhálón, a felidézés nehezen számítható, mivel nincs egyszerű módszer a web összes oldalának a relevancia szempontjából történő elemzésére. A legjobb, amit tehetünk, a felidézés becslése mintavételezéssel, vagy pedig teljesen figyelmen kívül hagyjuk a felidézést, és csak a pontosság alapján ítélünk.

A rendszer kompromisszumot köthet a pontosság és felidézés között. Extrém esetben a rendszer visszaadhatja az összes dokumentumot a dokumentumgyűjteményből az eredményhalmazban, 100%-os felidézést garantálva, azonban a pontossága kicsi lesz. Alternatívaként, a rendszer visszaadhat egyetlen dokumentumot, így a felidézés alacsony lesz, azonban tűrhető esélye van 100%-os pontosságra. A kompromisszum összefoglalásának egyik lehetséges módja az ROC-görbével (ROC curve) történhet. Az „ROC” a „vevő működési karakterisztika” (receiver operating characteristics) rövidítése (ami nem túlzottan felvilágosító név). Ez egy olyan grafikon, amely a hamis negatív arányt méri az y tengelyen és a hamis pozitív arányt az x tengelyen, ábrázolva az egyes kompromisszumos pontokat. A görbe alatti terület az IR-rendszer hatékonyságának összefoglalása.

A felidézést és pontosságot akkor definiálták, amikor az IR-kereséseket elsődlegesen könyvtárosok végezték, akik alapos, pontos találatokban voltak érdekeltek. Manapság a legtöbb (napi több százmillió) lekérdezést az internetfelhasználók végzik, akik kevésbé érdekeltek az alaposságban, sokkal inkább abban, hogy azonnal választ kapjanak. Számukra jó mérték az első releváns találat átlagos reciprokrangja (reciprocal rank). Azaz, amennyiben a rendszer első találata releváns, 1-es pontszámot kap a lekérdezésre, és amennyiben az első kettő nem releváns, de a harmadik az, akkor 1/3-ot. Egy alternatív mérték a válaszidő (time to answer), ami azt méri, hogy mennyi ideig tart a felhasználónak a problémára kívánt választ megtalálni. Ez kerül a legközelebb ahhoz, amit mérni szeretnénk, azonban azzal a hátránnyal rendelkezik, hogy minden egyes kísérlethez új emberi tesztalanycsoportra van szükség.

Az unigram modell az összes szót függetlenként kezeli, azonban mi tudjuk, hogy bizonyos szavak korreláltak: a „dívány” közeli kapcsolatban áll mind a „díványok”-kal, mind a „kanapé”-val. Számos IR-rendszer próbálja figyelembe venni ezeket a korrelációkat.

Például, amennyiben a lekérdezés [dívány], gyalázatos lenne kihagyni az eredményhalmazból azokat a dokumentumokat, amelyek a „DÍVÁNY” vagy a „díványok” szavakat tartalmazzák, de a „dívány”-t nem. A legtöbb IR-rendszer kisbetű-nagybetű konverziót (case folding) alkalmaz, hogy a „DÍVÁNY”-t „dívány” alakká alakítsa, számos rendszer pedig szótövesítő (stemming) algoritmusokat, hogy a „díványok” alakot a „dívány” szótőre redukálja. Ez tipikusan a felidézés kismértékű növekedését eredményezi (az angol nyelv esetén kb. 2%-ot). Azonban ronthatja a pontosságot. Például a „stocking” szótövesítése „stock”^[246] alakra valószínűleg csökkenteni fogja a ruházati, valamint pénzügyi eszközökre irányuló lekérdezések pontosságát, azonban növelheti a raktározásra irányuló lekérdezések felidézését. Szabályalapú szótövesítők (például az „-ing” végződés eltávolítása az angolban) nem képesek megkerülni ezt a problémát, de a szótárakon alapuló újabb algoritmusok igen (nem kell eltávolítani az „-ing” képzőt, ha a szó már szerepel a szótárban). Bár az angol nyelv esetén a szótövesítésnek csak kis hatása van, sokkal fontosabb más nyelvek esetén. A német nyelvben gyakran találkozhatunk olyan szavakkal, mint „Lebensversicherungsgesellschattsangestellter” (életbiztosító cég alkalmazottja). Az olyan nyelvek, mint a finn, a török, az inuit vagy a jupik rekurzív morfológiai szabályokkal rendelkeznek, amelyek elméletileg korlátlan hosszúságú szavakat generálnak.

A következő lépés a szinonimák (synonyms) felismerése, mint amilyen a „dívány” és a „kanapé”. A szótövesítéshez hasonlóan ez is a felidézés kismértékű növekedését eredményezheti, azonban a pontosságot veszélyezteti, ha túl agresszíven alkalmazzuk. Akik Tim Couch futballistára kíváncsiak, nem szeretnének átvergődni a kanapékról (couch – kanapé) szóló dokumentumokon. Az a probléma, hogy „a nyelv ugyanúgy irtózik az abszolút szinonimáktól, mint ahogy a természet retteg a vákuumtól” (Cruse, 1986). Azaz, amennyiben két szó azonos dolgot jelent, a nyelv beszélői törekednek a jelentés módosítására, hogy megszüntessék a zűrzavart.

Számos IR-rendszer bizonyos mértékig szó bigramokat használ, azonban csak néhányuk valósít meg egy teljes valószínűségi bigram modellt. A helyesírás-javító (spelling correction) eljárások alkalmazhatók mind a dokumentumok, mind a lekérdezések hibáinak javítására.

Végső finomításként az IR-rendszerek tökéletesíthetők metaadatok (metadata) figyelembevételével, amelyek a dokumentum szövegén kívül álló adatok, mint például emberek által megadott kulcsszavak vagy dokumentumok közötti hypertext-hivatkozások.

A valószínűségi rendezési elv szerint vegyünk egy eredményhalmazt, és a relevancia valószínűségének megfelelően sorba rendezve prezentáljuk a felhasználónak. Ennek akkor van értelme, ha a felhasználó az összes releváns dokumentum minél hamarább történő megtalálásban érdekelt. Azonban bajba kerül, mert nem veszi figyelembe a hasznosságot. Például ha a legrelevánsabb dokumentum két példányban szerepel a gyűjteményben, akkor az első megnézése után a második azonos relevanciájú, de zérus hasznosságú. Számos IR-rendszer rendelkezik mechanizmusokkal, amelyek eliminálják az előző találatokhoz túlzottan hasonlító eredményeket.

Az IR-rendszerek teljesítménynövelésének egyik leghatékonyabb módja a relevancia-visszacsatolás (relevance feedback), amely a felhasználó visszajelzése, hogy az eredeti eredményhalmazból mely dokumentumok voltak relevánsak. A rendszer ezután egy második eredményhalmazt prezentálhat, amelynek dokumentumai hasonlók a megadottakhoz.

Egy másik lehetséges megközelítés az eredményhalmaznak egy rendezett lista helyett egy címkézett faként történő prezentálása. A dokumentumosztályozás (document classification) során az eredményeket egy előre definiált témakör-taxonómiának megfelelően osztályozzuk. Például újsághírekből álló gyűjteményt a következő kategóriákba lehet sorolni: külföldi, belföldi, üzleti hírek, szórakozás és sport. Dokumentumklaszterezés (document clustering) esetén minden eredményhalmazra teljesen új kategóriafa készül. Az osztályozás akkor használható, ha a gyűjteményben kevés számú témakör található, míg a klaszterezést a világhálóhoz hasonló széles körű gyűjtemények esetén érdemes használni. Mindkét esetben, miután a felhasználó megad egy lekérdezést, az eredményhalmazt a kategóriáknak megfelelő mappákba rendezve kapja meg.

Az osztályozás felügyelt tanítási probléma, és mint ilyen, a 18. fejezetben ismertetett bármelyik módszerrel megtámadható. Az egyik népszerű megközelítés a döntési fák alkalmazása. Amennyiben rendelkezünk a megfelelő kategóriákkal címkézett dokumentumokból álló tanító halmazzal, építhetünk egyetlen döntési fát, amelynek levelei a dokumentumot a megfelelő kategóriához rendelik. Ez akkor működik jól, ha mindössze néhány kategória van; nagyobb kategóriahalmazok esetén minden egyes kategóriára külön döntési fát építünk, amelynek a levelei megadják, hogy a dokumentum az adott kategóriába tartozik-e vagy sem. Általában az egyes csomópontokban tesztelt tulajdonságok egyedi szavak. Például a „Sport” kategóriában az egyik csomópont tesztelheti a „kosárlabda” szó meglétét. Javított teljesítményű döntési fák, naiv Bayes-modellek, valamint szupport vektor gépek mindegyikét használták szövegosztályozásra, sok esetben a hitelesség 90–98%-os volt bináris osztályozás esetén.

A klaszterezés egy felügyelet nélküli tanítási módszer. A 20.3. alfejezetben láthattuk, hogy hogyan alkalmazható az EM algoritmus a klaszterezés eredeti becslésének javítására, Gauss-modellek keverékét használva. A dokumentumok klaszterezése nehezebb feladat, mert nem tudjuk, hogy az adatokat egy barátságos Gauss-modell generálta-e, és mert egy sokkal több dimenziós térrel kell elbánnunk. Számos megközelítést dolgoztak ki.

Az agglomeratív klaszterezés (agglomerative clustering) klaszterekből álló fát épít, lemenve egészen az egyedi dokumentumok szintjére. A fa bármely szinten nyeshető, hogy kevesebb kategóriát kapjunk, de ezt az algoritmuson kívül vesszük figyelembe. Az elején minden dokumentumot külön klaszternek tekintünk. Ezután megkeressük azt a két klasztert, melyek egy bizonyos távolságmérték szerint legközelebb állnak egymáshoz, és összevonjuk őket. Addig ismételjük a folyamatot, amíg csak egy klaszter marad. A két dokumentum távolságát meghatározó mérték a dokumentumok szavai közti átfedés valamilyen mértéke. Például reprezentálhatjuk a dokumentumot szógyakoriságok vektoraként, ahol a távolságot a két vektor euklideszi távolságaként értelmezzük. Két klaszter távolsága a klaszterek mediánjainak távolságaként értelmezhetjük, vagy a klaszterek elemeinek átlagos távolságát vehetjük figyelembe. Az agglomeratív klaszterezés időigénye O(n²), ahol n a dokumentumok száma.

A k-közép klaszterezés (k-means clustering) pontosan k darab kategória halmazát állítja elő. A következő elven működik:

A k-közép módszer O(n) időigényű, ez az egyetlen előnye az agglomeratív klaszterezéshez képest. Általában kevésbé pontos, mint az agglomeratív klaszterezés, bár egyesek szerint majdnem olyan hatékony (Steinbach és társai, 2000).

Az alkalmazott klaszterezési módtól függetlenül van még egy feladat, amit el kell végeznünk, mielőtt a klaszterezést az eredményhalmaz bemutatására használhatjuk: a klaszter jó leírásának megtalálása. Az osztályozás esetén a kategóriák előre definiáltak (például „jövedelmek”), míg a klaszterezés esetén ki kell találnunk a kategórianeveket. Az egyik választás a klaszter szempontjából reprezentatív szavak listájának használata. A másik lehetőség a klaszter középpontjához közel levő egyik dokumentum címének a használata.

Az eddigiekben csupán absztrakt módon definiáltuk az IR-rendszerek működését, azonban nem magyaráztuk el, hogy hogyan lehet olyan hatékonnyá tenni őket, hogy egy webes keresőgép visszaadhassa a legfelső találatokat egy több milliárd oldalas gyűjteményből egytized másodperc alatt. Minden IR-rendszer számára két kulcsfontosságú adatstruktúra szükséges: a szókincs, amely felsorolja a dokumentumok szavait, és az invertált index, amely megadja, hogy az egyes szavak hol szerepelnek a dokumentumgyűjteményben.

A szókincs (lexicon) egy olyan adatstruktúra, amely egy műveletet támogat: megadja, hogy egy adott szó hol szerepel az invertált indexben, amely a szó előfordulásait tárolja. Egyes megvalósítások esetén azt is visszaadja, hogy összesen hány dokumentum tartalmazza a szót. A szókincset hash-tábla vagy valamilyen hasonló adatstruktúrával ajánlott megvalósítani, amely lehetővé teszi a gyors kikeresést. Egyes esetekben kis információtartalmú gyakori szavakat kihagynak a szókincsből. Ezek a tiltólistás szavak (stop words) (például „a”, „egy”, „ez” stb.) helyet foglalnak az indexben, és nem javítják az eredmény rangsorolását. Az egyetlen jó indok arra, hogy mégis megtartsuk őket a szókincsben a kifejezéslekérdezést támogató rendszerek esetén áll fenn: a tiltólistás szavak szókincsbeli tárolása szükséges olyan lekérdezések kiszolgálására, mint pl. a „to be or not to be”.^[247]

Az invertált index^[248] (inverted index), a könyvünk végén található szójegyzékhez hasonlóan, találati listák (hit lists) halmazából – az egyes szavak előfordulási helyeiből – áll. A Boole-kulcsszó modell esetén a találati lista nem más, mint a dokumentumok listája. Az unigram modell esetén egy (dokumentum, gyakoriság) párokat tartalmazó lista. A kifejezéslekérdezés támogatásához a találati listának az adott szó minden egyes dokumentumon belüli előfordulási helyeit is tartalmaznia kell.

Amennyiben a lekérdezés egyetlen szó (Silverstein szerint ilyen az esetek 26%-a (Silverstein és társai, 1998)), akkor a feldolgozás igen gyors. Egyszerűen kikeressük a szót a szókincsből, hogy megkapjuk a találati lista címét, majd egy üres prioritási sort hozunk létre. Ezután egyesével végigmegyünk a találati lista dokumentumain, és megnézzük a szó gyakoriságát a dokumentumban. Amennyiben a prioritási sor R-nél kevesebb elemet tartalmaz (ahol R az eredményhalmaz elvárt mérete), akkor hozzáadjuk a (dokumentum, gyakoriság) párt a sorhoz. Ellenkező esetben, ha a gyakoriság nagyobb, mint a prioritási sor legkisebb elemének gyakorisága, akkor töröljük a legkisebb elemet, és hozzáadjuk az új (dokumentum, gyakoriság) párat. Ezáltal a lekérdezés megválaszolása O(H + R log R) időt vesz igénybe, ahol H a találati lista dokumentumainak száma. Amennyiben a lekérdezés n szót tartalmaz, akkor n találati listát kell összevonni, ami O(nH + R log R) időt vesz igénybe.

Azért mutattuk be az IR-rendszerek elméletét a valószínűségi modellen keresztül, mert ez a modell hasznosítja azokat az ötleteket, amelyeket más témákban is alkalmaztunk. A jelenlegi gyakorlati IR-rendszerek sokkal inkább egy másik megközelítést alkalmaznak, amelyet vektortér modellnek (vector space model) hívunk. Ez a modell ugyanúgy a szózsák-megközelítést alkalmazza, mint a valószínűségi modell. Minden egyes dokumentumot unigram szógyakoriságok vektoraként ábrázolunk. A lekérdezést is így ábrázoljuk, például a [Bayes information retrieval model] lekérdezést a

[0, …, 1, 0, …, 1, 0, …, 1, 0, …, 1, 0, …]

vektor írja le, amelyben az ötlet az, hogy minden egyes szóhoz külön dimenzió tartozik, és a lekérdezés vektorában minden dimenzió 0 értékű, kivéve azt a négy szót, amely a lekérdezésben előfordul. A releváns dokumentumokat úgy kapjuk meg, hogy megkeressük azokat a dokumentumokat, amelyek a lekérdezés vektorának legközelebbi szomszédai a vektortérben. A hasonlóság egyik lehetséges mértéke a lekérdezés- és dokumentumvektor skaláris szorzata: minél nagyobb ez a szorzat, annál közelebb van egymáshoz a két vektor. Algebrailag ez a mérték nagy pontszámot ad azoknak a szavaknak, amelyek mind a dokumentumokban, mind a lekérdezésben gyakran előfordulnak. Geometriailag a két vektor skaláris szorzata az általuk bezárt szög koszinusza, azaz ha két ilyen vektor koszinuszát maximalizáljuk (amennyiben azonos kvadránsban találhatók), akkor az általuk bezárt szög nullához közeli lesz.

A vektortér modell ennél sokkal többre képes. A gyakorlatban számos jellemzővel, finomítással, javítással és kiegészítéssel lett kibővítve. Az az alapötlet, miszerint a dokumentumokat a vektortérbeli hasonlóságuk alapján lehet rangsorolni, lehetővé teszi, hogy új ötleteket építsünk be a numerikus sorrendező rendszerbe. Egyesek azt állítják, hogy a valószínűségi modell ezeket a módosításokat sokkal tisztább elvi alapokon állva tenné lehetővé, azonban az IR-kutatók nem fognak váltani, amíg nem látnak egyértelmű teljesítményjavulást a másik modellhez képest.

Hogy egy átlagos IR-feladat indexelési problémájának nagyságrendjét érzékeltessük, vegyünk egy szabványos TREC (Text REtrieval Conference – Szöveg-visszakeresési Konferencia) dokumentumgyűjteményt, amely 750 ezer dokumentumot tartalmaz, öszszesen 2 GB (gigabájt) szöveggel. A szókincs körülbelül 500 ezer szót tartalmaz, szótövesítés és kisbetű-nagybetű konverzió után; ennyi szó tárolása 7 és 10 MB közötti tárterületet igényel. Az invertált index a (dokumentum, gyakoriság) párokkal 324 MB területet igényel, bár tömörítési technikák alkalmazásával csak 83 MB-ot. A tömörítés tárhelyet takarít meg, a feldolgozási követelmények kismértékű növelése árán. Azonban ha a tömörítés lehetővé teszi, hogy az egész indexet a memóriában – és nem háttértáron tároljuk –, akkor jelentős eredő teljesítménynövekedést kapunk. A kifejezéslekérdezés támogatása a tárigényt 1200 MB-ra növeli tömörítetlen, illetve 600 MB-ra tömörített esetben. A webes keresőgépek háromezerszer ekkora feladattal dolgoznak. A legtöbb probléma az esetükben is hasonló, azonban nem praktikus terabájtnyi mennyiségű adatot kezelni egyetlen számítógépen, ezért az indexet k szegmensre vágják, és minden szegmenst külön számítógép tárol. A lekérdezést mindegyik számítógép megkapja, majd a k eredményhalmazt egy eredményhalmazba vonják össze, amelyet megjelenítenek a felhasználó számára. A webes keresőgépeknek ráadásul másodpercenként több ezer lekérdezést kell kiszolgálniuk, így a k számítógép n másolatára van szükség. Az idő folyamán k és n folyamatosan növekszik.