Cara Mengidentifikasi Anomisasi Secara Akurat

33bits.org – Mengidentifikasi anomali dalam data sangat penting bagi kemajuan ilmu pengetahuan, keamanan nasional, dan keuangan. Namun, masalah privasi membatasi kemampuan kami untuk menganalisis data. Bisakah kami mencabut batasan ini dan mengidentifikasi anomali secara akurat tanpa mengganggu privasi mereka yang menyumbangkan data mereka? Kami menjawab pertanyaan ini untuk kasus yang paling relevan secara praktis, di mana catatan dianggap anomali relatif terhadap catatan lain.

Cara Mengidentifikasi Anomisasi Secara Akurat

Cara Mengidentifikasi Anomisasi Secara Akurat – Kami membuat empat kontribusi. Pertama, kami memperkenalkan gagasan privasi sensitif, yang mengkonseptualisasikan apa artinya mengidentifikasi anomali secara pribadi. Privasi sensitif menggeneralisasi konsep penting privasi diferensial dan dapat dianalisis. Yang penting, privasi sensitif mengakui konstruksi algoritmik yang memberikan jaminan privasi dan utilitas yang kuat dan praktis. Kedua, kami menunjukkan bahwa privasi diferensial secara inheren tidak mampu mengidentifikasi anomali secara akurat dan pribadi; dalam pengertian ini, generalisasi kami diperlukan. Ketiga, kami menyediakan kompiler umum yang mengambil sebagai input mekanisme pribadi yang berbeda (yang memiliki utilitas buruk untuk identifikasi anomali) dan mengubahnya menjadi mekanisme pribadi yang sensitif. Kompiler ini, yang sebagian besar penting secara teoritis, ditunjukkan untuk menghasilkan mekanisme yang utilitasnya sangat meningkat dibandingkan utilitas mekanisme input. Sebagai kontribusi keempat kami, kami mengusulkan mekanisme untuk definisi populer anomali -anomali) yang (i) dijamin bersifat pribadi secara sensitif, (ii) datang dengan jaminan utilitas yang dapat dibuktikan, dan (iii) secara empiris terbukti memiliki kinerja yang sangat akurat pada berbagai kumpulan data dan kriteria evaluasi.

PENGANTAR

Di garis depan penelitian hari ini dalam kedokteran dan ilmu alam adalah penggunaan analitik data untuk menemukan pola kompleks dari sejumlah besar data. Meskipun pendekatan ini sangat berguna, pendekatan ini menimbulkan masalah etika dan hukum terkait privasi yang serius  karena kesimpulan dapat diambil dari analisis data orang tersebut terhadap identitas orang tersebut, yang menyebabkan pelanggaran privasi . Dalam karya ini, kami fokus secara khusus pada masalah mengidentifikasi catatan anomali, yang memiliki aplikasi mendasar di banyak domain dan juga penting untuk kemajuan ilmiah . Misalnya, untuk mengobati kanker, kita harus mengetahui apakah tumor itu ganas; untuk menghentikan penipuan bank, kita harus menandai transaksi yang mencurigakan; dan untuk melawan terorisme, kita harus mengidentifikasi individu yang menunjukkan perilaku ekstrem. Perhatikan bahwa dalam pengaturan seperti itu, sangat penting untuk mengidentifikasi anomali secara akurat, misalnya, sangat penting untuk mengidentifikasi transaksi penipuan. Namun, dalam semua situasi ini, masih penting untuk melindungi privasi catatan normal (yaitu, non-anomali)  (misalnya, pelanggan dengan transaksi yang sah atau pasien dengan tumor jinak) tanpa mengorbankan akurasi (misalnya, memberi label tumor ganas sebagai jinak).

Kami memecahkan masalah identifikasi anomali yang akurat, pribadi, dan algoritmik (yaitu, memberi label catatan sebagai anomali atau normal oleh suatu algoritme) dengan penekanan pada pengurangan negatif palsu – memberi label anomali sebagai normal – tingkat. Metode saat ini untuk melindungi privasi bekerja dengan baik untuk melakukan statistik dan tugas agregat lainnya , tetapi metode tersebut secara inheren tidak dapat mengidentifikasi catatan anomali secara akurat. Selanjutnya, metode modern identifikasi anomali memberi label pada suatu arsip sebagai anomali (atau normal) berdasarkan tingkat ketidakmiripannya dengan arsip lain yang ada . Akibatnya, pelabelan catatan sebagai anomali khusus untuk dataset, dan mengetahui bahwa catatan anomali dapat membocorkan sejumlah besar informasi tentang catatan lainnya. Jenis kebocoran privasi ini adalah hambatan utama yang harus diatasi oleh metode identifikasi anomali pelestarian privasi. Karya ini adalah yang pertama mengembangkan metode (dalam pengaturan umum di mana anomali bergantung pada data) untuk secara akurat mengidentifikasi apakah suatu catatan anomali sekaligus menjamin privasi dengan membuatnya secara statistik tidak mungkin untuk menyimpulkan apakah catatan non-anomali disertakan dalam kumpulan data .

