זירת AI

יצירת נתונים סינתטיים תוך שמירה על פרטיות דיפרנציאלית עבור מסדי נתונים יחסיים

מאת Kaveh Alim, Hao Wang, Ojas Gulati, Akash Srivastava, Navid Azizan · פורסם: · עודכן:

המחקר מציע מסגרת ליצירת מסדי נתונים סינתטיים עם פרטיות דיפרנציאלית, המשמרת גם קשרים בין טבלאות ולא רק את תוכנן. במקום לשטח את המסד לטבלה אחת גדולה, השיטה מתחילה בטבלאות סינתטיות שנוצרו באמצעות כלים קיימים, ולומדת ביניהן קשרים באמצעות ייצוג כגרף דו־צדדי. בכל סבב נבחרות באופן פרטי התפלגויות משותפות שבהן הפער מהנתונים המקוריים גדול, נמדדות תשובות רועשות, ומעודכנת מטריצת הקשרים באמצעות אופטימיזציה רציפה. אלגוריתם דגימה בלתי מוטה הופך את המשקלים לקשרים בדידים, תוך שמירה על מספר קשרים קבוע. המחברים מספקים הוכחות לפרטיות, להתכנסות ולשגיאות קירוב, ומציעים חיתוך אקראי של המטריצה לשיפור המדרגיות. ניסויים ב־MovieLens וב־IPUMS, בשילוב מחוללי הטבלאות AIM ו־MST, מראים שיפור בהתאמת התפלגויות עם הגדלת תקציב הפרטיות. עם זאת, ערבות התועלת המרכזית מוגבלת לגרסה חד־סבבית ללא דגימה, והניסויים אינם מוכיחים שימור של כלל תכונות המסד או ביצועים במשימות למידה בהמשך.

יישומי המאמר

ארגונים יכולים ליצור עותק סינתטי של מידע המאוחסן בכמה טבלאות מקושרות, במקום לשתף את הרשומות המקוריות. לדוגמה, אפשר ליצור טבלאות מלאכותיות של תלמידים ומורים, וגם קשרי הרשמה ביניהם, תוך הגנה פורמלית על מידע אישי ושימור חלק מהדפוסים הסטטיסטיים החשובים. היתרון המעשי הוא האפשרות להשתמש בכלים קיימים ליצירת טבלאות פרטיות, ולהוסיף להם שכבה שלומדת את הקשרים בין הטבלאות. כך אין צורך לאחד מראש את כל הנתונים לטבלה ענקית, פעולה שעלולה לייצר כפילויות, להגדיל עלויות ולפגוע במבנה הנתונים. יישומים אפשריים כוללים בדיקות תוכנה ומסדי נתונים, בניית צינורות עיבוד, המחשות וניתוח ראשוני בתחומים כמו בריאות, פיננסים וממשל. עם זאת, המחקר בדק בעיקר התאמה של התפלגויות סטטיסטיות פשוטות, ולא הוכיח שהמידע מתאים לכל משימת חיזוי או להחלטות בעלות השלכות אישיות.

פירוט המאמר

הבעיה והמטרה

רוב השיטות ליצירת נתונים סינתטיים תחת פרטיות דיפרנציאלית מתמקדות בטבלה יחידה, בעוד שמידע ארגוני נשמר בדרך כלל במספר טבלאות מקושרות. יצירה נפרדת של טבלאות אינה משמרת בהכרח את הקשרים ביניהן. מנגד, איחוד המסד לטבלה אחת עלול ליצור כפילויות, ערכים חסרים, עומס חישובי ואי־בהירות לגבי זהות הרשומות כאשר מפרקים את התוצאה בחזרה. חזרת אותה רשומה במספר שורות גם עלולה להגדיל את רגישות השאילתות ואת הרעש הנדרש להגנת הפרטיות. מטרת המחקר היא להוסיף למחוללי טבלאות קיימים מנגנון לשחזור קשרים, שישמר סטטיסטיקות שימושיות ושלמות הפניות.

ייצוג הנתונים ויעד השימור

