anlak

Sevgili dostum İsmail Arı şuradaki yazısında PCA hakkında kapsamlı ve güzel bilgiler veriyor. İsmail yazısında kovaryans matrisini diyagonal hale getirecek dönüşüm üzerinden çıkarımı yapıyor. Ben problemi farklı bir açıdan ele alıp, PCA yapmak için neden özvektörleri bulmamız gerektiğini varyansın maksimizasyonu ile göstereceğim. Elimden geldiğince basit anlatmaya çalışacağım, mümkün olduğunca az süslü hatta Yunan alfabesinden olmayan harfler kullanacağım, buna rağmen anlamak için konu hakkında birazcık altyapıya sahip olmanız gerekebilir. Yine de yazının uzunluğu gözünüzü korkutmasın, yeterince anlaşılır olmak adına bilerek fazla açıklama yaptığımdan uzadı, içeriğin yeterince basit olduğunu umuyorum.

İlkin problemimizi tanımlayalım. Elimizde bir kısım veri var ve öyle bir dönüşüm yapmak istiyoruz ki, bu dönüşümün sonunda elimizdeki örnekler birbirinden mümkün olduğunca ayrılmış, dağılmış, saçılmış olsun.

Problemi matematiksel olarak ifade edelim. Elimizde $n$ adet veri örneği olsun. Her sütun bir veri örneğine denk gelecek şekilde $X$ matrisini oluşturalım. Dönüşüm matrisimiz $w$ olsun. Bu dönüşümün ($w^TX$) sonunda saçılımın en fazla olmasını istiyoruz.

İlkin tek boyuta indirecek dönüşümü $w_1$ ele alalım. Bu dönüşümün sonucunda elde ettiğimiz yeni değişkenlere de $z_1$ diyelim. Öyle bir dönüşüm arıyoruz ki, $z_1$ için saçılımın en fazla olmasını istiyoruz:
$$
\arg\max\limits_{w_1} \; \text{Var}(z_1)
$$

Başka bir deyişle:
$$
\arg\max\limits_{w_1} \; \text{Var}(w_1^TX)
$$

$$
\newcommand{\E}{\mathop{\mathbb E}}
\renewcommand{\< }{\left<}
\renewcommand{\>}{\right>}
\newcommand{\Var}{\text{Var}}
\newcommand{\CovSym}{\mathbf{\Sigma}}
$$

Varyansın tanımını hatırlayalım, $\< \cdot\>$ beklenen değer operatörü olmak üzere:
$$
\Var(x) = \< (x-\mu)^2\>
$$

İzdüşümden sonraki varyansı yerine koyalım, ortalamanın da aynı dönüşüme tabi olduğuna dikkatinizi çekerim:
$$
\begin{align*}
\Var(w^TX) &= \< (w^TX-w^T\mu)^2\> \\
&= \< w^T(X-\mu)(X-\mu)^Tw \> \\
&= w^T \< (X-\mu)(X-\mu)^T \> w\\
\end{align*}
$$

$\< (X-\mu)(X-\mu)^T\>$ ifadesinin kovaryansa, $\CovSym$, karşılık geldiğini biliyoruz (bilmiyorsak bakıp öğreniyoruz), o halde:

$$
\Var(w^TX) = w^T\CovSym w
$$

Bu bulduğumuzu yerine koyduğumuz zaman, esas problemimiz şu hale gelmiş oldu:

$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1
$$

Sözle ifade edecek olursak, $w_1$ yerine hangi değeri koyarsak $w_1^T\CovSym w_1$ ifadesi en büyük değerine ulaşır?

İfademize bakacak olursak, $w_1$ yerine sonsuz büyük/uzun bir değer koyarsak $w_1^T\CovSym w_1$ ifadesi en yüksek değerini alır. Bu sonuç pek işimize yaramıyor maalesef, elimize hiçbir şey geçmemiş oldu, o yüzden işimize yarayabilecek bir sonuç üretecek şekilde yeniden ifade etmeye çalışalım problemimizi.

$w_1$in uzunluğu değil, yönü önemli bizim için, çünkü onun üzerine sadece izdüşüm alıyoruz. 1 birim ya da 99 birim uzunluğunda olması bizi ilgilendirmiyor. O yüzden problemimizin düzgün bir çözümü olması için $w_1$in uzunluğunu 1 alalım:

$$
||w_1|| = 1
$$

Bu kısıtımızı esas ifademize yedirmemiz lazım. Bunu yapmanın yolu Lagrange Çarpanı yöntemini kullanmak, şuradaki yazımda bundan bahsetmiştim.
$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1 – \lambda (||w_1|| – 1)
$$

Başka bir deyişle:
$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1 – \lambda (w_1^T w_1 – 1)
$$

İfadeyi en yüksek ya da düşük yapan $w_1$ değerini bulmak için, $w_1$e göre türev alıp sıfıra eşitleriz (kalkülüsten hatırlarsınız):
$$
(\CovSym + \CovSym ^T) w_1 – 2 \lambda w_1 = 0
$$

