Model dywergencji od losowości - Divergence-from-randomness model

W dziedzinie pozyskiwania informacji , rozbieżności z przypadkowości , jeden z pierwszych modeli, jest jeden rodzaj probabilistycznego modelu. Zasadniczo służy do testowania ilości informacji zawartych w dokumentach. Opiera się na modelu indeksowania 2 Poissona Hartera. Model 2-Poissona zakłada hipotezę, że poziom dokumentów jest powiązany z zestawem dokumentów, w których słowa występują stosunkowo częściej niż w pozostałych dokumentach. Nie jest to „model”, ale ramy do ważenia terminów przy użyciu metod probabilistycznych i ma szczególny związek z ważeniem terminów opartym na pojęciu elitarności.

Wagi terminów są traktowane jako standard tego, czy dane słowo znajduje się w tym zestawie, czy nie. Wagi terminów są obliczane przez pomiar rozbieżności między rozkładem terminów uzyskanym w procesie losowym a rzeczywistym rozkładem terminów.

Rozbieżność z modelami losowości utworzonymi przez utworzenie instancji trzech głównych elementów struktury: najpierw wybór podstawowego modelu losowości, następnie zastosowanie pierwszej normalizacji i na końcu normalizowanie częstotliwości terminów. Podstawowe modele pochodzą z poniższych tabel.

Definicja

Odchylenie od losowości opiera się na tej idei: „Im bardziej rozbieżność między terminem-częstotliwością dokumentu a jego częstotliwością w zbiorze, tym więcej informacji niesie słowo t w dokumencie d. Innymi słowy, termin- waga jest odwrotnie skorelowana z prawdopodobieństwem występowania terminów w dokumencie d uzyskanym przez model losowości M. (By terrier.org)

(Formuła 1)

  1. M reprezentuje typ modelu losowości, który wykorzystuje do obliczania prawdopodobieństwa.
  2. d to całkowita liczba słów w dokumentach.
  3. t to liczba określonego słowa w d.
  4. k jest zdefiniowane przez M.

Możliwe, że użyjemy różnych modeli urny , aby wybrać odpowiedni model losowości M. W wyszukiwaniu informacji mamy dokumenty zamiast urn, a terminy zamiast kolorów. Istnieje kilka sposobów wyboru M, każdy z nich ma podstawową rozbieżność od modelu losowości, aby go wspierać.

Model

Modele podstawowe

D      Divergence approximation of the binomial
P      Approximation of the binomial
BE        Bose-Einstein distribution
G  Geometric approximation of the  Bose-Einstein 
I(n)   Inverse Document Frequency Model
I(F)   Inverse Term Frequency Model
I(ne) Inverse Expected Document Frequency Model

Modele DFR

BB2    Bernoulli-Einstein model with Bernoulli after-effect and normalization 2.
IFB2    Inverse Term Frequency model with Bernoulli after-effect and normalization 2.
In-expB2 Inverse Expected Document Frequency model with Bernoulli after-effect and normalization 2. The logarithms are base 2. This model can be used for classic ad-hoc tasks.
In-expC2  Inverse Expected Document Frequency model with Bernoulli after-effect and normalization 2. The logarithms are base e. This model can be used for classic ad-hoc tasks.
InL2    Inverse Document Frequency model with Laplace after-effect and normalization 2. This model can be used for tasks that require early precision.
PL2    Poisson model with Laplace after-effect and normalization 2. This model can be used for tasks that require early precision[7,8].

Pierwsza normalizacja