המסגרת התאורטית העיקרית מתארת שתי טבלאות כגרף דו־צדדי: כל רשומה היא צומת, וכל קשר בין רשומות מיוצג בכניסה בינארית במטריצת קשרים. המחברים מניחים חסם ידוע על מספר הקשרים של רשומה. יעד האיכות הוא שימור התפלגויות שוליות מסדר נמוך, לרבות התפלגויות משותפות של מאפיינים מטבלאות שונות. לדוגמה, אפשר למדוד את שיעור הקשרים המחברים תלמיד מקבוצת גיל מסוימת למורה ממחלקה מסוימת. התצפית המתמטית המרכזית היא שכאשר הטבלאות ומספר הקשרים קבועים, תשובות לשאילתות כאלה הן פונקציות ליניאריות של מטריצת הקשרים.

האלגוריתם המוצע

תחילה מייצרים כל טבלה סינתטית באמצעות מנגנון בעל פרטיות דיפרנציאלית, ללא תלות במשפחה מסוימת של מחוללים. לאחר מכן לומדים את הקשרים בין הטבלאות. הניסוח המקורי מבקש למזער את שגיאת הקירוב המרבית בשאילתות חוצות־טבלאות, אך בחירת מטריצה בינארית היא בעיה קומבינטורית קשה. לכן האלגוריתם פועל באיטרציות: מנגנון אקספוננציאלי בוחר קבוצות מאפיינים בעלות פער גדול בין ההתפלגות המקורית לסינתטית, ומנגנון גאוסי מוסיף רעש לתשובות המקוריות. על בסיס המדידות שנאספו נפתרת בעיית ריבועים פחותים עם משקלי קשר רציפים בין אפס לאחד וסכום קשרים קבוע. הפתרון הרציף מחושב בירידת גרדיאנט מוקרנת. לאחר כל צעד מקרינים את הווקטור בחזרה לתחום המותר באמצעות הזזה משותפת וקיטום לטווח התקין. המחברים מוכיחים קצב התכנסות של אחד חלקי מספר צעדי האופטימיזציה. העלות ליניארית במספר כל הקשרים האפשריים בין הטבלאות, כאשר ממדי השאילתות, מספר הצעדים והדיוק מוחזקים קבועים. חשוב להבחין: זה אינו זמן ליניארי במספר הרשומות או במספר הקשרים הקיימים, משום שמספר הקשרים האפשריים הוא מכפלת גדלי הטבלאות.

דגימה ושלמות מבנית

לאחר האופטימיזציה צריך להמיר משקלים לקשרים בדידים. דגימות ברנולי עצמאיות אינן מבטיחות מספר קשרים קבוע, ודגימה חוזרת תוך דחיית כפילויות עלולה להיות מוטה. האלגוריתם המוצע מקבץ הסתברויות לקבוצות שסכומן אינו עולה על אחד, משתמש רקורסיבית בהסתברויות המשלימות לבחירת קבוצות להחרגה, ובוחר איבר אחד מכל קבוצה שנשארה. כך נשמרים בדיוק מספר הקשרים והסתברות ההכללה של כל קשר. המחברים מוכיחים גם תלות שלילית בין המשתנים, המאפשרת לגזור חסמי ריכוז לשגיאת הדגימה. עבור יחיד־לרבים, אילוץ של קשר אחד לכל רשומת ילד מפשט את האופטימיזציה ואת הדגימה ומונע רשומות ילד יתומות.

פרטיות וערבויות תועלת

הגנת הפרטיות מתייחסת לשינוי ערכי רשומה אחת וכל הקשרים הקשורים אליה. הוכחת הפרטיות המפורטת משתמשת בגרסה חסומה שבה מספר הקשרים הכולל זהה במסדים שכנים. באמצעות חשבונאות של פרטיות דיפרנציאלית מרוכזת והרכבת מנגנונים מתקבלת ערבות כוללת שסוכמת את תקציבי הפרטיות של מחוללי הטבלאות ושל שלב הקשרים. האופטימיזציה והדגימה הן עיבוד המשך של תוצאות פרטיות ואינן צורכות תקציב נוסף. ערבות התועלת המרכזית חוסמת את השגיאה הממוצעת הריבועית באמצעות שמונה פעמים השגיאה הטובה ביותר האפשרית עבור הטבלאות הנתונות, בתוספת איבר פרטיות היורד עם גידול מספר הקשרים המקוריים. אולם היא מוכחת לסבב יחיד, למדידת כלל קבוצות המאפיינים, ולפני הדגימה הבדידה.

מדרגיות והערכה ניסויית

כדי להתמודד עם מטריצות גדולות מוצע חיתוך אקראי: מאחסנים את הקשרים באופן דליל, בוחרים תת־קבוצה מכל טבלה, מעדכנים רק את תת־המטריצה ומחזירים אותה למסד. בחירת שיעור טאו מכל טבלה מקטינה את ממד העדכון בגורם טאו בריבוע. זהו פתרון היוריסטי למגבלות זיכרון וזמן, ולא הרחבה מוכחת של ערבות התועלת. המימוש מבוסס PyTorch, והניסויים בוצעו בכרטיס NVIDIA V100 עם זיכרון של 16 גיגה־בייט. ההערכה השתמשה ב־MovieLens ובנתוני מפקד האוכלוסין IPUMS. ב־MovieLens נכללו 6,040 משתמשים ו־3,883 סרטים; קשרי הדירוג צומצמו ל־10,075 תוך הגבלת דרגת כל רשומה לעשרה. ב־IPUMS נבחרו 168,669 רשומות וקשרי הורות עם חסם דרגה ארבע, ונוצרה טבלה סינתטית בת 10,000 רשומות. הטבלאות נוצרו באמצעות AIM או MST, בתקציב אפסילון אחד לכל טבלה. מדד ההערכה היה שגיאה ממוצעת בשוליים תלת־ממדיים חוצי־טבלאות. הגדלת תקציב הפרטיות לשלב הקשרים הורידה את השגיאה ואת שונותה. מספר הסבבים הציג לרוב פשרה בצורת U, עם תוצאות מיטביות סביב 10–15 סבבים.

משמעות ומגבלות

התרומה העיקרית היא הפרדת יצירת תוכן הטבלאות מלמידת הקשרים, תוך שילוב גמיש של כלים קיימים והוכחות לכמה רכיבי ליבה. עם זאת, הניסויים מתמקדים בשני מאגרים ובניתוח פרמטרים, ואינם מציגים השוואה ישירה רחבה למחוללים יחסיים מתחרים או בדיקות ביצועים במשימות למידה downstream. איכות הקשרים מוגבלת גם באיכות הטבלאות שנוצרו מראש. שימור התפלגויות נמוכות־סדר אינו מבטיח שימור לוגיקה עסקית, דינמיקה זמנית או כל אילוץ רצוי. המחברים מציעים לחקור בהמשך יצירה משותפת של טבלאות וקשרים, שילוב מידע ציבורי ואכיפת אילוצים נוספים.

היילייטס

  • המסגרת מוסיפה קשרים פרטיים לטבלאות סינתטיות קיימות, ותומכת בקשרי רבים־לרבים ובגרסה מותאמת של יחיד־לרבים, ללא שיטוח המסד.
  • אלגוריתם הדגימה משמר בדיוק את מספר הקשרים המבוקש ואת הסתברות ההכללה של כל קשר; זמן ריצתו ליניארי במספר הקשרים האפשריים.
  • הוכחות הפרטיות נשענות על חסם למספר הקשרים של רשומה ועל הגדרת שכנות שבה מספר הקשרים הכולל קבוע; ערבות התועלת המרכזית מתייחסת לסבב יחיד ללא דגימה.
  • בניסויים בשני מאגרים ובשני מחוללי טבלאות, הגדלת תקציב הפרטיות הפחיתה שגיאות בהתפלגויות חוצות־טבלאות; מספר הסבבים המועיל ביותר היה בדרך כלל 10–15.

שאלות נפוצות

כיצד יוצרים נתונים סינתטיים לכמה טבלאות מקושרות תוך הגנה על הפרטיות?

מייצרים תחילה כל טבלה סינתטית באמצעות כלי בעל פרטיות דיפרנציאלית, ולאחר מכן לומדים בנפרד את הקשרים בין הטבלאות באמצעות מדידות מוגנות ברעש. כך אפשר ליצור, למשל, רשומות מלאכותיות של תלמידים ומורים לצד קשרי הרשמה ביניהם, בלי לשתף את הרשומות המקוריות. המסגרת נועדה לשמר התפלגויות סטטיסטיות גם בין טבלאות, והגנת הפרטיות שלה כפופה להנחות מוגדרות, ובהן חסם על מספר הקשרים של כל רשומה.

מדוע לא פשוט לאחד את כל הטבלאות לפני יצירת הנתונים הסינתטיים?

איחוד מסד נתונים יחסי לטבלה אחת עלול ליצור כפילויות, ערכים חסרים ועומס חישובי. כאשר אותה רשומה מופיעה בשורות רבות, גם רגישות השאילתות עלולה לגדול, ועמה כמות הרעש הנדרשת להגנת הפרטיות. הפרדת יצירת הטבלאות מלמידת הקשרים מאפשרת להשתמש במחוללים קיימים, כגון AIM ו־MST, בלי לשטח מראש את המסד ובלי להתמודד עם הקושי לשחזר את מבנה הרשומות לאחר מכן.

לאילו שימושים מתאימים נתונים סינתטיים יחסיים, ומה חשוב לבדוק לפני השימוש?

שימושים אפשריים כוללים בדיקות תוכנה ומסדי נתונים, בניית צינורות עיבוד, המחשות וניתוח ראשוני בתחומי הבריאות, הפיננסים והממשל. עם זאת, שימור התפלגויות סטטיסטיות אינו מבטיח התאמה לכל משימת חיזוי, שימור לוגיקה עסקית או עמידה בכל אילוצי המסד. לפני שימוש מעשי יש לבדוק את איכות הנתונים ביחס למשימה המיועדת; הניסויים אינם מוכיחים התאמה לקבלת החלטות בעלות השלכות אישיות.

כיצד האלגוריתם לומד קשרים בין טבלאות סינתטיות?

האלגוריתם מייצג שתי טבלאות כגרף דו־צדדי: הרשומות הן צמתים, והקשרים ביניהן מיוצגים במטריצה. בכל סבב נבחרות באופן פרטי קבוצות מאפיינים שבהן קיים פער גדול בין ההתפלגות המקורית לסינתטית, ונאספות עבורן מדידות בתוספת רעש גאוסי. לאחר מכן נפתרת בעיית אופטימיזציה עם משקלי קשר רציפים בין אפס לאחד וסכום קשרים קבוע. לבסוף, דגימה בלתי מוטה ממירה את המשקלים לקשרים בדידים, תוך שימור מדויק של מספר הקשרים והסתברות ההכללה של כל קשר.

כיצד תקציב הפרטיות ומספר הסבבים משפיעים על איכות הנתונים?

בניסויים ב־MovieLens וב־IPUMS, הגדלת תקציב הפרטיות של שלב הקשרים הפחיתה את השגיאה ואת שונותה בהתפלגויות חוצות־טבלאות. המשמעות היא פשרה: תקציב פרטיות גדול יותר מאפשר בדרך כלל דיוק גבוה יותר, אך מעניק הגנת פרטיות חלשה יותר. גם הוספת סבבים אינה משפרת תמיד את התוצאה; בניסויים התקבלו לרוב התוצאות הטובות ביותר סביב 10–15 סבבים. אלו ממצאים ניסויים, ולא כלל שמבטיח תוצאה דומה בכל מסד נתונים.

מה מבטיחות ההוכחות התאורטיות, והיכן נמצאות מגבלותיהן?

הוכחת הפרטיות מכסה שינוי בערכי רשומה אחת ובקשרים הקשורים אליה, תחת חסם על מספר קשריה ובהגדרת שכנות שבה מספר הקשרים הכולל קבוע. תקציב הפרטיות הכולל משלב את יצירת הטבלאות ואת מדידות הקשרים; האופטימיזציה והדגימה הן עיבוד המשך ואינן צורכות תקציב נוסף. לעומת זאת, ערבות התועלת המרכזית מוגבלת לסבב יחיד, למדידת כלל קבוצות המאפיינים ולשלב שלפני הדגימה הבדידה. היא אינה מבטיחה שימור של כלל תכונות המסד או הצלחה במשימות למידה בהמשך.

מחקרים קשורים