Kovaryans matrislerinin özelliğinden $\CovSym = \CovSym^T$ olduğunu biliyoruz. Bunu kullanıp ifadeyi düzenlersek:
$$
\begin{align*}
2 \CovSym w_1 – 2 \lambda w_1 = 0\\
\CovSym w_1 = \lambda w_1
\end{align*}
$$

elde ederiz ki, bu da tam olarak $w_1$in $\CovSym$’in özvektörü olduğunun ifadesidir. Kabaca hatırlatayım, $A$ bir matris, $\lambda$ bir skaler ve $x$ bir vektör ve $x$, $Ax = \lambda x$ sağlıyor ise $x$’e $A$’nın özvektörü denir.

Peki acaba $w_1$, $\CovSym$’in hangi özvektörü? Bunu bulmak için bulduğumuz sonucu esas problemimiz olan $w_1^T \CovSym w_1$ ifadesinde yerine koyalım, neticede bu ifadeyi maksimize etmeye çalışıyorduk en başından:
$$
\begin{align*}
w_1^T \CovSym w_1 &= w_1^T \lambda w_1 \\
&= \lambda w_1^T w_1\\
&= \lambda ||w_1||\\
&= \lambda
\end{align*}
$$

buluruz. $||w_1||$ uzunluğunun 1′e eşit olduğu bilgisini kullandık son adımda. Elde ettiğimiz sonuç ne demek? Şu demek: Esas ifademizi maksimize etmek istiyorsak $\lambda$’yı maksimize etmeliyiz. $\lambda$’nın da en büyük olması, en büyük özdeğer olduğu durumdur.

Sonuç olarak, ilk izdüşüm alacağımız yön, verinin kovaryans matrisinin en büyük özdeğerine denk düşen özvektör olarak seçilmelidir.

İkinci ve daha sonraki izdüşümler de benzer bir yolla bulunursa bunların da sırasıyla ikinci ve daha sonraki özdeğerlere denk düşen özvektörler olması gerektiği bulunabilir. Çıkarımı yaparken dikkat edilmesi gereken nokta, bir sonraki izdüşümleri yaparken bir önceki bulduğunuz yöne dik olmaları gerektiğidir, yani $w_1 \cdot w_2 = 0$. Bunu da Lagrange çarpanı olarak ifadenize eklemeniz gerekir.

Dikkat edilmesi gereken önemli noktalardan biri de, tüm bunları yaparken, verinizin ortalamasının $0$ olması gerekir, PCA öncesinde ve sonrasında bu gerekli dönüşümü yapmanız lazım.

05.02.2012

Yazar: bitkidoku
Kategorİ: matematik
Hiç yorum yok

Lagrange Çarpanı yöntemi genelde 2 fonksiyonun gradyanlarının birbirine paralel olmasıyla açıklanır. Bu yazıda maksimizasyon/minimizasyon problemlerinde Lagrange Çarpanları kullanımının biraz daha garip fakat daha kolay bir çıkarımından bahsedeceğim.

Diyelim ki elimizde bir $f(x, y)$ fonksiyonu var ve bu fonksiyonun aldığı en büyük değeri bulmaya çalışıyoruz. Matematiksel olarak ifade edecek olursak:

$$
\max\limits_{x,y} f(x,y)
$$

Ve diyelim ki çözümün $g(x, y)=c$ gibi bir koşulu da sağlaması gereksin. Eğer böyle bir kısıtımız olmasaydı $f()$in kısmi türevlerini alıp sıfıra eşitlerdik ve çözüme ulaşırdık (fonksiyon limitlerde sonsuza büyümüyorsa tabi).

Şimdi bu kısıtımızı denkleme yedirelim. Maximize edeceğimiz fonksiyona $0$ değerini eklemek ya da çıkartmak ifadeyi maximize eden değerleri değiştirmeyecektir. Yani:

$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + 0 \right]
$$

Aynı şekilde sıfırın herhangi bir katını da ekleyip çıkarmam sonucu değiştirmeyecektir:

$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + k\cdot 0 \right]
$$

$g(x, y)=c$ olan kısıtımızı da düzenlersek  $0=g(x, y)-c$ elde ederiz. Sıfırı yerine koyarsak üstteki denklemde:

$$
\max\limits_{x,y} f(x,y) = \max\limits_{x,y}  \left[ f(x,y) + k(g(x, y)-c) \right]
$$

Elde ettiğimiz ifade Lagrange Çarpanları ifadesi; $k$lar da Lagrange Çarpanı denilen şeyler. Kısıtmızı esas başladığımız maksimizasyon problemine Lagrange Çarpanlarını kullanarak yedirmiş olduk. Şimdi bu elde ettiğimiz yeni denklemin x’e ve y’ye göre kısmı türevini alıp sıfıra eşitleyip kısıtımıza göre en büyük aldığı değeri bulabiliriz.