Jeśli w dokumencie nie można znaleźć określonego rzadkiego terminu, wówczas w tym dokumencie prawdopodobieństwo, że termin ten będzie miał charakter informacyjny, jest w przybliżeniu zerowe. Z drugiej strony, jeśli rzadki termin pojawia się często w dokumencie, dlatego może mieć bardzo wysokie, prawie 100% prawdopodobieństwo, że będzie miał charakter informacyjny dla tematu wymienionego w dokumencie. Dobrym pomysłem może być również zastosowanie modelu językowego Ponte i Croft. Zauważ, że składnik ryzyka jest uwzględniony w DFR. Logicznie rzecz biorąc, jeśli termin-częstotliwość w dokumencie jest stosunkowo wysoki, to odwrotnie ryzyko, że termin nie ma charakteru informacyjnego, jest stosunkowo niewielkie. Powiedzmy, że mamy Formułę 1 dającą wysoką wartość, wtedy minimalne ryzyko ma negatywny wpływ na pokazanie niewielkiego przyrostu informacji. Dlatego decydujemy się zorganizować wagę Formuły 1, aby uwzględnić tylko część, która jest ilością informacji uzyskanych dzięki temu terminowi. Im więcej terminów występuje w zestawie elitarnym, tym mniejsza częstotliwość terminów wynika z losowości, a zatem tym mniejsze jest związane z tym ryzyko. Zasadniczo stosujemy dwa modele do obliczenia przyrostu informacji za pomocą terminu w dokumencie: 

the Laplace L model, the ratio of two Bernoulli's processes B.

Termin normalizacja częstotliwości

Przed zastosowaniem częstotliwości tf terminu w dokumencie, długość dl dokumentu normalizuje się do standardowej długości sl. Dlatego termin-częstotliwości tf są przeliczane w odniesieniu do standardowej długości dokumentu, czyli: 

 tfn = tf * log(1+ sl/dl) (normalization 1)

tfn reprezentuje znormalizowany termin częstotliwość. Inna wersja formuły normalizacyjnej jest następująca: 

 tfn = tf * log(1 + c*(sl/dl)) (normalization 2)

Normalizacja 2 jest zwykle uważana za bardziej elastyczną, ponieważ nie ma stałej wartości dla c.

  1. tf jest częstością wyrazu t w dokumencie d
  2. dl to długość dokumentu.
  3. sl to standardowa długość.

Narzędzia matematyczne i statystyczne

Przestrzeń prawdopodobieństwa

Przestrzeń próbkowania V

Indeksowanie teorii użyteczności opracowane przez Coopera i Marona to teoria indeksowania oparta na teorii użyteczności. Aby odzwierciedlić wartość dokumentów oczekiwaną przez użytkowników, terminy indeksu są przypisywane do dokumentów. Ponadto indeksowanie teorii użyteczności jest powiązane z „przestrzeń zdarzeń” w słowie statystycznym. W wyszukiwaniu informacji istnieje kilka podstawowych spacji Ω. Naprawdę prostą przestrzenią podstawową Ω może być zbiór V terminów t, który nazywamy słownikiem zbioru dokumentów. Ponieważ Ω=V jest zbiorem wszystkich wzajemnie wykluczających się zdarzeń, Ω może być również pewnym zdarzeniem z prawdopodobieństwem: 

   P(V)= Σ(t∈V)P(t)=1

Zatem P, rozkład prawdopodobieństwa, przypisuje prawdopodobieństwa do wszystkich zbiorów terminów dla słownika. Zauważ, że podstawowym problemem wyszukiwania informacji jest znalezienie oszacowania dla P(t). Szacunki są obliczane na podstawie próbkowania, a zbiór tekstów doświadczalnych dostarcza próbki potrzebne do oszacowania. Teraz natrafiamy na główny problem, jakim jest właściwe traktowanie dwóch dowolnych, ale niejednorodnych fragmentów tekstów. Paragons jak rozdział w Science Magazine i artykuł z gazety sportowej jako drugi. Można je traktować jako dwie różne próbki, ponieważ te skierowane do różnych populacji.

Pobieranie próbek z dokumentem

