구글의 FLoC 솔루션 (쿠키없는 세상, 그곳은 어떤곳일까..?)

« 2024/04 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

0. 들어가며

History

2019년 구글이 Privacy Sandbox 프로젝트의 시작을 발표하다.
Privacy Sandbox란 개인정보 보호에 해를 끼치지 않고 광고를 판매할 수 있는 표준을 구현하는 구글의 프로젝트 이름이다. 즉 웹상에서 유저의 개인정보인 쿠키(third-party)를 수집하지 않고도 광고 타겟팅을 할 수 있는 솔루션을 만들겠다는 의미이다. 또한 2022년까지 쿠키를 자사 웹브라우저 크롬에서 단계적으로 폐지하겠다고 함께 밝혔다. 그리고 구글은 이 솔루션이 FLoC(Federated Learning of Cohorts)를 기반으로 한다고 밝혔다.

2021년 1월, 구글이 Privacy Sandbox 프로젝트의 흥미로운 결과를 공개하다.
FLoC 기반의 새로운 솔루션을 기존 쿠키 기반 솔루션과 비교 테스트 한 결과, 약 95% 이상의 ROI(정확히는 conversions per dollar spent)을 기대할 수 있다는 결과를 발표했다 Wow.. 이러한 결과를 바탕으로 3월 3일, 구글은 2021년 2분기부터 구글애즈에서 FLoC 기반 솔루션을 제공하겠다고 밝혔다.

Motivation

21년 3월 초 '구글의 쿠키 수집을 대체할 새로운 솔루션 발표' 관련 기사를 접했고, 최근 대학원에서 연구(feat. 도비생활)를 시작한 동기가 Federated Learning과 씨름하며 받은 스트레스를 갑자기 굳이 본인에게 연락해서 따뜻한 욕설과 함께 한풀이했던 기억이 떠오른 저는 곧바로 아 그놈이구나! 라는 생각과 함께 흥미를 갖게 되었다.

이 글의 방향성
위 공부 동기를 보며 눈치채셨겠지만 제가 흥미를 느낀 건 FLoC 중에서도 Federated Learning 파트입니다. FLoC 솔루션을 Federated Learning과 Cohort Algorithm으로 나눌 수 있는데, ~~저는 Federated Learning 위주로 공부했고 Cohort Algorithm은 아직 깊게 공부하지 않았기에 이 글에서는 Federated Learning을 다룰 것입니다.~~
→ ~~하다보니 Cohort Algorithm도 공부하게 되었습니다. 함께 정리합니다.~~
→ 하다보니 Cohort Algorithm 정리가 길어졌습니다. Federated Learning은 별도 페이지에서 따로 정리합니다.

++ 구글의 FLoC 백서에 관련 내용이 기술 측면 뿐만 아니라, 비즈니스 측면에 대해서도 길지않게 잘 서술되어 있습니다. 페이지 하단 Reference에 추가해뒀으니 관심 있으신 분들은 꼭 읽어보시는 것을 추천드립니당

1. What is FLoC?

Definition
Federated Learning of Cohorts의 약자로, Federated Learning(연합학습) + Cohort Algorithm(군집 알고리즘)을 융합하여 만든 구글의 새로운 광고 타겟팅 솔루션이다. 유저에게 Cohort id를 부여함으로써 Cookie id를 대체할 수 있다고 주장한다.

Performance & Result
해당 솔루션을 통해 구글은 유저들의 정보를 수집하지 않고도 기존 솔루션과 비교했을 때, 유저 타겟팅을 95% 이상 해냈다. 유저의 정보를 수집하지 않았는데 유저를 도대체 어떻게 타겟팅하는걸까 (구? : 쌀 없이 밥을 짓는데 성공했습니다...?)

FLoC 솔루션의 5가지 원칙(in 백서)
1. Cohort id는 개인의 사이트 이동 기록에 대한 추적을 막아야 한다.
2. 각 Cohort는 비슷한 브라우저 행동을 가진 유저들로만 구성된다.
3. 각 유저는 자신들만의 고유한 최적화 함수를 지니기 때문에, Cohort assignment 알고리즘은 반드시 비지도 학습 알고리즘이여야 한다. (=Cohort id는 무조건 각 device에서 계산되어야 한다)
4. Cohort assignment 알고리즘은 명확하고 쉽게 설명될 수 있도록 "magic numbers"을 사용하지 않는다.
5. 개인의 Cohort를 계산하는 알고리즘은 저수준 장비의 브라우저에서 실행될 수 있도록 단순해야만 한다.

