Algoritme klasifikasi statistik manakah yang dapat memprediksi benar / salah untuk urutan input?

14

Diberikan urutan input, saya perlu menentukan apakah urutan ini memiliki properti yang diinginkan. Properti hanya bisa benar atau salah, yaitu, hanya ada dua kelas yang mungkin dimiliki urutan.

Hubungan yang tepat antara urutan dan properti tidak jelas, tetapi saya percaya itu sangat konsisten dan harus memberikan klasifikasi statistik. Saya memiliki sejumlah besar kasus untuk melatih classifier, meskipun mungkin sedikit bising, dalam arti ada sedikit kemungkinan urutan diberi kelas yang salah dalam rangkaian pelatihan ini.

Contoh data pelatihan:

Sequence 1: (7 5 21 3 3) -> true
Sequence 2: (21 7 5 1) -> true
Sequence 3: (12 21 7 5 11 1) -> false
Sequence 4: (21 5 7 1) -> false
...

Secara kasar, properti ditentukan oleh himpunan nilai dalam urutan (misalnya keberadaan "11" berarti bahwa properti hampir pasti salah), serta urutan nilai (misalnya "21 7 5 "Secara signifikan meningkatkan kemungkinan bahwa properti itu benar).

Setelah pelatihan, saya harus bisa memberi classifier urutan yang sebelumnya tidak terlihat, seperti (1 21 7 5 3), dan harus menampilkan kepercayaannya bahwa properti itu benar. Apakah ada algoritma yang terkenal untuk melatih classifier dengan input / output seperti ini?

Saya telah mempertimbangkan pengelompokan Bayesian yang naif (yang tidak benar-benar dapat disesuaikan dengan fakta bahwa pesanan itu penting, setidaknya bukan tanpa melanggar asumsi bahwa inputnya independen). Saya juga telah menyelidiki pendekatan model Markov yang tersembunyi, yang tampaknya tidak dapat diterapkan karena hanya satu output yang tersedia, alih-alih satu output per input. Apa yang saya lewatkan?

machine-learning classification modeling Roman Starkov
sumber

Apakah Anda memiliki cara untuk mengukur jarak antara sepasang urutan? Apakah panjang urutan min dan / atau maks diketahui?

Craig Wright

@CraigWright Tidak ada ukuran jarak yang dapat diterapkan yang dapat saya pikirkan. Panjang maksimum pada urutan 12 dan minimum sekitar 4 dapat diasumsikan. Juga, ada sekitar 30 nilai berbeda (mereka bukan alam yang tidak terikat; hanya sejumlah kecil kemungkinan)

Roman Starkov

Apa beberapa variabel respons yang Anda sebutkan? Saya sedang membaca masalah Anda karena ini adalah output biner dan mungkin Anda bisa membuat variabel dummy Var1.1, Var1.12, ..., Var12.12

B_Miner

@ B_Miner Saya mungkin salah paham bagaimana HMM bekerja, tetapi sepertinya itu berfungsi sebagai berikut: Saya memberi makan urutan input saya (abcde) dan menghasilkan urutan tersembunyi yang paling cocok dengan itu, yaitu (a 'b' c 'd' e ' ). Saya tidak berpikir variabel dummy akan menyelesaikan ini; Saya membutuhkan klasifikasi benar / salah untuk seluruh urutan.

Roman Starkov

@romkyns, itu bukan cara kerja HMM. HMM adalah proses probabilistik. Diberi urutan

dan HMM

, Anda dapat menghitung probabilitas bahwa

akan menghasilkan

(menggunakan pemrograman dinamis; algoritma maju). Selain itu, dengan diberikan serangkaian urutan pelatihan, Anda dapat menemukan HMM

yang memiliki kemungkinan maksimum menghasilkan urutan pelatihan tersebut (menggunakan algoritma Baum-Welch). Jadi HMM bisa jadi sesuatu untuk dicoba di sini. Akan ada beberapa detail yang harus diisi.

s

$s$

M

$M$

M

$M$

s

$s$

M

$M$

DW

9

Anda bisa mencoba pendekatan probabilistik yang mirip dengan classifier Bayes yang naif tetapi dengan asumsi yang lebih lemah. Misalnya, alih-alih membuat asumsi independensi yang kuat, buatlah asumsi Markov:

p (x ∣ c) = p (x_{0} ∣ c) \prod_{t} p (x_{t} ∣ x_{t - 1}, c)

$p(x \mid c) = p(x_0 \mid c)\prod_t p(x_t \mid x_{t - 1}, c)$

adalah label kelas Anda, adalah urutan Anda. Anda perlu memperkirakan dua distribusi bersyarat, satu untuk dan satu untuk . $c$ $x$ $c = 1$ $c = 0$

Dengan aturan Bayes:

p (c = 1 ∣ x) = \frac{p (x ∣ c = 1) p (c = 1)}{p (x ∣ c = 1) p (c = 1) + p (x ∣ c = 0) p (c = 0)} .

$p(c = 1 \mid x) = \frac{p(x \mid c = 1) p(c = 1)}{p(x \mid c = 1) p(c = 1) + p(x \mid c = 0) p(c = 0)}.$

Distribusi mana yang dipilih untuk tergantung pada asumsi lain yang dapat Anda buat tentang urutan dan berapa banyak data yang Anda miliki. $p(x_t \mid x_{t - 1}, c)$

Misalnya, Anda dapat menggunakan:

p (x_{t} ∣ x_{t - 1}, c) = \frac{π (x_{t}, x_{t - 1}, c)}{\sum_{i} π (x_{i}, x_{t - 1}, c)}

$p(x_t \mid x_{t - 1}, c) = \frac{\pi(x_t, x_{t - 1}, c)}{\sum_i \pi(x_i, x_{t - 1}, c)}$

Dengan distribusi seperti ini, jika ada 21 angka berbeda yang terjadi dalam urutan Anda, Anda harus memperkirakan parameter ditambah parameter untuk ditambah parameter untuk . $21 \cdot 21 \cdot 2 = 882$ $\pi(x_t, x_t, c)$ $21 \cdot 2 = 42$ $p(x_0 \mid c)$ $2$ $p(c)$

Jika asumsi model Anda tidak terpenuhi, itu dapat membantu untuk menyempurnakan parameter secara langsung sehubungan dengan kinerja klasifikasi, misalnya dengan meminimalkan rata-rata kehilangan-log

- \frac{1}{# D} \sum_{(x, c) \in D} \log p (c ∣ x)

$-\frac{1}{\#\mathcal{D}} \sum_{(x, c) \in \mathcal{D}} \log p(c \mid x)$

menggunakan gradient-descent.

Lucas
sumber

p (x_{t} | x_{t - 1}, c)

$p(x_t|x_{t-1},c)$

p (x_{t} ∣ x_{t - 1}, c)

$p(x_t \mid x_{t - 1}, c)$

E [x_{t} ∣ x_{t - 1}, c] = x_{t - 1}

$E[x_t \mid x_{t - 1}, c] = x_{t - 1}$

c

$c$

Lucas

6

Saya menyarankan agar Anda mendefinisikan beberapa fitur, dan kemudian memilih algoritma pembelajaran mesin untuk diterapkan ke fitur tersebut.

Fitur: Pada dasarnya, setiap fitur harus menjadi sesuatu yang dapat dihitung dari urutan tertentu, dan menurut Anda mungkin relevan dengan apakah urutan tersebut memiliki properti atau tidak. Berdasarkan uraian Anda, Anda dapat mempertimbangkan fitur-fitur seperti berikut:

$i$ $i$ (7 5 21 3 3)
(7 5 21 3 3)7 55 2121 33 3 $30^2$ $30^2$
"Kantung trigram." Anda juga dapat mempertimbangkan trigram, yang merupakan kelanjutan dari tiga angka berurutan dari urutan aslinya. Anda dapat melakukan hal yang sama seperti di atas.

$d=30+30^2+30^3$ $d$

$i$ $i$

$d$

DW
sumber

Upaya pertama yang saya benar-benar terapkan adalah "kantong trigram" dengan klasifikasi bayesian yang naif. Hasilnya menggembirakan tetapi tidak bagus. Saya pikir ini mungkin terkait dengan fakta bahwa trigram sama sekali tidak independen: jika saya memiliki "1 2 3" maka saya juga sangat mungkin memiliki trigram "2 3 *". Mungkin saya harus bereksperimen dengan fitur yang tepat lagi.

Roman Starkov

Bereksperimen lebih banyak, baik dengan set fitur yang berbeda dan dengan algoritma pembelajaran yang berbeda, adalah ide yang baik. Juga, berdasarkan uraian masalah Anda, Anda mungkin ingin menambahkan fitur untuk penampilan setiap nomor individu (sekumpulan kata, bukan hanya sekumpulan trigram): jika Anda hanya menggunakan trigram, Anda mempersulit algoritma pembelajaran mesin untuk belajar fakta seperti "urutan yang berisi 11 hampir pasti tidak memiliki properti".

DW

2

Apa yang Anda lakukan secara efektif adalah pengujian hipotesis pada deret waktu. HMM akan bekerja untuk Anda, meskipun Anda harus menyesuaikannya dengan kasus khusus Anda.

Jujur saja, jika Anda tidak bisa menuliskan semacam deskripsi matematis tentang apa yang ingin Anda deteksi, Anda tidak akan melangkah terlalu jauh. Mungkin Anda bisa memberi tahu kami tentang fitur apa yang Anda harapkan untuk dilihat?

pengguna873
sumber

1

Pembelajaran mesin telah menunjukkan kepada kita bahwa kita dapat melangkah jauh tanpa memiliki gagasan tentang apa yang harus dicari.

bayerj

1

Diberi panjang maksimum 12 pada urutan, maka jaringan saraf dengan 12 input dan satu output dapat bekerja, tetapi Anda harus mengisi akhir setiap urutan dengan nol atau nilai inert.

Craig Wright
sumber

1

Sudahkah Anda mencoba menggunakan jaringan Bayesian? Itulah hal pertama yang saya pikirkan ketika saya harus menggabungkan beberapa bagian data (datang satu per satu) untuk sampai pada probabilitas variabel acak.

Jaringan Bayesian tidak bergantung pada asumsi independensi bahwa Bayes naif.

BTW, model Markov tersembunyi adalah kasus khusus dari jaringan Bayesian.

DojoGojira
sumber

Algoritme klasifikasi statistik manakah yang dapat memprediksi benar / salah untuk urutan input?

Jawaban: