Mengukur entropi / informasi / pola matriks biner 2d

53

Saya ingin mengukur entropi / kepadatan informasi / pola-kemiripan dari matriks biner dua dimensi. Biarkan saya menunjukkan beberapa gambar untuk klarifikasi:

Tampilan ini harus memiliki entropi yang agak tinggi:

SEBUAH)

masukkan deskripsi gambar di sini

Ini harus memiliki entropi sedang:

B)

masukkan deskripsi gambar di sini

Foto-foto ini, akhirnya, semua harus memiliki entropi mendekati nol:

C)

masukkan deskripsi gambar di sini

D)

masukkan deskripsi gambar di sini

E)

masukkan deskripsi gambar di sini

Apakah ada beberapa indeks yang menangkap entropi, resp. "pola-rupa" dari pajangan ini?

Tentu saja, setiap algoritma (misalnya, algoritma kompresi; atau algoritma rotasi yang diusulkan oleh ttnphns ) peka terhadap fitur tampilan lainnya. Saya mencari algoritme yang mencoba menangkap properti berikut:

Simetri rotasi dan aksial
Jumlah pengelompokan
Pengulangan

Mungkin lebih rumit, algoritme bisa peka terhadap sifat-sifat " prinsip Gestalt " psikologis , khususnya:

Hukum kedekatan:
Hukum simetri: Gambar simetris dirasakan secara kolektif, meskipun terlepas dari jarak:

Tampilan dengan properti ini harus mendapatkan "nilai entropi rendah"; tampilan dengan poin yang agak acak / tidak terstruktur harus diberi "nilai entropi tinggi".

Saya sadar bahwa kemungkinan besar tidak ada algoritma tunggal yang akan menangkap semua fitur ini; oleh karena itu saran untuk algoritma yang hanya membahas sebagian atau bahkan hanya satu fitur sangat disambut baik.

Secara khusus, saya mencari konkrit, algoritma yang ada, atau untuk ide-ide spesifik yang dapat diterapkan (dan saya akan memberikan hadiah sesuai dengan kriteria ini).

algorithms binary-data entropy pattern-recognition information Felix S
sumber

Pertanyaan keren! Bisakah saya bertanya, apa yang memotivasi perlu tindakan tunggal? Tiga properti Anda (simetri, pengelompokan, dan pengulangan) di wajah mereka tampaknya cukup independen untuk menjamin tindakan terpisah.

Andy W

Sejauh ini saya agak sceptik sehingga Anda dapat menemukan algo universal yang menerapkan prinsip gestalt. Yang terakhir ini didasarkan terutama pada pengakuan prototipe yang sudah ada. Pikiran Anda mungkin memiliki ini, tetapi komputer Anda mungkin tidak.

ttnphns

Saya setuju untuk Anda berdua. Sebenarnya saya tidak mencari algoritma tunggal - meskipun kata-kata saya sebelumnya memang menyarankan ini. Saya memperbarui pertanyaan untuk secara eksplisit mengizinkan algoritma untuk properti tunggal. Mungkin seseorang juga memiliki ide tentang bagaimana menggabungkan hasil dari banyak algo (misalnya, "selalu mengambil nilai entropi terendah dari kumpulan algo")

Felix S

1

Bounty sudah berakhir . Terima kasih kepada semua kontributor dan ide-ide bagus! Karunia ini menghasilkan banyak pendekatan menarik. Beberapa jawaban mengandung banyak kerja otak, dan kadang-kadang sayang bahwa hadiah tidak dapat dipisahkan. Akhirnya, saya memutuskan untuk memberikan hadiah kepada @whuber, karena solusinya adalah algoritma yang menurut saya paling komprehensif mengenai fitur yang ditangkapnya, dan karena mudah diimplementasikan. Saya juga menghargai bahwa itu diterapkan pada contoh konkret saya. Yang paling mengesankan adalah kemampuannya untuk menetapkan angka dalam urutan yang tepat dari "peringkat intuitif" saya. Terima kasih, F

Felix S

35

