Saya terus menemukan istilah ini ketika membaca tentang pembelajaran penguatan, misalnya dalam kalimat ini:
Jika masalah dimodelkan dengan hati-hati, beberapa algoritma Penguatan Pembelajaran dapat menyatu ke optimal global
http://reinforcementlearning.ai-depot.com/
atau di sini:
Untuk Pi kebijakan tetap apa pun, algoritme TD yang dijelaskan di atas telah terbukti konvergen ke VPi
http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node62.html
Pemahaman saya tentang kata konvergen adalah bahwa itu berarti beberapa hal menyatu ke titik yang sama, tetapi bagaimana satu hal (algoritma) dapat melakukan itu?
algorithms
machine-learning
bintang laut
sumber
sumber
Jawaban:
Sebuah algoritma iteratif dikatakan konvergen saat, sebagai iterasi melanjutkan, output semakin dekat dan lebih dekat dengan beberapa nilai tertentu. Lebih tepatnya, tidak peduli seberapa kecil rentang kesalahan yang Anda pilih, jika Anda melanjutkan cukup lama fungsi tersebut pada akhirnya akan tetap berada dalam rentang kesalahan di sekitar nilai akhir.
Dalam beberapa keadaan, suatu algoritma tidak akan bertemu, memiliki keluaran yang selalu bervariasi dengan jumlah tertentu. Bahkan bisa menyimpang, di mana outputnya akan mengalami perubahan nilai yang lebih besar dan lebih besar, tidak pernah mendekati hasil yang bermanfaat. Lebih tepatnya, tidak peduli berapa lama Anda melanjutkan, nilai fungsi tidak akan pernah menetap dalam kisaran nilai "final" apa pun.
Ungkapan "konvergen ke global optimal" dalam kalimat pertama Anda adalah referensi ke algoritma yang dapat konvergen, tetapi tidak ke nilai "optimal" (misalnya algoritma mendaki bukit yang, tergantung pada fungsi dan kondisi awal, dapat menyatu ke maksimum lokal, tidak pernah mencapai maksimum global).
sumber
Apa itu konvergensi, secara umum
Konsep konvergensi adalah istilah matematika yang didefinisikan dengan baik. Ini pada dasarnya berarti bahwa "pada akhirnya" urutan elemen semakin dekat dan lebih dekat ke nilai tunggal. Kami menyebut nilai tunggal ini sebagai "batas".
Definisi formal berbunyi seperti ini:
Diberikan (tak terhingga) urutan bilangan real
X0, X1, X2, ... Xn ...kita katakanXn converges to a given number Ljika untuk setiap kesalahan positif yang Anda pikirkan, adaXmsedemikian rupa sehingga setiap elemenXnyang datang setelahXmberbeda dariLdengan kurang dari kesalahan itu.Contoh:
Bayangkan urutannya seperti ini:
Apakah Xn konvergen ke nol? Iya! Mengapa?
Pikirkan kesalahan E (misalnya,
E = 0.0025). Apakah ada elemen dalam urutan itu setelah itu setiap elemen di bawah0.025? Iya! Unsur itu adalahX3 = 0.001. Setelah X2, semuaXNada di bawah0.0025. Bisakah ini dilakukan untuk setiap E> 0? Iya. Untuk setiap kesalahan positif yang kita pilih, kita dapat melihat berapa banyak nol yang dimilikinya sebelum titik desimal pertamanya dan urutannya akan lebih rendah yang dimulai dari elemen yang memiliki jumlah nol yang sama.Ini artinya
Xn = 1/(10^5) converges to 0. Seperti dalam "itu bisa semakin dekat dan lebih dekat ke nol" sebanyak yang kita inginkan.Apa artinya suatu algoritma untuk konvergen?
"Secara teknis" yang konvergen bukanlah algoritme, tetapi nilai yang dimanipulasi atau diulang algoritme. Sebagai contoh, katakanlah kita sedang menulis sebuah algoritma yang mencetak semua digit PI.
Algoritme mulai mencetak angka seperti:
Kita bisa bertanya pada diri sendiri: apakah algoritme mencetak angka yang semakin dekat dengan PI? Dengan kata lain, apakah urutan
X0, X1, ... XN ...yang dicetak algoritma kami konvergen ke PI?Jika demikian, kami katakan algoritma kami menyatu ke PI.
Kami biasanya tertarik untuk membuktikan kebenaran suatu algoritma.
Biasanya, ketika kita menulis suatu algoritma, kita tertarik untuk mengetahui apakah solusi yang diberikan algoritma adalah yang benar untuk masalah yang dipecahkannya. Ini kadang-kadang bisa datang dalam bentuk konvergensi.
Secara umum, algoritma memiliki apa yang kita sebut metrik . Metrik adalah angka yang kami berikan untuk hasil yang diberikan algoritma. Sebagai contoh, dalam algoritma iteratif AI / Machine Learning, sangat umum bagi kita untuk melacak "kesalahan" yang dihasilkan oleh algoritma berdasarkan input. Kesalahan ini adalah metrik.
Dalam algoritma iteratif tersebut, setiap langkah menghasilkan kesalahan yang berbeda. Dan yang coba dilakukan oleh algoritma adalah meminimalkan kesalahan itu sehingga semakin kecil dan semakin kecil. Kami mengatakan bahwa algoritma akan menyatu jika urutan kesalahan menyatu.
Dalam kasus tersebut,
global optimumbiasanya didefinisikan sebagai pengaturan yang memiliki kesalahan serendah mungkin. Dalam hal itu, "algoritma konvergen ke global optimum" berarti bahwa "algoritma menghasilkan kesalahan dalam urutan yang menyatu dengan kesalahan serendah mungkin".Jika "global optimum" adalah "solusi yang tepat" kami, menyatakan bahwa algoritma kami konvergen sama dengan menyatakan bahwa algoritma kami benar.
Juga, perlu diingat bahwa menyatakan bahwa suatu algoritma konvergen memerlukan bukti (seperti yang kami lakukan untuk 0,001, 0,0001, ..., contoh kami).
Sebagai contoh, sebuah classifier
Contoh dari ini bisa dalam kasus classifier. Misalkan kita ingin mengklasifikasikan jika angka ganjil atau bahkan menggunakan algoritma pembelajaran mesin, dan bahwa kita memiliki dataset berikut:
Algoritme kami untuk setiap rangkaian angka meludah untuk masing-masing jika genap atau ganjil. Untuk itu, kita dapat mendefinisikan kesalahan metrik sebagai berapa kali kesalahannya dibagi dengan jumlah elemen yang diberikan.
Jadi, jika algoritme kami meludah:
Metrik kesalahan kami adalah
3/5 = 0.6. Sekarang katakanlah kita menjalankan algoritma lagi dan sekarang meludah:Metrik kesalahan kami adalah
1/5 = 0.2.Katakanlah itu berjalan lebih banyak dan lebih banyak, dan urutan kesalahan kami terlihat seperti ini:
0.6, 0.2, 0.1, 0.01, 0.000456, 0.00000543, 0.000000000444 ....Jadi pertanyaan besarnya adalah: apakah algoritma kami akan menjadi nol? Apakah akan pernah konvergen menjadi nol? Apakah algoritma kami akan bertemu? Bisakah kita membuktikan bahwa pada akhirnya itu akan benar (atau sedekat mungkin ke kanan)?
Semoga begitu :)
sumber