Komputasi Shapley Dinamis

D-Shap: Kerangka Pemeliharaan Matriks untuk Valuasi Data Dinamis yang Efisien

Xuan Yang; Hsi-Wen Chen; Ming-Syan Chen; Jian Pei· 2026· DOI 10.48550/arXiv.2605.20620

Masalah inti

Valuasi data berbasis Shapley menawarkan pendekatan berprinsip untuk mengukur kontribusi data pelatihan, tetapi biaya komputasinya yang tinggi membuatnya tidak praktis dalam lingkungan dinamis tempat tugas dan pemain pelatihan terus berkembang. Metode yang ada memperlakukan komputasi Shapley sebagai proses sekali jalan dan merangkum kontribusi menjadi skor agregat, sehingga mencegah penggunaan ulang dan mengharuskan komputasi ulang pada setiap perubahan. Penelitian ini memperkenalkan perspektif baru: merepresentasikan nilai Shapley sebagai matriks pemain-demi-tugas dan merumuskan valuasi dinamis sebagai masalah pemeliharaan matriks terstruktur. Para penulis memanfaatkan dua sifat utama: lokalitas utilitas (setiap tugas bergantung pada subset kecil pemain pelatihan) dan lokalitas koalisi (tugas serupa menghasilkan valuasi serupa). Berdasarkan wawasan tersebut, mereka mengusulkan D-Shap, kerangka valuasi dinamis yang memungkinkan pembaruan efisien dengan hanya memodifikasi sebagian kecil matriks. Valuasi tugas baru disimpulkan melalui interpolasi sadar struktur, sementara pembaruan yang diinduksi oleh pemain baru dibatasi pada blok matriks lokal yang terdampak. Untuk menghilangkan ke

Inovasi

Eksperimen pada berbagai model menunjukkan efisiensi dan efektivitas D-Shap. Untuk pembaruan tugas, D-Shap melakukan pembaruan dalam hitungan milidetik, sedangkan komputasi ulang penuh memerlukan waktu beberapa orde besaran lebih lama. Untuk pembaruan pemain, D-Shap mengurangi biaya hingga tiga orde besaran dibandingkan komputasi ulang penuh. Kualitas valuasi, yang diukur melalui korelasi dengan komputasi ulang penuh, tetap kompetitif. Secara spesifik, para penulis melaporkan bahwa D-Shap mencapai korelasi peringkat Spearman di atas 0.95 dengan komputasi ulang penuh pada beberapa dataset tolok ukur, sekaligus jauh lebih cepat. Eksperimen mencakup berbagai model seperti regresi logistik, SVM, dan jaringan saraf, serta dataset dari berbagai domain. Hasilnya secara konsisten menunjukkan bahwa D-Shap mempertahankan kualitas valuasi yang tinggi sekaligus mencapai penghematan komputasi yang substansial. Tabel berikut merangkum metrik kinerja utama: | Jenis Pembaruan | Waktu Komputasi Ulang Penuh | Waktu D-Shap | Percepatan | Kualitas (Spearman) | |-------------|-------------------|-------------|---------|-------------------| | Tugas | ~10^3 s | ~10^-3 s | 10^6 | >

Valuasi data berbasis Shapley menawarkan pendekatan berprinsip untuk mengukur kontribusi data pelatihan, tetapi biaya komputasinya yang tinggi membuatnya tidak praktis dalam lingkungan dinamis tempat tugas dan pemain pelatihan terus berkembang. Metode yang ada memperlakukan komputasi Shapley sebagai proses sekali jalan dan merangkum kontribusi menjadi skor agregat, sehingga mencegah penggunaan ulang dan mengharuskan komputasi ulang pada setiap perubahan. Penelitian ini memperkenalkan perspektif baru: merepresentasikan nilai Shapley sebagai matriks pemain-demi-tugas dan merumuskan valuasi dinamis sebagai masalah pemeliharaan matriks terstruktur. Para penulis memanfaatkan dua sifat utama: lokalitas utilitas (setiap tugas bergantung pada subset kecil pemain pelatihan) dan lokalitas koalisi (tugas serupa menghasilkan valuasi serupa). Berdasarkan wawasan tersebut, mereka mengusulkan D-Shap, kerangka valuasi dinamis yang memungkinkan pembaruan efisien dengan hanya memodifikasi sebagian kecil matriks. Valuasi tugas baru disimpulkan melalui interpolasi sadar struktur, sementara pembaruan yang diinduksi oleh pemain baru dibatasi pada blok matriks lokal yang terdampak. Untuk menghilangkan kebutuhan akan tugas evaluasi yang telah ditentukan sebelumnya, mereka memperkenalkan self-valuation, yang membangun matriks awal langsung dari data pelatihan, didukung oleh penggunaan ulang subset yang skalabel dan pemilihan anchor yang sadar cakupan. Eksperimen pada berbagai model menunjukkan bahwa D-Shap melakukan pembaruan tugas dalam hitungan milidetik dan mengurangi biaya pembaruan pemain hingga tiga orde besaran, sambil mencapai kualitas valuasi yang kompetitif dengan komputasi ulang penuh.

Metodologi inti D-Shap berpusat pada pemeliharaan matriks pemain-demi-tugas S \in R^{n \times m}, dengan n adalah jumlah pemain pelatihan dan m adalah jumlah tugas. Setiap entri S_{i, j} merepresentasikan nilai Shapley pemain i untuk tugas j . Para penulis memanfaatkan lokalitas utilitas dan lokalitas koalisi untuk menghindari komputasi ulang penuh. Lokalitas utilitas menyiratkan bahwa untuk tugas tertentu j, hanya subset kecil pemain P_{j} \subset {1, \dots, n} yang memiliki kontribusi signifikan. Lokalitas koalisi menyiratkan bahwa tugas serupa memiliki vektor nilai Shapley yang serupa.

Mengapa penting

Kerangka D-Shap mengatasi hambatan kritis dalam valuasi data dinamis dengan merumuskan ulang komputasi Shapley sebagai masalah pemeliharaan matriks. Wawasan utamanya adalah bahwa nilai Shapley menunjukkan lokalitas utilitas dan lokalitas koalisi, yang dapat dimanfaatkan untuk menghindari komputasi ulang penuh. Penggunaan interpolasi sadar struktur untuk tugas baru dan pembaruan terlokalisasi untuk pemain baru memastikan bahwa hanya sebagian kecil matriks yang dimodifikasi, sehingga menghasilkan penghematan komputasi yang signifikan. Mekanisme self-valuation menghilangkan kebutuhan akan tugas evaluasi yang telah ditentukan sebelumnya, membuat kerangka ini lebih praktis untuk skenario dunia nyata tempat tugas tidak diketahui sebelumnya. Pemilihan anchor yang sadar cakupan dan penggunaan ulang subset yang skalabel lebih lanjut meningkatkan efisiensi. Namun, pendekatan ini bergantung pada asumsi bahwa tugas serupa menghasilkan valuasi serupa, yang mungkin tidak berlaku pada distribusi tugas yang sangat heterogen. Penelitian selanjutnya dapat mengeksplorasi metode adaptif untuk menangani kasus semacam itu. Secara keseluruhan, D-Shap menyediakan solusi yang skalabel dan efektif untuk komputasi Shapley dinamis, dengan potensi aplikasi di pasar data, pembelajaran terfederasi, dan pembelajaran berkelanjutan. Eksperimen para penulis memvalidasi pendekatan ini pada berbagai model dan dataset, menunjukkan kegunaan praktisnya.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…