Mengapa mengoptimalkan kemungkinan log maksimum dan bukannya probabilitas

66

Di sebagian besar tugas pembelajaran mesin di mana Anda dapat merumuskan beberapa probabilitas yang harus dimaksimalkan, kami sebenarnya akan mengoptimalkan probabilitas alih-alih probabilitas untuk beberapa parameter . Misalnya dalam pelatihan kemungkinan maksimum, biasanya log-kemungkinan. Ketika melakukan ini dengan beberapa metode gradien, ini melibatkan faktor: $p$ $\log p$ $\theta$

\frac{\partial \log p}{\partial θ} = \frac{1}{p} \cdot \frac{\partial p}{\partial θ}

$\frac{\partial \log p}{\partial \theta} = \frac{1}{p} \cdot \frac{\partial p}{\partial \theta}$

Lihat di sini atau di sini untuk beberapa contoh.

Tentu saja, optimasi adalah setara, tetapi gradien akan berbeda, sehingga metode berbasis gradien akan berperilaku berbeda (terutama metode gradien stokastik). Apakah ada justifikasi bahwa gradien bekerja lebih baik daripada gradien ? $\log p$ $p$

probability optimization log-likelihood Albert
sumber

3

Anda perlu memperhatikan bahwa kami biasanya memaksimalkan kemungkinan menggunakan derivatif. Di sisi lain dalam banyak kasus kondisi independen diterapkan yang berarti bahwa kemungkinan adalah produk dari beberapa fungsi kepadatan probabilitas iid. Selain itu produk dari banyak nilai kecil (dalam interval [0,1]) menghasilkan nilai yang sangat kecil. Ini mengakibatkan kesulitan perhitungan.

TPArrow

@AlejandroRodriguez periksa jawaban saya di sini untuk lebih detail.

Paul

65

Metode gradien umumnya bekerja lebih baik mengoptimalkan daripada karena gradien dari umumnya lebih baik skala . Artinya, ia memiliki ukuran yang secara konsisten dan bermanfaat mencerminkan geometri fungsi tujuan, membuatnya lebih mudah untuk memilih ukuran langkah yang tepat dan mencapai optimal dalam langkah-langkah yang lebih sedikit. $\log p(x)$ $p(x)$ $\log p(x)$

Untuk melihat apa yang saya maksud, bandingkan proses optimasi gradien untuk dan . Pada setiap titik , gradien dari adalahJika kita kalikan dengan , kita mendapatkan ukuran langkah tepat yang diperlukan untuk mencapai global optimal pada titik asal, tidak peduli apa $p(x) = \exp(-x^2)$ $f(x) = \log p(x) = -x^2$ $x$ $f(x)$

