Elasticsearchin arkasındaki algoritma : Inverted Index ve TF-IDF

Kullandığımız çoğu toolun arkasında işleyen algoritmalar geçmişte yapılan researchlerin sonucudur. Çok fazla dikkat çekmiyor olsa da yapılan teorik researchler bu gibi işlerin temellerini oluşturur. Buz dağının altında kalan kısımdır da diyebiliriz . Görünür kısmından çok daha büyüktür.  Aslında bu yazıda elasticsearch konusu elasticsearchün popülerliği sebebiyle tamamen yazının daha ilgi çekici olmasını amaçlayarak başlığa eklediğim bir kısım.  Hemen hemen tüm arama motorları, kullanıcılar tarafından sorgulamayı desteklemek için inverted-index kullanır. 2015 yılında yapılan bir anket de, dijital kütüphanelerdeki metin tabanlı öneri sistemlerinin% 83’ünün TF-IDF kullandığını göstermiştir.

Aslında konuyu elasticsearchten bağımsız anlatacağım için konunun elasticsearch üzerindeki uygulanışını Elasticsearch In Action kitabının ilk chapterını okuyarak ya da elasticsearch’ün kendi sitesinden aşağıdaki linkten takip edebilirsiniz.

Yavaş yavaş esas konumuza gelebiliriz. Bu yazımda Inverted Index TF-IDF’in nasıl çalıştığını algoritmasını adım adım anlatmaya çalışacağım. Elinizde bir text bir de aramak istediğimiz pattern olduğunu varsayalım. Amacımız da patternimizi textimizin içerisinde aramak. Yani search yapmak. Örnek vermek gerekirse patternimizin “araba” olduğunu varsayarsak textimiz olan “almak istediğim araba çok pahalı” dizgisi içerisinde bu pattern var mı yok mu diye aramak istiyoruz. Eğer ki elimizdeki text kümesi üzerinde sık aralıklarla arama yapacaksak en makul yol bu texti indexlemekten geçer.

1.TOKEN BASED SEARCH ve FULL TEXT INDEX SEARCH

1.1 Token Based Index

Token based search dediğimiz search yapısı, elimizdeki texti kelimelere ayrıştırabildiğimiz yani tokenize edebildiğimiz ve bu şekilde üzerinde arama yaptığımız search yapısıdır. Yani genel olarak kelime bazlı arama yapılır.

1.2 Full Text Index 

Full text index search , textin ne olduğuyla ilgilenmez. Full text search için tek önemli şey arka arkaya gelen semboller dizisidir. Herhangi bir byte sequence oluşturulan index üzerinde arama yapılabilir. Yani textimizin tokenize olabilmesine gerek yoktur.

Bir örnek vermek gerekirse ;

Textimiz ; “Beğendiğim araba çok pahalı” olsun

Token based search yapmak istersek “araba” kelimesini arayabilirken “raba” yı arayamayız çünkü “raba” bizim textimiz içerisinde tokenize olabilecek yapıda bir kelime değildir. Ancak full text index yapısıyla “raba”‘yı da arayabiliriz.

1.1 TOKEN BASED INDEX

Bu kısımda step by step token based index üzerinde inverted index & TF-IDF ile searchin nasıl yapıldığı ve algoritmanın nasıl çalıştığını anlatmaya çalışacağım. Bir sonraki yazımda da full text indexten bahsetmeye çalışacağım.

1.1.1. Binary Term-Document Incidence Matrix’in Oluşturulması

Binary Term Document Incident Matrix yapısıyla kelimelerimizin hangi dökümanlar içerisinde bulunduğunu 0, 1lerden oluşan matrixleri içerisinde tutarız. Aşağıdaki matrix üzerinden ilerleyecek olursak, binary term document incident matrix oluşturmak için ilk yapmamız gereken şey, dökümanlarımızda bulunan tüm kelimelerimizi distinct bir şekilde tokenize etmektir. Bunun sonucunda elde edeceğimiz küme bizim matriximizde satırlarımızı oluşturucak. Sutünlarımızı da döküman isimlerimiz oluşturacak. Sonrasında eğer ki ilgili token o dökümanda varsa matrixteki konumuna 1 yok ise de 0 koyarak ilerleyeceğiz.

Aşağıdaki örnekte elimizde distinct olarak tokenize edilmiş kelimeler “Antony”, “Brutus”, “Ceaser”, “Caipurnia”, “Cleopatra”, “mercy” ve “worser”‘dir. Bunlar matriximizde satırlarımızı oluşturur. Sutünlarımız da dökümanlarımızın isimleri yani matriximiz özelinde “Antony and Cleopatra”, “Julius Ceaser”, “The Templest”, “Hamiet”, “Othello”, “Macbeth” dir.

Elimizdeki token o dökümanda geçiyorsa matrixte ilgili hücreye karşılık gelen kısma 1 koyuyoruz. Yani “Antony” kelimesi (tokeni) “Antony and Cleopatra”, “Juilius Caesar ve Macbhette” dökümanlarında geçiyor gibi..

Dolayısıyla elimizde N kelime M adet de döküman varsa NxM’lik bir binary matiximiz olmuş olur. Matrix’i oluşturduktan sonra bir kelime aramak istediğimizde tek yapmamız gereken o kelimenin yani tokenin bulunduğu satıra gidip 1 olan dökümanları geriye dönmekten ibarettir. Eğer ki iki kelimenin birleşimini aramak istiyorsak, yani  “Brutus” ve “Ceaser” tokenlarını aramak istiyorsak da tek yapmamız gereken satırları yani bit değerlerini AND lemektir.

Aslında inverted index kavramı da buradan gelliyor. Yani siz dökümanın içerisinden kelime aramıyorsunuz da kelimeler üzerinden kelimelerin bulunduğu dökümanlara gidiyorsunuz. Tersinir index.

1.1.2. Inverted Index

Buraya kadar bahsettiğimiz yapıyla elimizde 0 ve 1lerden oluşan bir NxM’lik bir matrix oluşur. Bu matrix üzerinde tahmini 0’lar 1’lere nazaran çok daha yoğun olacağından bu matrix sparse matrix olacaktır ve bellekte kapladığı yer de fazla olacaktır. Dolasıyla algoritmanın üzerinde çalışanlar bunu bir adım ileri götürmeye karar vermişler ve madem bizim böyle bir matriximiz var.  Biz bu matrixi tutmak yerine sadece tokenlarımınız geçtiği dökümanların ID listini tutalım ve alandan kazanalım gibi bir düşünceyle ilerlemişler ve ortaya aşağıdaki gibi bir yapı çıkmış ki bu da bizim inverted indeximiz oluyor.

1.1.3. Invertex Index Üzerinde Arama Yapma

Bitwise yani 0 ve 1lerden oluşan başta bahsettiğim gibi bir matrixte arama yaparken, iki kelimenin kesişimini arıyorsak satırları ANDlemenin yeterli olacağını söylemiştim. Artık bitwise bir matrix yerine her tokenin bulunduğu dökümanların Id listini sorted bir şekilde tutuyoruz. Burada iki kelimenin kesişimini aramanın maliyeti Sorted ıd listi kısa olan tokena oranlı lineerliğe sahiptir. Zaten Id listleri sorted tutmanın sebebi de aramayı linear zamanlı bir hale getirebilmektir. 

Burada temel mantık şu, iki satıra da bir pointer koyarız. Eğer pointerlar eşit değilse değeri küçük olanı bir sağa kaydırırız. Eşitse ikisini birden kaydırırız.

 

1.1.4. Positional Index

Inverted index üzerinde phase search yapamayız. Bunu yapmak için kullanmamız gereken yapı Positional indextir. Şuana kadar oluşturduğumuz inverted index yapısında elimizdeki tokenların hangi dökümanlarda geçtiğini tutmaya başladık. Şimdi ise bunun yanında o dökümanlardaki positionlarını da tutacak yapıyı oluşturuyoruz. Yani “Ceaser” tokeini (kelimesi) bizim için 2. dökümanda geçiyor demek artık yeterli değil 2. dökümanda örneğin 3. 7. ve 8. sırada geçiyoru da yapımıza ekliyoruz.

Aslında bu bizim space requirementimizi artırır ama positional Indexten phase query run edebilir oluruz. 

1.1.5. Relevancy Problemi :  Ranked Retrieval – TF-IDF

Diyelim ki aramak istediğimiz tokenı arattık ve bize bulunduğu dökümanları bu şekilde D {D8,D10,D100,D400}  döndü. Ancak burada önemli bir ihtiyaç doğuyor. Bu dönen dökümanların hangisi bizim için, aramak istediğimiz içerikle daha ilişkili yani relevant olduğunu nasıl anlarız. Burada kurulan logic gayet kolay. Aradığınız token hangi dökümanda daha çok geçiyorsa o sizin aradığınız içeriğe daha relevanttır diyebiliriz. Yani aratmak istediğiniz kelime “aslan” ise , bu döküman 1’de 3 kere, döküman ikide 300 kere geçiyorsa, döküman 2 sizin için daha öncelikli sırada olmalıdır. Yani aranan kelimenin en çok geçtiği dökümanı en öncelikli getirmek istiyorum. ANCAK….

İlk olarak matrix yapısına tekrar döndüğümüz için bu yapıyla yukarıda bahsettiğim positional Index yapısından kazançlarımızı kaybederiz ancak önemli iki konuya çözüm getirebiliriz.

ISSUE 1 – Kelimelerin Dökümandaki Sıklığı – Term Frequency – TF

Ama aradığımız kelimenin 300 defa geçtiği döküman 3 defa geçen dökümandan 100 kat daha mı değerlidir? Tabiki hayır, bu şekilde bir logicte arama yaptığımızda relevantlar arasında uçurum olur. Bu sebeple, bulunan çözüm occurence sayısının log 10 tabanını almaktır ve bu da çok büyük kat oranlarını birbirine yakınsar.

3 için 1+log 3  ve  300 için 1 + log 300 arasındaki ilişki daha anlamlı olur. Dolaysıyla matrisimiz de loglardan oluşan bir matrix olur.

ISSUE 2 – Dökümanda Nadir Geçen Kelimelerin Etki Ağırlığı – Inversed Document Frequency – IDF

Öyle kelimeler var ki kelimenin sayısı içeriğin relevancysi üzerinde etkili değildir Örneğin, “the” kelimesinin bir ingilizce bir textte 50 defa veya 100 defa geçmesi arasında bizim öncelik oranımızı değiştirecek bir fark olmamalı. Bunun tersi bir mantıkla da  özel kelimeler için düşünürsek, korku daha genel bir kelime ama araknafobia özel bir kelime. Araknafobia korkusu… Yani bu özel bir kelimenin çok geçmesinin verdiği katkı genel bir kelime den daha fazla olmalı. Yani sonuç olarak kelimelerin belirli önem ağırlıkları olmalı.

N döküman collecion sayısı, dft o termin kaç dökümanda geçtiğidir. Yani benim elimde 100 tane döküman var araknafobia 10 tanesinde geçiyor korku kelimesi 50 tanesinde geçiyor gibi. Çıkan sonucu, o kelimenin geçtiği değer ile yani ağırlık ile çarpıp ve yeni matrixi elde ederiz.

Artık  TF-IDF matriximizi aşağıdaki gibi oluşturmuş olduk.