Doğrusal regresyon ve iyileşme yöntemleri

Kaynak: xkcd

Doğrusal regresyon, veri analizi ile ilgili birçok alan için temel algoritmalardan biridir. Bunun nedeni açıktır. Bu, yüzlerce olmasa da onlarca yıldır yaygın kullanımına katkıda bulunan çok basit ve anlaşılır bir algoritmadır. Buradaki fikir, bir değişkenin bir dizi diğer değişkene doğrusal bağımlılığını varsaymamız ve sonra bu bağımlılığı yeniden sağlamaya çalışmamızdır.

Ancak bu makale, pratik sorunları çözmek için doğrusal regresyonun kullanılmasıyla ilgili değildir. Burada, bir makine öğrenimi modülü yazarken karşılaştığımız, kurtarılması için dağıtılmış algoritmaların uygulanmasının ilginç özelliklerini ele alacağız. apache tutuşturmak. Biraz temel matematik, makine öğrenimi ve dağıtılmış bilgi işlem, verileriniz binlerce düğüme dağıtılmış olsa bile doğrusal regresyonun nasıl gerçekleştirileceğini anlamanıza yardımcı olabilir.

Ne bahsediyoruz?

Doğrusal bağımlılığı yeniden sağlama göreviyle karşı karşıyayız. Giriş verileri olarak, her biri bağımlı değişkenin belirli bir değeriyle ilişkili olan, sözde bağımsız değişkenlerden oluşan bir dizi vektör verilir. Bu veriler iki matris biçiminde temsil edilebilir:

Şimdi, bağımlılık varsayıldığından ve üstelik doğrusal olduğundan, varsayımımızı matrislerin çarpımı biçiminde yazacağız (kaydı basitleştirmek için, burada ve aşağıda denklemin serbest teriminin arkasında gizli olduğu varsayılmaktadır). ve matrisin son sütunu birimleri içerir):

Bir doğrusal denklem sistemine çok benziyor, değil mi? Öyle görünüyor, ancak büyük olasılıkla böyle bir denklem sisteminin çözümü olmayacak. Bunun nedeni neredeyse her gerçek veride bulunan gürültüdür. Diğer bir neden, orijinal değişkenlere doğrusal olmayan şekilde bağlı olan ek değişkenlerin eklenmesiyle çözülebilecek doğrusal bağımlılığın olmaması olabilir. Aşağıdaki örneği düşünün:

Kaynak: Vikipedi

Bu, bir değişkenin (eksen boyunca) ilişkisini gösteren basit bir doğrusal regresyon örneğidir. ) başka bir değişkenden (eksen boyunca) ). Bu örneğe karşılık gelen doğrusal denklem sisteminin bir çözüme sahip olması için tüm noktaların tam olarak aynı düz çizgi üzerinde bulunması gerekir. Ama bu doğru değil. Ancak gürültü nedeniyle (veya doğrusal ilişki varsayımının hatalı olması nedeniyle) tam olarak aynı düz çizgi üzerinde uzanmıyorlar. Bu nedenle, gerçek verilerden doğrusal bir ilişki elde etmek için genellikle bir varsayım daha yapmak gerekir: giriş verileri gürültü içerir ve bu gürültünün normal dağılım. Diğer gürültü dağılımı türleri hakkında varsayımlarda bulunabilirsiniz, ancak vakaların büyük çoğunluğunda dikkate alınan normal dağılımdır ve daha sonra tartışılacaktır.

Maksimum olabilirlik yöntemi

Böylece rastgele normal dağılmış gürültünün varlığını varsaydık. Böyle bir durumda ne yapmalı? Bu durum için matematikte yaygın olarak kullanılmaktadır ve kullanılmaktadır. maksimum olabilirlik yöntemi. Kısacası özü seçimde yatıyor olasılık fonksiyonları ve daha sonraki maksimizasyon.

Normal gürültülü verilerden doğrusal bir ilişki kurmaya geri dönüyoruz. Varsayılan doğrusal ilişkinin matematiksel beklenti olduğuna dikkat edin. Mevcut normal dağılım. Aynı zamanda olasılığı gözlemlenebilirlerin varlığına bağlı olarak şu veya bu değeri alır , şuna benziyor:

Şimdi yerine koyalım и İhtiyacımız olan değişkenler şunlardır:

Geriye kalan tek şey vektörü bulmak , bu olasılığın maksimum olduğu yer. Böyle bir fonksiyonu maksimize etmek için, öncelikle logaritmasını almak uygundur (fonksiyonun logaritması, fonksiyonun kendisiyle aynı noktada maksimuma ulaşacaktır):

Bu da aşağıdaki işlevi en aza indirmeye gelir:

Bu arada buna yöntem denir en küçük kareler. Çoğunlukla yukarıdaki hususların tümü atlanır ve bu yöntem basitçe kullanılır.

QR ayrıştırması

Yukarıdaki fonksiyonun minimumu, bu fonksiyonun gradyanının sıfır olduğu nokta bulunarak bulunabilir. Ve degrade şu şekilde yazılacaktır:

QR ayrıştırması en küçük kareler yönteminde kullanılan minimizasyon problemini çözmeye yönelik bir matris yöntemidir. Bu bağlamda denklemi matris formunda yeniden yazıyoruz:

