Saya membaca buku ini ( NLTK ) dan itu membingungkan. Entropi adalah didefinisikan sebagai :

Entropi adalah jumlah dari probabilitas setiap label dikalikan dengan probabilitas log dari label yang sama

Bagaimana saya bisa menerapkan entropi dan entropi maksimum dalam hal penambangan teks? Bisakah seseorang memberi saya contoh yang mudah dan sederhana (visual)?

Saya menganggap entropi disebutkan dalam konteks membangun pohon keputusan .

Untuk menggambarkan, bayangkan tugas belajar untuk mengklasifikasikan pertama-nama dalam kelompok-kelompok pria / wanita. Itu diberi daftar nama yang masing-masing dilabeli dengan salah satu matau f, kami ingin mempelajari model yang sesuai dengan data dan dapat digunakan untuk memprediksi jenis kelamin dari nama depan baru yang tak terlihat.

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

Langkah pertama adalah memutuskan apa fitur dari data yang relevan dengan kelas target yang kita inginkan untuk memprediksi. Beberapa contoh fitur meliputi: huruf pertama / terakhir, panjang, jumlah vokal, apakah diakhiri dengan vokal, dll. Jadi setelah ekstraksi fitur, data kami terlihat seperti:

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

Tujuannya adalah untuk membangun pohon keputusan . Contoh pohon adalah:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

pada dasarnya setiap node mewakili tes yang dilakukan pada satu atribut, dan kami ke kiri atau kanan tergantung pada hasil tes. Kami terus melintasi pohon hingga mencapai simpul daun yang berisi prediksi kelas ( matau f)

Jadi jika kita menjalankan nama Amro di pohon ini, kita mulai dengan menguji " adalah panjangnya <7? " Dan jawabannya adalah ya , jadi kita turun ke cabang itu. Setelah cabang, tes berikutnya " adalah jumlah vokal <3? " Lagi dievaluasi menjadi true . Ini mengarah ke simpul daun berlabel m, dan dengan demikian prediksi adalah laki - laki (yang kebetulan saya, jadi pohon memprediksi hasilnya dengan benar ).

Pohon keputusan dibangun dengan cara top-down , tetapi pertanyaannya adalah bagaimana Anda memilih atribut mana yang akan dibagi pada setiap node? Jawabannya adalah menemukan fitur yang terbaik membagi kelas target menjadi simpul anak semurni mungkin (yaitu: simpul yang tidak mengandung campuran laki-laki dan perempuan, simpul yang lebih murni dengan hanya satu kelas).

Ukuran kemurnian ini disebut informasi . Ini mewakili jumlah informasi yang diharapkan yang akan diperlukan untuk menentukan apakah instance baru (nama depan) harus diklasifikasikan pria atau wanita, mengingat contoh yang mencapai node. Kami menghitungnya berdasarkan jumlah kelas pria dan wanita di node.

Entropi di sisi lain adalah ukuran ketidakmurnian (kebalikan). Ini didefinisikan untuk kelas biner dengan nilaia/bsebagai:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

Ini fungsi biner entropi digambarkan dalam gambar di bawah (variabel acak dapat mengambil salah satu dari dua nilai). Ini mencapai maksimum ketika probabilitasnya p=1/2, yang berarti bahwa p(X=a)=0.5atau p(X=b)=0.5memiliki kemungkinan 50% / 50% untuk menjadi salah satu aatau b(ketidakpastian maksimum). Fungsi entropi adalah minimum nol ketika probabilitas p=1atau p=0dengan kepastian lengkap ( p(X=a)=1atau p(X=a)=0masing - masing, menyiratkan yang terakhir p(X=b)=1).

Tentu saja definisi entropi dapat digeneralisasi untuk variabel acak diskrit X dengan hasil N (bukan hanya dua):

( logdalam rumus biasanya diambil sebagai logaritma ke basis 2 )

Kembali ke tugas klasifikasi nama kami, mari kita lihat sebuah contoh. Bayangkan pada suatu saat selama proses membangun pohon, kami mempertimbangkan pemisahan berikut:

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

Seperti yang Anda lihat, sebelum perpecahan kami memiliki 9 laki-laki dan 5 perempuan, yaitu P(m)=9/14dan P(f)=5/14. Menurut definisi entropi:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

Selanjutnya kita membandingkannya dengan entropi yang dihitung setelah mempertimbangkan pemisahan dengan melihat dua cabang anak. Di cabang kiri ends-vowel=1, kami memiliki:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

dan cabang kanan ends-vowel=0, kami memiliki:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

Kami menggabungkan entropi kiri / kanan menggunakan jumlah instance di setiap cabang sebagai faktor bobot (7 instance pergi ke kiri, dan 7 instance pergi ke kanan), dan mendapatkan entropi akhir setelah pemisahan:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

