Matthew Dawson¹, Badih Ghazi¹,*, Pritish Kamath¹, Kapil Kumar¹, Ravi Kumar¹, Bo Luan¹, Pasin Manurangsi¹, Nishanth Mundru¹, Harikesh Nair¹, Adam Sealfon¹, Shengyu Zhu¹ ¹Google
광고 전환 측정을 위한 Attribution Reporting API의 요약 보고서를 기반으로 계층적 쿼리를 수행하는 작업을 연구합니다. 최적화와 차분 프라이버시의 방법들이 API의 프라이버시 보호 장치로 인해 발생하는 노이즈를 처리하는 데 도움이 될 수 있음을 보여줍니다. 특히 다음을 위한 알고리즘을 제시합니다: (i) API 출력의 노이즈 제거 및 트리의 서로 다른 레벨 간 일관성 보장, (ii) 트리의 서로 다른 레벨 간 프라이버시 예산 최적화. 공개 데이터셋에 대한 제안된 알고리즘의 실험적 평가를 제공합니다.
키워드: 광고 전환 측정, 계층적 집계, 차분 프라이버시, attribution reporting API
지난 20년 동안 타사 쿠키[1]는 온라인 광고, 특히 광고 전환 측정에 필수적이었습니다. 이를 통해 게시자 사이트나 앱의 광고 노출(예: 클릭 또는 조회)을 광고주의 전환과 연결하여 집계된 전환 보고서(예: 노출의 하위 집합에 기인한 전환 수) 계산이나 광고 입찰 모델 학습[2, 3, 4, 5]이 가능했습니다. 그러나 최근 몇 년 동안 프라이버시 우려로 인해 여러 브라우저가 타사 쿠키를 폐지하기로 결정했습니다[6, 7, 8].
Attribution Reporting API[9, 10]는 Chrome 브라우저와 Android 모바일 운영 체제에서 프라이버시를 보호하는 광고 전환 측정 방법을 제공하고자 합니다. 이 API는 프라이버시 유출을 제한하기 위한 다양한 메커니즘에 의존하며, 여기에는 각 노출에 기인한 전환의 출력 보고서에 대한 기여도 제한과 차분 프라이버시를 만족시키기 위한 노이즈 주입이 포함됩니다(자세한 내용은 섹션 2 참조).
전환 보고 작업을 연구하는데, 쿼리는 전환과 노출의 일부 특징이 특정 주어진 값으로 제한되는 노출에 기인한 전환 수를 세는 것으로 구성됩니다. 특히 계층적 쿼리 설정에 중점을 두며, 여기서 목표는 특징이 특정 중첩 조건에 따라 제한되는 노출에 기인한 전환 수를 추정하는 것입니다. 그림 1의 예를 고려해보세요. 우리는 다음의 전환 수를 추정하고자 합니다:
- 캠페인 123의 노출에 기인한 전환
- 뉴욕에서 발생하도록 제한된 전환
- 금요일에 발생하도록 추가로 제한된 전환
일반적으로 목표는 그림 1과 유사한 주어진 트리의 각 노드에 대한 전환 수를 추정하는 것입니다.
이러한 추정치는 섹션 2.2에서 논의된 바와 같이 Attribution Reporting API의 요약 보고서를 사용하여 얻을 수 있습니다. 이 작업에서는 API가 반환하는 서로 다른 노드의 추정치를 노이즈 제거하고 추정치가 트리 구조와 일관되도록 보장하는 선형 시간 후처리 알고리즘을 제시합니다. 또한 우리의 알고리즘이 임의의 트리에 대한 모든 선형 비편향 추정기 중에서 최적임을 보여주며, 이는 정규 트리에 대한 결과[11, 12]를 확장합니다(섹션 4). API가 애드테크가 동일한 노출의 기여를 포함하는 서로 다른 측정에 프라이버시 예산을 할당할 수 있도록 하므로, 우리는 트리의 서로 다른 레벨에 걸쳐 프라이버시 예산 할당을 최적화하는 알고리즘을 제공합니다(섹션 5).
데이터셋의 행 수를 n이라 하고, 각 행의 값 도메인을 나타내는 (임의의) 집합을 𝒳라고 하자. 우리는 두 가지 유형의 열(속성)을 구분합니다: 알려진 것과 알려지지 않은 것. 또한 각 알려지지 않은 속성이 취할 수 있는 가능한 값의 집합에 대한 지식을 가정합니다.
정의 1 (DP [13]): ε ≥ 0에 대해, 알고리즘 𝒜는 하나의 행의 알려지지 않은 속성에서 다른 모든 데이터셋 쌍 X, X'에 대해, 그리고 모든 가능한 출력 o에 대해 Pr[𝒜(X) = o] ≤ e^ε · Pr[𝒜(X') = o]가 성립하면 ε-DP입니다.
보조정리 2 (기본 구성): 동일한 데이터셋에서 k개의 알고리즘 𝒜₁, ..., 𝒜ₖ를 실행하는 알고리즘 𝒜가 있고, 각 i ∈ [k]에 대해 𝒜ᵢ가 εᵢ-DP이고 εᵢ ≥ 0이면, 𝒜는 (Σᵢ εᵢ)-DP입니다.
보조정리 3 (후처리): ε > 0이고 R과 R'이 임의의 두 집합이라고 하자. 𝒜 : 𝒳ⁿ → R이 ε-DP 알고리즘이고, f : R → R'이 임의의 무작위 매핑이면, (f ∘ 𝒜) : 𝒳ⁿ → R'은 ε-DP입니다.
집계 가능한 보고서[10]는 다음과 같이 구성됩니다:
-
노출(소스) 등록: API는 애드테크가 게시자 사이트나 앱에서 노출(예: 클릭 또는 조회)을 등록할 수 있는 메커니즘을 제공합니다. 등록 중에 애드테크는 노출 측 집계 키(예: 캠페인이나 지리적 위치에 해당하는 키)를 지정할 수 있습니다.
-
전환(트리거) 등록: API는 또한 애드테크가 광고주 사이트나 앱에서 전환을 등록할 수 있는 메커니즘을 제공합니다. 이때 애드테크는 노출 측 집계 키의 각 설정에 해당하는 집계 가능한 값과 함께 전환 측 키 조각을 지정할 수 있습니다. 예를 들어, 전환 측 키 조각은 전환 유형이나 전환 타임스탬프(의 이산화)를 캡처할 수 있습니다. 결합된 집계 키(노출 측 집계 키와 전환 측 키 조각의 연결로 생각할 수 있음)는 최대 128비트로 제한됩니다. 집계 가능한 값은 1과 API의 L₁ 매개변수(2¹⁶ = 65,536으로 설정됨) 사이의 정수여야 합니다.
-
귀속: API는 전환이 동일한 애드테크가 등록한 마지막(만료되지 않은) 노출에 귀속되는 마지막 터치 귀속을 지원합니다.
-
히스토그램 기여 생성: API는 동일한 노출에 기인한 서로 다른 전환에 의해 생성된 모든 집계 가능한 보고서의 기여 합계가 최대 L₁ = 2¹⁶ 매개변수로 제한되도록 강제합니다.
계층적 쿼리 추정 문제를 공식적으로 정의합니다. 데이터셋 X가 주어지면, 각 노드가 일부 속성의 값에 조건화된 X의 행 하위 집합에 해당하는 트리를 고려합니다. 트리의 각 레벨이 새로운 속성의 값에 대한 조건을 도입하는 설정을 고려합니다. 알려진 속성의 경우, 노드의 자식 노드는 행 내에서 해당 속성이 취하는 서로 다른 값에 해당합니다. 알려지지 않은 속성의 경우, 자식 노드는 데이터셋에 실제로 나타나는지 여부와 관계없이 해당 속성의 모든 가능한 값에 해당합니다. 이 트리가 주어졌을 때, 문제는 귀속된 전환이 있는 각 노드에 해당하는 데이터 행의 대략적인 수를 프라이버시를 보호하면서 공개하는 것입니다.
다음의 오류 측정을 고려하는데, 이는 [22]에 정의되어 있습니다.
정의 7 (임계값에서의 RMS 상대 오류): 개수 c ≥ 0과 그 무작위 추정치 ĉ ∈ ℝ에 대해, ĉ로 c를 추정할 때 임계값 τ에서의 평균 제곱근 상대 오류는 RMSRE_τ(c, ĉ) := √E[(|ĉ-c|/max(τ,c))²]로 정의되며, 여기서 기댓값은 ĉ의 무작위성에 대한 것입니다.
트리에 있는 모든 노드의 개수 추정치(예: 그림 1에서와 같은 전환 수)가 있다고 가정합니다. 각 전환은 여러 노드의 개수에 기여합니다. 예를 들어, 뉴욕에서 금요일에 발생한 광고 캠페인 123의 전환은 왼쪽에서 6번째 리프에 기여하지만 각 조상 노드에도 기여합니다. 이는 다양한 노드의 개수 간에 관계를 부과합니다. 노드의 개수는 자식의 개수 합과 같아야 합니다. 이 속성을 가진 추정기를 일관적(consistent)이라고 합니다.
각 노드에 독립적인 노이즈를 추가하기 위해 이산 라플라스 메커니즘을 직접 적용하면 일관된 추정치가 되지 않습니다. 일관성은 리프의 개수만 추정하고 각 비리프 노드의 개수를 리프 자손의 개수를 더하여 추론함으로써 달성할 수 있지만, 이는 트리의 상위 노드에 대해 큰 오류를 초래할 수 있습니다. 대안으로, 독립적인 노드별 추정치를 후처리하여 일관성을 달성할 수 있습니다. DP는 후처리 하에서 보존되므로(보조정리 3), 이는 프라이버시 보장에 비용이 들지 않으며 정확도를 크게 향상시킬 수 있습니다.
우리는 이 알고리즘을 알고리즘 2의 임의 트리로 일반화합니다. 이를 통해 서로 다른 팬아웃과 서로 다른 레벨 또는 동일한 레벨의 서로 다른 노드에서 서로 다른 노이즈를 가진 트리를 처리할 수 있으며, 이는 우리가 연구하는 전환 보고 트리의 경우입니다.
트리 레벨에 프라이버시 예산을 할당하기 위해 가장 간단한 접근 방식은 레벨 간에 균등하게 나누거나 가장 낮은 레벨에 모든 예산을 배치하는 것입니다. 그러나 기본 구성(보조정리 2)을 통해 트리의 노드 간에 프라이버시 예산을 임의로 할당할 수 있으며, 불균등한 분산을 가진 노이즈가 있는 초기 추정치에도 후처리(알고리즘 2)를 적용할 수 있습니다. 이는 불균등한 프라이버시 예산 할당으로 정확도를 향상시킬 수 있는지, 그렇다면 어떻게 할 수 있는지에 대한 질문을 제기합니다.
실제 개수 c가 주어지면, 프라이버시 예산 할당을 최적화하기 위해 탐욕적 반복 접근 방식을 사용합니다. k를 할당의 세분성에 해당하는 단계 수(예: k = 20)라고 합시다. 초기에 각 레벨에 0(또는 극히 작은) 프라이버시 예산을 할당하고, (남은) 프라이버시 예산을 크기 ε/k의 k개 단위로 나눕니다. k개 단계 각각에서 추가 ε/k 프라이버시 예산을 사용할 때 가장 낮은 RMSRE_τ(T)를 초래할 레벨을 선택하고 해당 레벨의 프라이버시 예산을 ε/k만큼 증가시킵니다.
두 개의 공개 광고 전환 데이터셋에서 알고리즘을 평가합니다.
Criteo 스폰서 검색 전환 로그(CSSCL) 데이터셋 [23]: 이 데이터셋은 Criteo Predictive Search의 실시간 트래픽의 90일 로그 샘플에서 얻은 15,995,634개의 클릭을 포함합니다. 각 포인트는 사용자 행동(예: 광고 클릭 시간)과 30일 귀속 기간 내의 잠재적 후속 전환(해당 제품 구매)에 대한 정보를 포함합니다.
비딩을 위한 Criteo 귀속 모델링(CAMB) 데이터셋 [24]: Criteo 실시간 트래픽의 30일간 약 1600만 개의 노출로 구성됩니다.
우리의 사전 기반 예산 배분과 후처리 방법은 각 설정에서 다른 모든 접근 방식과 같거나 더 나은 성능을 보입니다(그림 4와 5).
이 작업에서 우리는 Attribution Reporting API를 위한 계층적 쿼리를 연구하고 일관성 적용 및 프라이버시 예산 배분을 위한 알고리즘을 제시했으며, 두 개의 공개 광고 데이터셋에서 그 성능을 보여주었습니다.
몇 가지 흥미로운 향후 방향을 논의합니다. 우리는 각 노출이 최대 하나의 귀속된 전환을 얻는 소위 OPC("클릭당 하나") 설정에 중점을 두었습니다. 중요한 방향은 노출이 여러 귀속된 전환을 얻을 수 있는 보다 일반적인 MPC("클릭당 많은") 설정으로의 확장을 고려하는 것입니다. 또한 전환 개수 추정 작업을 전환 값 추정 작업으로 확장하는 것도 흥미로울 것입니다. 우리의 평가에서 ε가 16 정도일 때 오류가 작지만, 이는 우리가 연구하는 데이터셋과 (제한된) 기능에 특정한 것입니다. 추가 기능(예: MPC 또는 전환 값)에서 작은 오류를 달성하려면 더 큰 ε 값이 필요할 것입니다.
[1] Wikipedia, HTTP cookie: third-party cookie, https://en.wikipedia.org/wiki/HTTP_cookie#Third-party_cookie, 2023.
[2] Q. Lu, S. Pan, L. Wang, J. Pan, F. Wan, H. Yang, A practical framework of conversion rate prediction for online display advertising, in: AdKDD, 2017.
[3] Y. Choi, M. Kwon, Y. Park, J. Oh, S. Kim, Delayed feedback model with negative binomial regression for multiple conversions, in: AdKDD, 2020.
... (참고문헌 계속)
🔥 7일 한정 특가:
99,000원→ 29,000원