{"id":3680,"date":"2024-02-17T03:10:43","date_gmt":"2024-02-16T18:10:43","guid":{"rendered":"https:\/\/saraheee.com\/?p=3680"},"modified":"2024-02-17T03:10:47","modified_gmt":"2024-02-16T18:10:47","slug":"algorithmic-foundations-5-randomized-response-laplace-mechanism","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/02\/algorithmic-foundations-5-randomized-response-laplace-mechanism\/","title":{"rendered":"[Algorithmic Foundations] #5. randomized response & laplace mechanism"},"content":{"rendered":"

3.2 Randomized response<\/h3>\n\n\n\n

Let XYZ be such an activity.
Faced with the query, “Have you engaged in XYZ in the past week?” the respondent is instructed to perform the following steps: <\/p>\n\n\n\n

1. Flip a coin
2. If tails, then respond truthfully
3. If heads, then flip a second coin and respond “Yes” if heads and “No” if tails.<\/p>\n\n\n\n

Claim 3.5. The version of randomized response described above is (ln3, 0)-differentially private.<\/p>\n\n\n\n

Proof. Fix a respondent.
Pr[Response = Yes|Truth = Yes] = 3\/4. (first coin comes up tails 1\/2, first and second come up heads 1\/4)
Pr[Response = Yes|Truth = No] = 1\/4.<\/p>\n\n\n\n

\\(\\frac{Pr[Response=Yes|Truth=Yes]}{Pr[Response=Yes|Truth=No]} = \\frac{3\/4}{1\/4} = \\frac{Pr[Response=No|Truth=No]}{Pr[Response=No|Truth=Yes]} = 3\\)<\/p>\n\n\n\n

3.3 The laplace mechanism<\/h3>\n\n\n\n

functions \\(f: \\mathbb{N}^{|X|} \\to \\mathbb{R}^k\\)\ub294 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \ucffc\ub9ac\uc758 \uac00\uc7a5 \uae30\ubcf8\uc801\uc778 \uc720\ud615
X\uac1c \ub370\uc774\ud130\ubca0\uc774\uc2a4\ub97c k\uac1c\uc758 \uc2e4\uc218\uc5d0 \ub9e4\ud551<\/p>\n\n\n\n

Definition 3.1<\/mark> (\\(l_1\\)-sensitivity). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\ud568\uc218\uc758 \ucd9c\ub825\uc774 \uc785\ub825 \ub370\uc774\ud130\uc5d0 \uc5bc\ub9c8\ub098 \ubbfc\uac10\ud558\uac8c \ubc18\uc751\ud558\ub294\uc9c0 \uce21\uc815\ud558\ub294 \uc9c0\ud45c
– \\(l_1\\) \ubbfc\uac10\ub3c4: \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\ud638\ud558\uae30 \uc704\ud574 \ucd9c\ub825\uc744 \uc5bc\ub9c8\ub098 \uad50\ub780\uc2dc\ucf1c\uc57c \ud558\ub294\uc9c0\uc5d0 \ub300\ud55c \uc0c1\ud55c
\ub370\uc774\ud130\ubca0\uc774\uc2a4\uc5d0\uc11c \ub2e8\uc77c \ud56d\ubaa9\uc774 \ucd94\uac00\ub418\uac70\ub098 \uc81c\uac70\ub420 \ub54c \ud568\uc218\uc758 \ucd9c\ub825 \uac12\uc774 \uc5bc\ub9c8\ub098 \ubcc0\ud560 \uc218 \uc788\ub294\uc9c0 \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n\n\n\n

Definition 3.2<\/mark> (The Laplace Distribution). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

0\uc744 \uc911\uc2ec\uc73c\ub85c \uc2a4\ucf00\uc77c b\ub97c \uac00\uc9c0\ub294 \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\ub97c \uac00\uc9c4 \ubd84\ud3ec
\uc9c0\uc218 \ubd84\ud3ec\uc758 \ub300\uce6d\uc801\uc778 \ud615\ud0dc\ub97c \uac00\uc9c4\ub2e4.<\/p>\n\n\n\n

x: \ud655\ub960 \ubcc0\uc218, \ubd84\ud3ec \uac12
b: \ubd84\ud3ec\uc758 \uc2a4\ucf00\uc77c\uc744 \uacb0\uc815\ud558\ub294 \ub9e4\uac1c\ubcc0\uc218(\uc774 \ubd84\ud3ec\uc758 \ubd84\uc0b0\uc740 \\(2b^2\\)) – \ud615\ud0dc \uc870\uc808
exp(-|x|\/b): x\uac00 0\uc5d0\uc11c \uba40\uc5b4\uc9c8\uc218\ub85d \ud655\ub960 \ubc00\ub3c4\uac00 \uc5b4\ub5bb\uac8c \uac10\uc18c\ud558\ub294\uc9c0 \uc124\uba85, b\ub294 \uac10\uc18c\uc728 \uc870\uc815
1\/2b: \uc815\uaddc\ud654 \uc0c1\uc218(Normalization constant), \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\uc758 \ucd1d \uba74\uc801\uc774 1\uc774 \ub418\ub3c4\ub85d \ubcf4\uc7a5\ud55c\ub2e4.
(\ubaa8\ub4e0 \uac00\ub2a5\ud55c x \uac12\uc5d0 \ub300\ud574 \ud655\ub960 \ubc00\ub3c4\ub97c \uc801\ubd84\ud558\uba74 1\uc774 \ub428)<\/p>\n\n\n\n

– \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\ub294 0\uc744 \uc911\uc2ec\uc73c\ub85c \ub300\uce6d\uc801, x\uc758 \uc808\ub300\uac12\uc774 \ucee4\uc9c8\uc218\ub85d \ud655\ub960 \ubc00\ub3c4\uac00 \uc9c0\uc218\uc801\uc73c\ub85c \uac10\uc18c<\/p>\n\n\n\n

\\(Lap(x|b) = \\frac{1}{2b}exp(-\\frac{|x-\\mu|}{b})\\) (\ubd84\ud3ec\uc758 \uc911\uc2ec\uc774 \u03bc\uc778 \uacbd\uc6b0)<\/p>\n\n\n\n

\\(\\int_{-\\infty}^{\\infty}f(x|\\mu, b)dx = \\int_{-\\infty}^{\\infty}\\frac{1}{2b}exp(-\\frac{|x-\\mu|}{b})dx\\)<\/p>\n\n\n\n

Definition 3.3<\/mark> (The Laplace Mechanism). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\\(M_L\\): \ud568\uc218 f\uc758 \uacc4\uc0b0 \uacb0\uacfc\uc5d0 \ub178\uc774\uc988\ub97c \ucd94\uac00\ud558\uc5ec \uacb0\uacfc\ub97c \ubcc0\ud615\ud55c\ub2e4.
\\(Y_i\\): \ub3c5\ub9bd \ub3d9\uc77c \ubd84\ud3ec \ub79c\ub364 \ubcc0\uc218, Lap(\u2206f\/\u03b5)\uc5d0\uc11c \ucd94\ucd9c\ub41c\ub2e4.
\u2206f: \\(l_1\\)\uc758 \uac10\ub3c4, \ucd5c\ub300 \ucd9c\ub825 \ucc28\uc774
\u03b5: \ud504\ub77c\uc774\ubc84\uc2dc \uc608\uc0b0 (\u03b5\u2193 \u2192 \ub370\uc774\ud130 \uc720\uc6a9\uc131\uc774 \ub0ae\uc544\uc9d0(\ub178\uc774\uc988\u2191), \u03b5\u2191 \u2192 \ud504\ub77c\uc774\ubc84\uc2dc \ubcf4\ud638 \uc218\uc900\uc774 \ub0ae\uc544\uc9d0)
\\(f: \\mathbb{N}^{|X|} \\to \\mathbb{R}^k\\): \ub370\uc774\ud130\ubca0\uc774\uc2a4 X\uc5d0\uc11c k\ucc28\uc6d0 \uc2e4\uc218 \ubca1\ud130\ub85c \ub9e4\ud551\ud558\ub294 \ud568\uc218<\/p>\n\n\n\n

Theorem 3.6<\/mark>. <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

(\u03b5,0)-differential privacy \ub9cc\uc871
\\(f: \\mathbb{N}^{|X|} \\to \\mathbb{R}^k\\) \uacb0\uacfc\uc5d0 \ub3c5\ub9bd\uc801\uc73c\ub85c \ubd84\ud3ec\ub41c \ub77c\ud50c\ub77c\uc2a4 \ub178\uc774\uc988 \\(Y_i\\)\ub97c \ucd94\uac00\ud558\uc5ec f(x) + (\\(Y_1, \\cdots, Y_k\\))\uc758 \ud615\ud0dc\ub85c \uacb0\uacfc\ub97c \ucd9c\ub825<\/p>\n\n\n\n

\ube44\uc728\uc774 \\(exp(\\epsilon \\cdot \\left| f(x)-f(y) \\right|_1\/\\Delta f)\\) \uc774\ud558
\\(\\left| f(x)-f(y) \\right|_1 \\leq \\Delta f\\)\uc774\ubbc0\ub85c \uc774 \ube44\uc728\uc740 exp(\u03b5)\uc744 \ucd08\uacfc\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n\n\n\n

1) \uc124\uc815
\uc778\uc811\ud55c \ub450 \ub370\uc774\ud130\ubca0\uc774\uc2a4 \\(x, y \\in \\mathbb{N}^{|X|}\\), \\(\\left| x-y \\right|_1 \\leq 1\\)\uc744 \ub9cc\uc871\ud55c\ub2e4.
f(\u30fb): \uc8fc\uc5b4\uc9c4 \ud568\uc218
\ud568\uc218 f\uc5d0 \ub300\ud574 \\(M_L\\)(x, f, \u03b5)\uc758 \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\ub97c \\(p_x\\), \\(M_L\\)(y, f, \u03b5)\uc758 \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\ub97c \\(p_y\\)\ub85c \ud45c\ud604\ud55c\ub2e4.
(\uac01 \ub370\uc774\ud130\ubca0\uc774\uc2a4 x, y\uc5d0 \ub300\ud574 \ub77c\ud50c\ub77c\uc2a4 \uba54\ucee4\ub2c8\uc998\uc744 \uc801\uc6a9\ud588\uc744 \ub54c\uc758 \ud655\ub960 \ubc00\ub3c4 \ud568\uc218)<\/p>\n\n\n\n

2) \ube44\uad50
\uc784\uc758\uc758 \uc810 \\(z \\in \\mathbb{R}^k\\)\uc5d0\uc11c \ub450 \ud655\ub960 \ubc00\ub3c4 \ud568\uc218\uc758 \ube44\uc728\uc744 \ube44\uad50\ud55c\ub2e4.
\ud568\uc218 f\uc758 \uac01 \ucd9c\ub825 i\uc5d0 \ub300\ud574, x\uc640 y\uc5d0 \ub300\ud55c \ud568\uc218 \uac12\uc758 \ucc28\uc774
b = \u2206f\/\u03b5<\/p>\n\n\n\n

3) \ubd84\uc11d
\uac01 \ucc28\uc6d0 i\uc5d0 \ub300\ud574, x\uc640 y\ub85c \uacc4\uc0b0\ub41c \ud568\uc218 \uac12\uc758 \ucc28\uc774\ub294 \\(\\left| f(x)_i – f(y)_i \\right|\\)
f\uc758 \ubbfc\uac10\ub3c4\uc640 \u03b5\uc5d0 \uc758\ud574 \uacb0\uc815\ub41c \ub178\uc774\uc988\uc758 \uc591\uc744 \uace0\ub824\ud560 \ub54c, \\(p_x(z)\/p_y(z)\\)\uc758 \ube44\uc728\uc740 exp(\u03b5)\uc744 \ub118\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n\n\n\n

* \uc0bc\uac01 \ubd80\ub4f1\uc2dd(Triangle Inequality)\uc5d0 \uc758\ud574,
\u2223a+b\u2223 \u2264 \u2223a\u2223+\u2223b\u2223, \u2223a\u2223\u2212\u2223b\u2223 \u2264 \u2223a\u2212b\u2223 \uc774\ub2e4.
\ub530\ub77c\uc11c |f(y)-z| – |f(x)-z| \u2264 |(f(y)-z) – (f(x)-z)| = |f(y) – f(x)| = |f(x) – f(x)|<\/p>\n\n\n\n

4) \uacb0\ub860
\ub77c\ud50c\ub77c\uc2a4 \uba54\ucee4\ub2c8\uc998\uc774\u00a0(\u03f5<\/em>,0)-\ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \ubcf4\uc7a5\ud55c\ub2e4.<\/p>\n\n\n\n

\uc774\ub860\uc801 \ubc30\uacbd \ubc0f \uc2e4\uc81c \uc801\uc6a9 \uac00\ub2a5\uc131\uc744 \uc81c\uc2dc\ud55c\ub2e4.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Reference<\/h4>\n\n\n\n
    \n
  • Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 3. Basic Techniques and Composition Theorems<\/li>\n<\/ul>\n\n\n\n

    <\/p>","protected":false},"excerpt":{"rendered":"

    I explain the Laplace distribution and its mechanism.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[154],"tags":[155,176,177],"class_list":["post-3680","post","type-post","status-publish","format-standard","hentry","category-dp","tag-differential-privacy","tag-feb-16-2024","tag-feb-17-2024"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3680"}],"collection":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/comments?post=3680"}],"version-history":[{"count":44,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3680\/revisions"}],"predecessor-version":[{"id":3770,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3680\/revisions\/3770"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=3680"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=3680"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=3680"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}