A Learning algorithms for binary neural networks

Abstract

Tümdevre teknolojisi son yıllarda, özellikle CMOS prosesinde, büyük gelişmeler göstermiştir [1]. Tranzistör boyutlarının giderek küçülmesi, tümdevre yoğunluğunu oldukça arttırmıştır. Ancak, küçük boyutlara inildikçe tasarım süresi uzamakta ve verim düşmektedir. Bu nedenle, tümdevre üretimindeki ekonomik kısıtlar kırmık yoğunluğu ve maliyet için bir optimum çözüm gerektirir. Kapasitif eşik lojiği (CTL) yapılan serim açısından oldukça sistematiktir ve bu yapıların serim alanı geleneksel lojik ile gerçeklenen devrelerden daha küçük olmaktadır [1], [2]. Boole fonksiyonlarının eşik lojiği kullanılarak gerçekleştirilmesi 1960'dan bu yana yoğun araştırmalar yapılan bir konudur. Eşik lojiğinin çok girişli sistemlerdeki kapasitesi ve karmaşık sayısal sistemlerin tasarımında yararlanılabilir bir alan olduğu ortaya konmuştur [1]. Herhangi bir boole fonksiyonu klasik AND - OR kapı dizisiyle gerçeklenebilmektedir. Benzer şekilde, AND ve OR kapısı görevi gören eşik lojiği yapılan ile de bu fonksiyonlar gerçeklenebilmektedir. Bu tür yapılar, yapay sinir ağlarının bir alt kümesidir ve bu tür ağlar üç tabakadan oluşmaktadır: Giriş tabakası, gizli tabaka ve çıkış tabakası. Böyle bir tasarım eşik lojiğinin avantajlarını kullanmadığı için önerilmemektedir. Bir yapay sinir ağının CTL yapılan ile gerçeklenebilmesi için ağırlıkların ve eşiklerin pozitif tamsayı olması ve nöronun transfer fonksiyonunun kesin sınırlayıcı olması gerekmektedir. Ancak, dijital VLSI teknolojisiyle gerçeklemeye uygun olabilecek tamsayı eşik ve ağırlıklara sahip yapay sinir ağı modeli öneren etkili bir öğrenme algoritması bulunmamaktadır. Bu çalışmada, üç tabakalı ikili yapay sinir ağlan için nöron sayısını otomatik tespit eden bir öğrenme algoritması tanıtılmıştır. Bu algoritma genel olarak negatif ve pozitif ağırlıklarla çalışmaktadır. Bir nöral ağı CTL devrelerle gerçeklemek gerekirse, bu algoritmanın bulduğu negatif ağırlıklara karşı düşen girişin tümleyeni alınarak bu negatif ağırlıklar pozitif değerlerine dönüştürülmelidir. Bu algoritma, aşağıda Rosenblatt tarafından tanımlanan nöron modelini kullanmaktadır [3], [4]: n 1=1 Burada jc" / = 1,...,«, girişleri, an, i = \,...,n, ağırlıkları, m, eşiği ve y, çıkışı göstermektedir. Nöronun transfer fonksiyonu/^ şu şekilde tanımlanmaktadır: /(£) = 0 if£<0 /(£) = ! İf£>0 £ = 0 ile tanımlanan (n-l)-boyutlu bir hiperdüzlern, lineer ayrılabilir bir boole fonksiyonunu sınıflayabilir. Ağ fonksiyonu olarak da adlandırılan bu hiperdüzlern şu şekilde net(x, cog) = coixi + 0*2X2 + - + öwc» - ata = 0 Lineer ayrılabilirlik özelliğine sahip bir boole fonksiyonu, yukardaki nöron modelindeki ağırlıklar ve eşik hesaplanarak tek bir nöronla gerçeklenebilmektedir. xı Eğer verilen bir boole fonksiyonu bu özelliğe sahip değilse, bu fonksiyonun birkaç lineer ayrılabilir fonksiyonlara parçalanarak bir yapay sinir ağı ile gerçeklenmesi gerekmektedir. Bu amaçla, geliştirilmiş genişlet-ve-kes öğrenme algoritması (modified expand-and-truncate learning algorithm, METL) geliştirilmiştir. Algoritma, fonksiyonun T olduğu ve '0' olduğu giriş vektörlerinin sayılarının belirlenmesi ile başlamaktadır. Eğer fonksiyonun T olduğu vektörlerin sayısı, '0' olduğu vektörlerin sayısından az ise Fminor=l, aksi takdirde Vmasx=0 şekilde tanımlanan bir azınlık gösterici tespit edilir. İstenen çıkışı PUio/a eşit olan giriş vektörleri, azınlık vektörleri; diğer vektörler de çoğunluk vektörleri olarak adlandırılmaktadır. Giriş vektörleri gerektiği gibi sınıflandırıldıktan sonra, fonksiyonun hangi boyuta indirgenebileceği test edilir. Bunun için, azınlık vektörleri kümesi incelemeye alınır. Bu kümedeki her bir eleman incelenerek değeri değişmeyen bir giriş aranır. Örnek olarak şu fonksiyonu dikkate alalım. {xix%xı} = {000, 001, 010} giriş vektörleri için / fonksiyonu '1' değerini alsın ve diğer giriş vektörleri için de/fonksiyonu '0' değerini alsın. Burada, azınlık vektörlerinin sayısı 3 'tür ve bu vektörler incelendiğinde *3 girişi hep '0' değerinde kaldığı görülmektedir. Böyle değişmeyen girişler tespit edildikten sonra Vmaoı değeri ve değişmeyen girişlerin değeri not edilir. Verilen örnekte Fmmor = 1 ve *3 = 0 olarak tespit edilir. Daha sonra, bu giriş azınlık vektörlerinden atılır ve çoğunluk vektörleri arasında, bu girişin değeri, not edilen değere eşit olmayan vektörler, çoğunluk vektörleri kümesinden atılır. Verilen örnekte, bu elemeden sonra ilk durumdaki azınlık vektörleri kümesi, {00, 01, 11} şekline dönüşür ve çoğunluk vektörleri kümesi de sadece {11} vektörünü içerir. Elemeden sonra elde edilen fonksiyon 2-boyutlu bir fonksiyondur ve benzer işlemler yapılarak bu fonksiyon da indirgenebilir. Bu indirgeme işlemi fonksiyon indirgenemez bir duruma gelene kadar devam edilir. Fonksiyon indirgendikten sonra fonksiyonun gerçeklenebileceği maksimum nöron sayısı belirlenir. Klasik lojik ailelerden bildiğimiz gibi herhangi bir «-boyutlu boole fonksiyonu 2n"1 nöron ile gerçeklenebilir. Bu limit, Karnaugh diyagramlarında açıkça xii görülebilmektedir. Fonksiyonun yapısını bildiğimiz takdirde, bu sınır azınlık vektörlerinin sayısı kadar olmaktadır ve şu şekilde ifade edilir: ^vmax =Inİn z'-Z/'WZ/'W /=1 (=1 Lineer Ayrıştırma (LS Decomposition, LSD) adı verilen bir metod, gerçeklenebilecek maksimum nöron sayışım bulmak için kullanılabilir. Bunun için azınlık vektörlerinden oluşan bir küme alınır. Her bir küme elemanı, alt alta bir tablo oluşturacak şekilde yazılır ve bunlar grup liderleri olarak adlandırılırlar. Sonra, her elemanın komşu vektörleri tespit edilir. Bunun için Hamming uzaklığı T olan vektörler tespit edilir ve grup liderinin yanına yazılır. Bu şekilde tablo oluşturulduktan sonra sıfırdan farklı en az komşulara sahip vektörler tespit edilir. Bu vektörlerin komşularının grup lideri olduğu gruplar listelenir ve en çok komşuya sahip olan grup ilk Lineer Ayrılabilir (LA) fonksiyon olarak seçilir. Bu seçilen grubun elemanları tablodan tamamen silinir ve geri kalan vektörler için bu işlemler yenilenir. Örnek olarak, 4-girişli bir fonksiyon düşünelim. Bu fonksiyon {4, 5, 6, 7, 15} giriş vektörleri için '1', diğerleri için '0' değerini alsın. Bu vektörlerin komşularının oluşturduğu tablo, Tablo l'deki gibidir. Tablo 1. Verilen Örneğin Komşular Tablosu xuı Tablo l'de görüldüğü gibi vektör 15, en az komşuya sahiptir. Bunun komşusunu incelersek, vektör 7'nin en fazla komşuya sahip olduğunu görürüz. Sonuçta, bu grubu LA fonksiyonu olarak seçip bu elemanları tablodan kaldırırsak Tablo 2 oluşur: Tablo 2. Verilen Örneğin indirgenmiş Komşular Tablosu Buradaki vektör 4 de, ikinci LA fonksiyon olur ve sonuçta ana fonksiyon, 2 alt LA fonksiyona ayrıştırılmış bulunmaktadır. Bu şekilde elde edilen nöron sayısını NLSDmax ile gösterelim. Son olarak, herhangi bir «-boyutlu boole fonksiyonu maksimum « nöron ile gerçeklenebilmektedir. Bunun için şu 4-girişli fonksiyonu dikkate alalım. {0, 3, 5, 6, 9, 10, 12, 15} için fonksiyon T, diğer vektörler için de '0' değerini alsın. Bu, giriş vektörlerinin en kötü dağılımıdır. Eğer { 1 } ve { 14} vektörleri, çıkışı ' 1 ' olacak şekilde dönüştürülürse, elde edilen fonksiyon, 2 nöron ile gerçeklenebilmektedir. Esas fonksiyona dönmek için bu değişikliği geri almamız gerektiğinden bu işlem için de 2 nöron gerekmektedir. Sonuçta, h1h2+h3h4 şeklinde gerçeklenecek bu fonksiyon için toplam 4 nöron gerekmektedir. Bu sayı da giriş vektörünün boyutuna eşittir. Genelleştirirsek, eğer m-girişli bir boole fonksiyonu, m-girişli bir fonksiyona indirgenebiliyorsa, gereken maksimum nöron sayısı şu şekilde bulunur: Ndimmax=m Bütün bu sınırlamalar birleştirilirse bir boole fonksiyonunu gerçeklemek için gereken maksimum nöron sayısı şu şekilde bulunur: XIV .**max - m^n[-'*vmax9-'*LSDmax'^'dimnıaxJ Temel vektörün tipini (doğru veya yanlış) belirlemek için şu yöntem kullanılabilir: İlk önce tüm vektörlerin (doğru ve yanlış) komşularının sayısı belirlenir. Komşu sayısı en fazla olan vektörün tipi, başlangıç tipi olarak seçilir. Eğer tipleri farklı iki vektör en fazla komşu sayısına sahipse, azınlık vektörlerinin tipi başlangıç tipi olarak seçilir. Belirlenen başlangıç tipi 0 (yanlış) ise doğru vektörler yanlış vektöre ve yanlış vektörler de doğru vektöre dönüştürülür. Başlangıç tipini belirleyen vektör temel vektör olarak seçilerek şu formüle göre ilk ağırlıklar bulunur: ÖVCı + (OıXı +... + ûfcCn - CÛb = 0, m = 2, Eğer f(vt) = 1 ve v^ = 1, û> = -2, Eğer fffl = 1 ve v'c = 0, gx = 4, Eğer f(vı) = 0 ve v'c = 1, m = -4, Eğer /(v,^ = 0 ve v^ = 0, n û^Z^c -3 Burada, vc, temel vektörü; V;, temel vektöre Hamming uzaklığı T olan vektörleri; m, eşiği; Vc1 ise temel vektörün /-nci bitini göstermektedir. Temel vektör ile aynı tipteki Vi vektörleri bir kümede toplanır. ÎDc ağırlıklar hesaplandıktan sonra temel vektöre en yakm aynı tipteki bir vektör seçilerek kümeye yerleştirilir ve aşağıdaki bağıntılar gereğince ağırlıklar hesaplanır: xv ©, =(4C,-2C0) i=l...» ?min =min| /^ =max nun./ r.'=1 mm./ max *>o = 2 Eğer /mm >./max koşulu gerçekleşiyorsa, bu denenen vektör kümeye dahil edilebilir ve bulunan ağırlıklar bu kümedeki vektörler ile diğer vektörleri birbirinden kesin olarak ayırır. Bu şart gerçekleşmediği takdirde ağırlıkları değiştirerek bu şart sağlanmaya çalışılır. Bunun için tmni sağlayan küme içindeki en az T sayısına sahip vektör (vrmin) ve^ax'i sağlayan en az T sayısına sahip, küme içinde olmayan vektör (v/max) belirlenir ve aşağıdaki bağmtı gereğince ağırlıklar değiştirilir. û)/,= ö),.+2v;mm-2v}B U <="" dif="" şartı="" aranır.="" değişkeni,="" ilk="" değer="" olarak="" +00="" seçilir="" ve="" bu="" iki="" şart="" sağlandığında="" ağırlıklar="" değiştirilir="" -="" mü,="" seçilir.="" değiştirildikten="" sonra="" ^="" ma="" tekrar="" hesaplanır="" işlemler="" fmm="" style="margin: 0px; padding: 0px; outline: 0px; color: rgb(34, 34, 34); font-family: Verdana, Arial, sans-serif; font-size: 10px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">./max oluncaya veya hiçbir şart sağlanmaymcaya kadar devam ettirilir. Eğer yukarıdaki hiçbir şart sağlanmıyorsa, o zaman bu denenen vektör kümeye dahil edilemez ve hesaplanmış ağırlıklar iptal edilerek bir önceki ağırlık değerlerine dönülür. Bu koşullar uyarınca her doğru vektör kümeye yerleştirilmeye çalışılır. Eğer geriye kalan hiçbir doğru vektör kümeye yerleştirüemiyorsa, en son hesaplanan ağırlıklar, birinci nöronun ağırlıkları olarak kabul edilir ve tüm geriye kalan vektörler dönüştürülür (doğrular yanlışlara ve yanlışlar da doğrulara). Bu dönüştürmeden sonra xvi doğru vektörler tekrar kümeye yerleştirilmeye çalışılır. Bu şekilde devam edilerek tüm doğru vektörler kümeye dahil edilir. İşlem sonunda otomatik olarak gerekli nöron sayısı da belirlenmiş olmaktadır. Tüm nöronlar belirlendikten sonra indirgenmiş fonksiyon, şu bağıntılar gereğince ana fonksiyona dönüştürülür: netfn (X,a>\) = a)ixj + net^ (x1,x2,-- ?,xM,xM,-. -,x",co0) + cd0- a\ /' a>\ = û>0 co, =nûAnetf"-l(xl,x2,---,xi_l,xl+l,---,x",û)0)\-l 0)\ = (00+0),, Eğer Vjmaot = 0 ve V = 1 cOj =-max co\ = o)0 VlGl *n-\ \Xı,X2,'",Xj_l,Xj+^,"',Xn,CO(ij\ 1.f".1^l,^,,~,_15~,+1,,~",~0, PS^rF. _._=1W «.» =, Eğer Fminor = 1 ve vm' = 0, o^maxiwef,(xı,x2,-,xM,x,+1,-,x,,,<»0) +1 ; L / ?> Eğer rminor= 1 vevm =1, Cû\ = 0)0+0), Burada/11, «-girişli fonksiyonu; vm', /n'nin azınlık vektörlerinin i-nci bitini; 7mm0r = / "(Vm); Xi, f n'nin azmlık vektörlerinin değeri değişmeyen girişini göstermektedir. Fonksiyon kaç kere indirgenmişse o kadar bu bağıntılar uygulanarak ana fonksiyona dönülür. Tüm ağırlıklar bulunduktan sonra çıkış nöronunun ağırlıklarını hesaplamak için bir T vektörü tanımlanır. Bu vektörün elemanları şu şekilde belirlenir: Eğer z'-nci nöron gerçek doğru vektörlere dayanılarak oluşturulduysa T1 = 1, dönüştürülmüş doğru vektörlere (gerçekte yanlış vektörler) dayanılarak oluşturulduysa T1 = 0 olarak seçilir. xvu Bu vektör bulunduktan sonra tüm dönüştürülmüş nöronların ağırlıkları -1 ile çarpılarak esas formlarına döndürülür ve «, gizli tabaka içindeki toplam nöron sayısını göstermek şartıyla çıkış nöronunun ağırlıkları şu sistematik metod ile bulunur. Metod, en içteki fonksiyon olan ne/n' den başlamaktadır. net0 = 2hn - 1 olarak seçilerek şu bağıntılar gereğince we?n-ı bulunur: netn-ı = (~ nıra[wef " ] + l)hn_x + net", Eğer T""1 = 1 ise, net "_ı = (max|W" ] + 1 \h"_x + netn - (max[«ef " ] + lj, Eğer T""1 = 0 ise. Bu metoda, net\ bulunana kadar devam edilir. Bulunan bu ağ fonksiyonunda «i'ler i- nci nöronun çıkışım; Aflerin katsayıları, çıkış nöronunun bu gizli nöronlara ait ağırlıkları ve sondaki negatif sayı da çıkış nöronunun eşiğini göstermektedir. Çıkış nöronunun ağırlıklarının bulunması ile METL algoritması, verilen bir boole fonksiyonunu 3 tabakalı bir yapay sinir ağı ile gerçeklemiş olmaktadır. METL algoritmasının en önemli özelliği, elde edilen yapay sinir ağının, negatif ağırlıklar dönüştürülmek suretiyle CTL devreleri ile VLSI teknolojisi kullanılarak gerçeklemenin mümkün olması ve önerilen bu ağın gizli tabakadaki nöron sayısının, en fazla giriş vektörünün boyutuna eşit olmasıdır. Bu son özellik, bize «-girişli genel amaçlı CTL tabanlı bir PLA devresinin, « tane gizli nörona sahip olabileceğini göstermektedir, örneğin; 16-girişli genel amaçlı NOR-NOR PLA devresinin ilk NOR dizisinde 32768 tane hat bulunurken, aynı giriş sayısına sahip CTL-CTL PLA devresinde bu sayı sadece 16'dır. Sonuçta, tümleştirme bakımından çok büyük bir yer kazancı sağlanmaktadır. METL algoritması, bazen bu sının aşan sonuçlar üretebilmektedir. Farklı başlangıç noktaları seçilerek her zaman «-girişli bir boole fonksiyonu, gizli tabakasında maksimum « nöron bulunduran 3 tabakalı, tüm ağırlıkların ve eşiklerin tamsayı olduğu bir yapay sinir ağı ile gerçeklenebilmektedir.

This study describes a learning algorithm called modified expand and truncate learning algorithm (METL) to train multilayer binary neural networks with guaranteed convergence for any binary-to-binary mapping. The most significant contribution of this study is the development of learning algorithm for three-layer binary neural networks which guarantees the convergence, automatically determining a required number of neurons in the hidden layer. This algorithm can realize any n- dimensional binary-to-binary mapping by a binary neural network that has maximum «-neurons in the hidden layer. Furthermore, the learning speed of the METL algorithm is much fester than that of other learning algorithms in a binary field. Neurons in the binary neural network employ a hard-limiting activation function, with only integer weights and integer thresholds. Therefore, this will greatly facilitate actual hardware implementation of binary neural network using currently available digital VLSI technology. Chapter 1 gives a short history of neural networks. Chapter 2 includes mathematical background of threshold logic that is necessary for describing the learning algorithm. Chapter 3 describes METL algorithm. The most important advantages of METL are explained with examples. In the conclusion part, the advantages of METL algorithm are mentioned. In the appendices, some necessary information and the source code of computer program that is used to test METL algorithm are listed.