Ada prosedur sederhana yang menangkap semua intuisi, termasuk unsur-unsur psikologis dan geometris. Ini bergantung pada penggunaan kedekatan spasial , yang merupakan dasar dari persepsi kita dan menyediakan cara intrinsik untuk menangkap apa yang hanya diukur secara tidak sempurna oleh simetri.

$m$ $n$ $k=2$ $2$ $3$ $3$ $\min(n,m)$ $\min(n,m)$

Untuk melihat bagaimana ini bekerja, mari kita lakukan perhitungan untuk array dalam pertanyaan, yang akan saya sebut hingga , dari atas ke bawah. Berikut adalah plot jumlah bergerak untuk ( adalah array asli, tentu saja) yang diterapkan pada . $a_1$ $a_5$ $k=1,2,3,4$ $k=1$ $a_1$

Gambar 1

Searah jarum jam dari kiri atas, sama dengan , , , dan . Array adalah oleh , kemudian oleh , oleh , dan oleh , masing-masing. Mereka semua terlihat agak "acak." Mari kita ukur keacakan ini dengan entropi basis-2 mereka. Untuk , urutan entropi ini adalah . Sebut ini "profil" dari . $k$ $1$ $2$ $4$ $3$ $5$ $5$ $4$ $4$ $2$ $2$ $3$ $3$ $a_1$ $(0.97, 0.99, 0.92, 1.5)$ $a_1$

Sebaliknya, di sini adalah jumlah bergerak dari : $a_4$

Gambar 2

Untuk ada sedikit variasi, di mana entropi rendah. Profilnya adalah . Nilai-nilainya secara konsisten lebih rendah daripada nilai-nilai untuk , mengkonfirmasikan pengertian intuitif bahwa ada "pola" yang kuat hadir dalam . $k=2, 3, 4$ $(1.00, 0, 0.99, 0)$ $a_1$ $a_4$

Kami membutuhkan kerangka referensi untuk menafsirkan profil ini. Array acak sempurna dari nilai-nilai biner akan memiliki hanya sekitar setengah nilainya sama dengan dan setengah lainnya sama dengan , untuk entropi . Jumlah yang bergerak dalam oleh lingkungan akan cenderung memiliki distribusi binomial, memberi mereka entropi diprediksi (setidaknya untuk array besar) yang dapat didekati dengan : $0$ $1$ $1$ $k$ $k$ $1 + \log_2(k)$

Plot entropi

Hasil ini didukung oleh simulasi dengan array hingga . Namun, mereka memecah untuk array kecil (seperti array oleh sini) karena korelasi antara windows tetangga (setelah ukuran jendela sekitar setengah dimensi array) dan karena jumlah data yang kecil. Berikut adalah profil referensi dari array acak oleh dihasilkan oleh simulasi bersama dengan plot beberapa profil aktual: $m=n=100$ $5$ $5$ $5$ $5$

Plot profil

Dalam plot ini profil referensi berwarna biru solid. Profil array sesuai dengan : merah, : emas, : hijau, : biru muda. (Termasuk akan mengaburkan gambar karena dekat dengan profil .) Secara keseluruhan profil sesuai dengan urutan dalam pertanyaan: mereka mendapatkan nilai lebih rendah pada sebagian besar nilai dengan meningkatnya urutan pemesanan. Pengecualiannya adalah : sampai akhir, untuk , jumlah bergeraknya cenderung memiliki entropi terendah . Ini menunjukkan keteraturan yang mengejutkan: setiap dari lingkungan di $a_1$ $a_2$ $a_3$ $a_4$ $a_5$ $a_4$ $k$ $a_1$ $k=4$ $2$ $2$ $a_1$ memiliki tepat atau kotak hitam, tidak pernah lebih atau kurang. Ini jauh lebih sedikit "acak" daripada yang mungkin dipikirkan. (Ini sebagian karena hilangnya informasi yang menyertai menjumlahkan nilai-nilai di setiap lingkungan, prosedur yang mengembunkan konfigurasi kemungkinan konfigurasi lingkungan menjadi hanya jumlah yang berbeda mungkin. Jika kita ingin memperhitungkan secara khusus untuk pengelompokan dan orientasi dalam setiap lingkungan, maka alih-alih menggunakan jumlah bergerak kita akan menggunakan gabungan bergerak. Artinya, setiap oleh lingkungan memiliki $1$ $2$ $2^{k^2}$ $k^2+1$ $k$ $k$ $2^{k^2}$ kemungkinan konfigurasi yang berbeda; dengan membedakan mereka semua, kita dapat memperoleh ukuran entropi yang lebih baik. Saya menduga ukuran seperti itu akan meningkatkan profil dibandingkan dengan gambar lain.) $a_1$

Teknik membuat profil entropi pada rentang skala terkontrol ini, dengan menjumlahkan (atau menyatukan atau menggabungkan) nilai-nilai dalam lingkungan yang bergerak, telah digunakan dalam analisis gambar. Ini adalah generalisasi dua dimensi dari ide yang terkenal untuk menganalisis teks pertama sebagai serangkaian huruf, kemudian sebagai serangkaian digraf (urutan dua huruf), kemudian sebagai trigraph, dll. Ia juga memiliki beberapa hubungan yang jelas dengan fraktal analisis (yang mengeksplorasi sifat-sifat gambar pada skala yang lebih halus dan lebih halus). Jika kita berhati-hati untuk menggunakan jumlah blok yang bergerak atau gabungan blok (sehingga tidak ada tumpang tindih antara jendela), kita dapat memperoleh hubungan matematika sederhana di antara entropi berturut-turut; namun,

Berbagai ekstensi dimungkinkan. Misalnya, untuk profil invarian rotasi, gunakan lingkungan melingkar daripada yang persegi. Semuanya digeneralisasi di luar array biner, tentu saja. Dengan array yang cukup besar, seseorang bahkan dapat menghitung profil entropi yang bervariasi secara lokal untuk mendeteksi non-stasioneritas.

Jika nomor tunggal diinginkan, alih-alih seluruh profil, pilih skala di mana keacakan spasial (atau ketiadaan) yang menarik. Dalam contoh-contoh ini, skala yang paling sesuai dengan lingkungan bergerak oleh atau oleh , karena untuk pola mereka semua bergantung pada pengelompokan yang menjangkau tiga hingga lima sel (dan lingkungan dengan hanya rata-rata menghilangkan semua variasi dalam lingkungan). array dan tidak berguna). Pada skala yang terakhir, entropi untuk hingga adalah , , , , dan $3$ $3$ $4$ $4$ $5$ $5$ $a_1$ $a_5$ $1.50$ $0.81$ $0$ $0$ $0$ ; entropi yang diharapkan pada skala ini (untuk array acak seragam) adalah . Ini membenarkan perasaan bahwa "seharusnya memiliki entropi yang agak tinggi." Untuk membedakan , , dan , yang diikat dengan entropi pada skala ini, lihat pada resolusi yang lebih halus berikutnya ( dengan lingkungan): entropinya masing-masing adalah , , , (sedangkan grid acak diharapkan untuk memiliki nilai ). Dengan langkah-langkah ini, pertanyaan awal menempatkan array dalam urutan yang tepat. $1.34$ $a_1$ $a_3$ $a_4$ $a_5$ $0$ $3$ $3$ $1.39$ $0.99$ $0.92$ $1.77$

whuber
sumber

Maaf, saya tidak bisa mengerti bagaimana Anda menghasilkan plot jumlah bergerak Anda. Tolong, jelaskan secara lebih rinci cara menghitung jumlah bergerak.

ttnphns

1

@ttnphns Berikut ini adalah halaman bantuan bergambar yang populer tentang topik tersebut.

whuber

4

Saya mereproduksi hasil dari jawaban yang sangat baik ini dengan @whuber menggunakan NumPy dan matplotlib dengan Python, tersedia di sini: github.com/cosmoharrigan/matrix-entropy

Cosmo Harrigan

(+1) Inilah prinsip yang sangat umum: Dengan sembarang multiset , ada entropi terkait alami dari distribusi probabilitas yang ditentukan oleh multiplisitas dari elemen-elemennya yang berbeda , yaitu , di mana adalah himpunan elemen yang berbeda dalam . Contohnya adalah multiset yang dibentuk oleh lingkungan berukuran- dari berbagai bentuk dalam objek dari berbagai dimensi. (Aku hanya diposting sebuah aplikasi 1D untuk panjang- substring .)

M

$M$

μ (e)

$\mu(e)$

e

$e$

p (e) := \frac{μ (e)}{\sum_{e \in S} μ (e)} (e \in S)

$p(e) := \frac{\mu(e)}{\sum_{e\in S}\mu(e)}\ \ (e\in S)$

S

$S$

M

$M$

k

$k$

k

$k$

res

@whuber Jawaban bagus. Meskipun ini masuk akal secara intuitif, adakah artikel atau buku teks yang bisa dikutip dari derivasi asli ini (saya berasumsi bahwa jika ini adalah karya asli Anda, Anda telah menerbitkannya secara resmi dalam jurnal)?

subhacom

10

Pertama, saran saya murni intuitif: Saya tidak tahu apa-apa di bidang pengenalan pola. Kedua, puluhan saran alternatif seperti milik saya dapat diajukan.

Saya mulai dengan gagasan bahwa konfigurasi reguler (yaitu, dengan entropi rendah) harus entah bagaimana simetris, isomorfis untuk ini atau itu tranformannya. Misalnya dalam rotasi.

Anda dapat memutar (putar ke 90 derajat, dari 180 derajat, dll) matriks Anda hingga konfigurasi sesuai dengan yang asli . Itu akan selalu setuju pada 4 rotasi (360 derajat), tetapi kadang-kadang bisa setuju sebelumnya (seperti matriks E dalam gambar).

Pada setiap rotasi, hitung jumlah sel dengan nilai tidak identik antara konfigurasi asli dan yang diputar. Misalnya, jika Anda membandingkan matriks A asli dengan rotasi 90 derajat, Anda akan menemukan 10 sel di mana ada spot di satu matriks dan kosong di matriks lain. Kemudian bandingkan matriks asli dengan rotasi 180 derajat: 11 sel tersebut akan ditemukan. 10 sel adalah perbedaan antara matriks A asli dan 270 derajat rotasi. 10 + 11 + 10 = 31 adalah keseluruhan "entropi" matriks A .

Untuk matriks B "entropi" adalah 20, dan untuk matriks E hanya 12. Untuk matriks C dan D "entropi" adalah 0 karena rotasi berhenti setelah 90 derajat: isomorfisme sudah tercapai.

masukkan deskripsi gambar di sini

ttnphns
sumber

Terima kasih atas saran Anda! Walaupun saya bisa memikirkan beberapa tampilan "mudah" yang tidak berubah-ubah pada transformasi rotasi, ini adalah pendekatan yang bagus dan mudah (dan dapat diperluas!). Saya harus berpikir tentang jenis transformasi yang ingin saya miliki. Dan saya suka pendekatan Anda menghitung poin dalam setiap transformasi.

Felix S

Terima kasih atas penghargaannya. Tetapi pendekatan itu hanyalah rintisan awal, sebuah gagasan umum, dan Anda benar mengatakan itu dapat diperluas.

ttnphns

Saya suka pendekatan Anda. Namun, untuk mendapatkan jawaban yang lebih umum mungkin perlu mengambil grup simetri yang lebih besar - identitas, 3 rotasi dan 4 refleksi (yaitu , en.wikipedia.org/wiki/Dihedral_group ). Kemudian hitung perbedaan ( ) antara semua pasangan (yaitu ) dan sebagai ukuran keacakan , di mana adalah jumlah batu hitam. Untuk bentuk yang murni acak, seseorang harus mendapatkan , sementara untuk sangat simetris . Hal yang baik adalah bahwa formula untuk berlaku untuk jumlah batu yang berbeda di papan tulis dan memiliki simetri BW.

D_{4}

$D_4$

d

$d$

8 * 7

$8* 7$

r = k \frac{1}{8 * 7} \frac{25}{2 n (25 - n)})

$r=k\frac{1}{8*7}\frac{25}{2n(25-n)})$

n

$n$

r \approx 1

$r\approx 1$

r \approx 0

$r \approx 0$

r

$r$

Piotr Migdal

Maaf karena terlalu rumit. Cukup untuk membandingkan pola asli dengan simetri yang berbeda dari identitas. Kemudian dalam faktor normalisasi ada bukannya .

7

$7$

7

$7$

7 * 8

$7*8$

Piotr Migdal

5

Informasi ini biasanya didefinisikan sebagai . Ada beberapa teori yang bagus menjelaskan bahwa adalah jumlah bit yang Anda butuhkan untuk kode menggunakan . Jika Anda ingin tahu lebih banyak tentang ini bacalah tentang pengkodean aritmatika . $h(x) = \log p(x)$ $\log_2 p(x)$ $x$ $p$

Jadi bagaimana itu bisa menyelesaikan masalah Anda? Mudah. Temukan beberapa yang mewakili data Anda dan gunakan mana adalah sampel baru sebagai ukuran kejutan atau informasi untuk menemukannya. $p$ $-\log p(x)$ $x$

Yang sulit adalah menemukan beberapa model untuk dan menghasilkan data Anda. Mungkin Anda bisa membuat algoritma yang menghasilkan matriks yang Anda anggap 'mungkin'. $p$

Beberapa ide untuk pemasangan . $p$

Jika Anda hanya melihat matriks 5x5, Anda hanya perlu bit untuk menyimpan semua matriks yang mungkin, jadi Anda bisa menghitung semuanya dan menetapkan probabilitas tertentu untuk masing-masing. $2^{25}$
Gunakan mesin Boltzmann terbatas agar sesuai dengan data Anda (maka Anda harus menggunakan energi gratis sebagai pengganti informasi, tapi tidak apa-apa),
Gunakan zip sebagai pengganti dan tidak peduli dengan keseluruhan cerita probabilitas dari atas. Bahkan secara formal tidak apa-apa, karena Anda menggunakan zip sebagai perkiraan kompleksitas Kolmogorov dan ini telah dilakukan oleh para ahli teori informasi yang juga mengarah ke jarak kompresi yang dinormalisasi , $-\log p(x)$
Mungkin menggunakan model grafis untuk memasukkan keyakinan sebelumnya spasial dan menggunakan variabel Bernoulli secara lokal.
Untuk menyandikan invarian translasi, Anda bisa menggunakan model berbasis energi menggunakan jaringan convolutional .

Beberapa ide di atas cukup berat dan berasal dari pembelajaran mesin. Jika Anda ingin memiliki saran lebih lanjut, cukup gunakan komentar.

bayerj
sumber

Jelas, entropi Kolmogorov adalah pendekatan terbaik, dalam arti filosofis, jika Anda berpikir tentang "kesederhanaan pola abstrak" dan Anda tidak mencoba untuk memprediksi seberapa sederhana itu akan menghasilkan pikiran manusia. Ini hanya menyatakan entropi sebagai "panjang program terpendek yang dapat menghasilkan pola itu". Tentu saja, Anda masih perlu menentukan bahasa komputer, tetapi Anda masih bisa mengandalkan mesin Turing abstrak untuk memainkan triknya.

Javier Rodriguez Laguna

Bahasa pemrograman tidak terlalu penting. Bagian tambahan dari program yang mengkompilasi dari bahasa A ke bahasa B akan mengambil peningkatan bit konstan (kompiler) dan dengan demikian dapat diabaikan.

bayerj

4

Proposal saya berikut ini lebih banyak wawasan daripada kesimpulan, jadi saya tidak bisa membuktikannya, tetapi setidaknya bisa menawarkan beberapa alasan. Prosedur penilaian "entropi" dari konfigurasi tempat meliputi:

Digitisasi bintik-bintik.
Lakukan perbandingan konfigurasi dengan dirinya sendiri yang diijinkan, beberapa kali, dengan analisis Procrustes ortogonal .
Plot hasil perbandingan (koefisien identitas) dan nilai jaggedness plot.

Digitisasi tempat , yaitu, ambil koordinatnya. Misalnya, di bawah ini adalah konfigurasi D Anda dengan bintik-bintik bernomor (urutan penomoran dapat berubah-ubah) dan koordinatnya. masukkan deskripsi gambar di sini

Lakukan permutasi dan lakukan analisis Procrustes. Izinkan tempat (baris dalam data) secara acak dan lakukan perbandingan Procrustes dari data asli (tidak diijinkan) dengan yang diijinkan; catat koefisien identitas (ukuran kesamaan dari dua konfigurasi, keluaran dengan analisis). Ulangi permutasi - Procrustes - menyimpan koefisien, berkali-kali (misalnya 1000 kali atau lebih).

Apa yang bisa kita tunggu dari koefisien identitas (IDc) yang diperoleh setelah operasi di atas pada struktur reguler ?Pertimbangkan misalnya konfigurasi di atas D. Jika kita membandingkan koordinat asli yang ditetapkan dengan dirinya sendiri, kita akan mendapatkan IDc = 1, tentu saja. Tetapi jika kita mengubah beberapa spot IDc antara set asli dan yang diaututasi akan menjadi beberapa nilai di bawah 1. Mari kita permute, misalnya, sepasang spot, berlabel 1 dan 4. IDc = .964. Sekarang, alih-alih, ubah titik 3 dan 5. Yang menarik, IDc akan menjadi 0,964 lagi. Nilai yang sama, mengapa? Bintik 3 dan 5 simetris dengan 1 dan 4, sehingga rotasi ke 90 derajat menempatkannya. Perbandingan procrustes tidak sensitif terhadap rotasi atau refleksi, dan dengan demikian permutasi dalam pasangan 1-4 adalah "sama" dengan permutasi dalam pasangan 5-3, untuk itu. Untuk menambahkan lebih banyak contoh, jika Anda mengubah urutan hanya titik 4 dan 7, IDc akan lagi .964! Tampaknya untuk Procrustes, permutasi dalam pasangan 4-7 adalah "sama" seperti dua di atas dalam arti bahwa ia memberikan tingkat kesamaan yang sama (sebagaimana diukur dengan IDc). Jelas, ini semua karena konfigurasi D teratur.Untuk konfigurasi reguler, kami berharap mendapatkan nilai IDC yang agak terpisah dalam eksperimen permutasi / perbandingan kami; sementara untuk konfigurasi tidak teratur, kami berharap bahwa nilainya akan cenderung berkelanjutan.

Plot nilai IDc yang direkam. Misalnya, mengurutkan nilai dan membuat garis-plot. Saya melakukan percobaan - 5000 permutasi - dengan masing-masing konfigurasi Anda A, B (keduanya sangat tidak teratur), D, E (keduanya biasa) dan inilah alur-plotnya:

masukkan deskripsi gambar di sini

Perhatikan seberapa jauh garis bergerigi D dan E (terutama D). Ini karena perbedaan nilai. Nilai untuk A dan B jauh lebih berkelanjutan. Anda dapat memilih sendiri beberapa jenis statistik yang memperkirakan tingkat diskresi / kesinambungan, alih-alih merencanakan. A sepertinya tidak lebih kontinu daripada B (untuk Anda, konfigurasi A agak kurang teratur, tetapi plot-garis saya tampaknya tidak menunjukkannya) atau, jika tidak, mungkin menunjukkan sedikit pola nilai IDc lainnya. Pola apa lagi? Ini di luar ruang lingkup jawaban saya. Pertanyaan besar apakah A memang kurang biasa daripada B: mungkin untuk mata Anda, tetapi tidak harus untuk analisis Procrustes atau mata orang lain.

Ngomong-ngomong, seluruh percobaan permutasi / Procrustes saya lakukan dengan sangat cepat. Saya menggunakan makro Procrustes analysis saya sendiri untuk SPSS (ditemukan di halaman web saya) dan menambahkan beberapa baris kode untuk melakukan permutasi.

ttnphns
sumber

3

Informasi timbal balik, dengan mempertimbangkan setiap dimensi sebagai variabel acak, sehingga setiap matriks sebagai satu set pasangan angka, harus membantu dalam semua kasus, kecuali untuk C, di mana saya tidak yakin dengan hasilnya.

Lihat diskusi sekitar Gambar 8 (dimulai pada p24) tentang analisis kinerja regresi dalam manual TMVA atau entri arxiv yang sesuai .

Metrik yang berbeda untuk distribusi yang berbeda

adavid
sumber

Saya memiliki masalah dalam membuka dokumen yang ditautkan.

ttnphns

Menambahkan tautan alternatif. Tetapi yang pertama bekerja untuk saya (baru saja diuji).

adavid

3

Alih-alih melihat sifat global dari pola (seperti simetri), kita dapat melihat yang lokal, misalnya jumlah tetangga yang dimiliki setiap batu (= lingkaran hitam). Mari kita tunjukkan jumlah total batu dengan . $s$

Jika batu-batu yang dilempar secara acak, distribusi tetangga adalah mana adalah kepadatan batu. Jumlah tempat tergantung jika batu ada di bagian dalam ( ), di tepi ( ) atau di sudut .

P_{r a n d, p} (k neighbors | n places) = (\binom{n}{k}) p^{k} (1 - p)^{n - k},

$P_{rand,p}(k\ \text{neighbors}|n\ \text{places} ) = {n \choose k} p^{k} (1-p)^{n-k},$

p = s / 25

$p = s/25$

n

$n$

n = 8

$n=8$

n = 5

$n=5$

(n = 3)

$(n=3)$

Jelas terlihat, bahwa distribusi tetangga di C) , D) dan E) jauh dari acak. Misalnya, untuk D) semua batu interior memiliki tepat tetangga (berlawanan dengan distribusi acak, yang menghasilkan alih-alih diukur ). $4$ $\approx (0\%,2\%,9\%,20\%,27\%,24\%,13\%,4\%,0\%)$ $(0\%,0\%,0\%,0\%,100\%,0\%,0\%,0\%,0\%)$

Jadi untuk menghitung jika suatu pola acak Anda perlu membandingkan distribusinya dengan tetangga dan membandingkannya dengan pola acak . Misalnya, Anda dapat membandingkan cara dan variansnya. $P_{measured}(k|n)$ $P_{rand,p}(k|n)$

Atau, seseorang dapat mengukur jaraknya dalam ruang fungsi, misalnya: mana adalah rasio titik yang diukur dengan spasi yang berdekatan dan adalah prediksi untuk pola acak, yaitu , dan .

\sum_{n = {3, 5, 8}} \sum_{k = 0}^{n} {[P_{m e a s u r e d} (k | n) P_{m e a s u r e d} (n) - P_{r a n d, p} (k | n) P_{r a n d, p} (n)]}^{2},

$\sum_{n=\{3,5,8\}} \sum_{k=0}^n\left[P_{measured}(k|n)P_{measured}(n) -P_{rand,p}(k|n)P_{rand,p}(n)\right]^2,$

P_{m e a s u r e d} (n)

$P_{measured}(n)$

n

$n$

P_{r a n d, p} (n)

$P_{rand,p}(n)$

P_{r a n d, p} (3) = 4 / 25

$P_{rand,p}(3) = 4/25$

P_{r a n d, p} (5) = 12 / 25

$P_{rand,p}(5) = 12/25$

P_{r a n d, p} (8) = 9 / 25

$P_{rand,p}(8) = 9/25$

Piotr Migdal
sumber

2