2. Explanation about FLoC solution

FLoC 솔루션의 목적은 결국 개인 프라이버시 문제를 해결하면서도 기존 관심도 기반 유저 타겟팅을 해내는 것이다. 이를 구현하기 위해 FLoC는 개인을 군중(Cohort)안에 숨기는 방법을 택했다.

위 Figure에서 볼 수 있듯, FLoC에서는 Cohort 알고리즘을 통해 Users(N=6) → Cohort(M=2)로 그룹핑했다. 기존의 쿠키id 기반 솔루션은 User에 쿠키 id를 할당하고 이들에 타겟팅했다. 하지만 위 FLoC 솔루션에서는 쿠키 id를 할당하지 않고, Cohort로 묶은 후에 각 Cohort에 Cohort id를 할당하여 Cohort 단위로 타겟팅을 한다. (Cookie id → Cohort id)

여기서 Cohort 알고리즘을 어떻게 짜느냐에 따라 A의 경우로 묶일 수도 있고, B의 경우로 묶일 수도 있다. 이 부분에서 기존 쿠키id 기반 솔루션보다는 정확성이 떨어질 수밖에 없겠지만, 구글은 이 문제를 해결하기 위해 관련 백서에서 나와있듯 여러 Cohort 알고리즘을 테스트해왔고 그 결과 95%라는 일치율을 이뤘다.

Clustering Algorithms

결국 가장 중요한 것은 각 유저들을 관심사 기준의 cohort id로 분류하는 방법(알고리즘)이고, 구글은 FLoC에 적용할 후보 클러스터링 알고리즘 3개에 대해 아래 항목들을 기준으로 테스트했다.

클러스터링 후보 알고리즘: SimHash, SortingLSH, Affinity hierarchical clustering with centroid

Privacy : 대규모 Cohorts에 포함된 유저는 어느정도인가?
→ 각 Cohort는 무조건 k-anonymous 성질을 만족해야 한다. k가 클수록 Privacy 성질이 높다.

Utility : 동일 Cohort에 포함된 유저들의 유사성은 어느정도인가?
→ 하지만 k가 너무 높다면 Cohort에 포함되어 있는 유저들의 관심도 유사성이 다를 수 있다.

Centralization : 유저 개인 정보들로부터 Cohort id를 계산하는 부분에서 데이터가 centralized server로 전송되어야 하는가?
→ Cohort id를 계산하는 과정은 반드시 device에서 진행되어야 한다. 광고주, 구글에서는 오로지 유저의 계산 결과인 Cohort id에 대해서만 접근 가능하다.

About Privacy-Utility Trade-off
Cohort 알고리즘이 필연적으로 가지는 Trade-off 관계이다. 더 많은 유저들이 동일한 cohort id를 공유한다면 Privacy는 상승할 것이지만 해당 Cohort가 대변하는 정보의 질은 점점 하락할 것이다. 이에 가장 이상적인 Cohort 알고리즘은 관심사가 비슷한 유저들을 최대한 많이 하나의 코호트로 군집화 하는것이다. 그렇다면 Privacy를 보호하기 위해 Privacy 값을 어떻게 정의할 것인가? 이를 위해 k-anonymous라는 개념을 도입했고 정의는 아래와 같다.
We say a cohort id is k-anonymous if it is shared by at least k users (즉, k값이 커질수록 해당 코호트에 포함된 유저들의 Privacy를 더 잘 보호함을 의미한다.)

Clustering 알고리즘의 input을 d-dimension vector 라고 하자. vector 하나가 유저 한명의 브라우저 정보를 담는다.(URL을 기준으로 one-hot encoding, NLP의 TF-IDF encoding 등의 방법을 사용합니다.)

1) SimHash

SimHash 알고리즘은 구글에서 만든 Locality-sensitive hashing(LSH) 중 하나이다.

Definition
input이 d-dimensional vector x이고, output이 x에 대응하는 해시값인 p-bit vector Hp(x)라고 하자. 이 때 해시 벡터의 i-th coordinate 값은 아래를 통해 계산된다.
where, w1, ..., wp are random unit-norm vectors
이를 통해 동일한 해시를 공유하는 input vectors(유저들)은 하나의 cohort에 대응되도록 한다. 여기서, SimHash의 output으로 나온 해시값이 같아도 유저들이 다를 수 있지 않느냐? 라는 질문에 대답은 아래와 같다.
ex) 3-bit SimHash x = (0.3, 0.8)인 벡터 x에 대해 아래 그림과 같이 w1, w2, w3의 unit norm 벡터가 있다고 가정하자. 그러면 x의 3-bit SimHash 값 H3(x) = [1,-1,1] 의 값이 나온다.

SimHash 값이 유사성을 대변할 수 있는가?
Let x1, x2 are input vectors. 이 둘이 동일한 해시 값(cohort id)을 가질 확률을 위 정의를 통해 계산하면 아래와 같다.
where, θ(x1, x2) corresponds to the angle between vectors x1, x2
위 식을 통해 두 벡터가 이루는 각이 작을수록 같은 해시값이 나올 확률이 커진다는 것을 알 수 있고, 게다가 그 값이 exponential하게 적용되기에 정말 이루는 각이 작을수록(similar할수록) 같은 해시값을 가짐을 알 수 있다.

Pros & Cons
(1) Pros
SimHash의 알고리즘을 보면 알 수 있듯이, 이 알고리즘은 한 유저의 Cohort 값(cohort id)을 다른 유저들의 정보 없이도 온전히 계산할 수 있다. → cohort id를 계산하기 위해 Centralized data collection이 필요 없다. 즉 유저의 데이터들이 구글로 전송되어 계산될 필요가 없으므로 Centralization 항목을 완벽하게 만족한다. (압도적 장점)
(2) Cons
SimHash 알고리즘은 minimum cluster size를 지정할 수 없다. → 만약 해시값이 1000101 인 유저가 한명이 될 수도 있다는 얘긴데, 이는 Privacy 측면에서 문제가 발생한다. 관련하여 구글에서는 이 문제를 특정 서버를 통해 각 Cohort의 크기를 트래킹한 후, Cohort가 k-anonymous 성질을 만족하지 않으면 cohort id를 반환하지 않는 방법을 통해 해결할 수 있다고 한다. ++ 이후 시뮬레이션 결과에서도 나오겠지만, 알고리즘이 비교적 간단한만큼 성능이 좋은 편은 아니다.

2) SortingLSH (Upgrade Version of SimHash)

Definition
SimHash 알고리즘으로 나온 Cohort를 다시한번 클러스터링함으로써 k-anonymity를 보장하면서도 SimHash의 사이즈 불균등(heterogeneous) 문제를 해결한 알고리즘

SimHash 알고리즘의 문제
SimHash 알고리즘을 진행한 후 계산된 Cohort를 봤더니 이슈가 발생했다. 아래 왼쪽 그림과 같이 각 Cohort의 사이즈가 매우 불균등(heterogeneous)하게 나타난 것이다. → Cohort마다 Utility 성능이 천차만별이게 되고, 사이즈가 큰 Cohort는 Utility 부문에서 비교적으로 유의미하게 낮은 성능을 갖게 됨.

흠.. 그러면 오른쪽 그림처럼 기존 2-bit Cohort에 Cohort 사이즈 비슷해지도록 선 하나 그어서 4-bit Cohort로 만들면 해결되지 않느냐? → 더 쪼개진 Cohort가 k-anonymous 성질을 깨뜨릴 수 있음
아 k-anonymous 성질을 만족하면서도 Cohort 사이즈를 균등하게 만들 수 있는 방법이 있을까..? 를 해결한 알고리즘이 SortingLSH이다.

SortingLSH 알고리즘의 원리
Let h1 = Hp(x1), . . . , hn = Hp(xn), h는 n명의 유저에 대해 SimHash를 통해 생성된 p-bit 해시값들이다. 기존의 SimHash 알고리즘이였다면 h값이 동일한 유저들을 기준으로 cohort를 생성했겠지만, SortingLSH는 아래 두가지 방법을 통해 Cohort들을 생성한다.
1) h1, ..., hn을 사전순으로 정렬하여 h(1) ≤ . . . ≤ h(n)의 해시리스트를 얻어낸다.
2) 위 정렬된 해시리스트에서 인접한 해시값들을 최소 k개 이상씩 묶어서 코호트로 묶는다.
ex) k-anonymity SortingLSH, k=3

Pros & Cons
(1) Pros
SimHash 알고리즘의 Cohort 사이즈 불균형 이슈를 해결했기에 SimHash보다 알고리즘의 성능이 향상되고, k-anonimity를 보장할 수 있다. → SimHash보다 Utility, Privacy 측면에서의 성능 향상
(2) Cons
딱히..?
++ 아래와 같은 질문이 나올 수도 있을 것 같다.
Q) SortingLSH 과정 중, 모든 유저의 해시값을 사전순으로 정렬하기 위해서는 모든 해시값들을 결국 한 곳인 Central server에 모아야 하는거 아닌가요? 그럼 Centralization 측면에서 큰 문제가 있을텐데요!
A) Central server에 고객들의 Raw 데이터가 전달되는 것이 아니라, 고객들의 해시값이 전달되는 것이기에 큰 문제는 없습니다. 또한 Central server에 해시값들을 모아야 하는 것은 맞지만, Centralization 측면에서 minimum cluster size 이슈를 해결한 버전의 SimHash 알고리즘과 동등한 위치(성능)를 가집니다. 왜냐하면 SimHash 알고리즘에서도 계산된 해시값들은 k-anonymity를 보장하기 위해서 서버에 필요하기 때문입니다.

3) Affinity hierarchical clustering with centroids

Affinity hierarchical 클러스터링 알고리즘에 관해 구체적으로 설명하기에는 길어지기에 아래 Reference에 해당 논문 전문(NIPS 2017)을 올려두고, 본문에서는 간략하게 정리하겠다.

Definition
Boruvka's MST 알고리즘을 기반으로 한 계층적 클러스터링 알고리즘으로, user-to-user similarity 그래프를 기반으로 계산된다. (where, Boruvka's MST 알고리즘은 그래프에서 minimum spanning tree를 찾기 위한 그리디 알고리즘)

Affinity hierarchical clustering 원리
1) About hierarchical clustering(계층적 군집화)?
계층적 군집화는 여러 군집 중에서 가장 유사도가 높거나 거리가 가까운 군집 두개를 선택하여 하나로 합치면서 군집 개수를 줄여가는 방법을 말한다.
2) About Affinity (hierarchical) clustering?
Affinity 클러스터링은 기본적으로 hierarchical하고, 아래 핵심적인 조건을 만족한다.
- 초기의 모든 노드는 그 자체로 하나의 클러스터이다.
- 각 round마다 어떤 클러스터든 그 클러스터에 가장 가까운 클러스터와 병합하도록 한다.
- 설정한 목표 클러스터 개수에 도달하면 알고리즘을 멈춘다.
  example of Affinity clustering

Affinity Clustering의 변형을 통한 Cohort id 계산 과정
Graph construction, Graph clustering, User to cluster assignment의 3단계로 계산이 이뤄진다.
1) Graph construction
user-to-user similarity weighted 그래프를 만든다. (User는 노드에 대응, User간 유사도는 edges에 대응된다. 또한 User간의 유사도는 cosine similarity-weighted edge로 나타낸다)
2) Graph clustering
유저 클러스터링 알고리즘은 hierarchical agglomerative 클러스터링을 변형하여 쓴다. 이는 Bottom-up 방식의 hierarchical 알고리즘으로 다음과 같다.
- 모든 노드는 그 자체로 하나의 클러스터이다.
- 클러스터들은 각 클러스터가 설정한 최소 클러스터 사이즈에 도달할때까지 병합한다.
- 이후 각 클러스터에 대해 클러스터에 포함된 유저 정보들의 평균을 냄으로써 centroid(데이터 중심)을 계산한다.
3) User to cluster assignment
마지막 단계는 각 사용자를 클러스터에 연결하는 과정이다. 간단하게 각 유저를 가장 가까운 centroid가 있는 코호트에 할당함으로써 이루어진다.

Pros & Cons
1) Pros
Utility 측면에서의 성능이 좋다. (정확도 상승)
2) Cons
SimHash, SortingLSH와 달리 affinity 클러스터링은 첫번째 단계(Graph construction)에서 유저들의 raw 브라우징 기록에 접근하게 된다. → Centralization 측면을 아예 무시하게 됨.
++ 아래와 같은 질문이 나올 수 있을 것 같다.
Q) 단점으로 Centralization을 아예 무시하게 된다면, FLoC의 목적인 '유저 개인정보 수집을 중단하자'에 위배되기에 아무리 성능이 좋아도 필요없는 방법 아닌가. 이게 왜 클러스터링 알고리즘 후보에 있는것인가?
A) 이 알고리즘의 Centralization 이슈를 Federated Learning(연합학습)을 이용하여 기술적으로 해결할 수 있습니다.
Federated Learning(연합학습)이란?

3. Evaluation for Datasets

지금까지 연합학습 부분을 제외하고 FLoC 솔루션에 대해 공부했다. 이제 위에서 정리한 3가지 Cohort 알고리즘 후보들을 데이터셋에 적용하여 성능을 평가해보겠다.

1) Datasets

Million Song Dataset(MSD) : 카테고리와 유저 id들이 매핑되어있는 100만개 노래 데이터로, 65만명의 청취 기록으로 만들어졌다.

MovieLens 25M : 추천 시스템을 평가할 때 사용하는 기준 데이터셋

2) Results

Cosine similarity(유사도) 평가
- Affinity centroid >> Sorting LSH > SimHash
- 역시나 raw 상태의 데이터를 사용한 Affinity centroid 알고리즘이 매우 높은 성능을 보임을 알 수 있다.

Word clouds
i) Random cohorts에 대한 Word clouds
ii) 8-bits SimHash cohorts에 대한 Word clouds
iii) affinity clustering에 대한 Word clouds
- affinity clustering을 했을 때, SimHash에 의한 Word cloud보다 cohort의 크기가 더 작고 전반적으로 잘 정의되었음을 알 수 있다. (라고 구글 측에서 말하는데 사실 명확하게 무엇이 더 잘되었는지는 평가하기 애매해보임)

3) For Google Display Ads Dataset

Datasets
GDN에서 7일동안 수집한 동일하지 않은 URLs

Feature Extraction (피쳐 추출, URL → vector)
One-hot encoding, TF-IDF encoding, Topic categories(url 상에서 나타나는 카테고리, =Vert depth 3) 총 3가지 방법으로 진행한다.

클러스터링 알고리즘
SimHash 알고리즘

Evaluation
Building interest profiles, Building conversion profiles, Evaluating predictive power 항목에 통해 평가한다.

Results

Conclusions
- 매우 높은 익명성 수준에서도 Cohort로 유저를 그룹화하면 랜덤 클러스터링보다 3.5배 더 높은 recall 값을 가진다.
- 인코딩 방법은 Topic 카테고리를 통해 인코딩하는게 성능이 가장 좋다.

4. Conclusion

단순히 연합학습에 대한 흥미로 시작했던 FLoC에서 Cohort 알고리즘까지 파다보니 길어져서 연합학습은 추후에 따로 다시 정리하겠다. 힘들고 졸리고 피곤하다. 몇가지 중요한 사실을 요약하고 글을 마무리짓겠다.

FLoC는 아직 정식 서비스 되지 않은 솔루션으로, 글을 쓰고 있는 현재까지도 관련된 정보가 차례차례 공개되고 있다. 그나마 공식적인 자료라면 FLoC 백서인데 이 또한 마지막 수정일이 20.10.22이고, 이 백서에서도 마찬가지로 아직 어느 알고리즘을 사용할지 등에 대해서는 계속 테스트 중이라고 밝혔다. (완전한 솔루션 X)

따라서 위 3가지 Cohort 알고리즘 중 어떤 알고리즘을 사용하는지는 아직 공개되지 않았으나 Floc API를 통해 대강 확인해본 결과 SimHash, SortLSH, Affinity hierarchical clustering with centroids 모두를 파라미터를 통해 선택적으로 사용할 수 있도록 제공해주는 것 같다.