Apakah KNN memiliki fungsi kerugian?

Saya tidak menemukan definisi fungsi kerugian pada wiki dalam konteks pembelajaran mesin.

ini kurang formal, cukup jelas.

Pada intinya, fungsi kerugian sangat sederhana: ini adalah metode untuk mengevaluasi seberapa baik algoritma Anda memodelkan dataset Anda. Jika prediksi Anda benar-benar mati, fungsi kerugian Anda akan menghasilkan angka yang lebih tinggi. Jika mereka cukup bagus, itu akan menghasilkan angka yang lebih rendah. Saat Anda mengubah potongan algoritme untuk mencoba dan meningkatkan model Anda, fungsi kerugian Anda akan memberi tahu Anda jika Anda pergi ke mana pun.

tampaknya tingkat kesalahan KNN bukanlah fungsi yang bisa memandu model itu sendiri mengoptimalkan, seperti Gradient Descent.

Jadi, apakah KNN memiliki fungsi kerugian?

machine-learning fu DL
sumber

Jawaban:

$k$ -NN tidak memiliki fungsi kerugian yang dapat diminimalkan selama pelatihan. Bahkan, algoritma ini sama sekali tidak dilatih. Satu-satunya "pelatihan" yang terjadi untuk -NN, adalah menghafal data (membuat salinan lokal), sehingga selama prediksi Anda dapat melakukan pencarian dan suara terbanyak. Secara teknis, tidak ada fungsi yang dipasang pada data, dan dengan demikian, tidak ada optimasi yang dilakukan (tidak dapat dilatih menggunakan gradient descent). $k$

Tim
sumber

kNN tidak menggunakan fungsi kerugian selama "pelatihan", tapi itu tidak berarti ada tidak fungsi kerugian yang mendefinisikan kNN. Sebagai contoh: Telah diketahui bahwa median meminimalkan rata-rata kehilangan perbedaan absolut. Tetapi Anda tidak pernah menghitung rata-rata abs loss, dan Anda tidak menggunakan optimasi seperti gradient descent untuk menghitung median. Ini masih merupakan fakta yang berguna yang kadang-kadang meminimalkan kehilangan rata-rata. Dengan cara yang sama, Anda mungkin dapat membangun fungsi kerugian yang kNN selalu meminimalkan

nikie

@nikie itu benar, tetapi di kNN menggunakannya hanya sebagai fungsi agregasi lokal di antara tetangga (sulit diterjemahkan ke kerugian keseluruhan untuk meminimalkan). Juga untuk k = 1 Anda tidak menggunakan fungsi seperti itu. Apalagi itu tidak digunakan untuk pelatihan. Menyebutnya fungsi kehilangan hanyalah latihan mental untuk memaksa kNN agar memenuhi beberapa definisi classifier, saya tidak menemukan alasan kuat untuk mendefinisikannya seperti itu.

Tim

@nikie - Saya menambahkan fungsi kerugian dalam jawaban baru. Tim - keuntungan dari menulisnya dengan cara ini adalah lebih mudah untuk melihat bagaimana seseorang dapat membuat tujuan "lebih lembut" dengan beralih dari kernel top hat (menghitung jumlah poin - kNN biasa) ke kernel Gaussian (bobot poin oleh kedekatan).

Mil

@Miles itu benar, tetapi bagaimanapun juga tidak berguna selain teori, akademik, diskusi. Secara praktis, algoritme tidak dilatih menggunakan fungsi kerugian dan tidak praktis untuk melakukannya. Saya akan mengatakan bahwa berbicara tentang fungsi kerugian untuk kNN lebih membingungkan daripada membantu dalam kebanyakan kasus.

Tim

Saya pikir pertanyaan itu tampaknya bersifat teoretis, tetapi Anda benar bahwa tidak ada gunanya praktis untuk mengetahui kerugiannya. Mungkin OP sedang mencari sesuatu seperti analisis komponen lingkungan? Saya menghubungkannya dalam jawaban.

Mil