Związek dokumentu z eksperymentami wynika ze sposobu wyboru przestrzeni próbnej. W IR termin eksperyment lub próba jest tu używany w znaczeniu technicznym, a nie zdrowym rozsądku. Na przykład dokumentem może być eksperyment, co oznacza, że ​​dokument jest sekwencją wyników t∈V lub po prostu próbką populacji. Porozmawiamy o przypadku obserwowania liczby Xt =tf wystąpień danego słowa t w ciągu eksperymentów. Aby wprowadzić tę przestrzeń zdarzeń, powinniśmy wprowadzić iloczyn przestrzeni prawdopodobieństwa związanych z eksperymentami ciągu. Moglibyśmy wprowadzić naszą przestrzeń próbną, aby powiązać punkt z możliwymi konfiguracjami wyników. Korespondencję jeden do jednego dla przestrzeni próbki można zdefiniować jako: 

  Ω=Vld

Gdzie ld to liczba prób eksperymentu lub w tym przykładzie długość dokumentu. Możemy założyć, że każdy wynik może, ale nie musi, zależeć od wyników poprzednich eksperymentów. Jeśli eksperymenty są zaprojektowane tak, że wynik wpływa na następne wyniki, wówczas rozkład prawdopodobieństwa na V jest inny w każdym badaniu. Częściej jednak, w celu ustalenia prostszego przypadku, gdy przestrzeń prawdopodobieństwa jest niezmienna w IR, często przyjmuje się założenie niezależności terminu. Dlatego wszystkie możliwe konfiguracje Ω=Vld są uważane za równie prawdopodobne. Biorąc pod uwagę to założenie, każdy dokument możemy uznać za proces Bernoulliego. Przestrzenie prawdopodobieństwa iloczynu są niezmienne, a prawdopodobieństwo danego ciągu jest iloczynem prawdopodobieństw w każdej próbie. W konsekwencji, jeśli p=P(t) jest prawdopodobieństwem a priori, że wynikiem jest t, a liczba eksperymentów wynosi ld, otrzymujemy prawdopodobieństwo Xt=tf równe: 

  P(Xt=tf|p)=(ld pick tf)ptfqld-tf

Jest to suma prawdopodobieństwa, że ​​wszystkie możliwe konfiguracje mają wyniki tf poza ld. P(Xt=tf|p) jest rozkładem prawdopodobieństwa, ponieważ 

 Σ(t∈V)P(Xt=tf|p)=(p+q)ld=1
  1. ld Długość dokumentu re.
  2. tf Termin częstotliwość t w dokumencie d.
  3. Xt Liczba wystąpień określonego słowa na jednej liście.

Wiele próbek

Rozważając już hipotezę posiadania jednej próbki, musimy wziąć pod uwagę, że mamy kilka próbek, na przykład zbiór D dokumentów. Sytuacja posiadania zbioru N dokumentów jest abstrakcyjnie równoważna ze schematem umieszczania pewnej liczby Tot V kolorowych typów kulek w zbiorze N komórek. Dla każdego wyrazu t∈V możliwa konfiguracja położenia kulek spełnia równania: 

 tf1+...+tfN=Ft

I warunek 

 F1+...+FV=Tot

Gdzie Ft jest liczbą kulek tego samego koloru t, które mają być rozłożone w komórkach N. W ten sposób zmieniliśmy podstawową przestrzeń. Wynikiem naszego eksperymentu będą dokumenty, w których piłka zostanie umieszczona. Ponadto będziemy mieli wiele możliwych konfiguracji zgodnych z liczbą kolorowych kulek.

  1. Ft Całkowita liczba żetonów t w kolekcji.
  2. Tot Całkowita liczba żetonów w kolekcji D

Dystrybucje

Rozkład dwumianowy

Dystrybucja hipergeometryczna

Statystyki Bosego-Einsteina

Dystrybucje gruboogonowe

Wniosek

Rozbieżność z modelu losowości opiera się na modelu Bernoulliego i jego formach granicznych, rozkładzie hipergeometrycznym, statystyce Bosego-Einsteina i jej formach granicznych, połączeniu rozkładu dwumianowego z rozkładem beta oraz rozkładzie tłuszczu ogonowego. Rozbieżność z modelem losowości pokazuje ujednoliconą strukturę, która ma potencjał do konstruowania wielu różnych efektywnych modeli IR.

Aplikacje

Zastosowania i charakterystyka

  1. Model rozbieżności od losowości można zastosować w automatycznym indeksowaniu w wyszukiwaniu informacji. Można je wyjaśnić jako elitarność rozprawy — pojęcie treści informacyjnej terminu w dokumencie.
  2. Skuteczność modeli opartych na rozbieżności od losowości jest bardzo wysoka w porównaniu zarówno z modelem BM25, jak i modelem językowym. W przypadku krótkich zapytań wydajność modeli rozbieżności od losowości jest zdecydowanie lepsza niż modelu BM25, który od 1994 r. służy jako standardowa baza do porównywania modeli.
  3. Model rozbieżności z losowością może pokazać najlepszą wydajność przy zaledwie kilku dokumentach w porównaniu z innymi umiejętnościami rozszerzania zapytań.
  4. Ramy modelu rozbieżności od losowości są bardzo ogólne i elastyczne. Dzięki rozszerzeniu zapytań przewidzianemu dla każdego komponentu możemy zastosować różne technologie w celu uzyskania najlepszej wydajności.

Bliskość

Bliskość może być obsługiwana w rozbieżności od losowości, aby uwzględnić liczbę wystąpień pary terminów zapytania w oknie o wstępnie zdefiniowanym rozmiarze. Aby sprecyzować, DFR Dependence Score Modifier DSM implementuje oba modele pBiL i pBiL2, które obliczają losowość podzieloną przez długość dokumentu, a nie statystyki pary w korpusie pary w korpusie.

Przykłady rozbieżności od losowości

Niech t będzie terminem, a c zbiorem. Niech termin występuje w tfc=nL(t,c)=200 lokalizacjach oraz w df(t,c)=nL(t,c)=100 dokumentach. Oczekiwana średnia częstotliwość terminów wynosi avgtf(t,c)=200/100=2; jest to średnia w dokumentach, w których występuje ten termin. Niech ND(c)=1000 będzie sumą dokumentów. Występowanie terminu w dokumentach wynosi 10%: PD(t|c)=100/1000. Oczekiwana średnia częstotliwość terminów wynosi 200/1000=1/5 i jest to średnia dla wszystkich dokumentów. Termin częstotliwość jest pokazany jako Kt =0,...,6.

Wykres dla przykładu 1.jpg

Poniższa tabela pokazuje, że kolumna nD jest liczbą dokumentów zawierających kt wystąpienie t, pokazane jako nD(t,c,kt). Kolejna kolumna nL to liczba Lokalizacji, w których występuje termin, zgodnie z następującym równaniem: nL=kt*nD. Kolumny po prawej pokazują prawdopodobieństwa obserwowane i Poissona. P obs,elite(Kt) to prawdopodobieństwo zaobserwowane we wszystkich dokumentach. P poisson,all,lambda(Kt) to prawdopodobieństwo Poissona, gdzie lambda(t,c)=nL(t,c)/ND(c)=0,20 to parametr Poissona. Tabela ilustruje, jak obserwowane prawdopodobieństwo różni się od prawdopodobieństwa Poissona. P poisson(1) jest większe niż P obs(1), natomiast dla kt>1. obserwowane prawdopodobieństwa są większe niż prawdopodobieństwa Poissona. W ogonie obserwowanego rozkładu znajduje się więcej masy niż zakłada rozkład Poissona. Co więcej, kolumny po prawej ilustrują użycie elitarnych dokumentów zamiast wszystkich dokumentów. Tutaj prawdopodobieństwo pojedynczego zdarzenia opiera się wyłącznie na lokalizacji dokumentów elitarnych.

Dalsze zainteresowanie przykładami

  1. Dopasowywanie długości dokumentu .
  2. Stosowanie DFR w dokumentach XML zawierających tylko treść
  3. Wprowadzenie do modeli DFR

Bibliografia

  1. ^ „Rozbieżność od losowości (DFR) Framework” . Terrier Team, Uniwersytet w Glasgow.

Zewnętrzne linki