Ada cara yang sangat sederhana untuk mengonseptualisasikan konten informasi yang mengacu pada ide Shannon (diakui satu dimensi) menggunakan probabilitas dan probabilitas transisi untuk menemukan representasi string teks yang paling tidak berlebihan. Untuk gambar (dalam kasus khusus ini gambar biner didefinisikan pada matriks persegi) kita dapat merekonstruksi secara unik dari pengetahuan turunan x dan y (-1,0, + 1). Kita dapat mendefinisikan probabilitas transisi 3x3 dan fungsi kepadatan probabilitas global, juga 3x3. Informasi Shannon kemudian diperoleh dari rumus penjumlahan logaritmik klasik yang diterapkan lebih dari 3x3. Ini adalah urutan kedua informasi ukuran Shannon dan dengan baik menangkap struktur spasial dalam 3x3 pdf.

Pendekatan ini lebih intuitif ketika diterapkan pada gambar skala abu-abu dengan lebih dari 2 tingkat (biner), lihat https://arxiv.org/abs/1609.01117 untuk rincian lebih lanjut.

Kieran Larkin
sumber

1

Dalam membaca ini, ada dua hal yang terlintas dalam pikiran. Yang pertama adalah bahwa banyak sifat gestalt cukup menantang untuk diprediksi, dan banyak pekerjaan tingkat PhD digunakan untuk mencoba mencari tahu model bagaimana pengelompokan berlangsung. Naluri saya adalah bahwa aturan paling mudah yang dapat Anda pikirkan akan berakhir dengan contoh-contoh balasan.

Jika Anda dapat mengesampingkan deskripsi pengelompokan gestalt untuk saat ini, saya pikir abstraksi yang bermanfaat adalah menganggap masukan Anda sebagai kasus khusus dari sebuah gambar. Ada banyak algoritma dalam visi komputer yang bertujuan untuk menetapkan tanda tangan pada gambar berdasarkan serangkaian fitur yang berskala invarian dan fitur invarian. Saya pikir yang paling terkenal adalah fitur SIFT:

http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

Pada dasarnya output Anda akan menjadi vektor baru yang memberikan bobot untuk fitur-fitur ini. Anda dapat menggunakan vektor ini dan menerapkan heuristik untuk itu (menemukan norma, mungkin) dan berharap itu menjelaskan apa yang Anda cari. Atau, Anda bisa melatih penggolong untuk mengambil vektor fitur sebagai input dan katakan saja apa kesan Anda tentang 'entropinya'. Kelebihan dari ini adalah bahwa ia akan menggunakan fitur SIFT yang sesuai (yang pasti berlebihan untuk masalah Anda) dan membangun semacam pemetaan yang mungkin sangat tepat. Kelemahannya adalah Anda harus melakukan banyak hal untuk memberi label pada diri Anda sendiri, dan apa yang Anda dapatkan mungkin lebih sulit untuk ditafsirkan, tergantung pada classifier yang Anda gunakan.

Saya harap ini membantu! Banyak algoritma penglihatan komputer tradisional mungkin juga cocok untuk Anda di sini - penelusuran cepat melalui wikipedia di portal itu dapat memberi Anda wawasan tambahan.

penjelasan
sumber

0

Contoh Anda mengingatkan saya pada tabel kebenaran dari aljabar boolean dan sirkuit digital. Di ranah ini, peta Karnaugh (http://en.wikipedia.org/wiki/Karnaugh_map) dapat digunakan sebagai alat untuk menyediakan fungsi boolean minimal untuk mengekspresikan seluruh kotak. Atau, menggunakan identitas aljabar boolean dapat membantu mengurangi fungsi ke bentuk minimalnya. Menghitung jumlah istilah dalam fungsi boolean yang diperkecil dapat digunakan sebagai ukuran entropi Anda. Ini memberi Anda simetri vertikal dan horizontal bersama dengan mengompresi tetangga yang berdekatan, tetapi tidak memiliki simetri diagonal.

Menggunakan aljabar boolean, kedua sumbu diberi label dari AE mulai dari sudut kiri atas. Dengan cara ini, contoh C akan memetakan ke fungsi boolean (! A &! E). Untuk contoh lain, sumbu perlu diberi label secara terpisah (yaitu AE, FJ).

edgester
sumber

Mengukur entropi / informasi / pola matriks biner 2d

Jawaban: