Pengangkutan optimum dan penggunaannya kepada keadilan

​Penterjemah |. Li Rui

Penilai |. Asal-usul teori pengangkutan optimum boleh dikesan kembali ke 1781, apabila saintis Perancis Gaspard Monge mengkaji kaedah yang dikatakan "menggerakkan bumi" dan membina kubu untuk tentera Napoleon. Secara keseluruhannya, pengangkutan yang optimum ialah masalah bagaimana untuk memindahkan semua sumber (seperti bijih besi) dari satu set asal (lombong) ke satu set destinasi (loji keluli) sambil meminimumkan jumlah jarak yang mesti dilalui oleh sumber. Secara matematik, penyelidik ingin mencari fungsi yang memetakan setiap asal ke destinasi sambil meminimumkan jumlah jarak antara asal dan destinasi yang sepadan. Walaupun penerangannya tidak berbahaya, kemajuan pada konsep asal masalah, yang dikenali sebagai konsep Menger, terhenti selama hampir 200 tahun.

Pada tahun 1940-an, ahli matematik Soviet Leonid Kantorovich menyesuaikan perumusan masalah ke dalam versi moden, yang kini dikenali sebagai teori Monge Kantorov, yang merupakan langkah pertama ke arah penyelesaian. Kebaharuan di sini ialah beberapa bijih besi dari lombong yang sama dibenarkan untuk dibekalkan kepada loji keluli yang berbeza. Sebagai contoh, 60% bijih besi dari lombong boleh disediakan kepada loji keluli, manakala baki 40% bijih besi dari lombong boleh disediakan kepada loji keluli yang lain. Secara matematik, ini bukan lagi fungsi, kerana asal yang sama kini memetakan ke destinasi yang berpotensi berbilang. Sebaliknya, ini dikenali sebagai gandingan antara taburan asal dan taburan destinasi, seperti yang ditunjukkan dalam rajah di bawah, memilih lombong daripada taburan biru (asal) dan bergerak secara menegak di sepanjang rajah menunjukkan di mana bijih besi dihantar Taburan; loji keluli (destinasi).

Sebagai sebahagian daripada perkembangan baharu ini, Kantorivich memperkenalkan konsep penting yang dipanggil jarak Wasserstein. Sama seperti jarak antara dua titik pada peta, jarak Wasserstein (juga dikenali sebagai jarak jentolak yang diilhamkan oleh senario asalnya) mengukur jarak antara dua taburan, seperti taburan biru dan magenta dalam kes ini. Jika semua lombong besi jauh dari semua loji besi, maka jarak Wasserstein antara taburan (lokasi) lombong dan taburan loji keluli akan menjadi besar. Walaupun dengan penambahbaikan baharu ini, masih tidak jelas sama ada terdapat cara terbaik untuk mengangkut sumber bijih besi, apatah lagi kaedah yang mana. Akhirnya, pada tahun 1990-an, teori ini mula berkembang pesat apabila penambahbaikan dalam analisis dan pengoptimuman matematik membawa kepada penyelesaian separa kepada masalah tersebut. Pada abad ke-21, pengangkutan optimum mula merebak ke bidang lain, seperti fizik zarah, dinamik bendalir, dan juga statistik dan pembelajaran mesin.

Pengangkutan optimum dalam era moden

Dengan ledakan teori baharu, pengangkutan optimum telah menjadi pusat kepada banyak algoritma statistik dan kecerdasan buatan baharu sejak dua dekad yang lalu. Dalam hampir setiap algoritma statistik, data dimodelkan, secara eksplisit atau tersirat, sebagai mempunyai beberapa taburan kebarangkalian asas. Sebagai contoh, jika data tentang pendapatan individu dikumpul di negara yang berbeza, akan terdapat pengagihan kebarangkalian pendapatan penduduk tersebut di setiap negara. Jika seseorang ingin membandingkan dua negara berdasarkan pengagihan pendapatan penduduk mereka, maka seseorang memerlukan cara untuk mengukur jurang antara kedua-dua pengagihan. Inilah sebabnya mengapa mengoptimumkan pengangkutan (terutamanya jarak Wasserstein) menjadi sangat berguna dalam sains data. Walau bagaimanapun, jarak Wasserstein bukanlah satu-satunya ukuran jarak antara dua taburan kebarangkalian. Malah, disebabkan kaitannya dengan teori fizik dan maklumat, dua pilihan jarak L-2 dan perbezaan Kullback-Leibler (KL) secara sejarah adalah lebih biasa. Kelebihan utama jarak Wasserstein berbanding alternatif ini ialah ia mengambil kira kedua-dua nilai dan kebarangkalian mereka semasa mengira jarak, manakala jarak L-2 dan perbezaan KL hanya mengambil kira kebarangkalian. Imej di bawah menunjukkan contoh set data buatan tentang pendapatan untuk tiga negara fiksyen.

Dalam kes ini, memandangkan taburan tidak bertindih, jarak L-2 (atau perbezaan KL) antara taburan biru dan magenta akan sama dengan taburan biru dan taburan magenta Jarak L-2 antara taburan hijau adalah lebih kurang sama. Sebaliknya, jarak Wasserstein antara taburan biru dan magenta akan jauh lebih kecil daripada jarak Wasserstein antara taburan biru dan hijau kerana terdapat perbezaan yang ketara antara nilai (pemisahan mendatar). Sifat jarak Wasserstein ini menjadikannya ideal untuk mengukur perbezaan antara taburan, terutamanya perbezaan antara set data.

Mencapai keadilan dengan pengangkutan yang optimum

