Định nghĩa Differential Privacy
Trước khi định nghĩa về Differential Privacy, cần mô hình hóa không gian dữ liệu Tập vũ trụ X bao gồm tất cả các bản ghi, và một bộ dữ liệu x được biểu diễn dưới dạng vector trong không gian N | X |, trong đó x i đại diện cho số lượng bản ghi loại i có trong x.
Để xác định khoảng cách giữa hai bộ dữ liệu trong không gian dữ liệu, chúng ta sử dụng định nghĩa sau: Khoảng cách giữa hai bộ dữ liệu x và y, với x, y thuộc N và |X| là kích thước của tập dữ liệu, được tính theo chuẩn l1 như sau: d(x,y) = ∥x−y∥1 = ∑ |Xi - Yi|.
Khoảng cách giữa hai bộ dữ liệu x và y thuộc tập N được xác định bởi khoảng cách Hamming, tức là số lượng bản ghi khác nhau giữa chúng Hai bộ dữ liệu x và y được xem là hàng xóm nếu chúng chỉ khác nhau một bản ghi duy nhất.
Differential Privacy cung cấp một nền tảng toán học vững chắc để đo lường rủi ro rò rỉ thông tin cá nhân Theo định nghĩa 1.3, một thuật toán ngẫu nhiên M được coi là (ε,δ)–DP nếu với mọi đầu ra, nó đảm bảo rằng sự khác biệt giữa các kết quả không làm lộ thông tin cá nhân.
OcủaM, và với mọi đầu vào hàng xóm D,D ′ ,
Khi δ = 0, thuật toán ngẫu nhiên M được coi là thuần tuý Differential Privacy Đối với bất kỳ thuật toán thuần tuý nào, với ε rất nhỏ, xác suất để quan sát một đầu ra cụ thể gần như không khác biệt đối với các dữ liệu đầu vào hàng xóm Điều này đảm bảo rằng không thể xác định chính xác một cá nhân từ tập dữ liệu hàng xóm của họ theo nghĩa xác suất.
Trong luận văn này, chúng tôi chỉ tập trung khai thác các thuật toán thuần tuý Differential Privacy.
Thuật toán đảm bảo tính riêng tư di động (DP) có đặc điểm quan trọng là kết quả cuối cùng vẫn duy trì tính riêng tư, ngay cả khi một thuật toán tùy ý được áp dụng lên đầu ra của thuật toán ban đầu Điều này giúp ngăn chặn việc khai thác thông tin qua xử lý hậu kỳ Theo Định lý 1.1, nếu A1 là thuật toán thỏa mãn ε–DP, thì bất kỳ thuật toán nào A2 áp dụng lên A1 cũng sẽ vẫn thỏa mãn ε–DP.
Chứng minh Gọi D,D ′ là hai dữ liệu hàng xóm,S là tập hợp đầu ra của
A1 vàt là một đầu ra tuỳ ý của thuật toánA2 Khi đó:
Trong định lý 1.2, thuật toán A1 được cho là thỏa mãn ε1-DP, trong khi A2 thỏa mãn ε2-DP Khi kết hợp hai thuật toán này, thuật toán tổng hợp A(D) = A2(A1(D), D) vẫn đảm bảo tính riêng tư với mức độ bảo vệ thông tin ε1 + ε2 Điều này cho thấy rằng việc sử dụng nhiều thuật toán DP với các tham số khác nhau trên cùng một đầu vào vẫn duy trì tính bảo mật cần thiết.
Chứng minh Gọi D,D ′ là hai dữ liệu hàng xóm,S là tập hợp đầu ra của
A1 vàt là một đầu ra tuỳ ý của thuật toánA2 Khi đó:
Ví dụ về mô hình Differential Privacy
Một tổ chức xã hội đã thực hiện khảo sát trực tuyến về hành vi hút thuốc lá của người dùng, trong đó Dwork đề xuất một thuật toán ngẫu nhiên để ghi lại kết quả khảo sát.
2 Nếu ra mặt sấp, ghi lại đúng hành vi của khách hàng.
3 Nếu ra mặt ngửa, tung đồng xu thêm một lần nữa.
4 Ở lần tung thứ hai, nếu ra mặt ngửa thì ghi có và ghi không nếu ra mặt sấp.
Bằng một vài tính toán xác suất, dễ thấy rằng đây là một thuật toán ln 3-
DP Ở đây, không mất tính tổng quát, giả sửO=”yes”, trường hợpO=”no” chứng minh hoàn toàn tương tự.
Pr[M(D ′ ) =O] = Pr[Response = Yes|Smoker ]
Pr[Response = Yes| Non-Smoker ] = 3/4
Thuật toán ngẫu nhiên cung cấp một mức độ bảo vệ thông tin cho người tham gia khảo sát, vì kết quả được ghi nhận một cách ngẫu nhiên thay vì cố định.
Cơ chế Laplace
Một trong những phương pháp cơ bản để thực hiện Differential Privacy là thêm nhiễu vào kết quả đầu ra Cơ chế Laplace áp dụng phân phối Laplace để thêm nhiễu vào các kết quả từ các truy vấn số như trung bình, trung vị, đếm số lượng phần tử và tổng các phần tử trong dữ liệu Tham số của cơ chế Laplace thay đổi tùy thuộc vào độ nhạy cảm của truy vấn Độ nhạy cảm toàn cục của hàm truy vấn số được định nghĩa là độ thay đổi tối đa trong kết quả của truy vấn khi có sự thay đổi nhỏ trong dữ liệu đầu vào.
1 trong đóD,D ′ lấy trên tât cả các dữ liệu đầu vào là hàng xóm của nhau.
Độ nhạy cảm của truy vấn thể hiện sự biến đổi của đầu ra khi có sự thay đổi nhỏ trong dữ liệu đầu vào Điều này giúp xác định lượng nhiễu cần thêm vào để che giấu sự thay đổi đó Theo định nghĩa 1.5, với mọi truy vấn số f, cơ chế Laplace sẽ thêm nhiễu vào đầu ra của f theo một công thức cụ thể.
ML(D,f(ã),ε):= f(D) + (Y 1 , ,Y k ) trong đóY i là biến ngẫu nhiên tuân theo phân phốiLap(∆f/ε)
Khi độ nhạy cảm ∆f tăng cao, để giảm thiểu rủi ro rò rỉ thông tin cá nhân ε, giá trị nhiễu cần thêm vào sẽ phải lớn hơn Định lý 1.3 cho thấy rằng cơ chế Laplace là phương pháp tạo ra thuật toán ε–thuần túy trong Differential Privacy.
Giả sử x, y là hai dữ liệu hàng xóm tùy ý với ∥x−y∥₁ = 1 Gọi px và py lần lượt là hàm mật độ xác suất của ML (x, f(ã), ε) và ML (y, f(ã), ε) Khi đó, với z ∈ Rᵏ, ta có pₓ(z) pᵧ(z) k.
⩽exp(ε)Vậy cơ chế Laplace làε–thuần tuý DP.
Cơ chế mũ
Trong phần trước, chúng tôi đã trình bày về cơ chế Laplace thêm nhiễu có phân phối Laplace để xáo trộn đầu ra của các truy vấn số Tuy nhiên, trong một số trường hợp, đặc tính của dữ liệu không cho phép thay đổi quá lớn giá trị đầu ra như giá thầu, hoặc khi dữ liệu chỉ chứa các giá trị rời rạc hữu hạn như biến nhị phân 0, 1, việc thêm nhiễu Laplace trở nên không phù hợp Do đó, cơ chế mũ được đề xuất, trong đó thay vì xáo trộn trực tiếp giá trị biến đầu ra, chúng tôi sẽ xáo trộn xác suất để chọn một giá trị trong tập hợp hữu hạn các giá trị khả thi.
Trong một thuật toán tùy ý, hàm trọng số xác suất u được sử dụng để lựa chọn ứng viên đầu ra, trong đó ứng viên có xác suất cao hơn sẽ được chọn Độ nhạy cảm của hàm u được định nghĩa như sau: Gọi R là tập hợp các giá trị có thể của đầu ra và u: N | X | × R → R Độ nhạy cảm ∆u được xác định theo công thức cụ thể.
D,D ′ |u(D,r)−u(D ′ ,r)|. trong đóD,D ′ lấy trên tất cả các bộ dữ liệu đầu vào là hàng xóm của nhau.
Cơ chế mũ tương tự như cơ chế Laplace, tạo ra xáo trộn đầu ra dựa trên độ nhạy cảm của hàm Cơ chế mũ ME(x,u,R) chọn đầu ra r∈R với xác suất tỷ lệ theo công thức exp(εu(x,r)²∆u) Đặc biệt, cơ chế mũ đảm bảo thuật toán ε–thuần tuý differential privacy.
Chứng minh Giả sử x,y là 2 dữ liệu hàng xóm và r là giá trị bất kỳ nằm trong tập đầu ra Khi đó:
=exp(ε)Vậy cơ chế mũ làε–thuần tuý DP.
Tương quan giữa hiệu năng và an toàn của thuật toán Differ-
Việc thêm nhiễu vào dữ liệu nhằm bảo vệ thông tin cá nhân tạo ra một chiếc khiên bảo vệ, nhưng đồng thời cũng ảnh hưởng đến độ chính xác và khả năng ứng dụng của thuật toán trong phân tích dữ liệu lớn Đối với các cơ chế tạo ra Differential Privacy, khi hằng số ε giảm để giảm thiểu rủi ro rò rỉ thông tin, lượng nhiễu cần thêm vào để xáo trộn dữ liệu đầu ra sẽ tăng lên Trong phần này, chúng tôi sẽ nghiên cứu mối tương quan này thông qua việc quan sát kết quả của thuật toán phân lớp Naive Bayes đảm bảo Differential Privacy Thuật toán Gaussian Naive Bayes giả định rằng dữ liệu đầu vào tuân theo phân phối chuẩn, từ đó tính toán xác suất hậu nghiệm để phân lớp, sử dụng hai đại lượng thống kê là trung bình và phương sai.
[3] thêm nhiễu Laplace vào cả trung bình và phương sai để tạo ra thuật toán Gaussian Naive Bayes thoả mãn DP.
Hình 1.1: Ảnh hưởng của ε đối với kết quả phân lớp.
Tiếp theo, chúng tôi sẽ sử dụng mã nguồn mở thuật toán Gaussian Naive Bayes đã được thêm nhiễu Laplace để đảm bảo Differential Privacy của IBM
Đồ thị 1.1 minh họa mối tương quan giữa lượng thông tin rò rỉ (ε) và độ chính xác của thuật toán, cho thấy hiệu năng của thuật toán thay đổi theo lượng thông tin rò rỉ trong khoảng từ 10⁻² đến 10² Sau khi chạy thuật toán 200 lần cho mỗi giá trị ε, chúng tôi đã tính toán trung bình sai số phân lớp để tạo ra một đồ thị mượt mà hơn Quan sát đồ thị cho thấy độ chính xác phân lớp tương đối thấp khi ε rất nhỏ, nhưng tăng nhanh chóng khi ε tăng dần đến 10².
Mặc dù việc tối ưu khả năng bảo vệ và tính chính xác của thuật toán DP là quan trọng, nhưng cải thiện một trong hai yếu tố này thường dẫn đến sự suy giảm của yếu tố còn lại Độ dốc của mối tương quan giữa hai đại lượng này có thể khác nhau tùy thuộc vào thuật toán và dữ liệu được nghiên cứu Do đó, để đạt được sự cân bằng tối ưu giữa hiệu năng và mức độ bảo vệ, cần nghiên cứu kỹ lưỡng cho mỗi ứng dụng trên từng tập dữ liệu cụ thể, dựa trên mục đích của phân tích dữ liệu.
Differential Privacy với thuật toán rừng ngẫu nhiên
Trong chương này, chúng tôi giới thiệu một thuật toán rừng ngẫu nhiên được cải tiến, đáp ứng tiêu chuẩn bảo mật DP, dựa trên các nghiên cứu của Li và Patil Khác với phương pháp của họ, chúng tôi loại bỏ bước thêm nhiễu Laplace, giả định rằng tin tặc chỉ có thể truy cập dữ liệu đầu ra và mô hình cây, giúp bảo vệ các truy vấn số cụ thể trong thuật toán Thuật toán này áp dụng cơ chế mũ trong việc chọn đặc trưng tại mỗi lần phân nhánh, tạo ra cây quyết định với phân nhánh xác suất, khác biệt so với các thuật toán rừng ngẫu nhiên truyền thống.
Thuật toán rừng ngẫu nhiên thoả mãn DP cho bài toán phân lớp 15
Nội dung thuật toán
Thuật toán rừng ngẫu nhiên thường sử dụng hàm Information Gain hoặc Gini Index để xác định tiêu chí phân nhánh Khi áp dụng Differential Privacy vào thuật toán này, chúng tôi lựa chọn hàm Gini Index âm.
Mã giả của thuật toán được thể hiện trong thuật toán 1.
Algorithm 1:Thuật toán rừng ngẫu nhiên đảm bảo DP
Result: Rừng ngẫu nhiên phân lớp đảm bảo Differential Privacy
Input: D: Tập huấn luyện; B: Số lượng cây quyết định;P ε ′ : Ngân sách riêng tư;h: Độ sâu;A ={A 1 , A d }: Tập các trường thông tin của dữ liệu dùng phân lớp
3 Lấy mẫu ngẫu nhiênZ với kích thước|D|;
4 Xây dựng cây quyết định, lặp lại các bước sau cho đến khih=0
1 Chọn ngẫu nhiênmtrường thông tin từ d đặc trưng đầu vào.mthông thường là √ d.
2 Sử dụng cơ chế mũ bằng cách chọn đặc trưng rẽ nhánhAvới xác suất exp − 2∆q ε q(Z,A)
− 2∆q ε q(Z,A) ở đâyqlà Gini index của đặc trưng A
3 Phân nhánh nút hiện tại thành 2 nút con, gánh=h−1.
6 Output là một tập hợp các cây quyết định, trong đó việc phân lớp dữ liệu đầu vào mới được thực hiện thông qua việc tổng hợp kết quả phân loại từ các cây quyết định này.
Việc tính toán độ nhạy cảm của chỉ số Gini là rất quan trọng trong việc thực hiện cơ chế mũ Friedman đã chỉ ra rằng hàm chỉ số Gini có độ nhạy cảm toàn cục là 2 Định lý 2.1 nêu rõ rằng, với tập dữ liệu T và tập hợp các lớp C, đối với mỗi thuộc tính A và lớp c thuộc C, ta có thể xác định T j A là tập hợp các phần tử trong T mà thuộc tính A có giá trị j, và T j,c A là số lượng phần tử trong T j A thuộc lớp c.
Đặt τ =|T |,τ A j =|T j A |,τ A j,c =|T j,c A | Khi đó hàm Gini Index âm: q Gini (T ,A) =−∑ j∈A τ A j
có độ nhạy cảm toàn cục S(q Gini ) =2
Chứng minh rằng với hai tập dữ liệu hàng xóm bất kỳ chỉ khác nhau ở một bản ghi r, nếu giả sử r A = j, chúng ta chỉ cần tập trung vào giá trị của số hạng τ A j.
Từ định lý trên, ta có thể xây dựng thuật toán phân nhánh cho cây quyết định sử dụng cơ chế mũ như sau (xem thuật toán 2).
Algorithm 2:Cơ chế mũ sử dụng để chọn đặc trưng phân nhánh.
Result: Đặc trưng phân nhánh
Input: D: Tập dữ liệu; A ={A 1 , A n }: Tập hợp các đặc trưng của dữ liệu; ε: hằng số đặc trưng cho lượng thông tin rủi ro
4 Tính Gini indexGi và điểm phân nhánhSi ứng với đặc trưngAi
5 gini.append(G i ); splitting_point.append(S i )
10 idx←random.choice([1, ,n], probability = prob_array)
11 ChọnA idx cùng với điểm chia splitting_point[idx]
Kết quả phân lớp trên bộ dữ liệu iris và NYC taxi
To implement the algorithm, we reinstalled the Random Forest algorithm based on the source code from references [8] and [9], utilizing sklearn's Random Forest classifier with the iris dataset to compare the performance of the algorithms The results are as follows:
Hình 2.1: Hiệu năng của 3 thuật toán random forest trên bộ dữ liệu iris dataset.
Chương trình của chúng tôi cho ra kết quả phân lớp thấp hơn so với sklearn’s random forest classifier đã được tối ưu hóa, như thể hiện trong hình 2.1 Kết quả này cũng cho thấy rằng thuật toán rừng ngẫu nhiên có Differential Privacy đạt được mức phân lớp thấp nhất, phù hợp với lý thuyết.
Chúng tôi đã kiểm tra ảnh hưởng của lượng thông tin rủi ro đến hiệu năng của thuật toán, và kết quả cho thấy rằng với ε lớn, hiệu năng của thuật toán rừng ngẫu nhiên DP vượt qua cả hai thuật toán trước đó Chúng tôi giả thuyết rằng việc thêm yếu tố ngẫu nhiên trong quá trình chọn đặc trưng có thể đã giảm hiện tượng over-fitting, từ đó nâng cao hiệu năng dự báo Tuy nhiên, hiện tượng này chỉ xuất hiện khi ε có giá trị lớn, điều này thường không thực tiễn trong việc áp dụng các thuật toán có Differential Privacy.
Hình 2.2: Hiệu năng phụ thuộc vào giá trị củaε otrên bộ dữ liệuiris.
Chúng tôi đã tiến hành thử nghiệm thuật toán trên bộ dữ liệu taxi New York Để xây dựng bài toán phân lớp, thời gian mỗi chuyến đi được chia thành các đoạn 5 phút, và chúng tôi dự đoán đoạn thời gian mà mỗi hành trình mới sẽ rơi vào.
Kết quả một lần nữa khẳng định lý thuyết rằng chương trình của sklearn mang lại dự báo tốt nhất, trong khi việc cài đặt Differential Privacy đã làm giảm đáng kể độ chính xác của thuật toán.
Thuật toán rừng ngẫu nhiên thoả mãn DP cho bài toán hồi quy 20
Chúng tôi đã thực hiện bài toán hồi quy bằng cách chạy thuật toán rừng ngẫu nhiên tự cài đặt và phiên bản của sklearn trên bộ dữ liệu Boston và taxi NYC Để đánh giá hiệu năng của hai chương trình này, chúng tôi sử dụng các chỉ số MSE và R² Kết quả của các lần chạy cho thấy sự phụ thuộc vào số lượng cây trong mô hình.
Hình 2.3: Hiệu năng phụ thuộc vàoε trên bộ dữ liệu NYC taxi.
Hình 2.4: So sánh hàm MSE andR 2 trên bộ dữ liệu Boston and NYC Taxi. quyết định có thể quan sát trên đồ thị 2.4.
Trong bài toán hồi quy, cơ chế mũ yêu cầu hàm mất mát như MSE phải đảm bảo độ nhạy cảm bị chặn trên tập dữ liệu đầu vào Tuy nhiên, hàm MSE không đáp ứng yêu cầu này với bộ dữ liệu NYC taxi ban đầu Vì vậy, chúng tôi đã chuẩn hoá bộ dữ liệu và thực hiện thuật toán trên cả bộ dữ liệu Boston và NYC taxi.
Kết quả dự báo cho thấy việc chuẩn hoá dữ liệu có thể đảm bảo tính bị chặn của độ nhạy cảm hàm MSE, nhưng lại làm giảm khả năng của cơ chế mũ trong việc đánh trọng số các đặc trưng, dẫn đến việc không tìm ra được đặc trưng phân nhánh tối ưu nhất Khả năng chọn đặc trưng tốt nhất chỉ gấp tối đa 2 lần khả năng chọn đặc trưng xấu nhất, điều này cho thấy các cây quyết định chưa đủ hiệu quả trong quá trình phân nhánh để cải thiện dự báo.
Phương pháp mẫu ngẫu nhiên và tổng hợp
Dựa trên những khó khăn khi triển khai thuật toán rừng ngẫu nhiên với cài đặt DP cho bài toán hồi quy, chúng tôi đã chọn một phương pháp khác, sử dụng kỹ thuật lấy mẫu ngẫu nhiên kết hợp với tổng hợp kết quả Đầu tiên, dữ liệu ban đầu được chia thành các mẫu con ngẫu nhiên có kích thước đều nhau, mỗi mẫu là đầu vào cho hàm f, đại diện cho các thuật toán học máy như rừng ngẫu nhiên hoặc XGboost Kết quả từ hàm f sau đó được tổng hợp bằng hàm g, trong đó chúng tôi sử dụng hàm lấy trung vị Cuối cùng, nhiễu được thêm vào hàm g để tạo ra hàm h với độ nhạy cảm đồng đều hơn so với hàm gốc, từ đó đảm bảo kết quả dự báo đạt tiêu chuẩn differential privacy.
Độ nhạy cảm trơn
Trong chương trước, chúng ta đã thảo luận về việc thêm nhiễu vào quá trình tạo DP với biên độ cố định, tỷ lệ thuận với độ nhạy cảm toàn cục ∆f Tuy nhiên, với một số hàm như hàm trung vị, phương pháp này không hiệu quả khi thêm nhiễu lớn và không phản ánh đúng độ nhạy cảm của từng điểm dữ liệu Vì vậy, trong mục này, chúng tôi sẽ giới thiệu một độ đo khác về độ nhạy cảm mang tính địa phương hơn Định nghĩa 3.1 (Độ nhạy cảm địa phương) sẽ được trình bày để làm rõ hơn khái niệm này.
N | X | Khi đó độ nhạy cảm địa phương tại xđược xác định như sau:
LS f (x) =max y ∥f(x)− f(y)∥ trong đóychạy trên tất cả các hàng xóm của x.
Từ định nghĩa trên, độ nhạy cảm toàn cục có thể biểu diễn thành:
Khi thêm nhiễu tỷ lệ với độ nhạy cảm địa phương, độ chính xác của thuật toán dự báo có thể được cải thiện đáng kể nhờ giảm thiểu lượng nhiễu Tuy nhiên, phương pháp này quá đơn giản và không đáp ứng tiêu chí của Differential Privacy (DP) Để khắc phục điều này, chúng tôi giới thiệu một lớp hàm chặn trên của LS f(x) vừa thể hiện tính địa phương của x, vừa đảm bảo an toàn khi thêm nhiễu tương ứng với độ lớn của nó Định nghĩa 3.2 nêu rõ rằng hàm số S:N | X | →R được gọi là β–chặn trên trơn của độ nhạy cảm địa phương của hàm f nếu thỏa mãn hai điều kiện nhất định.
Trong lớp hàm này, chúng ta chú trọng đến hàm có độ lớn tối ưu nhất Định nghĩa 3.3 nêu rõ rằng với β > 0, độ β–nhạy cảm trơn của hàm f, ký hiệu là S ∗ f,β, là hàm β–chặn trên trơn nhỏ nhất trong số tất cả các β–chặn trên trơn của độ nhạy cảm địa phương của hàm f Điều này có nghĩa là S ∗ f ,β (x) phải nhỏ hơn hoặc bằng S(x) với mọi x thuộc N | X |, trong khi S(x) là một β–chặn trên trơn tùy ý của độ nhạy cảm địa phương của f Định lý 3.1 cung cấp một phương pháp để xác định độ nhạy cảm trơn mà chúng ta sẽ áp dụng trong chương này.
Chứng minh.Trước hết, ta chỉ ra S ∗ f ,β là một chặn trên củaLS f Thật vậy:
Chúng ta sẽ chứng minh rằng S ∗ f ,β là β–trơn, tức là S ∗ f ,β (y) ⩾ exp(−β)S ∗ f,β (x) cho mọi cặp dữ liệu hàng xóm x và y Cụ thể, giả sử x ′ ∈ N | X | thoả mãn điều kiện S ∗ f ,β (x) ≤ LS f (x ′ ).exp(−β∥x−x ′ ∥ 1 ) Bằng cách áp dụng bất đẳng thức tam giác, chúng ta có thể rút ra mối quan hệ giữa y và x ′.
S ∗ f ,β là β–chặn trên trơn của độ nhạy cảm địa phương của f Chúng tôi sẽ chứng minh rằng đây là hàm bé nhất trong tất cả các chặn trên trơn Đồng thời, chúng tôi cũng sẽ chứng minh điều này một cách tương đương.
S(x)⩾LS f (y).exp(−β∥x−y∥ 1 ) được chứng minh bằng quy nạp theo d(x,y) Trong trường hợp cơ sở khi d(x,y) = 0, điều này hiển nhiên vì S(x) là một chặn trên của f Giả sử bất đẳng thức S(x ′ )⩾LS f (y).exp(−β∥x ′ −y∥ 1 ) đúng với mọi dữ liệu x ′ ,y thỏa mãn d(x ′ ,y) = k Khi đó, đối với hai dữ liệu x,y mà d(x,y) = k+1, luôn tồn tại x ′ ∈ N | X | thỏa mãn d(x,x ′ ) = 1 và d(x ′ ,y) = k.
Sử dụng tính chất của hàm chặn trên trơn và giả thiết quy nạp, ta có:
=LS f (y).exp(−β∥x−y∥ 1 )Theo nguyên lý quy nạp, ta có đpcm.
Hiệu chỉnh nhiễu
Một phân bố xác suất với hàm mật độ h được gọi là (α,β)–chấp nhận được nếu tồn tại hai số thực ε, δ và hai hàm số α, β phụ thuộc vào ε, δ, thỏa mãn hai điều kiện nhất định với mọi ∆ ∈ R^d và λ ∈ R, trong đó ∥∆∥₁ ≤ α.
|λ|⩽β và với mọi tập con đo được S ∈R d :
Một phân bố chấp nhận được sẽ không thay đổi nhiều khi thực hiện phép dịch chuyển hoặc giãn nở với tỷ lệ nhỏ Định lý khẳng định rằng phân bố này có thể được sử dụng để thêm nhiễu với biên độ tỷ lệ theo một chặn trên trơn của độ nhạy cảm địa phương, từ đó tạo ra thuật toán thỏa mãn Differential Privacy Cụ thể, giả sử Z là biến ngẫu nhiên với hàm mật độ xác suất h và có phân phối xác suất (α, β) – chấp nhận được, thì với hàm truy vấn f : N | X | → R và β – chặn trên trơn của độ nhạy cảm địa phương S: N | X | → R, thuật toán sẽ hoạt động theo cách đã được định nghĩa.
Chứng minh Gọi x,y∈ N | X | là hai dữ liệu hàng xóm, S là tập con của
Kí hiệu S(x) α = N(x) Dễ thấy rằng, A(x) ∈ S khi vào chỉ khi Z ∈ S1 với
⩽exp(ε).Pr[A(y)∈S] +δ trong đó, bất đẳng thức thứ nhất được suy ra từ tính chất dịch chuyển của phân phối chấp nhận được, với chú ý:
LS f (x) ⩽α và bất đẳng thức thứ hai được suy ra từ tính chất giãn nở của phân phối chấp nhận được, với chú ý: lnN(x)
Tính toán độ nhạy cảm trơn
Định nghĩa 3.5 Độ nhạy cảm địa phương với khoảng cách kcủa f là:
Từ đây, ta có thể biểu diễn độ nhạy cảm trơn thông qua độ nhạy cảm địa phương có khoảng cách.
Do đó, để tính độ nhạy cảm trơn của f, ta chỉ cần tính các đại lượngA (k) (x). Định lý 3.3 Độ nhạy cảm trơn của hàm trung vị là:
Độ nhạy cảm địa phương tại khoảng cách k đạt giá trị lớn nhất khi trung vị là đầu mút của một khoảng trống lớn Điều này có thể thực hiện bằng cách thay thế vị trí x m−k+t ,x m−k+t+1 , ,xm+t−1 theo nguyên tắc: xi=0 nếu i0, thuật toánM là (ε,δ)-Differential Private với: δ =min λ exp(αM(λ)−λ ε)
DP-SGD cung cấp một thuật toán tổng quát có thể áp dụng cho các phương pháp học sâu Để tăng tốc độ hội tụ, các tham số của thuật toán có thể được tối ưu hóa dựa trên đặc điểm của từng loại dữ liệu, kết hợp với các thuật toán tiền xử lý như PCA nhằm nâng cao độ chính xác Mặc dù khả năng bảo vệ của thuật toán được mô tả chi tiết trong định lý 4.1, việc tính toán trong thực tế vẫn gặp nhiều khó khăn và cần thêm các phân tích đánh giá.
Algorithm 5:Thuật toán DP-DBSCAN
Input:D=P 1 ,P 2 , ,Pn: Tập dữ liệu; E ps: Bán kính lân cận;
MinPts: Số điểm tối thiểu trong một cụm; ε: tham số DP
1 Thêm nhiễu vào hàm khoảng cách:dis ′ (X,Y) =∑ n i=1 (x i ,y i ) 2 +Lap
6 Thêm các điểm cốt lõi vào Dcore
7 Chọn hai điểm xa nhất p 1 ,q 1 từDcore
15 Chọn điểm lớn nhất ∑count(core() i=1 dis(P,P ′ ) thêm vàoCore()
22 Đánh dấu Plà điểm ngoại lai;
Algorithm 6:Hàm expandCluster(P,NeighborPts,C,Eps,MinPts)
3 if P ′ chưa được thăm then
4 Đánh dấu P ′ đã được thăm;
6 if P ′ chưa là thành viên của bất kỳ cụm nào then
1 returntất cả các điểm P ′ nằm trong lân cận tâm P bán kínhE ps;
Algorithm 8:Thuật toán DP-SGD
Result:Nghiệm tối ưuθT của hàm mất mát
Input:x 1 ,x 2 , ,xN: Tập dữ liệu; L(θ) = N 1 ∑ N i=1 L(θ,xi): Hàm mất mát; η t : bước nhảy; σ: biên độ nhiễu; L: kích thước một nhóm;C: chặn chuẩn của vector gradient
3 Lấy mẫu ngẫu nhiên L t với kích thước L
5 Chuẩn hoá vector hướng giảm g t (x i )←g t (x i )/max
7 Cập nhật nghiệm tối ưu θ t+1 =θt−ηt.get
Luận văn này một lần nữa khẳng định tiềm năng ứng dụng to lớn của mô hình Differential Privacy trong việc bảo vệ dữ liệu riêng tư của người dùng Các đóng góp chính của tác giả bao gồm việc phát triển và cải tiến các phương pháp bảo vệ thông tin cá nhân, đồng thời nâng cao hiệu quả của việc sử dụng mô hình này trong các hệ thống thực tế.
• Trình bày lý thuyết toán học của mô hình thống kê Differential Privacy.
• Cài đặt thuật toán rừng ngẫu nhiên cho bài toán phân lớp và hồi quy cho bộ dữ liệu NYC.
Xây dựng và cài đặt thuật toán rừng ngẫu nhiên và XGBoost cho bài toán hồi quy là một quy trình quan trọng trong phân tích dữ liệu Kỹ thuật lấy mẫu ngẫu nhiên được áp dụng để cải thiện độ chính xác của mô hình Việc tổng hợp kết quả từ các thuật toán này giúp tối ưu hóa hiệu suất dự đoán và nâng cao khả năng phân tích.
Bên cạnh các kết quả đạt được, luận văn còn một số vấn đề tồn tại cần được nghiên cứu và phát triển trong tương lai:
• Nghiên cứu cách chọn tham số ε trong mối liên hệ với độ chính xác của thuật toán.
• Cải thiện hiệu năng của thuật toán DP.
Cài đặt lập trình động (DP) vào các thuật toán tham lam trong việc tìm tập độc lập của đồ thị là một hướng nghiên cứu có tính ứng dụng cao.
[1] C Dwork and A Roth,The Algorithmic Foundations of Differential Pri- vacy Foundationsand Trends in Theoretical Computer Science, vol 9, no 3-4, pp 211–407, 2013.
[2] B Seleshi and S Assef,A case study on differential privacy 2007.
[3] J Vaidya, A Basu, B Shafiq, and Y Hong,Differentially private naive bayes classification Proceedings - 2013 IEEE/WIC/ACM International
Conference on Web Intelligence, WI 2013, vol 1, pp 571–576, 2013.
[4] IBM/differential-privacy-library: Diffprivlib: The IBM Differential Pri- vacy Library Available at https://github.com/IBM/differential-privacy- library.
[5] Z Li and S L, Random forest algorithm under differential privacy.
International Conference on Communication Technology Proceedings, ICCT, vol 2017-Octob, no 2, pp 1901–1905, 2018.
[6] A Patil and S Singh,Differential private random forest Proceedings of the 2014 International Conference on Advances in Computing, Commu- nications and Informatics, ICACCI 2014, pp 2623–2630, 2014.
[7] A Friedman and A Schuste, Data Mining with Differential PrivacyCategories and Subject Descriptors Proceedings of the 16th ACM