Sekarang dengan membandingkan entropi sebelum dan sesudah pemisahan, kami memperoleh ukuran perolehan informasi , atau berapa banyak informasi yang kami peroleh dengan melakukan pemisahan menggunakan fitur tertentu:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Anda dapat menginterpretasikan perhitungan di atas sebagai berikut: dengan melakukan pemisahan dengan end-vowelsfitur, kami dapat mengurangi ketidakpastian dalam hasil prediksi sub-pohon dengan jumlah kecil 0,1518 (diukur dalam bit sebagai unit informasi ).

Pada setiap simpul pohon, perhitungan ini dilakukan untuk setiap fitur, dan fitur dengan perolehan informasi terbesar dipilih untuk pemisahan secara serakah (sehingga mendukung fitur yang menghasilkan pemisahan murni dengan ketidakpastian / entropi rendah). Proses ini diterapkan secara rekursif dari simpul akar ke bawah, dan berhenti ketika simpul daun berisi instance yang semuanya memiliki kelas yang sama (tidak perlu membaginya lebih lanjut).

Perhatikan bahwa saya melewatkan beberapa detail yang berada di luar ruang lingkup tulisan ini, termasuk cara menangani fitur numerik , nilai yang hilang , pohon overfitting dan pemangkasan , dll.

Untuk memulainya, sebaiknya dipahami the measure of information.

Bagaimana kami measureinformasinya?

Ketika sesuatu yang tidak mungkin terjadi, kami katakan itu adalah berita besar. Juga, ketika kita mengatakan sesuatu yang dapat diprediksi, itu tidak terlalu menarik. Jadi untuk mengukur ini interesting-ness, fungsi harus memuaskan

• jika probabilitas acara adalah 1 (dapat diprediksi), maka fungsinya memberikan 0
• jika probabilitas acara mendekati 0, maka fungsi tersebut harus memberikan angka tinggi
• jika probabilitas 0,5 kejadian terjadi itu memberikan one bitinformasi.

Salah satu ukuran alami yang memenuhi kendala adalah

I(X) = -log_2(p)

di mana p adalah probabilitas acara X. Dan unit dalam bit, menggunakan komputer bit yang sama. 0 atau 1.

Contoh 1

Balik koin yang adil:

Berapa banyak informasi yang bisa kita dapatkan dari satu flip koin?

Jawaban: -log(p) = -log(1/2) = 1 (bit)

Contoh 2

Jika sebuah meteor menyerang Bumi besok, p=2^{-22}maka kita bisa mendapatkan 22 bit informasi.

Jika Matahari terbit besok, p ~ 1maka itu adalah 0 bit informasi.

Entropi

Jadi jika kita mengambil ekspektasi interesting-nessdari suatu peristiwa Y, maka itu adalah entropi. yaitu entropi adalah nilai yang diharapkan dari keunikan suatu acara.

H(Y) = E[ I(Y)]

Secara lebih formal, entropi adalah jumlah bit yang diharapkan dari suatu peristiwa.

Contoh

Y = 1: peristiwa X terjadi dengan probabilitas p

Y = 0: suatu peristiwa X tidak terjadi dengan probabilitas 1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

Basis log 2 untuk semua log.

Saya tidak bisa memberikan gambar, tetapi mungkin saya bisa memberikan penjelasan yang jelas.

Misalkan kita memiliki saluran informasi, seperti lampu yang berkedip sekali sehari baik merah atau hijau. Berapa banyak informasi yang disampaikannya? Tebakan pertama mungkin satu bit per hari. Tetapi bagaimana jika kita menambahkan biru, sehingga pengirim memiliki tiga opsi? Kami ingin memiliki ukuran informasi yang dapat menangani hal-hal selain kekuatan dua, tetapi masih bersifat aditif (cara mengalikan jumlah pesan yang mungkin dengan dua menambahkan satu bit). Kita bisa melakukan ini dengan mengambil log ₂ (jumlah pesan yang mungkin), tetapi ternyata ada cara yang lebih umum.

Misalkan kita kembali ke merah / hijau, tetapi bola lampu merah telah padam (ini adalah pengetahuan umum) sehingga lampu harus selalu menyala hijau. Saluran sekarang tidak berguna, kita tahu apa flash berikutnyajadi kilasan tidak menyampaikan informasi, tidak ada berita. Sekarang kami memperbaiki bohlam tetapi menerapkan aturan bahwa bohlam merah tidak boleh berkedip dua kali berturut-turut. Ketika lampu berkedip merah, kita tahu apa yang akan terjadi selanjutnya. Jika Anda mencoba mengirim bit stream melalui saluran ini, Anda akan menemukan bahwa Anda harus menyandikannya dengan lebih banyak flash daripada jumlah bit yang Anda miliki (sebenarnya 50% lebih banyak). Dan jika Anda ingin menggambarkan urutan flash, Anda dapat melakukannya dengan bit lebih sedikit. Hal yang sama berlaku jika setiap blitz independen (bebas konteks), tetapi blitz hijau lebih umum daripada merah: semakin miring kemungkinan semakin sedikit bit yang Anda butuhkan untuk menggambarkan urutannya, dan semakin sedikit informasi yang dikandungnya, hingga semua-hijau, batas-habis terbakar habis.

Ternyata ada cara untuk mengukur jumlah informasi dalam sinyal, berdasarkan probabilitas dari berbagai simbol. Jika probabilitas menerima simbol x _i adalah p _i , maka pertimbangkan kuantitasnya

-log p i

Semakin kecil p _i , semakin besar nilai ini. Jika x _i menjadi dua kali lebih tidak mungkin, nilai ini meningkat dengan jumlah yang tetap (log (2)). Ini seharusnya mengingatkan Anda untuk menambahkan satu bit ke pesan.

Jika kita tidak tahu apa simbolnya (tetapi kita tahu probabilitasnya) maka kita dapat menghitung rata-rata nilai ini, berapa banyak yang akan kita dapatkan, dengan menjumlahkan berbagai kemungkinan yang berbeda:

I = -Σ p i log (p i )

Ini adalah konten informasi dalam satu flash.

Bola lampu merah terbakar: p red = 0, p green = 1, I = - (0 + 0) = 0
Peralatan merah dan hijau: p merah = 1/2, p hijau = 1/2 , I = - (2 * 1/2 * log (1/2)) = log (2)
Tiga warna, dapat digunakan: p i = 1/3, I = - (3 * 1/3 * log (1/3)) = log (3)
Hijau dan merah, hijau dua kali lebih mungkin: p merah = 1/3 , p hijau = 2/3, I = - (1/3 log (1/3) + 2/3 log (2/3)) = log ( 3) - 2/3 log (2)

Ini adalah konten informasi, atau entropi, pesan. Maksimal ketika simbol yang berbeda dapat dilengkapi. Jika Anda seorang fisikawan, Anda menggunakan log natural, jika Anda seorang ilmuwan komputer Anda menggunakan log ₂ dan mendapatkan bit.

Saya sangat merekomendasikan Anda membaca tentang Teori Informasi, metode bayesian dan MaxEnt. Tempat untuk memulai adalah buku (tersedia gratis online) ini oleh David Mackay:

http://www.inference.phy.cam.ac.uk/mackay/itila/

Metode inferensi tersebut jauh lebih umum daripada sekadar penambangan teks dan saya tidak dapat benar-benar memikirkan bagaimana seseorang dapat mempelajari cara menerapkan ini ke NLP tanpa mempelajari beberapa dasar umum yang terkandung dalam buku ini atau buku pengantar lainnya tentang Machine Learning dan MaxEnt bayesian metode.

Hubungan antara entropi dan teori probabilitas untuk pemrosesan dan penyimpanan informasi sangat, sangat dalam. Untuk memberikan rasa, ada teorema karena Shannon yang menyatakan bahwa jumlah maksimum informasi yang dapat Anda lewati tanpa kesalahan melalui saluran komunikasi berisik sama dengan entropi dari proses kebisingan. Ada juga teorema yang menghubungkan seberapa banyak Anda dapat mengompres sepotong data untuk menempati memori seminimal mungkin di komputer Anda dengan entropi proses yang menghasilkan data.

Saya tidak berpikir itu benar-benar perlu bahwa Anda belajar tentang semua teorema tentang teori komunikasi, tetapi tidak mungkin untuk mempelajari ini tanpa mempelajari dasar-dasar tentang apa yang entropi, bagaimana itu dihitung, apa hubungannya dengan informasi dan kesimpulan, dll. ...

Ketika saya menerapkan algoritma untuk menghitung entropi gambar, saya menemukan tautan ini, lihat di sini dan di sini .

Ini adalah pseudo-code yang saya gunakan, Anda harus menyesuaikannya agar berfungsi dengan teks daripada gambar tetapi prinsip-prinsipnya harus sama.

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

Saya mendapat kode ini dari suatu tempat, tetapi saya tidak dapat menggali tautannya.

Secara informal

entropi adalah ketersediaan informasi atau pengetahuan, Kurangnya informasi akan mengarah pada kesulitan dalam prediksi masa depan yang merupakan entropi tinggi (prediksi kata berikutnya dalam penambangan teks) dan ketersediaan informasi / pengetahuan akan membantu kita memprediksi masa depan yang lebih realistis (entropi rendah).

Informasi yang relevan dari jenis apa pun akan mengurangi entropi dan membantu kita memprediksi masa depan yang lebih realistis, bahwa informasi dapat berupa kata "daging" ada dalam kalimat atau kata "daging" tidak ada. Ini disebut Penguatan Informasi

Secara formal

entropi adalah kurangnya urutan ketidakpastian

Ketika Anda membaca buku tentang NLTK akan menarik Anda membaca tentang Modul Klasifikasi MaxEnt http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Untuk klasifikasi penambangan teks, langkah-langkahnya bisa: pra-pemrosesan (tokenization, steaming, pemilihan fitur dengan Information Gain ...), transformasi ke numerik (frekuensi atau TF-IDF) (saya pikir ini adalah langkah kunci untuk dipahami saat menggunakan teks sebagai input ke algoritma yang hanya menerima numerik) dan kemudian mengklasifikasikan dengan MaxEnt, yakin ini hanyalah sebuah contoh.