Beberapa fakta tentang pengklasifikasi cascading, yang jarang dipertimbangkan secara serius dalam artikel ilmiah.

Hai Habr! Hari ini kita akan berbicara tentang pengakuan lagi. Yaitu, tentang model pengenal sederhana seperti pengklasifikasi cascading. Kaskade itu digunakan dalam metode populer Viola dan Jones, yang sudah sering mereka tulis di Habré (misalnya, di sini , di sini dan di sini ). Yang menyedihkan adalah bahwa meskipun ada banyak artikel, tidak ada yang serius mempelajari pengklasifikasi cascading. Dan tidak hanya di Habré, tetapi juga komunitas ilmiah. Meskipun cascading classifier tampak sederhana, ada banyak jebakan dan fitur menarik. Karena itu, kami sedang terburu-buru untuk berbagi pengetahuan kami dengan Anda. Jadi, jika tertarik, selamat datang ke kucing.

Cascading classifier adalah model yang sangat sederhana. Ini terdiri dari beberapa level yang berurutan, yang masing-masing dapat direpresentasikan sebagai classifier biner. Preseden yang diselidiki dimasukkan ke input tingkat pertama dan kemudian "perjalanan" tingkat demi tingkat. Jika pada level berikutnya, classifier mengakui preseden sebagai negatif, maka itu tidak lagi dianalisis oleh pengklasifikasi yang tersisa dari kaskade. Model sederhana seperti itu menjadi populer setelah publikasi metode Viola dan Jones [1], di mana, sebagaimana dinyatakan, itu digunakan untuk memberikan kinerja tinggi. Tetapi apakah ini hanya untuk ini? Apakah ini hanya sebuah cascading classifier? Mari kita cari tahu!

Kami akan membangun artikel hari ini di Habré dalam format, baru bagi kami. Kami akan memilih beberapa pernyataan yang akan kami ungkapkan secara terperinci dan bahkan menyangkal di suatu tempat. Jadi mari kita mulai!

Klasifikasi cascading dalam metode Viola dan Jones hanya digunakan untuk mempercepat pengoperasian detektor objek

Dalam artikel asli [1] di halaman pertama ada ungkapan seperti itu:

Kontribusi utama ketiga dari makalah ini adalah metode untuk menggabungkan penggolong yang lebih kompleks berturut-turut dalam struktur kaskade yang secara dramatis meningkatkan kecepatan detektor dengan memfokuskan perhatian pada daerah yang menjanjikan dari gambar.

Memang, metode asli Viola dan Jones dirancang untuk mencari objek dalam gambar. Selain itu, masalah deteksi diselesaikan dengan metode sliding window menggunakan binary classifier, yang diterapkan pada setiap titik gambar yang diselidiki pada skala yang berbeda. Ketidakseimbangan data yang dipelajari pada tahap deteksi ("kosong" daerah tanpa objek yang diinginkan dalam setiap gambar yang diteliti, jutaan atau bahkan milyaran kali lebih banyak dari daerah dengan objek) mendorong penggunaan kaskade - mekanisme yang memungkinkan Anda dengan cepat memotong daerah "kosong".

Tapi itu tentang menggunakan classifier yang sudah terlatih. Sekarang mari kita beralih ke prosedur pelatihan classifier. Ternyata ada masalah yang sama persis dengan ketidakseimbangan sampel: jumlah contoh negatif jauh lebih besar (jutaan dan bahkan miliaran kali lebih banyak) daripada jumlah contoh positif. Namun berkat arsitekturnya, setiap tingkat kaskade baru dilatih oleh metode AdaBoost bukan pada seluruh sampel pelatihan negatif, tetapi hanya pada serangkaian kesalahan terbatas dari tingkat kaskade sebelumnya! Ini memungkinkan Anda untuk menjalankan mesin pelatihan AdaBoost pada sampel yang seimbang dan terbatas!

Seperti yang Anda lihat, penggunaan cascade classifier dalam metode Viola dan Jones menembak dua kali:

1. Ini memungkinkan Anda untuk dengan mudah melatih pengklasifikasi, secara alami menghindari masalah set pelatihan "tak terbatas";
2. Ini memberikan kliping cepat daerah "kosong" selama deteksi objek, karena yang produktivitas rata-rata tinggi dicapai.

Baiklah, mari kita terus mempelajari kaskade klasik dan beralih ke masalah kinerja.

Dengan pemikiran ini, pengklasifikasi cascading adalah alat akselerasi.

Mari kita kembali lagi ke pertanyaan tentang tujuan kaskade, tetapi sekarang di sisi lain. Jika Anda melihat cascade classifier secara matematis, Anda dapat melihat bahwa cascade adalah bentuk konjungtif dari pengklasifikasi yang kuat (masing-masing dapat direpresentasikan sebagai komposisi linier fitur):

$$

$$Cascade\left(x\right)=\prod_{i=1}^{N}\left[S_i\left(x\right)>0\right], \\ S\left(x\right)=\left[\sum_{t=1}^{T}{\alpha_t\cdot h_t\left(x\right)}>0\right],$$

Dimana $$$\left[\bullet\right]$- fungsi indikator.

Mengingat terbatasnya jumlah atribut yang tersedia (yang, dalam praktiknya, ketika mengejar kinerja, ternyata menjadi situasi normal), bentuk konjungtif dari pengklasifikasi yang kuat memiliki kemampuan yang lebih ekspresif daripada pengklasifikasi linier tunggal. Ini mudah dimengerti jika Anda membayangkan contoh sederhana, di mana ruang fitur terdiri dari dua elemen, dan objek positif dan negatif yang dinyatakan dalam koordinat karakteristik ini terletak seperti yang ditunjukkan pada gambar di bawah ini (objek hijau adalah yang positif dan yang merah adalah yang negatif). Jelas bahwa tidak ada classifier linier tunggal yang dapat membagi sampel ini dengan benar. Tetapi kaskade empat tingkat akan mengatasi tugas ini dijamin.


Dengan demikian, penggunaan cascade classifier, selain meningkatkan produktivitas, juga memberikan daya ekspresif yang lebih besar daripada classifier linier tunggal, dalam kondisi sejumlah fitur yang terbatas.

Cascading classifier memberikan kinerja tinggi secara konsisten dan dapat dengan mudah digunakan dalam sistem pengenalan waktu nyata

Seperti yang kami katakan di atas, skema kaskade memungkinkan Anda untuk mencapai kinerja tinggi karena penyaringan cepat "kosong" daerah, karena jumlah mereka beberapa urutan besarnya lebih besar daripada jumlah daerah yang mengandung objek. Waktu pemrosesan wilayah "kosong" berbeda dari waktu pemrosesan wilayah dengan objek beberapa kali (sebanding dengan panjang kaskade - jumlah level kaskade).

Karena jumlah daerah yang mengandung objek berbeda dari gambar ke gambar, waktu pemrosesan setiap frame juga berbeda. Karena kenyataan bahwa ada daerah yang jauh lebih sedikit dengan objek pada bingkai daripada daerah tanpa objek, perbedaan dalam waktu pemrosesan diukur bukan puluhan kali, tetapi puluhan persen, yang, bagaimanapun, signifikan dalam sistem pengenalan industri.

Dengan demikian, waktu operasi dari cascade classifier dalam gambar yang berbeda dapat sangat bervariasi. Oleh karena itu, ketika melakukan pengukuran serius kinerja pengklasifikasi, pengukuran harus dilakukan dari waktu operasi rata-rata dan dalam kasus terburuk. Dan selalu siap untuk "ketidakkonsistenan" sementara seperti saat menggunakan pengklasifikasi cascading.

