-
Mining Multi-Label Samples from Single Positive Labels (NeurIPS'22) 눈문 소개
올해 11월 말에 열릴 머신러닝 학회인 NeurIPS 2022에 제가 제출했던 논문 “Mining Multi-Label Samples from Single Positive Labels”이 어셉되어서 리뷰하고자 합니다. 소개 자연에 존재하는 많은 이미지 데이터셋은 여러 가지의 속성을 가지고 있습니다. 예를 들어, 얼굴 이미지 데이터셋은 검은 머리, 웃는 표정, 남성과 같은 속성을 가질 수 있습니다. 일반적으로 이런 다중 속성을 모두 조작하여 이미지를 생성하기 위해서는 모든 속성의 존재 여부가 레이블링된(다중 레이블) 데이터셋을 사용해야 하는데 이는 대채로 매우 비쌉니다. “Mining Multi-Label Samples from Single Positive...
-
Sum-Check Protocol and Applications
Introduction 최근 개인적인 사정으로 공부를 제대로 못하다가 정신을 차리고 Thaler의 책을 읽고 있습니다. 그 내용 중 일부분인 Sum-Check Protocol과 이를 활용한 application들에 대해서 짚고 넘어가고자 합니다. 이번 글에서는 다루지 않으나, 최근 등장한 HyperPLONK도 역시 Sum-Check Protocol에 기반하고 있으니, 이를 공부하기 위해서라도 Sum-Check에 대해서 제대로 공부해놓는 것이 좋아보입니다. The Sum-Check Protocol $v$-variate polynomial $g$가 유한체 $\mathbb{F}$ 위에서 정의되었다고 합시다. 목표는 \[H = \sum_{(b_1, \cdots, b_v) \in \{0,1\}^v} g(b_1, \cdots , b_v)\] 가 성립함을 증명하는 것인데, 특히...
-
The Short-Side Advantage in Random Matching Markets
이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의...
-
Differential Privacy
들어가며 IT기술들이 발전하며 개개인의 데이터 가치는 나날이 높아지고, 그만큼 관심이 많아지고 있습니다. 얼마 전에는 구글과 메타가 개인정보 불법수집으로 인해 과징금을 내는 등, 회사들에서도 개인정보에 관심을 가지고 있습니다. 개인정보들 중에서도 조금더 민감한 정보들이 있을 수 있습니다. 이름이나 생일같은 정보는 하나만 있으면 개인을 특정하기 굉장히 어렵지만, 희귀병이 있다거나 하는 등 한 가지의 정보만 있더라고 개인을 특정할 수 있는 문제들도 있습니다. 이번에는 이러한 데이터들을 어떻게 privacy를 지키면서 관리할 수 있는지에 대해 알아보려고 합니다. Differential privacy 이전부터는 Database에 데이터를...
-
알고리즘 문제 접근 과정 11
알고리즘 문제 접근 과정 11 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Two Machines - ICPC 2019 Seoul Nationalwide Internet Competition L번 관찰 주어진 문제를 간단히 본다면, 머신 A와 머신 B에서 각각 작업에 걸리는 시간이 다른 N개의 일을, A와 B에 적절히 할당하여 동시에 일을 진행하고,...