19.10.2011

Yazar: bitkidoku
Kategorİ: bilim,geek,matematik
Hiç yorum yok

Gerçek hayattan alınmış sayısal verilerin ilk basamaklarının dağılımının beklenenin aksine düzenli olmadığını söylesem ne yapardınız? Ne yapacaksınız, “hmmm” diyip konuyu daha detaylı anlatmamı beklersiniz en fazla.

Örneğin Tanzanya’daki şehirlerin nüfuslarını listelediğimizi düşünün. Benford kanununa göre bu listedeki sayıların ilk basamağının 1 olma olasılığı, diğer rakamlardan bi tanesi olma olasılığından daha büyüktür. Hatta gerçek hayattan alınmış verilerin ilk basamağındaki rakamların dağılımı şu şekildedir der:

Başka bir şekilde gösterecek olursak, doğal bir veride ilk basamakta rakamların görülme sıklığı şu şekildedir:

Böylesine enteresan bir olayın geçerliliğini bir örnekle inceleyelim. Vikipedi’deki Türkiye’deki göller başlığındaki göllerin yüzölçümlerinin ilk basamaklarının görülme sıklığını yukarıda çizdiğimiz grafik gösterelim (mavi: Benford beklenen değeri, kırmızı: Türkiye’deki göller verisi ):

Bir de göllerin yüzölçümüyle ilgili verinin logaritmik trend çizgisini* çizelim ki ilişkiyi daha iyi anlayalım:

Ne acayip di mi? Şimdi aynı işlemi Türkiye’deki illerin nufusu için yapalım:

Hahah çok eğlenceli. Peki hayatta bunun pratik uygulaması neler olabilir? Basitçe bir veri setinin insan üretimi olup olmadığını anlayabiliriz bu sayede. Vergi kaçıranları saptamak için muhasebe kayıtlarına basit bir analiz yapılıp şüpheli adaylar çıkartılabilir[1] ya da tam tersi vergi kaçırırken daha gerçekçi olsun diye sayıları Benford kanuna uyacak şekilde seçebiliriz. Hatta bir fotoğrafa sonradan müdahele edilip edilmedigini de benzer bir yolla anlayabiliriz.

Ek: Memin’in orjinal fikri olarak, aynı işlemi bilgisayarımda çalışan işlemlerin bellek kullanım değerlerine uyguladım. Sonuç gene şaşmadı. Her zamanki gibi mavi çizgi beklenen değer, kırmızı çizgi gerçek hayattan elde ettiğim veri.

* trend/eğilim çizgisi: Veriye en iyi şekilde uyan çizgi. elle de çizebileceğiniz gibi, Excel benzeri modern hesaplama araçları hatayı en aza indirecek biçimde bu işi sizin için yapar. Sadece bu terim başlı başına bir yazı konusu olabilir, meraklısına anahtar kelime: Linear Regression

1. Mark J. Nigrini (May). “I’ve Got Your Number“. Journal of Accountancy.

27.07.2008

Yazar: bitkidoku
Kategorİ: matematik
1 Yorum

Problemimiz şu: 3 boyutta, bir doğrunun üzerindeki iki noktayı biliyoruz (P1 ve P2). Ve doğrunun üzerinde olmayan bir noktamız var (P3). Bu doğru üzerinde öyle bir nokta (P) arıyoruz ki, P-P3 uzunluğu en az olsun.

Daha anlaşılır olması için şekille gösterelim:

1. Aradaki mesafenin en az olması için vektörü vektörüne dik olmalıdır.
2. 2 vektörün birbirine dik olmasının koşulu skaler çarpımlarının (dot product) 0 olmasıdır. Buna göre:
   
3. Ayrıca P noktasının P1 ve P2 noktalarından geçen doğru olduğunu biliyoruz. Bu koşulun denklemini yazarsak:
   
   Bu denklemi düzenleyip açarsak, elimizde 3 tane farklı denklem olur:
4. Elimizde 4 tane bilinmeyen ve toplam 4 tane denklem var (2. adımdan 1 tane, 3. adımdan 3 tane). Biraz uğraştırsa da elde çözülebilir. Lineer cebir ve bilgisayar gibi araçlar kullananlar için denklem sisteminin düzenlenmiş hali:
   
   Denklem sayfanın dışına taştığı için, küçülttüm. Özgün halini görmek için üstüne tıklayabilirsiniz.

Peki bütün bunlar gerçek hayatta ne işinize yarayacak? Büyük ihtimalle hiç bi işinize yaramayacak, ama benim işime bir kaç yerde yaradı. Belki gerçekten bu denklemlere ihtiyacı olan birileri var orada bir yerlerde. Kim bilir.. Sevgiyle kalın efendim.

10.10.2006

Yazar: bitkidoku
Kategorİ: geek,matematik
1 Yorum