Dengan jumlah data yang besar dikumpulkan setiap hari dan pembelajaran mesin menjadi lebih biasa dalam banyak industri, saintis data mesti lebih berhati-hati untuk tidak membiarkan mereka Analitis dan algoritma berterusan bias dan bias sedia ada dalam data. Sebagai contoh, jika set data kelulusan gadai janji rumah mengandungi maklumat tentang kaum pemohon, tetapi minoriti telah didiskriminasi dalam proses pengumpulan disebabkan kaedah yang digunakan atau berat sebelah tidak sedarkan diri, maka model yang dilatih pada data tersebut akan mencerminkan sisihan asas.

Mengoptimumkan penghantaran boleh membantu mengurangkan berat sebelah ini dan meningkatkan keadilan dalam dua cara. Kaedah pertama dan paling mudah ialah menggunakan jarak Wasserstein untuk menentukan sama ada terdapat potensi bias dalam set data. Sebagai contoh, seseorang boleh menganggarkan jarak Wasserstein antara pengagihan amaun pinjaman yang diluluskan untuk wanita dan pengagihan amaun pinjaman yang diluluskan untuk lelaki Jika jarak Wasserstein adalah sangat besar, iaitu, signifikan secara statistik, maka potensi bias mungkin disyaki. Idea untuk menguji sama ada terdapat perbezaan antara dua kumpulan diketahui dalam statistik sebagai ujian hipotesis dua sampel.

Sebagai alternatif, penghantaran optimum malah boleh digunakan untuk menguatkuasakan keadilan dalam model apabila set data asas itu sendiri berat sebelah. Ini berguna dari perspektif praktikal, kerana banyak set data dunia nyata menunjukkan beberapa tahap berat sebelah, dan mengumpul data tidak berat sebelah boleh menjadi sangat mahal, memakan masa atau tidak boleh dilaksanakan. Oleh itu, adalah lebih praktikal untuk menggunakan data sedia ada, tidak kira betapa tidak sempurnanya, dan cuba memastikan model itu mengurangkan berat sebelah ini. Ini dicapai dengan menguatkuasakan kekangan dalam model yang dipanggil pariti demografi yang kuat, yang memaksa ramalan model untuk bebas dari segi statistik daripada sebarang atribut sensitif. Satu pendekatan ialah memetakan taburan ramalan model kepada taburan ramalan terlaras yang tidak bergantung pada atribut sensitif. Walau bagaimanapun, pelarasan ramalan juga mengubah prestasi dan ketepatan model, jadi terdapat pertukaran antara prestasi model dan tahap model bergantung pada atribut sensitif (iaitu, keadilan).

Pastikan prestasi model optimum dengan menukar ramalan sesedikit mungkin sambil memastikan ramalan baharu bebas daripada atribut sensitif, menghasilkan penghantaran yang optimum. Pengedaran baharu yang diramalkan oleh model terlaras ini dipanggil Wasserstein centroid dan telah menjadi subjek kajian sepanjang dekad yang lalu. Pusat graviti Wasserstein adalah serupa dengan min bagi taburan kebarangkalian kerana ia meminimumkan jumlah jarak dari dirinya ke semua taburan lain. Imej di bawah menunjukkan tiga taburan (hijau, biru dan magenta) bersama-sama dengan pusat Wasserstein mereka (merah).

Dalam contoh di atas, katakan model dibina untuk meramalkan umur dan pendapatan seseorang berdasarkan set data yang mengandungi atribut sensitif, seperti status perkahwinan Terdapat tiga kemungkinan nilai: bujang (biru), berkahwin (hijau), dan balu/bercerai (magenta). Plot serakan menunjukkan taburan ramalan model untuk setiap nilai yang berbeza. Tetapi ingin menyesuaikan nilai-nilai ini supaya ramalan model baru buta kepada status perkahwinan seseorang, setiap taburan ini boleh dipetakan ke pusat graviti merah menggunakan pengangkutan optimum. Kerana semua nilai dipetakan kepada pengedaran yang sama, seseorang tidak lagi boleh menilai status perkahwinan seseorang berdasarkan pendapatan dan umur, atau sebaliknya. Pusat graviti mengekalkan kesetiaan model sebanyak mungkin.

Peningkatan data dan model pembelajaran mesin yang semakin meluas yang digunakan dalam perniagaan dan membuat keputusan kerajaan telah membawa kepada kemunculan persoalan sosial dan etika baharu tentang cara memastikan penggunaan model ini secara adil. Banyak set data mengandungi beberapa jenis berat sebelah disebabkan oleh sifat cara ia dikumpulkan, jadi adalah penting bahawa model yang dilatih mengenainya tidak memburukkan lagi berat sebelah ini atau sebarang diskriminasi sejarah. Pengangkutan optimum hanyalah satu cara untuk menyelesaikan masalah ini, yang telah berkembang sejak beberapa tahun kebelakangan ini. Hari ini, terdapat cara yang pantas dan cekap untuk mengira peta dan jarak pengangkutan yang optimum, menjadikan pendekatan ini sesuai untuk set data besar moden. Memandangkan orang semakin bergantung pada model dan cerapan berasaskan data, keadilan telah dan akan terus menjadi isu teras dalam sains data, dan pengangkutan optimum akan memainkan peranan penting dalam mencapai matlamat ini.

Tajuk asal: ​​Pengangkutan Optimum dan Penerapannya untuk Kesaksamaan​​​, pengarang: Terrence Alsup​

Atas ialah kandungan terperinci Pengangkutan optimum dan penggunaannya kepada keadilan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!