Dalam praktik kami, kami telah menghadapi masalah serius karena perbedaan yang signifikan dalam waktu operasi kaskade dalam rata-rata dan kasus terburuk. Sebagai bagian dari proyek otomatisasi jalan tol, kami memecahkan masalah dalam mengenali jenis mobil, di mana salah satu sub-tugas utama adalah masalah penghitungan roda. Tentu saja, kami menggunakan metode Viola dan Jones untuk mendeteksi roda pada frame individual. Karena variabilitas roda yang besar (lihat gambar di bawah), kaskade yang terlatih cukup panjang (20 tingkat). Kami menyaksikan langsung masalah yang tidak menyenangkan terkait dengan waktu pemrosesan yang berbeda untuk setiap frame, yang secara serius mencegah kami membangun sistem pengenalan secara real time.


Kemudian kami mengembangkan ide pengklasifikasi cascading klasik ke pohon keputusan penuh, mengembangkan teknologi pembelajaran yang unik untuk pohon keputusan seperti itu (ingat bahwa perlu untuk mengusulkan algoritma yang akan memungkinkan kita untuk menghindari masalah yang terkait dengan set pelatihan "tanpa akhir"). Detail algoritma ini dapat ditemukan dalam karya ilmiah kami [3]. Di sini kami hanya melaporkan beberapa fakta:

1. Jalur terpanjang di pohon yang terlatih terdiri dari 6 pengklasifikasi kuat (skema classifier pohon terlatih ditunjukkan pada gambar di bawah).
2. Klasifikasi pohon yang terlatih memberikan kualitas kerja yang lebih baik dibandingkan dengan kaskade yang dilatih sebelumnya. Ini logis dan mengikuti fakta bahwa kekuatan ekspresif kaskade mirip pohon (yang merupakan bentuk konjungtif-disjungtif) lebih tinggi daripada kekuatan ekspresif kaskade (konjungtif bentuk).
3. Penggolong pohon terlatih secara serius menghindari kaskade dalam kasus terburuk, hampir tanpa kehilangan rata-rata.

Tabel di bawah ini menyajikan perbandingan numerik dari cascade dan pengklasifikasi pohon.


Jadi, jika Anda benar-benar ingin menggunakan pengklasifikasi cascading dalam sistem pengenalan secara real time, maka selalu ingat tentang fitur yang terkait dengan kecepatan kerja dalam kasus rata-rata dan terburuk.

Teknologi pelatihan cascading classifier sangat jelas sehingga tidak ada yang perlu dipikirkan secara serius.

Oh, ini mungkin salah satu topik paling sulit yang terkait dengan pengklasifikasi cascading. Intinya adalah bahwa dalam semua artikel yang kami temui, proses pembelajaran kaskade dijelaskan dengan sangat buruk, dangkal dan tanpa pembenaran yang tepat dari efektivitas algoritma kaskade pembelajaran. Biasanya, algoritma pembelajaran kaskade terlihat seperti ini:

1. Tentukan nilai pembagian pengakuan salah ($$$F$) untuk seluruh kaskade.
2. Tentukan nilai-nilai pembagian pengakuan sejati ($$$d$) dan sebagian kecil dari pengakuan salah ($$$f \lt F$) untuk setiap tingkat pengakuan.
3. Tentukan sampel validasi untuk secara jujur ​​mengevaluasi indikator kualitas dari penggolong akhir.
4. Latih setiap tingkat kaskade baru (yang, kita ingat, dilatih pada semua contoh positif yang tersedia, serta pada kesalahan positif palsu dari kaskade saat ini) sehingga kinerjanya $$$d_i$dan $$$f_i$tidak lebih buruk dari yang diberikan, yaitu $$$d_i>d$dan $$$f_i \lt f$. Omong-omong, proses memastikan indikator-indikator ini dengan sendirinya juga sangat menarik.
5. Tambahkan level yang baru dilatih ke kaskade dan evaluasi indikator kualitasnya dalam sampel validasi. Jika tingkat pengakuan salah kurang dari target$$$F$, lalu selesaikan pelatihan. Jika tidak, lanjutkan ke langkah 4 untuk mempelajari tingkat kaskade baru.

