arXiv:1511.04472

Solving Jigsaw Puzzles with Linear Programming

Rui Yu, Chris Russell, Lourdes Agapito

제출 2015-11-13

원문 초록

We propose a novel Linear Program (LP) based formula- tion for solving jigsaw puzzles. We formulate jigsaw solving as a set of successive global convex relaxations of the stan- dard NP-hard formulation, that can describe both jigsaws with pieces of unknown position and puzzles of unknown po- sition and orientation. The main contribution and strength of our approach comes from the LP assembly strategy. In contrast to existing greedy methods, our LP solver exploits all the pairwise matches simultaneously, and computes the position of each piece/component globally. The main ad- vantages of our LP approach include: (i) a reduced sensi- tivity to local minima compared to greedy approaches, since our successive approximations are global and convex and (ii) an increased robustness to the presence of mismatches in the pairwise matches due to the use of a weighted L1 penalty. To demonstrate the effectiveness of our approach, we test our algorithm on public jigsaw datasets and show that it outperforms state-of-the-art methods.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2503.10945v3cs.LG공통 태그 Position공식 코드 · Papers with Code

머신러닝에서 차분 프라이버시 보장을 보고하기 위한 가우시안 DP

Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning

DP-SGD와 같은 머신러닝(ML) 알고리즘에 대한 차분 프라이버시(DP) 보장을 보고하는 현재의 관행은 불완전하고 잠재적으로 오해를 초래할 수 있는 그림을 제시합니다. 예를 들어, 어떤 메커니즘에 대해 단일 $(\varepsilon, \delta)$만 알려진 경우, 표준 분석은 학습 데이터 레코드에 대한 매우 정확한 추론 공격이 존재할 수 있음을 보여주지만, 보다 신중한 분석을 통해 살펴보면 대부분의 실용적인 메커니즘에서는 그러한 정확한 공격이 존재하지 않습니다. 이 포지션 페이퍼에서 우리는 ML에서 DP 보장을 전달하는 주요 수단으로 _비점근적_ 가우시안 차분 프라이버시(GDP)를 사용하는 것이 이러한 잠재적 단점을 피할 수 있다고 주장합니다. DP 문헌의 두 가지 최근 발전, 즉 (i) DP-SGD의 프라이버시 프로파일과 $f$-DP 곡선을 임의의 정확도로 계산할 수 있는 오픈소스 수치 어카운턴트, (ii) DP 표현에 대한 의사결정 이론적 메트릭을 활용하여, 우리는 수치 어카운턴트를 사용해 GDP에 대한 비점근적 경계를 제공하는 방법을 보이고, GDP가 해당 메트릭으로 정량화된 오차를 거의 없이 DP-SGD 및 관련 알고리즘의 전체 프라이버시 프로파일을 포착할 수 있음을 보여줍니다. 우리의 주장을 뒷받침하기 위해, 최신 DP 대규모 이미지 분류와 미국 10년 인구조사를 위한 TopDown 알고리즘의 프라이버시 프로파일을 조사하였으며, 모든 경우에서 GDP가 해당 프로파일에 현저히 잘 맞음을 관찰하였습니다. 마지막으로 이 접근 방식의 강점과 약점에 대해 논의하고, GDP로부터 이점을 얻을 수 있는 다른 프라이버시 메커니즘에 대해 논의합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.