Üç Yüzyıl Sonra Newton'un Yöntemi Sonsuz Karmaşık Problemleri Çözebilir

Araştırmacılar sürekli olarak en iyi çözümleri aramaktadırlar. Bir havacılık merkezi için en uygun yeri belirlemek, bir yatırım portföyünde riski azaltırken getirileri maksimize etmek veya trafik lambalarını dur işaretlerinden ayırt edebilen otonom araçlar geliştirmek isteyebilirler. Matematiksel olarak, bu problemler fonksiyonların minimum değerlerini bulmaya dönüşmektedir. Ancak, tüm bu senaryolarda fonksiyonlar o kadar karmaşıktır ki, doğrudan değerlendirilmesi zordur. Bu nedenle, araştırmacılar yerine minimum değerleri yaklaşık olarak bulmak zorunda kalmaktadırlar.

Newton'un Algoritması

Bu işin en iyi yöntemlerinden birinin, Isaac Newton tarafından 300 yıldan fazla bir süre önce geliştirilen bir algoritma olduğu ortaya çıkmaktadır. Bu algoritma nispeten basittir. Görmediğiniz bir yerde en alçak noktaya doğru yolunuzu bulmaya çalışmaya benzer. İlerledikçe bilmeniz gereken tek şey, yükselip yükselmediğiniz veya eğimin artıp artmadığıdır. Bu bilgiyi kullanarak, minimum için oldukça hızlı bir tahmin oluşturabilirsiniz. Güçlü yeteneklerine rağmen; onlarca yıl sonra Newton yöntemi, lojistik, finans, bilgisayarlı görme ve hatta saf matematikte modern problemleri ele almak için temel bir araç olmaya devam etmektedir—ancak önemli bir dezavantajı da vardır. Tüm fonksiyonlarla iyi çalışmaz. Bu nedenle, matematikçiler bu tekniği incelemeye devam ettiler, kapsamını genişletmek için etkinliğini azaltmadan farklı yollar araştırıyorlar. Geçen yaz, Princeton Üniversitesi'nden Amir Ali Ahmadi ve eski öğrencileri Abrar Chaudhry ve Jeffrey Zhang, Newton yöntemini şimdiye kadarki en geniş fonksiyon sınıfında verimli çalışacak şekilde genişletti. Ahmadi, "Newton yöntemi optimizasyonda 1000 farklı uygulamaya sahiptir. Algoritmamız muhtemelen onun yerini alacak," diye belirtti.

Zamane Dayanıklı Bir Teknik

1680'lerde Newton, son derece karmaşık bir fonksiyonla uğraşırken bile, onun en derin vadisini bulmanıza yardımcı olacak en az iki bilgi parçasına erişiminiz olduğunu fark etti. İlk olarak, fonksiyonun birinci türevini, yani eğimini hesaplayabilirsiniz: belirli bir noktadaki gradyan. İkinci olarak, eğimin kendisinin değişim hızını (fonksiyonun ikinci türevini) hesaplayabilirsiniz. Karmaşık bir fonksiyonun minimumunu bulmaya çalıştığınızı varsayalım. İlk olarak, gerçek minimuma yakın olduğunu düşündüğünüz fonksiyon üzerinde bir nokta seçin. Bu noktada fonksiyonun birinci ve ikinci türevlerini hesaplayın. Bu türevler, özel bir ikinci derece denklemi oluşturmak için kullanılabilir—eğer fonksiyonunuz iki boyutluysa bir parabol, daha yüksek boyutluysa bir çanak şekli olan paraboloid adını alan bir şekil. Taylor yaklaşımı adı verilen bu ikinci derece denklem, seçilen noktadaki fonksiyonunuza yakından benzer. Şimdi, orijinal yerine ikinci derece denklemin minimumunu hesaplayın—bu bilinen bir formül kullanılarak kolayca yapılabilir. (Bu, ikinci derece denklemlerin basit olmasından dolayıdır; denklemler karmaşıklaştıkça minimumları hesaplamak pahalı hale gelir.) Sonuç olarak bir nokta elde edersiniz. Ardından, bu noktanın koordinatlarını orijinal fonksiyonunuza yeniden girin ve muhtemelen gerçek minimumuna daha yakın bir yeni noktaya ulaşacaksınız. Tüm süreci yeniden başlatın. Newton, bu süreci tekrarlamaya devam ederseniz, sonunda daha karmaşık orijinal fonksiyonun minimumuna ulaşacağınızı kanıtladı. Bu yöntemin her zaman başarılı olmadığı, özellikle de gerçek minimumdan çok uzaktaki bir noktadan başlanırsa çalışmadığı ortaya çıkıyor. Ama genellikle işe yarar. Bazı arzu edilen özellikleri vardır. Modern makine öğrenimi modellerinde kullanılan algoritma olan gradyan inişi gibi diğer yinelenen yöntemler, doğru minimuma lineer bir hızda yakınsar. Newton'un yöntemi buna çok daha hızlı bir şekilde, "ikinci derece" hızında yakınsar. Diğer bir deyişle, gradyan inişine göre daha az yineleme ile minimum değeri bulabilir. (Newton yönteminin her yinelemesi, gradyan inişine göre daha hesaplama açısından pahalıdır, bu yüzden araştırmacılar bu yöntemleri belirli uygulamalarda, örneğin sinir ağlarını eğitmek için tercih etmektedirler. Ancak Newton'un yöntemi hala oldukça etkilidir ve çeşitli bağlamlarda kullanışlıdır.) Newton, her noktada sadece birinci ve ikinci türevleri almanın yerine üçüncü ve dördüncü türevleri de alsaydı, gerçek minimuma daha hızlı ulaşmak için yöntemi daha karmaşık Taylor yaklaşımları, ikinci dereceden daha yüksek derecelerle elde edebilirdi. Ancak stratejisinin çekirdeği, karmaşık bir fonksiyonu daha basit birine dönüştürmekti. Bu daha karmaşık Taylor denklemleri, Newton'un matematiksel kapasitesinin ötesindeydi.

Salınım İçin Bir Alan Bulmak

Bir denklemi minimize etmeyi kolaylaştıran nedir? İki özellik: birincisi, denklemin çanak şeklinde veya "konveks" olmasıdır. Sayısız vadi içermek yerine, sadece bir tanesine sahiptir—bu da minimize etmeye çalışırken herhangi bir rastgele vadiyi en alçak olanla karıştırma konusunda endişelenmenize gerek kalmadığı anlamına gelir. İkinci özellik, denklemi kareler toplamı olarak yazabilmektir. Ancak Ahmadi, Chaudhry ve Zhang, Taylor yaklaşımını yeterince ayarlamak için yarı tanımlı programlama adlı bir teknik kullanarak onu hem kareler toplamı hem de konveks hale getirmenin, ne de kadar orijinal fonksiyonundan uzaklaşmadan yararlanmalarını sağladılar. Taylor genişlemesine bir düzeltme faktörü ekleyerek, istenen özelliklere sahip bir denklem haline getirmişlerdir. Ahmadi, "Taylor genişlemesini minimize etmeyi kolaylaştıracak şekilde hafifçe ayarlayabiliriz. Küçük bir ayarlama yapılmış bir Taylor genişlemesi düşünün," dedi. Sonra o ve meslektaşları, çok sayıda türev içeren bu modifiye edilmiş Taylor genişlemesini kullanarak, algoritmalarının hâlâ orijinal fonksiyonun doğru minimumuna yakınsadığını gösterdiler. Ayrıca, yakınsama hızı kullanılan türev sayısıyla eşleşiyor: tıpkı Newton'un iki türev kullanarak doğru minimuma ikinci dereceden bir hızda yaklaşabilmesi gibi, araştırmacılar üç türev kullanarak onu üçüncü dereceden bir hızda yaklaşabildiler ve bu şekilde devam ettirebildiler. Newton'un yönteminin orijinal versiyonunda olduğu gibi, bu yeni algoritmanın her yinelemesi de gradyan inişi gibi yöntemlerden daha hesaplama açısından pahalıdır. Bu nedenle, bu yeni çalışma şimdilik otonom araçların çalışma şeklini, makine öğrenme algoritmalarını veya hava trafik kontrol sistemlerini değiştirmeyecektir. Bu senaryolar için hala gradyan inişi en iyi seçim olmaya devam etmektedir.