f^{'} (x) = - 2 x .

$f'(x) = -2x.$

1 / 2

$1/2$

x

$x$ aku s. Ini berarti bahwa kita tidak perlu bekerja terlalu keras untuk mendapatkan ukuran langkah yang baik (atau "tingkat pembelajaran" dalam jargon ML). Tidak peduli di mana titik awal kami, kami hanya mengatur langkah kami untuk setengah gradien dan kami akan berada di titik asal dalam satu langkah. Dan jika kita tidak tahu faktor pasti yang diperlukan, kita bisa memilih ukuran langkah sekitar 1, melakukan sedikit pencarian garis, dan kita akan menemukan ukuran langkah besar dengan sangat cepat, yang bekerja dengan baik di mana pun adalah. Properti ini tangguh untuk terjemahan dan penskalaan . Sementara penskalaan akan menyebabkan penskalaan langkah optimal berbeda dari 1/2, setidaknya penskalaan langkah akan sama tidak peduli apa , jadi kita hanya perlu menemukan satu parameter untuk mendapatkan optimalisasi berbasis gradien yang efisien skema.

x

$x$

f (x)

$f(x)$

f (x)

$f(x)$

x

$x$

Sebaliknya, gradien memiliki sifat global yang sangat buruk untuk optimisasi. Kami memilikiIni mengalikan gradien yang sangat bagus, berperilaku baik dengan faktor yang meluruh (lebih cepat dari) secara eksponensial dengan meningkatnya . Pada , kita sudah memiliki , jadi langkah sepanjang vektor gradien sekitar kali terlalu kecil. Untuk mendapatkan ukuran langkah yang masuk akal menuju optimal, kita harus skala gradien dengan kebalikannya, konstanta yang sangat besar $p(x)$

p^{'} (x) = f^{'} (x) p (x) = - 2 x \exp (- x^{2}) .

$p'(x) = f'(x) p(x)= -2x \exp(-x^2).$

- 2 x

$-2x$

\exp (- x^{2})

$\exp(-x^2)$

x

$x$

x = 5

$x = 5$

\exp (- x^{2}) = 1.4 \cdot 10^{- 11}

$\exp(-x^2) = 1.4 \cdot 10^{-11}$

10^{- 11}

$10^{-11}$

\sim 10^{11}

$\sim 10^{11}$ . Gradien berskala buruk seperti itu lebih buruk daripada tidak berguna untuk tujuan optimisasi - kami akan lebih baik hanya mencoba langkah satuan dalam arah menanjak daripada mengatur langkah kami dengan penskalaan terhadap ! (Dalam banyak variabel menjadi sedikit lebih berguna karena kita setidaknya mendapatkan informasi terarah dari gradien, tetapi masalah penskalaan tetap ada.)

p^{'} (x)

$p'(x)$

p^{'} (x)

$p'(x)$

Secara umum tidak ada jaminan bahwa akan memiliki sifat penskalaan gradien yang besar seperti contoh mainan ini, terutama ketika kita memiliki lebih dari satu variabel. Namun, untuk hampir semua masalah nontrivial, akan menjadi cara, jauh lebih baik daripada . Ini karena kemungkinannya adalah produk besar dengan banyak istilah, dan log mengubah produk itu menjadi jumlah, sebagaimana dicatat dalam beberapa jawaban lainnya. Asalkan persyaratan dalam kemungkinan berperilaku baik dari sudut pandang optimasi, log mereka umumnya berperilaku baik, dan jumlah fungsi berperilaku baik. Dengan berperilaku baik maksudku $\log p(x)$ $\log p(x)$ $p(x)$ $f''(x)$ tidak berubah terlalu banyak atau terlalu cepat, mengarah ke fungsi yang hampir kuadratik yang mudah dioptimalkan dengan metode gradien. Jumlah turunan adalah turunan dari jumlah, tidak peduli apa pun urutan turunannya, yang membantu memastikan bahwa tumpukan besar jumlah penjumlahan memiliki turunan kedua yang sangat masuk akal!

Paul
sumber

4

+1 Jawaban ini memunculkan dan menekankan poin-poin yang sampai ke inti permasalahan.

whuber

47

Underflow

Komputer menggunakan representasi pecahan titik mengambang angka terbatas, mengalikan begitu banyak probabilitas dijamin sangat mendekati nol.

Dengan , kami tidak memiliki masalah ini. $log$

Uri Goren
sumber

3

+1 untuk stabilitas numerik - ini dan jawaban Yuril harus satu!

Alec Teal

1

Anda dapat menghitung produk dalam ruang log, sehingga menjadi jumlah, dan kemudian mentransfernya kembali. Atau Anda menghitung yang sama dengan . Jadi, stabilitas numerik bukan pertanyaannya.

\frac{\partial \log p}{\partial θ} \cdot p

$\frac{\partial \log p}{\partial \theta} \cdot p$

\frac{\partial p}{\partial θ}

$\frac{\partial p}{\partial \theta}$

Albert

1

Perlu diingat bahwa Anda sebutkan, adalah penggandaan probabilitas dari semua peristiwa dalam sampel, dan adalah elemen yang mengalami underflow.

p

$p$

p

$p$

Uri Goren

5

@Filip Terminologi di utas ini agak keliru. Kami sedang mendiskusikan kepadatan probabilitas , bukan probabilitas. Kepadatan bersifat arbitrer: bergantung pada unit pengukuran. Selain itu, untuk ukuran sampel yang cukup, kepadatan probabilitas dari setiap sampel sederhana dari model parametrik pada akhirnya akan kurang dari . Dalam masalah besar (dengan jutaan data), densitas probabilitas secara rutin adalah atau lebih kecil. Bahkan sampel ukuran dari distribusi Normal standar hampir pasti memiliki kepadatan probabilitas kurang dari .

2^{- 127}

$2^{-127}$

2^{- 1000000}

$2^{-1000000}$

80

$80$

2^{- 127}

$2^{-127}$

whuber

4

@FilipHaglund: whuber benar, bagaimanapun, fakta kepadatannya bukan pengamatan penting di sini. Kami bisa saja mendiskusikan proses diskrit dan berbicara tentang probabilitas aktual (dan pada kenyataannya, OP tidak mengatakan apa pun yang mengecualikan kasus ini). Tetapi kita berbicara tentang probabilitas untuk hasil yang sangat spesifik (misalnya, satu juta pengamatan berjalan dengan cara tertentu). Satu hasil spesifik tidak mungkin, tetapi dalam kesimpulan inferensi Bayes tentang probabilitas adalah penting, jadi kita perlu tahu seberapa besar kemungkinan yang lebih besar dari satu kemungkinan kecil dari yang lain.

Meni Rosenfeld

34

Logaritma probabilitas probabilitas gabungan ganda disederhanakan menjadi jumlah logaritma probabilitas individual (dan aturan penjumlahan lebih mudah daripada aturan produk untuk diferensiasi)

$\log \left(\prod_i P(x_i)\right) = \sum_i \log \left( P(x_i)\right)$
Logaritma dari anggota keluarga distribusi probabilitas eksponensial (yang termasuk normal di mana-mana) adalah polinomial dalam parameter (yaitu kemungkinan maksimum direduksi menjadi kuadrat-terkecil untuk distribusi normal)

$\log\left(\exp\left(-\frac{1}{2}x^2\right)\right) = -\frac{1}{2}x^2$
Bentuk yang terakhir lebih stabil secara numerik dan secara simbolis lebih mudah dibedakan daripada yang sebelumnya.
Terakhir tetapi tidak kalah pentingnya, logaritma adalah transformasi monoton yang menjaga lokasi ekstrem (khususnya, parameter yang diestimasikan dalam kemungkinan maksimum identik untuk formulasi asli dan formulasi log-transformasi)

TemplateRex
sumber

5

Alasan 2 tidak bisa cukup ditekankan. Untuk memaksimalkan kemungkinan log untuk model linier dengan noise Gaussian, Anda hanya perlu memecahkan masalah kuadrat-terkecil, yang sama dengan menyelesaikan sistem persamaan linear.

Paul

Alasan 1 dan 3 hanya menggambarkan cara menghitungnya. Anda dapat menghitungnya seperti itu dan kemudian mengubahnya kembali (dikalikan dengan ) untuk mendapatkan . Sebenarnya cukup umum untuk menghitung dalam ruang log untuk stabilitas numerik. Tapi itu tidak menjelaskan mengapa Anda menggunakan gradien itu. Alasan 4 juga bukan alasan mengapa gradien lebih baik. Anda dapat melakukannya dengan banyak transformasi lain juga. Alasan 2 menarik tetapi saya masih belum yakin mengapa gradien polinomial lebih baik daripada gradien fungsi lain.

p

$p$

\frac{\partial p}{\partial θ}

$\frac{\partial p}{\partial \theta}$

\log p

$\log p$

Albert

@Albert turunan dari polinomial adalah polinomial satu derajat lebih rendah (khususnya, kuadrat menjadi linear), sedangkan eksponensial tidak hanya di bawah diferensiasi

TemplateRex

@TemplateRex: Ya, itu jelas. Tapi saya bertanya tentang properti konvergensi dalam metode gradien stokastik.

Albert

25

Jauh lebih mudah untuk mengambil turunan dari jumlah logaritma daripada mengambil turunan dari produk, yang mengandung, katakanlah, 100 pengganda.

Yurii
sumber

10

Plus Anda mengurangi potensi masalah numerik ketika istilah menjadi sangat kecil atau besar.

Björn

8

Sebaliknya, OP secara implisit menyediakan cara terbaik untuk menghitung turunan dari setiap produk fungsi non-negatif: gandakan jumlah turunan dari log dengan produk itu sendiri. (Penggandaan ini paling baik dilakukan dalam hal logaritma, yang menghilangkan masalah numerik yang disebutkan dalam komentar @ Björn juga.) Jadi, "kemudahan" tidak menawarkan kekuatan penjelas yang nyata, juga tidak menjawab pertanyaan yang lebih bermakna tentang membandingkan gradien .

whuber

10

Sebagai aturan umum, masalah optimisasi yang paling mendasar dan mudah adalah mengoptimalkan fungsi kuadratik. Anda dapat dengan mudah menemukan fungsi yang optimal di mana pun Anda mulai. Bagaimana ini memanifestasikan tergantung pada metode spesifik tetapi semakin dekat fungsi Anda ke kuadrat, semakin baik.

Seperti dicatat oleh TemplateRex, dalam berbagai masalah, probabilitas yang masuk ke dalam menghitung fungsi kemungkinan berasal dari distribusi normal, atau diperkirakan oleh itu. Jadi jika Anda bekerja pada log, Anda mendapatkan fungsi kuadratik yang bagus. Sedangkan jika Anda bekerja pada probabilitas, Anda memiliki fungsi itu

Tidak cembung (kutukan algoritma optimasi di mana-mana)
Melintasi banyak skala dengan cepat, dan karenanya memiliki rentang yang sangat sempit di mana nilai fungsi menunjukkan tempat mengarahkan pencarian Anda.

Fungsi mana yang lebih Anda optimalkan, ini , atau ini ?

(Ini sebenarnya yang mudah; dalam aplikasi praktis pencarian Anda dapat memulai sejauh ini dari yang optimal sehingga nilai-nilai fungsi dan gradien, bahkan jika Anda dapat menghitungnya secara numerik, akan dapat dibedakan dari 0 dan tidak berguna untuk keperluan optimasi algoritma. Tapi mengubah ke fungsi kuadrat membuat ini sepotong kue.)

Perhatikan bahwa ini sepenuhnya konsisten dengan masalah stabilitas numerik yang telah disebutkan. Skala log alasan diperlukan untuk bekerja dengan fungsi ini, persis alasan yang sama bahwa probabilitas log berperilaku jauh lebih baik (untuk optimasi dan tujuan lain) daripada yang asli.

Anda juga bisa mendekati ini dengan cara lain. Bahkan jika tidak ada keuntungan pada log (yang ada) - kita akan tetap menggunakan skala log untuk derivasi dan perhitungan, jadi alasan apa yang ada untuk menerapkan transformasi exp hanya untuk menghitung gradien? Kami mungkin tetap konsisten dengan log.

Meni Rosenfeld
sumber

@TemplateRex: Log dari fungsi cembung positif (ke bawah) adalah cembung, tetapi sebaliknya tidak benar. Probabilitasnya tidak cembung sehingga tidak ada yang perlu dipertahankan, tetapi lognya cembung. Lihatlah grafik yang saya tautkan - exp (-10x ^ 2) jelas bukan cembung, tetapi -10x ^ 2 adalah.

Meni Rosenfeld

4

Dengan menggunakan kami meningkatkan jangkauan dinamis dari algoritma optimasi. The dalam aplikasi biasanya produk dari fungsi. Misalnya, dalam estimasi kemungkinan maksimum itu adalah produk dari bentuk , di mana Adalah fungsi kerapatan, yang dapat berupa lebih besar atau kurang dari 1, btw. $\ln p$ $p$ $L(x|\theta)=\Pi_{i=1}^n f(x_i|\theta)$ $f(.)$

Jadi, ketika sangat besar, yaitu sampel yang besar, fungsi kemungkinan Anda biasanya jauh dari 1: itu sangat kecil atau sangat besar, karena itu fungsi kekuasaan . $n$ $L(.)$ $L\sim f(.)^n$

Dengan mengambil log, kami cukup meningkatkan rentang dinamis dari setiap algoritma optimasi, memungkinkannya bekerja dengan nilai yang sangat besar atau kecil dengan cara yang sama.

Aksakal
sumber

0

Beberapa jawaban yang bagus telah diberikan. Tetapi baru-baru ini saya menemukan yang baru:

Seringkali, Anda diberikan set data pelatihan besar , dan Anda mendefinisikan beberapa model probabilistik , dan Anda ingin memaksimalkan kemungkinan untuk . Mereka dianggap independen, yaitu Anda memiliki Sekarang, Anda sering melakukan semacam pelatihan berbasis gradien stokastik (batch), yaitu di setiap langkah, untuk kerugian Anda , Anda mengoptimalkan untuk , yaitu $\mathcal{X}$ $p(x|\theta)$ $x \in \mathcal{X}$

p (X | θ) = \prod_{x \in X} p (x | θ) .

$p(\mathcal{X}|\theta) = \prod_{x\in\mathcal{X}} p(x|\theta) .$

L

$L$

L (X^{'} | θ)

$L(\mathcal{X'}|\theta)$

X^{'} \subset X

$\mathcal{X'} \subset \mathcal{X}$

θ^{'} := θ - \frac{\partial \sum_{x \in X^{'}} L (x | θ)}{\partial θ} .

$\theta' := \theta - \frac{\partial \sum_{x\in\mathcal{X'}} L(x|\theta)}{\partial \theta} .$ Sekarang, langkah-langkah stokastik ini diakumulasikan secara aditif. Karena itu, Anda menginginkan properti yang secara umum Ini adalah kasus untuk

L (X | θ) = \sum_{x \in X} L (x | θ) .

$L(\mathcal{X}|\theta) = \sum_{x\in\mathcal{X}} L(x|\theta) .$

L (x | θ) = - \log p (x | θ) .

$L(x|\theta) = -\log p(x|\theta) .$

Albert
sumber

Mengapa mengoptimalkan kemungkinan log maksimum dan bukannya probabilitas

Jawaban: