Doğal dil işlemede kullanılan graph tabanlı algoritmalara geçmeden graph nedir onu tanımlamamız gerekiyor.
Kısaca şöyle tanımlayabiliriz, graph teorisi nesneler arasındaki bağlantıların matematiksel olarak gösterimine deniyor. Teorem ilk olarak matematikçi Leonhard Euler tarafından 1735’te işlendi. Graph teorisinde bir graph node’lar(vertices) ve edge’lerden oluşur. Node’lar entity’leri edgeler ise node’lar arasındaki bağlantıları gösterir.
PageRank Algoritması
PageRank (PR) Google’ın arama sonuçlarını sıralamak için kullandığı graph temelli bir algoritmadır. Algoritma Google’ın kurucuları Lawrence Page ve Sergey Brin tarafından yayınlandı. PageRank bir sayfanın ne kadar önemli olduğunu tahmin edebilmek için sayfaya verilen bağlantıların sayısını ve kalitesini ölçer. A sayfası için PageRank değerini hesaplamak için aşağıda verilen formülü kullanılıyor.
PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
PR(A) A sayfasının PageRank değerini, PR(T1) A sayfasına bağlantı veren T1 sayfalarının PageRank değerini, C(T1), T1 sayfasından diğer sayfalara verilen linklerin sayısını, d ise 0-1 arasında değişen damping parametresini gösteriyor. PageRank iterative olarak çalışan bir algoritmadır. İlk anda tüm sayfaların değerleri aynıdır. Sayfaların PageRank değerleri iterasyonlar sonucu belirlenir. Örneğin, A,B ve C isminde 3 tane sayfamız olduğunu ve d değeri de 0.7 olduğunu düşünelim.
Sayfalar şekilde olduğu gibi birbirine bağlantılı olduğunu varsayalım. A sayfasının C sayfasından referans aldığını görüyoruz. C sayfasının ise başka bir sayfaya referansı bulunmuyor. Sayfalar arasında bağlantı olmasaydı PR değeri 0 olacaktı. A sayfası için PageRank formülünü bu sayfalar için uygularsak.
PR(A) = (1 – d) × ( 1 / N ) + d × ( PR(C) / 1 )
Benzer şekilde B sayfası da A sayfasından referans alıyor. A sayfasının başka bir sayfaya referansı bulunmuyor. Bu durumda PR formülünde belirtilen C(Tn) değeri 1 oluyor. Bu durumda PR(B) değerini aşağıdaki şekilde bulabiliriz.
PR(B) = (1 – d) × ( 1 / N ) + d × ( PR(A) / 1 )
C sayfası da şekilde görüldüğü gibi B sayfasından referans alıyor. B sayfasının ise başka bir sayfaya referansı bulunmamakta. PR formülünü C sayfasının PageRank değerini bulmak için uygularsak.
PR(C) = (1 – d) × ( 1 / N ) + d × ( PR(B) / 1 )
Verilen değerleri formülde yerlerine koyduğumuzda,
PR(A) = (1 – 0.7) x (1/3)+ 0.7x(PR(C)/1) -> PR(A) = 0.1 + 0.7 × PR(C)
PR(B) = (1 – 0.7) x (1/3)+ 0.7x(PR(A)/1) -> PR(B) = 0.1 + 0.7 × PR(A)
PR(C) = (1 – 0.7) x (1/3)+ 0.7x(PR(B)/1) -> PR(C) = 0.1 + 0.7 × PR(B)
Denklemleri çözersek sayfalara ait PR değerlerini hesaplamış oluyoruz.
PR(A) = 1/3 = 0.33 PR(B) = 1/3 = 0.33 PR(C) = 1/3 = 0.33
TextRank Algoritması
TextRank algoritması (Mihalcea 2004) PageRank algoritmasını temel alır ve graph temelli bir algoritmadır. PageRankta değinildiği gibi sayfalar arasındaki referans ilişkileri sayfanın önemini belirlemede önemli bir rol oynar. Ana düşünce önemli olan sayfalar önemli olan sayfalardan referans alır ve bir sayfanın PageRank değerini bir kullanıcının o sayfayı ziyaret etme olasılığı belirlemesidir. PageRank algoritmasını text summarization uygulamalarında kullanabiliriz. PageRank algoritması bir textin özetini çıkaracak şekilde uyarlanabilir. Bunun için öncellikle sayfalar yerine cümlelerin temel alınması gerekiyor. Bu nedenle TextRank algoritmasında sayfalar yerine cümleler bulunuyor. İki cümle arasında ki benzerlik PageRank algoritmasında ki bir sayfanın diğerine referans verilmesi olarak düşünülebilir. Cümleler arasındaki benzerlik skorları benzerlik matrisinde tutulabilir. Bu benzerlik değerleri üzerinden bir sıralama yapılarak verilen bir metnin özeti çıkarılabilir. TextRank algoritmasında kullanılan temel adımları incelersek.
Step 1: Metin üzerinde pre-processing işlemi yapılır. Ardından metin cümlelere bölünür.
Step 2: Cümlelerden bir dil modeli oluşturulur. Cümlelere karşılık gelen dil modeli oluşturulurken BOW, TD-IDF veya hazır kelime vektörlerinden biri olan GloVe kullanılabilir.
Step 3: Cümle vektörlerinde ki benzerlik değerleri benzerlik matrisinde saklanır.
Step 4: Similarity matrisi bir grapha çevrilir. Graph’ta vertices(nodes) cümleleri, similarity score’ları ise edge olarak gösteriliyor. Similarity measure olarak cosine similarity kullanılabilir.
Step 5: Graph’taki sıralanan similarity skorlarına göre cümle seçimi yapılır.
LexRank Algoritması
LexRank algoritması (Erkan, 2014) TextRank gibi PageRank algoritmasını temel alır ve graph temelli bir algoritmadır. Ana fikir cümlelerin okuyucuya benzer diğer cümleleri tavsiye etmesi üzerinedir. Bir cümlenin önemi öneren cümlelerin öneminden de kaynaklanmaktadır. Bu sayede bir cümlenin özet olarak seçilebilmesi için diğer birçok cümleye benzer olması gerekmektedir. Bu özetleme yaklaşımına Centrality-based Sentence Salience deniyor. LexRank ile TextRank algoritması arasındaki temel fark, graph edge’lerine weight ataması yapan weighting fonksiyonundadır. TextRank tüm ağırlıkları PageRankte olduğu gibi birim ağırlık olarak kabul eder ve cümle ranklerini buna göre hesaplar. Başka bir deyişle TextRank PageRank’in birebir uygulaması gibi çalışır. LexRank ise ağırlık atamak için cümle centrality’sini hesaplar. LexRank algoritmasında kullanılan temel adımları incelersek.
Step 1: Metin üzerinde pre-processing işlemi yapılır. Ardından metin cümlelere bölünür.
Step 2: Cümlelerden dil modeli oluşturulur.
Step 3: Cümle vektörleri grapha çevrilir. Graphta her bir cümle bir nodeu temsil ediyor. Edgeler ise cümleler arasında ki benzerlik ilişkilerini temsil ediyor.
Step 4: Cümleler arasındaki benzerlik TF-IDF formülüyle modifiye edilmiş cosine formülüyle bulunuyor.
Formül x e y cümlelerinin arasındaki distance değerini ölçüyor. Birbirine benzer cümleler uzaklık olarak daha yakın değerlere sahip oluyor.
Step 5: Cümle skorlarının tutulduğu similarity matrix oluşturuluyor.
Step 6: Similarity matrix değerlerine göre bir sıralama oluşturulup, cümle seçimi yapılıyor.
Luhn Algoritması
1958 yılında Hans Peter Luhn tarafından yayınlanan algoritma metin özetleme alanında yapılmış ilk çalışmalardan birisidir. Algoritma kredi kartı numarası checksum işlemleri gibi çeşitli alanlarda da kullanılıyor. Luhn algoritması TD-IDF modelini temel alır. Luhn’ a göre konu yazar tarafından detaylandırılırken bazı kelimeler sıklıkla kullanılır. Kelimenin sık kullanılması o kelimenin yazı için önemini gösterir. Bir kelime bir yazı içerisinde ne kadar sık bulunursa bu kelimelerin her birine daha fazla önem verilebilir. Luhn algoritmasında kullanılan temel adımları incelersek.
Step 1: İlk adımda önemli olan kelimeler başka bir deyişle keywordler belirlenir. Metinde kullanım sıklığına göre en az ve en fazla kullanılan kelimeler belirlenir. En çok geçen kelimeler ve en az geçen kelimeler ignore edilir.
Step 2: Metindeki her cümle için weight hesaplanır. Weight değerleri cümleler için birer skor değeridir. Skor değeri bulmak için öncelikle window size değerini hesaplamamız gerekiyor. Window size değeri cümlede geçen iki önemli kelime(keywords) arasında ki uzaklık değerini gösteriyor. Score değeri önemli kelime sayısının karesinin window size değerine bölümünden oluşuyor.
Step 3: Her cümle için hesaplanan skor değerleri sıralanır. Ardından cümle seçimi yapılır.
Anlatılan algoritmalarını çalışma sürecini bir görsel üzerinden göstermek istersek.
Sonraki makalelerde yukarıdaki grafiği detaylandırmaya çalışacağım özetle bir metin özetleme uygulaması yapmak istiyorsak. Öncelikle üzerinde çalışma yapacağımız bir dataset bulmamız gerekiyor. Sonrasında bu dataset data preprocessing işlemleri olan daha önce bahsettiğimiz Tokenizing,Lemmatizing ve stop words işlemlerini uyguluyoruz. Sonraki aşamada TD-IDF veya BOW dil modelleme yöntemlerini kullanarak bir dil modeli oluşturuyoruz. Oluşturduğunuz dile modeline ise extractive metin özetleme algoritmaları olan,yukarıda bahsi geçen yöntemlerden birini uyguluyoruz. Çıktı olarak ise verdiğimiz datasetteki cümlelerin özetini almamız gerekiyor tabiki. Her algoritmanın veya yöntemin kendine göre avantajları var. Bunu ise Rouge/Bleu metin özetlme kalite ölçütlerine göre değerlendiriyoruz.
Bu makalemde extractive metin özetleme yöntemlerinde graph theory temelli textrank,lexrank ve td-idf temelli luhn algoritmasını anlattım. Umarım faydalı olmuştur sonraki yazılarda görüşmek üzere.
Murat 🙂
