İleri ve geri zincirleme (Forward and Backward Chaining)

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bilgisayar bilimlerinde, özellikle de mantıksal sistemlerin ispatında kullanılan ileri zincirleme ve geri zincirleme yöntemlerini açıklamaktır.

Yöntemin çalışması oldukça basittir. Öncelikle problem, mantık düzleminde modellenir. Buradaki mantık sistemi sonlu ispatı olan herhangi bir system olabilir. Örneğin birinci dereceden mantık (first order logic) veya daha özel olarak boole cebiri kullanılabilir.

Modelleme aşamasının ardından problemin çözümüne geçilir. İşte tam bu noktada ileri zincirleme (forward chaining) veya geri zincirleme (backward chaining) yöntemlerinden birisi seçilebilir.

Örneğin aşağıdaki mantıksal sistemi ve şekli ele alalım:

Sistemde görüldüğü üzere bazı mantıksal dizilimler verilmiş ve son iki satırda A ve B önermelerinin (kaziye) doğru olduğu belirtilmiştir.

Buna göre sağdaki çizim, hangi durumlarda, hangi diğer durumların doğru olacağını bu mantıksal sistemden çıkarır. Örneğin p=> q ifadesi, çizimin en tepesinde gösterilmiş ve p önermesinin (predicate, kaziyesinin) doğruluğu halinde q önermesinin de (kaziyesinin de) doğru olacağını ifade etmektedir.

Benzer şekilde, L önermesinin (kaziyesinin) doğruluğu A ve B önermelerine bağlı olduğu gibi, A ve P önermelerinin doğruluğuna da bağlanmıştır. Bu iki sistemden birisinin doğru olması sonucun doğruluğunu sağlar.

Şimdi şekilde gösterilen sistemi ileri zincirleme (forward chaining) yöntemi ile çözelim. Öncelikle sistemdeki bütün doğruluk şartlarını sayısal olarak ifade ediyoruz:

Şekilde görüldüğü üzere bütün doğruluk şartları birer sayı ile ifade edilmiştir. Söz gelimi, M önermesinin doğruluğu L ve B önermesi gibi 2 önermenin doğruluğunu gerektirir. Bu yüzden M birleşiminde 2 sayısı bulunur. Benzer şekilde Q önermesinde bulunan 1 sayısı, sadece P önermesinin doğruluğunun yeterli olduğunu ifade etmektedir.

Şimdi ileri zincirleme yöntemini kullanarak sistemin doğru olduğu verilen A ve B önermelerinden itibaren çözümünü izleyelim.

Öncelikle A ve B’ye komşu olan düğümlerdeki değerleri 1’er azaltıyoruz:

Yukarıdaki şekilde ileri zincirleme işlemi (forward chaingin) A önermesi için çalıştırılmış olup A’nın komşularını 1 azaltmıştır. Sırada B önermesi var ve onu da çalıştıralım:

Görüldüğü üzere B’nin komşuları da 1 azaldığında 0 değerine sahip bir düğüm elde ettik. Bu durumda L’nin doğru olduğunu söyleyebiliriz çünkü L’nin doğru olması için gereken 2 değer de sağlandı. Yani mantıksal sistemimizde bulunan

A Ù B Þ L

Satırını sağlamış olduk. Buradan doğruluğunu bulduğumuz L önermesinin komşularını 1 azaltıyoruz:

L’nin komşularının 1 azalması sonucunda M’nin değeri 0’a inmişi oluyor ve artık M için de doğru diyebiliyoruz. Şimdi M’nin komşularını 1 azaltalım:

Artık P için doğru sonucuna ulaştık ve P’nin iki komşusununda değerini 1 azaltarak sonucu buluyoruz:

Görüldüğü üzere zaten doğru olduğunu bildiğimiz L için tekrar doğru sonucunu bulduk ve ilave olarak Q için de doğru sonucunu bulduk.

Demek ki ilk sistem bize verildiğinde, Q’nun değeri sorulsaydı, doğru olduğunu söyleyebilirdik, ancak bunu bilgisayarın bulması için yukarıda adım adım anlatılan aşamaların tamamlanması gerekmektedir.