Jika sebagai akibat dari algoritma di atas dilatih $$$K$tingkat kaskade, maka Anda dapat memperkirakan kompleksitas rata-rata bagian dari pengakuan kaskade yang benar sebagai berikut:

$$

$$N=n_1+\sum_{i=2}^{K}\left(n_i\prod_{j=2}^{i}p_j\right),\\ D=\prod_{i=1}^{K}d_i,$$

Dimana $$$n_i$- kompleksitas $$$i$tingkat kaskade $$$p_i$- probabilitas perhitungan $$$i$kaskade tingkat, dan $$$d_i$- Berbagi pengakuan yang benar $$$i$kaskade tingkat.

Seperti yang Anda lihat, kompleksitas kaskade tidak berpartisipasi dalam algoritma pelatihan yang disajikan, oleh karena itu, tentu saja, itu tidak dapat disebut efektif dalam kinerja. Pada saat yang sama, kita tahu pasti bahwa para ilmuwan di seluruh dunia sangat yakin akan pentingnya mempelajari algoritma untuk kaskade yang efektif. Sebagai konfirmasi, berikut adalah kutipan dari sebuah artikel oleh Paul Viola dan Michael Jones [4]:

The overall training process involves two types of tradeoffs. In most cases classifiers with more features will achieve higher detection rates and lower false positive rates. At the same time classifiers with more features require more time to compute. In principle one could define an optimization framework in which
– the number of classifier stages,
– the number of features, $$$n_i$, of each stage,
– the threshold of each stage
are traded off in order to minimize the expected number of features $$$N$given a target for $$$F$and $$$D$. Unfortunately finding this optimum is a tremendously difficult problem.

Sangat menarik bahwa ulasan kami tentang literatur yang relevan, dibuat pada tahun 2016, menunjukkan bahwa pada saat itu tidak ada algoritma pelatihan yang efektif untuk pengklasifikasi cascading. Ngomong-ngomong, saat itulah kami di Smart Engines menyelesaikan masalah ini. Kami mempelajari fungsional berikut, yang tergantung pada kesalahan deteksi jenis pertama ($$$E_1$), kesalahan deteksi jenis kedua ($$$E_2$) dan kesulitan sedang ($$$N$):

$$

$$F\left(E_1,\ {\ E}_2,\ N\right)=\ {\ \beta_1\cdot\ E}_1+\ \beta_2\cdot E_2+\ \ \beta_3\cdot N.$$

Pemilihan parameter $$$\beta_1$, $$$\beta_2$dan $$$\beta_3$, atur biaya relatif kesalahan jenis pertama dan kedua, serta kompleksitas detektor yang dihasilkan. Selanjutnya, dalam proses pelatihan pengklasifikasi kaskade, algoritma serakah digunakan untuk menghitung parameter pada setiap level untuk mendapatkan kaskade yang memaksimalkan fungsional yang dipilih. Penjelasan terperinci dari algoritma yang dikembangkan ini berada di luar cakupan artikel ini, tetapi kami selalu siap untuk membaginya dengan Anda, pembaca kami, dengan menyediakan tautan bibliografi [5].

Kesimpulan

Untuk meringkas semua yang dikatakan di pihak kami, menggunakan model cascading classifier sebagai contoh, kami ingin menarik kesimpulan berikut:

1. Jarang mungkin untuk memenuhi karya ilmiah di mana semua rincian yang diperlukan dijelaskan secara menyeluruh.
2. Sangat berguna untuk membaca kembali artikel-artikel ilmiah, dengan serius memikirkan sifat-sifat dan keterbatasan model-model yang disajikan di dalamnya, bahkan jika pada pandangan pertama sepertinya semuanya “dikunyah” dalam artikel tersebut.
3. Akan selalu ada tempat untuk penelitian ilmiah yang layak, bahkan jika model yang diteliti diusulkan 20 tahun yang lalu.

Kami sangat senang jika materi yang disajikan dalam artikel ini bermanfaat dan, tentu saja, selalu siap untuk diskusi yang bermanfaat di komentar.

Terima kasih