Státnice I3: Vyhledávání a extrakce informací
Z ωικι.matfyz.cz
Velkou část otázky pokrývá předmět Dokumentografické informační systémy Michala Kopeckého -- rajjo 17:37, 29 Aug 2010 (CEST)
- slidy k předmětu Dokumentografické informační systémy
- wen:Information_retrieval
Informační systémy[editovat | editovat zdroj]
- Faktografické vs. dokumentografické
- Zpřístupnění vs. dodání dokumentu
- Indexace nutná -- termy
- řízená, neřízená
- tezaury
- Kritérium predikce + maxima
- Precision, recall
Vyhledávání v textu[editovat | editovat zdroj]
- Triviální algoritmus
- Knuth-Morris-Pratt
- Aho-Corrasicková
Boolské informační systémy[editovat | editovat zdroj]
- Dokument reprezentován množinou termů, které ho vystihují
- Dotazy: AND, OR, NOT, wildcards, víceslovné, proximitní omezení, tezaurus, lemmatizace
- Invertovaný indexový soubor (org. po termech)
- Uspořádání výsledků (DNF, počet splněných konjunkcí)
- Zpětná vazba
Vektorové informační systémy[editovat | editovat zdroj]
- Každý z $ n $ dokument reprezentování $ m $-složkovým vektorem vah důležitostí termů ($ \in [0,1] $)
- Indexový soubor je matice vah $ m\times n $
- Dotaz je taky vektor, vyhodnocení a řazení pomocí:
- základní $ Sim(\vec{w}_i,\vec{q}) = \sum_{k=1}^n w_{i,k}q_k $
- vylepšení na délku vektorů (počet nenulových $ w_k $) -- dělení $ \sum w_i + \sum q $, $ \sum w_i + \sum q - 2 \sum wq $ nebo $ \sqrt{\sum w_i^2 \cdot \sum q^2} $
- jiné -- normalizace na jednotkovou délku vektorů
- Nerozlišuje se disjunkce a konjunkce
- Negace = přidání záporných vah do dotazů
- Indexace podle term frequency -- $ TF_{i,j} = \frac{t_j}{\sum_{i=1}^m t_i} $ (podíl počtu výskytů daného termu v dokumentu z celk. počtu termů v něm)
- Normalizovaná $ NTF = \frac{1}{2} + \frac{TF}{2 \max(TF)} $ (do $ \{0\} \cup [1/2,1] $).
- Inverzní $ ITF_j = \log(n/k) $, pokud se term $ j $ vyskytuje v $ k $ dokumentech z $ n $.
- Výpočet vah $ w = \frac{NTF\cdot ITF}{Z} $ ($ Z $ je normalizace)
- Matice podobnosti termů -- závislost a zastupitelnost termů
Induktivní systémy[editovat | editovat zdroj]
- Dvouvrstvá neuronová síť se zpětnou aplikací vah (1. vrstva - termy, 2. - dokumenty)
- Laterální inhibice -- zabránění nárůstu vah
Signaturové systémy[editovat | editovat zdroj]
- Uložení na pomalých médiích -- předstupeň k lepší metodě
- Každý dokument i search term má signaturu, která funguje jako maska (pokud je bitový and signatury dokumentu a termu nenulový, je dokument možná relevantní a použije se k detailnímu hledání)
- Přiřazení signatury -- každý term: jedna jednička na nějakém místě / hashovací funkce
- Zabránění příliš mnoha jedničkám v signaturách dokumentů -- rozdělení na bloky (pevné délky nebo pevného počtu jedniček v signatuře)
- Wildcardy obecně nejsou možné, jen s monotónními signaturami
Rozšířená boolská logika[editovat | editovat zdroj]
- Reprezentace stejná jako vektorový model
- Dotazy stejné jako s boolskou logikou, ale s váhami (pokud nejsou uvedeny, bere se 1)
- OR -- vzdálenost od nulového dokumentu $ DF = (0,\dots,0) $ jako $ \sqrt[p]{\frac{q_a^p w_{i,a}^p + q_b^p w_{i,b}^p}{q_a + q_b}} $ (kde $ q_a,q_b $ jsou váhy dotazu)
- AND -- vzdál. od jednotkového dokumentu jako <maht>1 - \sqrt[p]{\frac{q_a^p(1-w_{i,a})^p + q_b^p(1-w_{i,b})^p}{q_a + q_b}}</math>
- Pro $ p = 1 $ je to vlastně vektorový model, pro $ p\to\infty $ se blíží k boolskému
Rozlišovací hodnoty termů v indexu[editovat | editovat zdroj]
- Informace o tom, jak dobře termy rozlišují dokumenty -- co se stane, když nějaký z nich vyhodíme
- Rozlišovací hodnota $ DV_k = Q^{(k)} - Q $, kde $ Q = \frac{\sum_{i=1}^n Sim(d_i,C)}{n} $ je průměrná podobnost dokumentů s centroidem ("průměrným dokumentem" $ C = \frac{\sum_{i=1}^n d_i}{n} $) a $ Q^{(k)} $ je totéž, odstraníme-li $ k $-tý dokument.
- Je možné použít jako $ IFT $, má lepší vlastnosti než ten logaritmus (viz výše)
Přibližné hledání[editovat | editovat zdroj]
- Detekce chyb, nalezení blízkých termů ve slovníku:
- Počet společných digramů
- Hammingova míra (počet operací replace při doplnění slova znakem $ \lambda $ na stejnou délku)
- Levenshteinova míra (počet operací replace, insert nebo delete)
- Lze použít konečné automaty
Státnice -- Matematická lingvistika
Složitost a vyčíslitelnost -- Tvorba algoritmů, Odhady složitosti, NP-úplnost, Aproximační algoritmy, Vyčíslitelné funkce, Rekurzivní množiny, Nerozhodnutelné problémy, Věty o rekurzi.
Datové struktury -- Stromy, Hašování, Dynamizace, Vnější paměť, Třídění.
Formální popis jazyka -- Závislostní syntax, Frázové gramatiky, Obecná lingvistika, FGD, Formální sémantika
Statistické metody -- Korpusy, Strojové učení, Stochastické metody, Experimenty
Automatické zpracování jazyka -- Analýza jazyka, Generování jazyka, Analýza a syntéza řeči, Extrakce informací, Strojový překlad