Setiap algoritma statistik secara eksplisit atau implisit meminimalkan beberapa tujuan, bahkan jika tidak ada parameter atau hiperparameter, dan bahkan jika minimalisasi tidak dilakukan secara iteratif. KNN sangat sederhana sehingga orang biasanya tidak berpikir seperti ini, tetapi Anda sebenarnya dapat menuliskan fungsi objektif eksplisit:

\hat{t} = {argmax}_{C} \sum_{i : x_{i} \in N_{k} ({x}, \hat{x})} δ (t_{i}, C)

$\hat{t} = \text{argmax}_\mathcal{C} \sum_{i: x_i \in N_k(\{x\}, \hat{x})} \delta(t_i, \mathcal{C})$

Apa yang dikatakan ini bahwa kelas prediksi untuk suatu titik sama dengan kelas yang memaksimalkan jumlah poin lain yang ada di himpunan titik terdekat yang juga memiliki kelas yang sama, diukur dengan yaitu ketika berada di kelas , sebaliknya. $\hat{t}$ $\hat{x}$ $\mathcal{C}$ $x_i$ $k$ $N_k(\{x\}, \hat{x})$ $\delta(t_i, \mathcal{C})$ $1$ $x_i$ $\mathcal{C}$ $0$

Keuntungan dari menulisnya dengan cara ini adalah bahwa seseorang dapat melihat bagaimana membuat tujuan "lebih lembut" dengan menimbang poin berdasarkan jarak. Mengenai "pelatihan," tidak ada parameter di sini yang cocok. Tetapi orang dapat menyetel metrik jarak (yang digunakan untuk mendefinisikan ) atau bobot poin dalam jumlah ini untuk mengoptimalkan beberapa tujuan klasifikasi tambahan. Ini mengarah ke Analisis Komponen Lingkungan: https://www.cs.toronto.edu/~hinton/absps/nca.pdf yang mempelajari metrik jarak. $N_k$

Miles
sumber

-3

Saya tidak setuju dengan jawaban yang diterima (agak).

KNN adalah algoritma klasifikasi , dan tidak masuk akal untuk menjalankan algoritma klasifikasi tanpa kehilangan fungsi: Anda akan tertarik pada seberapa baik algoritma itu melakukannya. Dalam kasus KNN, Anda dapat, misalnya, mengevaluasi kualitas klasifikasi dengan melihat jumlah akurasi rata-rata di setiap kelas. Atau, Anda bisa fokus hanya pada ketepatan algoritma.

Metode optimisasi yang memberdayakan KNN tidak tergantung pada fungsi kerugian, jadi selama pelatihan, itu tidak pernah menarik bagi fungsi kerugian, dan bahkan tidak menggunakan gradient-descent untuk melatih.

Bandingkan ini dengan "K-terdekat tetangga classifier": untuk kelas , pertama-tama melatih berarti, dan kemudian menentukan kelas setiap titik dengan jumlah dominan poin milik masing-masing centroid. Misalnya Anda bisa melatih algoritme ini dengan minimalisasi langkah-bijaksana pada kesalahan kuadrat terkecil dari masing-masing centroid (menghitung ulang centroid berdasarkan tetangga terdekat), tetapi pada waktu pengujian, fungsi kerugian Anda akan kembali menjadi beberapa bentuk akurasi pada masing-masing kelas, meskipun algoritma asli tidak memiliki ketergantungan pada ini. $K$ $K$

Alex R.
sumber

Metrik untuk menilai kinerja algoritma dan kehilangan untuk memperkecil adalah dua hal yang berbeda. Bahkan, Anda dapat meminimalkan kerugian yang berbeda dari metrik yang Anda kejar (misalnya untuk alasan komputasi).

Tim

@Tim: Saya pikir kita berada di halaman yang sama seperti itulah tepatnya yang ingin saya sampaikan di paragraf terakhir, di mana metrik digunakan untuk melatih. Tapi, Anda masih menginginkan fungsi kerugian setelah pelatihan untuk mengevaluasi algoritme. Algoritme klasifikasi yang dilatih tanpa menarik beberapa jenis fungsi kerugian (selama atau setelah) pada kelas secara definisi tidak diawasi.

Alex R.