Böylece matrisi ayrıştırıyoruz matrislere и ve bir dizi dönüşüm gerçekleştirin (QR ayrıştırma algoritmasının kendisi burada ele alınmayacak, yalnızca eldeki göreve ilişkin kullanımı dikkate alınacaktır):

Matris diktir. Bu da işten kurtulmamızı sağlar :

Ve eğer değiştirirsen üzerinde , o zaman işe yarayacak . Hesaba katıldığında bir üst üçgen matristir, şuna benzer:

Bu, ikame yöntemi kullanılarak çözülebilir. Öğe olarak bulunur , önceki öğe olarak bulunur ve benzerleri.

Burada, QR ayrıştırmasının kullanımına bağlı olarak ortaya çıkan algoritmanın karmaşıklığının şuna eşit olduğunu belirtmekte fayda var: . Üstelik matris çarpım işleminin iyi bir şekilde paralelleştirilmesine rağmen bu algoritmanın etkili bir dağıtılmış versiyonunu yazmak mümkün değildir.

Dereceli alçalma

Bir fonksiyonun minimizasyonu hakkında konuşurken, her zaman (stokastik) gradyan iniş yöntemini hatırlamakta fayda vardır. Bu, bir fonksiyonun bir noktadaki gradyanını yinelemeli olarak hesaplamaya ve daha sonra bunu gradyanın tersi yönde kaydırmaya dayanan basit ve etkili bir minimizasyon yöntemidir. Bu tür her adım, çözümü minimuma yaklaştırır. Degrade hala aynı görünüyor:

Bu yöntem aynı zamanda gradyan operatörünün doğrusal özelliklerinden dolayı iyi bir şekilde paralelleştirilmiş ve dağıtılmıştır. Yukarıdaki formülde toplam işaretinin altında bağımsız terimlerin bulunduğunu unutmayın. Başka bir deyişle, tüm indeksler için gradyanı bağımsız olarak hesaplayabiliriz. ilk andan itibaren , buna paralel olarak endekslerin gradyanını hesaplayın karşı . Daha sonra ortaya çıkan degradeleri ekleyin. Eklemenin sonucu, endekslerin gradyanını ilkinden itibaren hemen hesaplamışız gibi aynı olacaktır. . Böylece, eğer veriler birkaç veri parçası arasında dağıtılmışsa, gradyan her bir parça için bağımsız olarak hesaplanabilir ve daha sonra bu hesaplamaların sonuçları nihai sonucu elde etmek için toplanabilir:

Uygulama açısından bakıldığında bu paradigmaya uyuyor Harita indirgeme. Gradyan inişinin her adımında, gradyanı hesaplamak için her veri düğümüne bir görev gönderilir, ardından hesaplanan gradyanlar bir araya toplanır ve bunların toplamının sonucu, sonucu iyileştirmek için kullanılır.

Uygulama kolaylığına ve MapReduce paradigmasında yürütülebilme yeteneğine rağmen, degrade inişin dezavantajları da vardır. Özellikle, yakınsama sağlamak için gerekli adımların sayısı, diğer daha özel yöntemlere kıyasla önemli ölçüde daha yüksektir.

LQR

LQR hem doğrusal regresyonu geri yüklemek hem de doğrusal denklem sistemlerini çözmek için uygun olan, sorunu çözmenin başka bir yöntemidir. Ana özelliği matris yöntemlerinin avantajlarını yinelemeli bir yaklaşımla birleştirmesidir. Bu yöntemin uygulamaları her iki kütüphanede de bulunabilir. scipyve MATLAB. Bu yöntemin açıklaması burada verilmeyecektir (makalede bulunabilir) LSQR: Seyrek doğrusal denklemler ve seyrek en küçük kareler için bir algoritma). Bunun yerine, LSQR'yi dağıtılmış bir ortamda uygulamaya uyarlamaya yönelik bir yaklaşım gösterilecektir.

LSQR yöntemi aşağıdakilere dayanmaktadır: iki köşegenleştirme prosedürü. Bu yinelenen bir prosedürdür ve her yineleme aşağıdaki adımlardan oluşur:


Ama eğer matrisin olduğunu varsayarsak yatay olarak bölümlenmişse, her yineleme iki MapReduce adımı olarak temsil edilebilir. Bu şekilde, her yineleme sırasında veri aktarımlarını en aza indirmek mümkündür (yalnızca bilinmeyenlerin sayısına eşit uzunluğa sahip vektörler):

Doğrusal regresyonu uygularken kullanılan bu yaklaşımdır. Apache Ignite ML.

Sonuç

Pek çok doğrusal regresyon kurtarma algoritması vardır ancak bunların hepsi her koşulda uygulanamaz. Dolayısıyla QR ayrıştırması, küçük veri kümelerinde doğru çözüm için mükemmeldir. Gradyan inişin uygulanması kolaydır ve hızlı bir şekilde yaklaşık bir çözüm bulmanızı sağlar. Ve LSQR, önceki iki algoritmanın en iyi özelliklerini birleştirir; çünkü dağıtılabilir, gradyan inişe kıyasla daha hızlı yakınsar ve ayrıca QR ayrıştırmasının aksine, yaklaşık bir çözüm bulmak için algoritmanın erken durdurulmasına olanak tanır.

Kaynak: habr.com