Kami meresmikan gagasan privasi yang sesuai untuk deteksi dan identifikasi anomali dan mengembangkan konstruksi umum untuk mencapai hal ini. Perhatikan bahwa kami mengasumsikan kurator tepercaya, yang melakukan identifikasi anomali. Jika data didistribusikan dan kurator tepercaya tidak tersedia, seseorang dapat menggunakan komputasi multipartai yang aman untuk mensimulasikan kurator tepercaya, di mana sekarang metodologi yang sama seperti pada pengaturan sebelumnya dapat digunakan.

Meskipun definisi dan konstruksi privasi yang kami kembangkan tidak terikat pada definisi anomali spesifik apa pun, kami menginstansiasinya untuk jenis anomali tertentu: (β, r)-anomaly , yang merupakan model yang lazim digunakan untuk mengkarakterisasi anomali dan menggeneralisasi banyak definisi lain dari anomali. Instansiasi teknis ini secara alami meluas ke varian lain yang terkenal dari formalisasi ini. Berdasarkan definisi anomali ini, sebuah record (yang hidup dalam ruang metrik) dianggap anomali jika terdapat paling banyak record yang serupa dengannya, yaitu dalam jarak r. Parameter dan r diberikan oleh pakar domain atau ditemukan melalui analisis eksplorasi dengan kemungkinan menggunakan metode pribadi yang berbeda (karena parameter ini dapat diperoleh dengan meminimalkan statistik agregat, misalnya, risiko atau kesalahan rata-rata) untuk melindungi privasi dalam proses ini.

Mengapa kita membutuhkan gagasan privasi baru?

Kami mempertimbangkan pengaturan kurator tepercaya untuk privasi. Kurator tepercaya memiliki akses ke database, dan menjawab pertanyaan identifikasi anomali menggunakan mekanisme. Privasi individu dilindungi jika output dari mekanisme identifikasi anomali tidak terpengaruh oleh ada atau tidaknya record individu dalam database (yang merupakan input ke mekanisme). Ini adalah gagasan privasi (yaitu perlindungan) dari catatan yang kami pertimbangkan di sini; ini melindungi individu dari risiko apa pun yang timbul karena adanya informasinya dan pertama kali diformalkan dalam karya mani privasi diferensial (di mana privasi diukur dengan parameter > 0: semakin kecil , semakin tinggi privasi) dan dapat secara informal dinyatakan sebagai berikut: mekanisme acak yang mengambil database sebagai input adalah -diferensial pribadi jika untuk dua database input yang berbeda dengan satu record, probabilitas (sesuai dengan dua database) terjadinya peristiwa apapun berada dalam faktor perkalian eε (yaitu, hampir sama dalam semua kasus). Sayangnya, hanya menggunakan privasi diferensial tidak menjawab kebutuhan akan privasi dan jaminan akurasi praktis yang berarti dalam kasus kami. Misalnya, memberikan privasi yang sama kepada semua orang sangat menurunkan akurasi dalam mengidentifikasi anomali. Untuk database, penambahan record pada region yang sparse dalam hal titik data menimbulkan anomali. Sebaliknya, penghapusan catatan anomali biasanya menghilangkan anomali sama sekali. Oleh karena itu, akurasi yang dapat dicapai untuk identifikasi anomali melalui privasi diferensial terbatas seperti yang dijelaskan di bawah ini.

Privasi diferensial untuk fungsi biner f:D→{0,1}, seperti identifikasi anomali, hadir dengan keterbatasan bawaan yang dapat dijelaskan melalui grafik Gambar 1a. Perbaiki mekanisme M yang seharusnya menghitung f, dengan properti bahwa mekanisme ini secara pribadi berbeda. Fakta bahwa f adalah biner dan M adalah pribadi yang berbeda memiliki efek sebagai berikut. Untuk dua database x dan y yang berbeda dalam satu record, katakan bahwa f (x) = 0 dan f (y) = 1. Sekarang, perhitungan sederhana menunjukkan bahwa batasan privasi diferensial menciptakan tradeoff: setiap kali M membuat kesalahan kecil dalam komputasi f (x) maka terpaksa banyak kesalahan ketika komputasi pada “tetangga” y dan sebaliknya. Selain itu, semakin tinggi persyaratan privasi (yaitu untuk yang lebih kecil) semakin ketat tradeoff ini, seperti yang digambarkan pada Gambar 1a. Secara formal, kami menyatakan fakta ini sebagai berikut.

Klaim 1. Perbaiki >0,f:D→{0,1}, dan DP M:D→{0,1} secara sewenang-wenang. Untuk setiap x dan y, jika f (x) f (y) dan x − y‖1 = 1, maka P (M (x) f (x)) ≥ 1/(1 + eε) atau P ( M (y) f (y)) 1/(1 + eε).