Geri Zincirleme (Backward Chaining)

Gelelim aynı amaç için kullanılan, yani bir mantıksal sistemi çözmek için kullanılan geri zincirleme yöntemine. İleri zincirleme yöntemine çok benzer olarak yine bir mantıksal sistem, bir şekil üzerinde gösterilebilr:

Sistemde diyelim ki Q’nun değerini merak ediyor olalım. Bilgisayar algoritması, bu defa Q’nun değerinin doğruluğunun P’nin değerinin doğruluğuna bağlı olduğunu çözerek işe başlayacaktır. Aslında geri zincirlemede kullanılan yaklaşım, tam olarak ileri zincirlemenin tersidir. İleri zincirlemede, doğruluğunu bildiğimiz önermelerden başlanırken, geri zincirlemede, doğruluğunu aradığımız önermelerden başlıyoruz. Burada doğruluğunu aradığımız önerme Q olduğuna göre, Q’dan başlayarak sistemi dolaşacağız. İlk adımda Q’nun doğruluğu, P’nin doğruluğuna bağlıdır, o halde Q yerine P doğru mudur diye sistemi çözmeye çalışırız:

P’nin doğruluğu, şekilde de görüldüğü üzere, L ve M’ye bağlıdır ve artık L ve M doğru mudur diye sorarız. Bunlardan birisinin yanlış olması halinde sonuç yanlış veya ikisinin de doğru olması halinde sonuç doğru olacaktır. Burada sonuç ile kastedilen P ve dolayısıyla Q’dur. Dikkat edilirse artık L ve M’ye bakarak Q’nun değerini tahmin edebiliyoruz. Devam edelim:

L’nin doğruluğuna bakıldığında P ve A bulunmakta, aslında bu sorunun cevabını P’nin değerini bilmediğimiz için veremeyiz. Ancak burada bir tehlike bizi bekliyor, şayet doğruluğunu araştırmak için DFS (depth first search, derin öncelikli arama) benzeri bir algoritma ile ağacı (veya şekli (graph) ) dolaşıyorsak, bu durumda bir sonsuz döngüye (fasit daire) girme ihtimalimiz bulunuyor. Bunu engellemek için diyelim ki derinliği sabitledik ve L’nin doğruluğu için A ve B ikilisine bakmaya karar verdik:

Sonuçta A ve B doğru ise L doğru demektir. O halde L doğru mu sorusunu sormayı bırakıyor ve M doğrumu A ve B doğru mu sorularını arayarak sistemi çözmeye devam ediyoruz. M’nin doğruluğu ise L ve B’ye dayanmakta, o halde bir kere daha L’nin doğruluğunu sorguluyor ve yukarıda anlatıldığı üzere bir kere daha A ve B’nin doğruluğunu sorguluyoruz. Neticede sorumuz basitçe A ve B doğru mudur şeklinde oluyor.

Verilen mantıksal sistemden de bildiğimiz üzere A ve B doğrudur, o halde Q da doğrudur diyebiliriz, çünkü sistemi buraya kadar adım adım çözdük ve neticede Q’nun doğruluğunu sorgulamanın A ve B’nin doğruluğunu sorgulamak olduğunu gördük.

Geri zincirleme (backward chaining) yaklaşımında istenirse buradan geriye dönülerek bütün sistemdeki önermelerin durumları doğru veya yanlış olarak işaretlenebilir. Ancak geri zincirleme algoritması, bu aşamada aranan Q önermesinin sonucunu bularak durabilir de. Bu iki yaklaşım arasındaki fark aslında CPS (call by passing style) ile birikimsel tarz (accumulation style) arasındaki fark gibidir.

İki yöntemde de sonuç doğru bir şekilde bulunur. Belki ufak bir fark olarak dikkat edilmesi gereken, geri zincirlemede, özel olarak aranan bir önermenin sonucuna konsantre olmamız, buna bağlı olarak da bazı büyük sistemlerde, sistemin sadece belirli bir kısmını çözüyor olmamız görülebilir. Buna mukabil, ileri zincirleme yaklaşımında, sistemin tamamı çözülmektedir.