केडीडी 2018, डे वन, ट्यूटोरियल

वर्ष का एक मुख्य डेटा विज्ञान सम्मेलन आज लंदन में शुरू हो गया है। मैं जल्द ही इस बारे में बात करने की कोशिश करूँगा कि सुनने में दिलचस्प क्या था।

शुरुआत घबराई हुई थी: उसी दिन, उसी केंद्र में यहोवा के साक्षियों की एक सामूहिक बैठक आयोजित की गई थी, इसलिए केडीडी पंजीकरण डेस्क को खोजना आसान नहीं था, और जब मैंने आखिरकार यह पाया, तो लाइन 150-200 मीटर लंबी थी। फिर भी, ~ 20 मिनट के इंतजार के बाद, उसे एक प्रतिष्ठित बैज मिला और वह एक मास्टर क्लास में गया।

डेटा विश्लेषण में गोपनीयता

पहली कार्यशाला डेटा विश्लेषण में गोपनीयता बनाए रखने के लिए समर्पित थी। शुरुआत में, मुझे देर हो गई थी, लेकिन, जाहिर है, मुझे कुछ भी खोना नहीं था - उन्होंने इस बारे में बात की कि गोपनीयता कितनी महत्वपूर्ण है और हमलावर निजी जानकारी का कितना बुरा उपयोग कर सकते हैं, इसका खुलासा किया गया है। वैसे, Google, लिंक्डइन और ऐप्पल के काफी सम्मानित लोग बताते हैं। मास्टर वर्ग के परिणामस्वरूप बहुत सकारात्मक प्रभाव पड़ा, स्लाइड्स यहां सभी उपलब्ध हैं ।

यह पता चलता है कि डिफरेंशियल प्राइवेसी की अवधारणा लंबे समय से अस्तित्व में है, जिसका विचार शोर को जोड़ना है जो सच्चे व्यक्तिगत मूल्यों को स्थापित करना मुश्किल बनाता है, लेकिन सामान्य वितरण को पुनर्स्थापित करने की क्षमता को बनाए रखता है। वास्तव में, दो पैरामीटर हैं: e - डेटा का खुलासा करना कितना मुश्किल है, और d - उत्तर कितने विकृत हैं।

मूल अवधारणा बताती है कि विश्लेषक और डेटा - "क्यूरेटर" के बीच किसी प्रकार का मध्यवर्ती लिंक है, यह वह है जो सभी अनुरोधों को संसाधित करता है और प्रतिक्रियाएं उत्पन्न करता है ताकि शोर निजी डेटा को अस्पष्ट कर दे। वास्तव में, स्थानीय विभेदक गोपनीयता मॉडल अक्सर उपयोग किया जाता है, जिसमें उपयोगकर्ता का डेटा उपयोगकर्ता के डिवाइस पर रहता है (उदाहरण के लिए, एक मोबाइल फोन या पीसी), हालांकि, जब डेवलपर के अनुरोधों का जवाब देते हैं, तो आवेदन व्यक्तिगत डिवाइस से एक डेटा पैकेट भेजता है जो यह पता लगाने की अनुमति नहीं देता है कि वास्तव में क्या है। इस विशेष उपयोगकर्ता ने उत्तर दिया। यद्यपि, बड़ी संख्या में उपयोगकर्ताओं से प्रतिक्रियाएं जोड़ते समय, आप उच्च सटीकता के साथ समग्र चित्र को पुनर्स्थापित कर सकते हैं।

एक अच्छा उदाहरण है "क्या आपका गर्भपात हुआ है" सर्वेक्षण? यदि आप "माथे पर" एक सर्वेक्षण करते हैं, तो कोई भी सच नहीं बताएगा। लेकिन अगर आप सर्वेक्षण को इस प्रकार व्यवस्थित करते हैं: "एक सिक्का टॉस करें, अगर कोई ईगल है, तो उसे फिर से फेंक दें और ईगल को" हाँ "कहें, लेकिन" नहीं "पूंछ पर, अन्यथा सच्चाई का जवाब दें", व्यक्तिगत गोपनीयता बनाए रखते हुए सच्चे वितरण को पुनर्स्थापित करना आसान है। इस विचार का विकास संवेदनशील आँकड़े Google RAPPOR (RAndomized Privacy-Preserves Ord Ord Report) एकत्र करने का मैकेनिक्स था, जिसका उपयोग क्रोम और इसके कांटे के उपयोग पर डेटा एकत्र करने के लिए किया गया था।

ओपन सोर्स में क्रोम की रिहाई के तुरंत बाद, काफी बड़ी संख्या में लोग दिखाई दिए, जो एक ओवरराइड होम पेज, सर्च इंजन, अपने स्वयं के विज्ञापन पासा, आदि के साथ अपना ब्राउज़र बनाना चाहते थे। स्वाभाविक रूप से, उपयोगकर्ता और Google इस बारे में उत्साहित नहीं थे। आगे की कार्रवाइयाँ आमतौर पर समझ में आती हैं: सबसे सामान्य प्रतिस्थापनों का पता लगाने और प्रशासनिक रूप से कुचलने के लिए, लेकिन अप्रत्याशित रूप से सामने आया ... क्रोम की गोपनीयता नीति ने Google को उपयोगकर्ता के होमपेज और खोज इंजन को स्थापित करने के बारे में जानकारी लेने और इकट्ठा करने की अनुमति नहीं दी :(

इस सीमा को पार करने और RAPPOR को बनाने के लिए, जो निम्नानुसार काम करता है:

1. होम पेज पर डेटा एक छोटा, लगभग 128 बिट, ब्लूम फ़िल्टर में दर्ज किया गया है।
2. स्थायी सफेद शोर इस ब्लूम फ़िल्टर में जोड़ा जाता है। स्थायी = इस उपयोगकर्ता के लिए, शोर को बचाने के बिना, कई अनुरोध उपयोगकर्ता डेटा को प्रकट कर सकते हैं।
3. निरंतर शोर के ऊपर, प्रत्येक अनुरोध के लिए उत्पन्न व्यक्तिगत शोर सुपरिंपोज किया जाता है।
4. परिणामस्वरूप बिट वेक्टर Google को भेजा जाता है, जहां समग्र चित्र का डिक्रिप्शन शुरू होता है।
5. सबसे पहले, सांख्यिकीय विधियों द्वारा हम समग्र चित्र से शोर के प्रभाव को घटाते हैं।
6. अगला, हम उम्मीदवार बिट वैक्टर (सिद्धांत में सबसे लोकप्रिय साइट / खोज इंजन) का निर्माण करते हैं।
7. एक आधार के रूप में प्राप्त वैक्टर का उपयोग करते हुए, हम तस्वीर को फिर से बनाने के लिए एक रेखीय प्रतिगमन का निर्माण करते हैं।
8. अप्रासंगिक उम्मीदवारों को दबाने के लिए LASSO के साथ रैखिक प्रतिगमन को मिलाएं।

योजना के अनुसार, फ़िल्टर का निर्माण इस तरह दिखता है:



RAPPOR को लागू करने का अनुभव बहुत सकारात्मक रहा और इसकी मदद से एकत्र किए गए निजी आंकड़ों की संख्या तेजी से बढ़ रही है। मुख्य सफलता कारकों में, लेखकों ने पहचान की:

1. मॉडल की सादगी और स्पष्टता।
2. कोड का खुलापन और प्रलेखन।
3. त्रुटियों की सीमाओं के अंतिम रेखांकन पर उपस्थिति।

हालांकि, इस दृष्टिकोण में एक महत्वपूर्ण सीमा है: डिक्रिप्शन के लिए उम्मीदवार के उत्तर की सूची होना आवश्यक है (यही वजह है कि ओ - साधारण)। जब Apple ने पाठ संदेशों में प्रयुक्त शब्दों और इमोजी के बारे में आंकड़े एकत्र करना शुरू किया, तो यह स्पष्ट हो गया कि यह दृष्टिकोण अच्छा नहीं था। परिणामस्वरूप, WDC-2016 सम्मेलन में, iOS पर घोषित शीर्ष नई विशेषताओं में से एक अंतर गोपनीयता का अतिरिक्त था। अतिरिक्त शोर के साथ एक स्केच संरचना का संयोजन भी आधार के रूप में इस्तेमाल किया गया था, हालांकि, कई तकनीकी समस्याओं को हल करना पड़ा:

1. ग्राहक (टेलीफोन) को इस उत्तर को उचित समय में बनाने और संग्रहीत करने में सक्षम होना चाहिए।
2. इसके अलावा, इस प्रतिक्रिया को एक सीमित आकार के नेटवर्क संदेश में पैक किया जाना चाहिए।
3. Apple की ओर से, यह सभी उचित समय में एकत्रित होना चाहिए।

नतीजतन, हम एन्कोडिंग शब्दों के लिए काउंट-मिन-स्केच का उपयोग करते हुए एक योजना के साथ आए, फिर हमने यादृच्छिक रूप से केवल एक हैश फ़ंक्शंस की प्रतिक्रिया का चयन किया (लेकिन उपयोगकर्ता / शब्द जोड़ी के लिए पसंद को ठीक करने के साथ), वेक्टर का उपयोग करके डैमर्ड ट्रांसफ़ॉर्म और केवल सर्वर पर भेजा गया चयनित हैश फ़ंक्शन के लिए एक महत्वपूर्ण "बिट"।

सर्वर पर परिणाम को पुनर्स्थापित करने के लिए, उम्मीदवार परिकल्पना की समीक्षा करना भी आवश्यक था। लेकिन, यह पता चला कि एक बड़े शब्दकोश आकार के साथ यह एक क्लस्टर के लिए भी जटिल है। यह किसी भी तरह से खोज के सबसे आशाजनक क्षेत्रों का चयन करने के लिए आवश्यक था। शुरुआती बिंदुओं के रूप में बिगग्राम का उपयोग करने के साथ प्रयोग, जिसमें से आप फिर मोज़ेक को इकट्ठा कर सकते हैं, असफल था - सभी बड़े समान रूप से लोकप्रिय थे। बिग्राम + शब्द हैश दृष्टिकोण ने समस्या को हल किया, लेकिन गोपनीयता का उल्लंघन हुआ। नतीजतन, हम उपसर्ग पेड़ों पर बसे: शब्द के शुरुआती हिस्सों और फिर पूरे शब्द पर आंकड़े एकत्र किए गए थे।

हालांकि, अनुसंधान समुदाय द्वारा Apple द्वारा उपयोग किए जाने वाले गोपनीयता एल्गोरिदम के विश्लेषण से पता चला है कि गोपनीयता को अभी भी दीर्घकालिक आंकड़ों के साथ समझौता किया जा सकता है ।

उपयोगकर्ता वेतन के वितरण के अपने अध्ययन के साथ लिंक्डइन एक अधिक कठिन स्थिति में था। तथ्य यह है कि अंतर गोपनीयता अच्छी तरह से काम करती है जब हमारे पास बहुत बड़ी संख्या में माप होते हैं, अन्यथा शोर को मज़बूती से निकालना संभव नहीं है। वेतन सर्वेक्षण में, रिपोर्ट की संख्या सीमित है, और लिंक्डइन ने एक अलग रास्ता लेने का फैसला किया: तकनीकी बेनामी और साइबर स्पेस टूल को k-Anonymity की अवधारणा के साथ संयोजित करें: उपयोगकर्ता डेटा को पर्याप्त रूप से प्रच्छन्न माना जाता है यदि आप इसे एक पैकेट में जमा करते हैं जहां एक ही इनपुट विशेषताओं के साथ k उत्तर हैं (उदाहरण के लिए, स्थान और पेशा) जो केवल लक्ष्य चर (वेतन) में भिन्न होता है।

नतीजतन, एक जटिल कन्वेयर का निर्माण किया गया था जिसमें विभिन्न सेवाएं एक-दूसरे को डेटा के टुकड़े संचारित करती हैं, लगातार एन्क्रिप्ट करती रहती हैं ताकि एक मशीन उन्हें पूरी तरह से खोल न सके। नतीजतन, उपयोगकर्ताओं को सहकर्मियों में विशेषताओं से विभाजित किया जाता है, और जब कोहोर्ट न्यूनतम आकार तक पहुंच जाता है, तो इसके आंकड़े विश्लेषण के लिए एचडीएफएस पर जाते हैं।



टाइमस्टैम्प विशेष ध्यान देने योग्य है: इसे भी नामांकित करने की आवश्यकता है, अन्यथा आप यह पता लगा सकते हैं कि किसका उत्तर कॉल का लॉग है। लेकिन मैं पूरी तरह से समय नहीं निकालना चाहता, क्योंकि यह डायनामिक्स का पालन करना दिलचस्प है। नतीजतन, हमने उन विशेषताओं के लिए टाइमस्टैम्प जोड़ने का फैसला किया, जिनके द्वारा कॉहर्ट बनाया गया है, और इसमें इसका औसत औसत है।

परिणाम एक दिलचस्प प्रीमियम सुविधा है और कुछ दिलचस्प खुले-अंत प्रश्न हैं:
GDPR का सुझाव है कि, अनुरोध पर, हमें सभी उपयोगकर्ता डेटा को हटाने में सक्षम होना चाहिए, लेकिन हमने इसे छिपाने की कोशिश की ताकि अब हम यह नहीं जान सकें कि यह किसका डेटा है। बड़ी संख्या में विभिन्न स्लाइस / कोहॉर्ट्स पर डेटा होने से, आप मैचों को अलग कर सकते हैं और खुली विशेषताओं की सूची का विस्तार कर सकते हैं

यह दृष्टिकोण बड़े डेटा के लिए काम करता है, लेकिन निरंतर डेटा के साथ काम नहीं करता है। अभ्यास से पता चलता है कि बस डेटा का नमूना लेना एक अच्छा विचार नहीं है, लेकिन NIPS2017 में Microsoft ने इसके साथ काम करने के तरीके पर एक समाधान प्रस्तावित किया। दुर्भाग्य से, विवरणों का खुलासा करने का समय नहीं था।

बड़ा ग्राफ विश्लेषण

बड़े रेखांकन के विश्लेषण पर दूसरी कार्यशाला दोपहर में शुरू हुई। इस तथ्य के बावजूद कि वह Google के लोगों के नेतृत्व में भी था, और उससे अधिक अपेक्षाएं थीं, वह उसे बहुत कम पसंद करता था - उन्होंने अपनी बंद प्रौद्योगिकियों के बारे में बात की, फिर भोज और सामान्य दर्शन में पड़ गए, फिर जंगली विवरणों में डूब गए, यहां तक ​​कि कार्य को तैयार करने का समय भी नहीं था। फिर भी, मैं कुछ दिलचस्प पहलुओं को पकड़ने में सक्षम था। स्लाइड यहां देख सकते हैं ।

सबसे पहले, मुझे अहंकार-नेटवर्क क्लस्टरिंग नामक योजना पसंद आई, मुझे लगता है कि इसके आधार पर दिलचस्प समाधान बनाना संभव है। विचार बहुत सरल है:

1. हम एक विशिष्ट उपयोगकर्ता के दृष्टिकोण से स्थानीय ग्राफ पर विचार करते हैं, लेकिन स्वयं माइनस।
2. हम इस ग्राफ को क्लस्टर करते हैं।
3. इसके बाद, हम अपने उपयोगकर्ता के शीर्ष को "क्लोन" करते हैं, प्रत्येक क्लस्टर में एक उदाहरण जोड़ते हैं और किनारों द्वारा उन्हें एक-दूसरे से नहीं जोड़ते हैं।

समान रूप से परिवर्तित ग्राफ में, कई समस्याओं को अधिक आसानी से हल किया जाता है और रैंकिंग एल्गोरिदम क्लीनर का काम करते हैं। उदाहरण के लिए, इस तरह के ग्राफ को संतुलित तरीके से विभाजित करना बहुत आसान है, और दोस्तों की सिफारिश में रैंकिंग करते समय, पुल नोड्स बहुत कम शोर होते हैं। यह इस कार्य के लिए था कि ENC के मित्रों की सिफारिशों को माना / प्रचारित किया गया था।

लेकिन सामान्य तौर पर, ENC सिर्फ एक उदाहरण था, Google में एक पूरा विभाग ग्राफ़ पर एल्गोरिदम विकसित करने और उन्हें एक पुस्तकालय के रूप में अन्य विभागों को आपूर्ति करने में लगा हुआ है। पुस्तकालय की घोषित कार्यक्षमता प्रभावशाली है: एसएनए के लिए एक सपना पुस्तकालय, लेकिन सब कुछ बंद है। सबसे अच्छे मामले में, व्यक्तिगत ब्लॉकों को लेखों द्वारा पुन: पेश करने की कोशिश की जा सकती है। यह दावा किया जाता है कि पुस्तकालय में Google के अंदर सैकड़ों कार्यान्वयन हैं, जिनमें ट्रिलियन किनारों से अधिक ग्राफ शामिल हैं।

तब MapReduce मॉडल के प्रचार में लगभग 20 मिनट थे, जैसे कि हम नहीं जानते कि यह कितना अच्छा था। जिसके बाद लोगों ने दिखाया कि रैंडमाइज्ड कॉन्सटेबल कोर सेट्स मॉडल का उपयोग करके कई जटिल समस्याओं (लगभग) को हल किया जा सकता है। मुख्य विचार यह है कि किनारों के बारे में डेटा बेतरतीब ढंग से एन नोड्स में बिखरे हुए हैं, वहां उन्हें मेमोरी में खींच लिया जाता है और समस्या को स्थानीय रूप से हल किया जाता है, जिसके बाद समाधान के परिणाम केंद्रीय मशीन में स्थानांतरित होते हैं और एकत्र होते हैं। यह तर्क दिया जाता है कि इस तरह से आप कई समस्याओं के लिए सस्ते अनुमान प्राप्त कर सकते हैं: कनेक्टिविटी घटक, न्यूनतम फैले जंगल, अधिकतम मिलान, अधिकतम कवरेज, आदि। कुछ मामलों में, एक ही समय में, दोनों मैपर करते हैं और एक ही समस्या को हल करते हैं, लेकिन वे थोड़ा अलग हो सकते हैं। एक सरल समाधान का नाम कैसे दिया जाए, इसका एक अच्छा उदाहरण है ताकि लोग इस पर विश्वास करें।

फिर इस बारे में बातचीत हुई कि मैं यहाँ किसके लिए जा रहा था: बैलेंस्ड ग्राफ़ पार्टिशनिंग। यानी कैसे एन भागों में एक ग्राफ को काटने के लिए ताकि भागों का आकार लगभग बराबर हो, और भागों के अंदर बॉन्ड की संख्या बाहरी बॉन्ड की संख्या से काफी अधिक हो। यदि आप इस तरह की समस्या को अच्छी तरह से हल करने में सक्षम हैं, तो कई एल्गोरिदम आसान हो जाते हैं, और यहां तक ​​कि ए / बी परीक्षण वायरल प्रभाव के मुआवजे के साथ और अधिक कुशलता से चलाया जा सकता है। लेकिन कहानी थोड़ा निराश करती है, सब कुछ एक "सूक्ति योजना" की तरह लग रहा था: पदानुक्रमित चक्कर क्लस्टरिंग, चाल, असंतुलन जोड़ने पर आधारित संख्या असाइन करें। कोई विवरण नहीं। केडीडी पर इस बारे में बाद में उनकी एक अलग रिपोर्ट होगी, मैं जाने की कोशिश करूंगा। साथ ही एक ब्लॉग पोस्ट है ।



फिर भी, उन्होंने कुछ प्रतियोगियों के साथ तुलना की, उनमें से कुछ खुले हैं: स्पिनर , एफबी से यूबी 13, माइक्रोसॉफ्ट से फेनियल , मेटिस । आप उन्हें भी देख सकते हैं।

फिर हमने तकनीकी विवरण के बारे में थोड़ी बात की। वे रेखांकन के साथ काम करने के लिए कई प्रतिमानों का उपयोग करते हैं:

1. फ्लूम के शीर्ष पर MapReduce। मुझे नहीं पता था कि यह संभव था - फ्लूम को इकट्ठा करने के लिए इंटरनेट पर बहुत नहीं लिखा गया है, लेकिन डेटा का विश्लेषण करने के लिए नहीं। मुझे लगता है कि यह एक इंट्रा-गूगल विकृति है। UPD: मुझे पता चला कि यह वास्तव में एक आंतरिक Google उत्पाद है, इसका Apache Flume से कोई लेना-देना नहीं है, क्लाउड में कुछ ersatz है जिसे डेटाफ्लो कहा जाता है
2. MapReduce + वितरित हैश टेबल। वे कहते हैं कि यह एमपी राउंड की संख्या को काफी कम करने में मदद करता है, लेकिन इंटरनेट पर इस तकनीक के बारे में बहुत कुछ नहीं लिखा गया है, उदाहरण के लिए, यहां
3. प्रागेल - वे कहते हैं कि वह जल्द ही मर जाएगा।
4. ASYnchronous Message Passing सबसे शांत, सबसे तेज़ और सबसे आशाजनक है।

ASYMP का विचार प्रागेल के समान है:

1. नोड वितरित किए जाते हैं, अपना राज्य रखते हैं और पड़ोसियों को संदेश भेज सकते हैं;
2. मशीन को प्राथमिकताओं के साथ एक कतार बनाया गया है, क्या भेजना है (ऑर्डर अतिरिक्त के क्रम से भिन्न हो सकता है);
3. एक संदेश प्राप्त होने पर, नोड राज्य को बदल सकता है या नहीं भी कर सकता है; बदलते समय, हम पड़ोसियों को संदेश भेजते हैं;
4. सभी कतारें खाली होने पर समाप्त करें।

उदाहरण के लिए, जुड़े हुए घटकों की खोज करते समय, हम यादृच्छिक वेट यू [0,1] के साथ सभी छोरों को शुरू करते हैं, जिसके बाद हम कम से कम पड़ोसियों को एक-दूसरे को भेजना शुरू करते हैं। तदनुसार, पड़ोसियों से उनके न्यूनतम प्राप्त करने के बाद, हम उनके लिए न्यूनतम की तलाश कर रहे हैं, आदि, जब तक कि न्यूनतम को स्थिर नहीं किया जाता है। वे अनुकूलन के लिए एक महत्वपूर्ण बिंदु नोट करते हैं: संदेशों को एक नोड से हटाने के लिए (यह मोड़ है), केवल पिछले एक को छोड़कर। वे यह भी बात करते हैं कि नोड्स की स्थिति को बनाए रखते हुए असफलताओं से उबरना कितना आसान है।

वे कहते हैं कि वे समस्याओं के बिना बहुत तेज एल्गोरिदम का निर्माण करते हैं, यह सच प्रतीत होता है - अवधारणा सरल और तर्कसंगत है। प्रकाशन हैं ।

नतीजतन, निष्कर्ष खुद पता चलता है: बंद प्रौद्योगिकियों के बारे में कहानियों पर जाना दुखद है, लेकिन कुछ उपयोगी बिट्स को पकड़ा जा सकता है।