Paralel hesaplama ile ilgili iki yararlı kaynak:
Temmuz 17, 2008
Yapay Sinir Ağları
Aşağıdaki yazı http://www.yapay-zeka.org/ sitesinden alınmıştır.
Bu metnin dışında konuyla ilgili iki yararlı kaynak:
http://turhalmyo.gop.edu.tr/ogr/ebu/programlama/ysa.pdf
http://herseyekitap.googlepages.com/YapaySinirAglari.doc
Yapay Sinir Ağları (Artificial Neural Networks)
Yapay sinir ağları, insan beyninin özelliklerinden olan öğrenme yolu ile yeni bilgiler türetebilme, yeni bilgiler oluşturabilme ve keşfedebilme gibi yetenekleri herhangi bir yardım almadan otomatik olarak gerçekleştirmek amacı ile geliştirilen bilgisayar sistemleridir. Bu yetenekleri geleneksel programlama yöntemleri ile gerçekleştirmek oldukça zordur veya mümkün değildir. O nedenle, yapay sinir ağları bilim dalının, programlanması çok zor veya mümkün olmayan olaylar için geliştirilmiş adaptif bilgi işleme ile ilgilenen bir bilgisayar bilim dalı olduğu söylenebilir.
Yapay sinir ağları, olayların örneklerine bakmakta, onlardan ilgili olay hakkında genellemeler yapmakta, bilgiler toplamakta ve daha sonra hiç görmediği örnekler ile karışılışınca öğrendiği bilgileri kullanarak o örnekler hakkında karar verebilmektedir. 1990’lı yıllardan beri bilgisayarların öğrenmesini sağlayan Yapay Sinir Ağları teknolojisinde oldukça hızlı bir gelişme görüldü. Yapay sinir ağları, insan beyninin özelliklerinden olan öğrenme yolu ile yeni bilgiler türetebilme, yeni bilgiler oluşturabilme ve keşfedebilme gibi yetenekleri herhangi bir yardım almadan otomatik olarak gerçekleştirmek amacı ile geliştirilen bilgisayar sistemleri olduklarından hem yeni gelişmelere neden oldular hem de nasıl çalıştığı bilinmeyen insan beyni hakkında yapılan araştırmalara da önemli katkılar sağladılar ve sağlamaktadırlar.
Başka bir bakış açısıyla Yapay Sinir Ağları teknolojisi insanlığın doğayı araştırma ve taklit etme çabalarının en son ürünlerinden bir tanesi olarak da yorumlanabilir.
Yapay Sinir Ağları, basit biyolojik sinir sisteminin çalışma şeklini simüle etmek için tasarlanan programlardır. Simüle edilen sinir hücreleri (nöronlar) içerirler ve bu nöronlar çeşitli şekillerde birbirlerine bağlanarak ağı oluştururlar. Bu ağlar öğrenme, hafızaya alma ve veriler arasındaki ilişkiyi ortaya çıkarma kapasitesine sahiptirler. Diğer bir ifadeyle, YSA’lar, normalde bir insanın düşünme ve gözlemlemeye yönelik doğal yeteneklerini gerektiren problemlere çözüm üretmektedir. Bir insanın, düşünme ve gözlemleme yeteneklerini gerektiren problemlere yönelik çözümler üretebilmesinin temel sebebi ise insan beyninin ve dolayısıyla insanın sahip olduğu yaşayarak veya deneyerek öğrenme yeteneğidir.
Biyolojik sistemlerde öğrenme, nöronlar arasındaki sinaptik (synaptic) bağlantıların ayarlanması ile olur. Yani, insanlar doğumlarından itibaren bir yaşayarak öğrenme süreci içerisine girerler. Bu süreç içinde beyin sürekli bir gelişme göstermektedir. Yaşayıp tecrübe ettikçe sinaptik bağlantılar ayarlanır ve hatta yeni bağlantılar oluşur. Bu sayede öğrenme gerçekleşir. Bu durum YSA için de geçerlidir. Öğrenme, eğitme yoluyla örnekler kullanarak olur; başka bir deyişle, gerçekleşme girdi/çıktı verilerinin işlenmesiyle, yani eğitme algoritmasının bu verileri kullanarak bağlantı ağırlıklarını (weights of the synapses) bir yakınsama sağlanana kadar, tekrar tekrar ayarlamasıyla olur.
YSA’lar, ağırlıklandırılmış şekilde birbirlerine bağlanmış bir çok işlem elemanlarından (nöronlar) oluşan matematiksel sistemlerdir. Bir işlem elemanı, aslında sık sık transfer fonksiyonu olarak anılan bir denklemdir. Bu işlem elemanı, diğer nöronlardan sinyalleri alır; bunları birleştirir, dönüştürür ve sayısal bir sonuç ortaya çıkartır. Genelde, işlem elemanları kabaca gerçek nöronlara karşılık gelirler ve bir ağ içinde birbirlerine bağlanırlar; bu yapı da sinir ağlarını oluşturmaktadır.
Sinirsel (neural) hesaplamanın merkezinde dağıtılmış, adaptif ve doğrusal olmayan işlem kavramları vardır. YSA’lar, geleneksel işlemcilerden farklı şekilde işlem yapmaktadırlar. Geleneksel işlemcilerde, tek bir merkezi işlem elemanı her hareketi sırasıyla gerçekleştirir. YSA’lar ise herbiri büyük bir problemin bir parçası ile ilgilenen, çok sayıda basit işlem elemanlarından oluşmaktadır. En basit şekilde, bir işlem elemanı, bir girdiyi bir ağırlık kümesi ile ağırlıklandırır, doğrusal olmayan bir şekilde dönüşümünü sağlar ve bir çıktı değeri oluşturur. İlk bakışta, işlem elemanlarının çalışma şekli yanıltıcı şekilde basittir. Sinirsel hesaplamanın gücü, toplam işlem yükünü paylaşan işlem elemanlarının birbirleri arasındaki yoğun bağlantı yapısından gelmektedir.
Çoğu YSA’da, benzer karakteristiğe sahip nöronlar tabakalar halinde yapılandırılırlar ve transfer fonksiyonları eş zamanlı olarak çalıştırılırlar. Hemen hemen tüm ağlar, veri alan nöronlara ve çıktı üreten nöronlara sahiptirler.
YSA’nın ana öğesi olan matematiksel fonksiyon, ağın mimarisi tarafından şekillendirilir. Daha açık bir şekilde ifade etmek gerekirse, fonksiyonun temel yapısını ağırlıkların büyüklüğü ve işlem elemanlarının işlem şekli belirler. YSA’ların davranışları, yani girdi veriyi çıktı veriye nasıl ilişkilendirdikleri, ilk olarak nöronların transfer fonksiyonlarından, nasıl birbirlerine bağlandıklarından ve bu bağlantıların ağırlıklarından etkilenir.
Bu sayfalarda hem yapay sinir ağlarının felsefesi anlatılmış hem de bu teknolojinin teknik ayrıntılarına yer verilmeye çalışılmıştır.
Yapay Sinir Ağları İle İlgili Kavramlar ve Algoritmalar
and MadalineYapay Sinir Ağlarının Türleri
Kaynaklar
AŞAĞISI DÜZENLENECEK: http://yapay-sinir-aglari.uzerine.com/
1. YAPAY SİNİR AĞLARINA GENEL BİR BAKIŞ 1.1 Genel Tanım
Yapay sinir ağları (YSA), insan beyninin özelliklerinden olan öğrenme yolu ile yeni bilgiler türetebilme, yeni bilgiler oluşturabilme ve keşfedebilme gibi yetenekleri, herhangi bir yardım almadan otomatik olarak gerçekleştirebilmek amacı ile geliştirilen bilgisayar sistemleridir. [1]
Yapay sinir ağları; insan beyninden esinlenerek, öğrenme sürecinin matematiksel olarak modellenmesi uğraşı sonucu ortaya çıkmıştır. Bu nedenledir ki, bu konu üzerindeki çalışmalar ilk olarak beyni oluşturan biyolojik üniteler olan nöronların modellenmesi ve bilgisayar sistemlerinde uygulanması ile başlamış, daha sonraları bilgisayar sistemlerinin gelişimine de paralel olarak bir çok alanda kullanılır hale gelmiştir.
İnsan beyninin çalışma prensibini taklit ederek çalışan bu sistemler, her ne kadar bilgisayar teknolojisi hızlı bir gelişim göstermiş, işlem hızları nano saniyeler mertebesine inmiş olsa da, bırakalım insan beynini, ilkel bir canlı beyninin fonksiyonları dahi baz alındığında, böyle bir organizmanın yanında çok ilkel kalmaktadır. Nano saniyeler bazındaki işlem hızları ile YSA’lar, mili saniyeler mertebesindeki işlen hızları ile işlem yapan insan beyninin işlevselliğinin henüz çok uzağındadır.
Burada kısa bir hatırlatma yapmak gerekirse; insan beyninde yaklaşık 10¹¹ sinir hücresinin varlığından bahsedilmekle birlikte, bu sayının bilgisayar ortamında modellenmesi şu an için mümkün görünmemektedir. Fakat karar hızı açısından insan beyni ile henüz yarışamasalar bile, YSA’lar yapısallıkları ve hassas eşleştirmelerin başarı ile gerçekleştirebilmeleri ile gün geçtikçe daha fazla uygulama alanı bulmaktadır. 1.2 YSA’ların Genel Özellikleri
YSA’lar, uygulanan ağ modeline göre değişik karakteristik özellikler göstermelerine karşın temel birkaç ortak özelliğe sahiptirler.
Birinci özellik; YSA’larda sistemin paralelliği ve toplamsal işlevin yapısal olarak dağılmışlığıdır.[2] YSA lar bir çok nörondan meydana gelir ve bu nöronlar eş zamanlı olarak çalışarak karmaşık işlevleri yerine getirir. Diğer bir değişle karmaşık işlevler bir çok nöronun eş zamanlı çalışması ile meydana getirilir. Süreç içerisinde bu nöronlardan her hangi biri işlevini yitirse dahi sistem güven sınırları içerisinde çalışmasına devam edebilir.
İkinci özellik ise genelleme yeteneği, diğer bir değişle ağ yapısının, eğitim esnasında kullanılan nümerik bilgilerden eşleştirmeyi betimleyen kaba özellikleri çıkarsaması ve böylelikle eğitim sırasında kullanılmayan girdiler için de, anlamlı yanıtlar üretebilmesidir.[3]
Üçüncü olarak; ağ fonksiyonları non-lineer olabilmektedir. Yapı üzerinde dağılmış belli tipteki non-lineer alt birimler özellikle, istenen eşleştirmenin denetim ya da tanımlama işlemlerinde olduğu gibi non-lineer olması durumunda işlevin doğru biçinde yerine getirilebilmesini matematiksel olarak olası kılarlar.
Dördüncü özellik ise; sayısal ortamda tasarlanan YSA’ların, donanımsal gerçekleştirilebilirlikleridir. Bu özellik beklide YSA’ların günlük hayatta daha da fazla yaşamımızın içine gireceğinin (girebileceğinin) göstergesidir. 1.3 YSA’ların Avantaj ve Dezavantajları
YSA’lar makina öğrenmesi gerçekleştirebilirler. Yapay sinir ağlarının temel işlevi zaten bilgisayarın öğrenmesini sağlamaktır. Olayları öğrenerek benzer olaylar karşısında mantıklı kararlar verebilirler.
Bilgi işleme yöntemleri geleneksel programlamadan farklıdır. Bu nedenle geleneksel programlamanın getirdiği bir çok olumsuzluk ortadan kaldırılabilir
Bilgiler ağın tamamında saklanır. Geleneksel programlamada olduğu gibi bilgiler veri tabanları yada dosyalarda belli bir düzende tutulmaz, ağın tamamına yayılarak değerler ile ölçülen ağ bağlantılarında saklanmaktadır. Nöronlardan bazılarının işlevini yitirmesi, anlamlı bilginin kaybolmasına neden olmaz.
Örnekleri kullanarak öğrenirler. YSA’nın öğrenebilmesi için örneklerin belirlenmesi, bu örneklerin ağa gösterilerek istenen çıktılara göre ağın eğitilmesi gerekmektedir. Ağın başarısı, seçilen örnekler ile doğru orantılıdır, ağa olay bütün yönleri ile gösterilemezse ağ yanlış çıktılar üretebilir.
Daha önce görülmemiş örnekler hakkında bilgi üretebilirler. YSA’lar eğitimleri sırasında kendilerine verilen örneklerden genellemeler çıkarırlar ve bu genellemeler ile yeni örnekler hakkında bilgi üretebilirler.
Algılamaya yönelik olaylarda kullanılabilirler. YSA’ların en başarılı oldukları alanlar, algılamaya yönelik uygulama alanlarıdır. Bu alanlarda başarıları kanıtlanmıştır.
Örüntü (pattern) ilişkilendirme ve sınıflandırma yapabilirler. YSA’lar kendilerine örnekler halinde verilen örüntüleri kendisi veya diğerleri ile ilişkilendirebilir. Ayrıca kendisine verilen örneklerin kümelenmesi ile, bir sonraki verinin hangi kümeye dahil olacağının karar verilmesi konusunda kullanılabilirler.
Örüntü tamamlama yapabilirler. Ağa eksik bilgileri içeren örüntüler verildiğinde eksik bilgilerin tamamlanması konusunda başarılıdırlar.
Kendi kendine öğrenebilme ve organize etme yetenekleri vardır. YSA’lar online olarak öğrenebilirler ve kendi kendilerini eğitebilirler.
Eksik bilgi ile çalışabilmektedirler. Geleneksel sistemlerin aksine YSA’lar eğitildikten sonra veriler eksik bilgi içerse dahi, çıktı üretebilirler. Bu durum bir performans kaybı yaratmaz, performans kaybı eksik bilginin önemine bağlıdır. Burada bilgilerin önem dereceleri eğitim sırasında öğrenilir.
Hata töleransına sahiptirler. YSA’ların eksik bilgilerle çalışabilmeleri ve bazı hücreleri bozulsa dahi çalışabilmeleri, onları hatalara karşı töleranslı yapar.
Dereceli bozulma (Graceful degradation) gösterirler. Bir ağ, zaman içerisinde yavaş ve göreceli bir bozulmaya uğrar. Ağlar problemin ortaya çıktığı anda hemen bozulmazlar.
Dağıtık belleğe sahiptirler. YSA’larda bilgi ağa dağılmış bir şekilde tutulur. Hücrelerin bağlantı ve ağırlık dereceleri, ağın bilgisini gösterir. Bu nedenle tek bir bağlantının kendi başına anlamı yoktur.
Burada çok temel bazı avantajlardan bahsedilmekle beraber, YSA’ların daha pek çok avantajı vardır.
YSA’ların, pek çok avantajın yanında bazı dezavantajları da vardır. Belli başlı dezavantajları;
Donanım bağımlıdır. YSA’ların en önemli sorunu donanım bağımlı olmalarıdır. YSA’ların en önemli özellikleri ve var oluş nedenlerinden birisi olan paralel işlem yapabilme yeteneği, paralel çalışan işlemciler ile performans gösterir.
Uygun ağ yapısının belirlenmesinde belli bir kural yoktur. YSA’larda probleme uygun ağ yapısının belirlenmesi için geliştirilmiş bir kural yoktur. Uygun ağ yapısı deneyim ve deneme yanılma yolu ile belirlenmektedir.
Ağın parametre değerlerinin belirlenmesinde belli bir kural yoktur. YSA’larda öğrenme katsayısı, hücre sayısı, katman sayısı gibi parametrelerin belirlenmesinde belirli bir kural yoktur. Bu değerlerin belirlenmesi için belirli bir standart olmamakla birlikte her problem için farklı bir yaklaşım söz konusu olabilmektedir.
Öğrenilecek problemin ağa gösterimi önemli bir problemdir. YSA’lar nümerik bilgiler ile çalışabilmektedirler. Problemler YSA’lara tanıtılmadan önce nümerik değerlere çevrilmek zorundadırlar. Burada belirlenecek gösterim mekanizması ağın performansını doğrudan etkileyecektir. Bu da kullanıcının yeteneğine bağlıdır.
Ağın eğitiminin ne zaman bitirilmesi gerektiğine ilişkin belli bir yöntem yoktur. Ağın örnekler üzerindeki hatasının belirli bir değerin altına indirilmesi eğitimin tamamlandığı anlamına gelmektedir. Burada optimum neticeler veren bir mekanizma henüz yoktur ve YSA ile ilgili araştırmaların önemli bir kolunu oluşturmaktadır.
Ağın davranışlarının açıklanamamaktadır. Bu sorun YSA’ların en önemli sorunudur. YSA bir probleme çözüm ürettiği zaman, bunun neden ve nasıl olduğuna ilişkin bir ipucu vermez. Bu durum ağa olan güveni azaltıcı bir unsurdur.
Geleneksel Algoritmalar
Yapay Sinir Ağları
Tablo 1.1 Geleneksel algoritmalar ile YSA’lar 1.4 YSA’ların Kullanıldığı Alanlar
Yapay sinir ağları başlıca; Sınıflandırma, Modelleme ve Tahmin uygulamaları olmak üzere, pek çok alanda kullanılmaktadır. Başarılı uygulamalar incelendiğinde, YSA’ların çok boyutlu, gürültülü, karmaşık, kesin olmayan, eksik, kusurlu, hata olasılığı yüksek sensör verilerinin olması ve problemi çözmek için matematiksel modelin ve algoritmaların bulunmadığı, sadece örneklerin var olduğu durumlarda yaygın olarak kullanıldıkları görülmektedir. Bu amaçla geliştirilmiş ağlar genellikle şu fonksiyonları gerçekleştirmektedirler; [4]
YSA’lar pek çok sektörde değişik uygulama alanları bulmuştur. Bunlardan bazıları;
Uzay: uçuş simülasyonları, otomatik pilot uygulamaları, komponentlerin hata denetimleri vs.
Otomotiv: otomatik yol izleme, rehber, garanti aktivite analizi, yol koşullarına göre sürüş analizi vs.
Bankacılık: kredi uygulamaları geliştirilmesi, müşteri analizi ve kredi müraacat değerlendirilmesi, bütçe yatırım tahminleri vs.
Savunma: silah yönlendirme, hedef seçme, radar, sensör sonar sistemleri, sinyal işleme, görüntü işleme vs.
Elektronik: kod sırası öngörüsü, çip bozulma analizi, non-lineer modelleme vs.
Eğlence: animasyonlar, özel efektler, pazarlama öngörüsü vs.
Finans: kıymet biçme, pazar performans analizi, bütçe kestirimi, hedef belirleme vs.
Sigortacılık: ürün optimizasyonu, uygulama politikası geliştirme vs.
Üretim: üretim işlem kontrolü, ürün dizaynı, makina yıpranmalarının tespiti, dayanıklılık analizi, kalite kontrolü, iş çizelgeleri hazırlanması vs.
Sağlık: göğüs kanseri erken teşhis ve tedavisi, EEG, ECG, MR, kalite artırımı, ilaç etkileri analizi, kan analizi sınıflandırma, kalp krizi erken teşhis ve tedavisi vs.
Petro kimya: arama, verim analizi vs.
Robotik: yörünge kontrol, forklift robotları, görsel sistemler, uzaktan kumandalı sistemler, optimum rota belirleme vs.
Dil: sözcük tanıma, yazı ve konuşma çevrimi, dil tercüme vs.
Telekomünikasyon: görüntü ve data karşılaştırma, filtreleme, eko ve gürültü sönümlendirilmesi, ses ve görüntü işleme, trafik yoğunluğunun kontrolü ve anahtarlama vs.
Güvenlik: parmak izi tanıma, kredi kartı hileleri saptama, retina tarama, yüz eşleştirme vs.
Bu örnekler çoğaltılabilir. Görüldüğü gibi YSA’lar günlük hayatımızda farkında olmadığımız pek çok alanda kullanılmaktadır. Gün geçtikçe uygulama alanları genişlemekte ve gelişmektedir. 1.5 YSA’ların Tarihçesi
YSA’lar ile ilgili çalışmalar 20, yy’ın ilk yarısında başlamış ve günümüze kadar büyük bir hızla devam etmiştir. Bu çalışmaları 1970 öncesi ve sonrası diye iki kısma ayırmak mümkündür. Zira 1970 yılları YSA için bir dönüm noktasını teşkil etmiş daha önce aşılması imkânsız görünen pek çok problem bu dönemlerde aşılmıştır.
İlk yapay sinir ağı modeli 1943 yılında, bir sinir hekimi olan Warren McCulloch ile bir matematikçi olan Walter Pitts tarafından gerçekleştirilmiştir. McCulloch ve Pitts, insan beyninin hesaplama yeteneğinden esinlenerek, elektrik devreleriyle basit bir sinir ağı modellemişlerdir.
1948 yılında “Wiener “Cybernetics” isimi kitabında, sinirlerin çalışması ve davranış özelliklerine değinmiş, 1949 yılında ise Hebb “Organization of Behavior” adlı eserinde öğrenme ile ilgili temel teoriyi ele almıştır.
Hebb kitabında öğrenebilen ve uyum sağlayabilen sinir ağları modeli için temel oluşturacak “Hebb kuralı”nı ortaya koymuştur. Hebb kuralı; sinir ağının bağlantı sayısı değiştirilirse, öğrenebileceğini ön görmekteydi.
1957 yılında Frank Rosenblatt’ın Perceptron’u geliştirmesinden sonra, YSA’lar ile ilgili çalışmalar hız kazanmıştır. Perceptron; beyin işlevlerini modelleyebilmek amacıyla yapılan çalışmalar neticesinde ortaya çıkan tek katmanlı eğitilebilen ve tek çıkışa sahip bir ağ modelidir. [5]
1959 yılında Bernand Widrow ve Marcian Hoff (Stanford Üniversitesi) ADALINE (Adaptive Linear Neuron) modelini geliştirmişler ve bu model YSA’ların mühendislik uygulamaları için başlangıç kabul edilmiştir. Bu model Rosenblatt’ın Perceptron’una benzemekle birlikte, öğrenme algoritması daha gelişmiştir. Bu model uzun mesafelerdeki telefon hatlarındaki yankıları ve gürültüleri yok eden bir adaptif filtre olarak kullanılmış, ve gerçek dünya problemlerine uygulanan ilk YSA olma özelliğini kazanmıştır. Bu yöntem günümüzde de aynı amaçla kullanılmaktadır.
1960 ların sonlarına doğru YSA çalışmaları durma noktasına gelmiştir. Buna en önemli etki; Minsky ve Pappert tarafından yazılan Perceptrons adlı kitaptır. Burada YSA’ların doğrusal olmayan problemleri çözemediği meshur XOR problemi ile ispatlanmış, ve YSA çalışmaları bıçak gibi kesilmiştir.
Tüm bunlara rağmen Anderson, Amari, Cooper, Fukushima, Grossberg, Kohonen, Hopfield gibi bilim adamları çalışmalarını sürdürmüşler, 1972 de Kohonen ve Anderson Associative memory konusunda benzer çalışmalar yayınlamışlardır. Kohonen daha sonra 1982 yılında Kendi kendine Öğrenme Nitelik Haritaları (Self Organizing Feature Maps SOM) konusundaki çalışmasını yayınlamıştır. 1960′ların sonlarına doğru Grosberg Carpenter ile birlikte Adaptif Rezonans Teorisini (ART) geliştirmiştir.
1970′lerin sonlarına doğru Fukushima, NEOCOGNITRON modelini tanıtmıştır. Bu model şekil ve örüntü tanıma amaçlı geliştirilmiştir.
1982 1984 yıllarında Hopfield tarafından yayınlanan çalışmalar ile YSA’ların genelleştirilebileceği ve çözümü zor problemlere çözüm üretebileceğini göstermiştir. Geleneksel gezgin satıcı problemini çözmüştür. Bu çalışmaların neticesi Hinton ve arkadaşları’nın geliştirdiği Boltzman Makinası’nın doğmasına yol açmıştır.
1988 yılında, Broomhead ve Lowe radyal tabanlı fonksiyonlar modelini (Radial Basis Functions RBF) geliştirmişler ve özellikle filtreleme konusunda başarılı sonuçlar elde etmişlerdir. Daha sonra Spect, bu ağların daha gelişmiş şekli olan Probabilistik ağlar (PNN) ve Genel Regresyon Ağlarını (GRNN) geliştirmiştir. [6]
Bu tarihten günümüze kadar sayısız çalışma ve uygulama geliştirilmiştir.
[1] Öztemel E., Yapay Sinir Ağları, sf 29, Papatya Yayıncılık, İstanbul, 2003
[2] Haykin S., Neural Networks, sf 41, Macmillan Collage Printing Company, New Jersey 1994
[3] Efe M. Ö., Kaynak O. Yapay Sinir Ağları ve Uygulamaları, sf 1, Boğaziçi Üniversitesi, İstanbul 2004
[4] Öztemel E., Yapay Sinir Ağları, sf 36, Papatya Yayıncılık, İstanbul, 2003
[5] Elmas Ç., Yapay Sinir Ağları Kuram, Mimari, Eğitim, Uygulama, sf 27-28, Seçkin Yayıncılık, Ankara 2003
[6] Öztemel E., Yapay Sinir Ağları, sf 40, Papatya Yayıncılık, İstanbul, 2003
[7] Age. Sf 38, 39, 41
Yazan Ergin Altıntaş
Kaynak:http://www.yapay-zeka.org/
Karmaşıklık-NP
P harfi “polynomial”, NP harfleri ise “non-deterministic polynomial” ifadelerini temsil eder, türkçe karşılıkları “polinom” ve “belirleyici olmayan polinom“dur. “P eşittir NP?” ise Hesaplama Teorisi‘nin en temel ve meşhur problemidir.
Polinomsal zamanda çözülen problemler
Hesaplama teorisinde, bazı tip problemlerin çözümü için en etkili algoritmaların çalışma süresinin girilen verinin büyüklüğüne bir polinom cinsinden bağlı olduğu bilinmektedir (buna polinomsal zamanda çalışan algoritma adı verilir), bu tür problemler P kategorisindeki problemlerdir. Mesela verilen 
basamaklı bir sayının asal olup olmadığını kontrol etmek için çalışma süresi 
mertebesinde bir polinomla hesaplanabilen bir algoritma vardır. Dolayısıyla verilen bir sayının asal olup olmadığının araştırılması P kategorisinde bir problemdir.
Polinomsal zamanda çözülemeyen problemler
Buna karşılık bir diğer grup problem vardır ki bunlar için sorulan soruya girilen verinin büyüklüğüne polinom mertebesinde bağımlı bir sürede cevap verecek bir algoritma bilinmemektedir. Fakat bu tür bazı problemler için eğer bir şekilde cevabı tahmin edebiliyorsak, tahminimizin doğruluğunu sınamak için veri büyüklüğüne polinom mertebesinde bağımlı sürelerde çalışacak algoritmalar vardır. Bu tür problemler, yani bir tahminin doğruluğunun kontrolü için çalışma süresi verinin büyüklüğüne polinom cinsinden bağımlı bir algoritma olan problemler de NP kategorisini oluştururlar. Örnek olarak verilen basamaklı bir sayının asal çarpanlarının neler olduğu sorusunu düşünebiliriz. Bu sorunun cevabı için bilinen en iyi algoritmanın çalışma süresi sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden (
misali) bağımlıdır (buna üstel zamanda çalışan algoritma denir), fakat bu problem için eğer bir şekilde cevabı tahmin edebiliyorsak tahminimizin doğruluğunu sınamak için sayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur. Dolayısıyla verilen bir n basamaklı sayının asal çarpanlarının neler olduğu sorusu NP kategorisindedir.
P ve NP arasındaki bağ
Bu iki kategoriden NP’nin P’yi içerdiğini görmek kolaydır. Eğer bir sorunun cevabını verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla bulabiliyorsak, bu soruya cevap olarak üretilmiş bir tahminin doğruluğunu da verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla kontrol edebiliriz. Bunun için verilen sorunun cevabını verecek algoritmayı çalıştırıp, onun verdiği cevabı kendi tahminimizle karşılaştırmak yeterlidir. “P=NP?” problemi bunun tersinin de doğru olup olmadığını sorar. Yani NP kategorisinde olup da P kategorisinde olmayan problemler var mıdır? Veya diğer bir dille asal çarpanların bulunması için polinom mertebesinde bir sürede çalışacak bir algoritma gerçekten yok mu yoksa var da biz mi bulamıyoruz? Bu alanın uzmanlarının çoğunun görüşü bu tür algoritmaların gerçekten de var olmadıkları için bulunamadığı (yani P nin NP’ye eşit olmadığı) şeklinde ancak bu soruya kesin bir cevap verilebilmesi şimdilik çok zor gözüküyor.
Kaynak:Wikipedia