Apa yang terjadi pada tradeoff inheren ini ketika x dan y berbeda di lebih dari satu record? Seperti yang ditunjukkan pada Gambar 1b tradeoff ini santai. Kami mencatat bahwa untuk menurunkan tradeoff, tidak ada yang spesifik untuk metrik 1 (digunakan untuk privasi diferensial), tetapi sebaliknya kami dapat menggunakan metrik apa pun di ruang basis data; karya lain yang dianggap metrik umum misalnya, [25, 33]. Pekerjaan kami mengusulkan metrik jarak yang sesuai untuk identifikasi anomali, dalam hubungannya dengan relaksasi privasi diferensial yang sesuai. Dengan cara ini kami akan membuat pengaturan privasi yang bermakna (tetapi juga dapat dianalisis).

Apa yang kita inginkan dari gagasan baru?

Kami ingin melonggarkan privasi diferensial karena memberikan perlindungan bagi semua orang sangat menurunkan akurasi identifikasi anomali. Salah satu kemungkinan relaksasi, cocok untuk masalah yang dihadapi, adalah memberikan perlindungan hanya untuk sebagian dari catatan. Kami mencatat bahwa relaksasi tersebut didukung oleh undang-undang privasi, misalnya, GDPR memungkinkan untuk melepaskan privasi untuk aktivitas ilegal [21]. Melindungi kumpulan catatan awalan, yang diputuskan independen dari database, bekerja ketika anomali didefinisikan independen dari catatan lain. Namun, untuk definisi anomali yang bergantung pada data, gagasan privasi seperti itu gagal melindungi catatan normal. Di sini masalah muncul karena sifat tetap dari kumpulan yang spesifik untuk basis data. Dalam kasus definisi anomali yang bergantung pada data, jika kami ingin memberikan jaminan privasi ke data normal – sebut saja sensitif – rekaman yang ada dalam database, maka menetapkan kumpulan rekaman sensitif itu sendiri akan membocorkan informasi dan dapat menyebabkan pelanggaran privasi. Dengan demikian, catatan sensitif harus didefinisikan berdasarkan premis yang lebih mendasar untuk mengurangi ketergantungan tersebut. Gagasan tentang catatan sensitif ini memainkan peran penting dalam mendefinisikan gagasan privasi, bernama privasi sensitif, yang sesuai untuk masalah identifikasi anomali.

Kami berkomentar bahwa meskipun metode identifikasi anomali memberikan pelabelan biner, mereka menetapkan skor untuk mewakili seberapa jauh sebuah catatan dengan demikian model-model ini (secara implisit atau eksplisit) menetapkan suatu catatan suatu tingkat keterpencilan sehubungan dengan catatan-catatan lain, yang menjadi pertimbangan diskusi berikut.

Gagasan privasi yang tepat dalam pengaturan kami harus memungkinkan mekanisme privasi memiliki dua properti penting berikut. Pertama, semakin terpencil (atau non-terluar) suatu catatan, semakin tinggi akurasi yang dapat dicapai mekanisme privasi untuk identifikasi anomali, yang berbeda dengan DP (Gambar 2c). Kedua, semua catatan sensitif harus memiliki DP seperti jaminan privasi untuk nilai parameter privasi yang sama.

Mekanisme yang bersifat pribadi di bawah privasi sensitif mencapai kedua properti tersebut, yang memberikan hasil eksperimen indikatif pada data contoh; lihat Bagian A.1 untuk detail eksperimen dan nilai parameter). Selain itu, ia memiliki properti tambahan: dalam pengaturan yang khas, anomali tidak kehilangan privasi sama sekali; sebaliknya, semakin terpencil suatu catatan, semakin rendah privasi yang dimilikinya

Bagaimana kita mendefinisikan gagasan privasi baru?

Untuk mendefinisikan privasi, kita memerlukan ruang metrik di atas basis data karena mekanisme pribadi perlu secara statistik mengaburkan perbedaan antara basis data yang dekat dalam ruang metrik. Sementara privasi diferensial menggunakan metrik · 1 , kami menggunakan metrik yang berbeda pada basis data, yang dapat didefinisikan menggunakan gagasan catatan sensitif. Secara informal, kami mengatakan sebuah catatan sensitif terhadap database jika itu normal atau menjadi normal di bawah perubahan kecil—kami memformalkannya di Bagian 3. Kami berpendapat bahwa gagasan tentang catatan sensitif ini cukup alami, dan ini terinspirasi dari literatur deteksi anomali yang ada . Karena, menurut definisi, catatan anomali berbeda secara signifikan dari catatan lain dalam database , perubahan kecil dalam database tidak akan mempengaruhi label catatan anomali. Mengingat definisi catatan sensitif, grafik atas database didefinisikan dengan menambahkan tepi antara dua database jika dan hanya jika mereka berbeda dalam catatan sensitif. Metrik di atas basis data sekarang diberikan oleh panjang jalur terpendek antara basis data dalam grafik ini. Ruang metrik ini memiliki properti bahwa basis data yang berbeda dengan catatan sensitif lebih dekat dibandingkan dengan basis data yang berbeda dalam catatan non-sensitif. Kami menggunakan ruang metrik yang diusulkan untuk menentukan privasi sensitif, yang memungkinkan kami untuk menyesuaikan keseimbangan antara akurasi dan privasi.