획득 비용이 큰 대상 임베딩에서의 정확한 희소 할당: 실현값을 고정한 최적성 인증과 실증 감사
Exact Sparse Assignment with Costly Target Embeddings: Fixed-Realization Certificates and an Empirical Audit
한국어 초록
임베딩 기반 일대일 연결은 컴퓨터 비전과 데이터 통합에서 흔히 쓰인다. 탐지 결과를 추적 궤적에 연결하거나 서로 다른 데이터베이스의 레코드를 연결하는 것이 그 예다. 이 파이프라인은 흔히 간선 점수를 저비용 항과 신경망 임베딩 내적의 합으로 정하고, 일부 항목을 미할당 상태로 둘 수 있는 희소 할당 문제를 푼다. 대상 임베딩을 얻는 비용이 크면 일부를 선별적으로 획득하고, 현재 할당의 최적성을 인증한 시점에 중단할 수 있다. 본 연구는 노름이 1인 임베딩의 최적성 인증을 제시한다. 모든 재할당에서 알 수 없는 부분을 지지 함수로 제한하고, 두 번째 희소 할당으로 가능한 최대 강건 이득을 구한다. 현재 배정된 상대를 중심으로 삼는 공유 경계는 어떤 고정 중심 삼각부등식 경계보다도 적어도 그만큼 엄밀하다. 신경망 특징이 배치 구성에 따라 달라질 수 있을 때 무엇을 인증하는지도 명확히 한다. 인증 대상은 이미 획득한 행의 실제 값과 나머지 행을 단위 공 안의 값으로 채울 수 있는 모든 경우다. 다른 배치로 순전파를 다시 실행한 결과는 다른 문제다. 별도로 배치를 구성해 만든 캐시와 대조하면 다른 성질을 검사하게 된다. 첫 파일럿에서 이 방식은 목적 함수가 $2.49\times10^{-6}$만큼 어긋난 것처럼 보이는 허위 실패를 만들었다. 가중치를 고정한 인코더 두 종과 공개 텍스트 개체 매칭 벤치마크 네 개로 교정한 절차를 감사했으며, 이미지 데이터는 사용하지 않았다. 인증 시뮬레이션 96건과 온라인 선별 실행 시간 측정 120건에서 모두 해당 실행의 실현값에 대해 정확했다. 가장 큰 목적 함수 차이는 $6.82\times10^{-13}$이었다. 그룹 크기가 8일 때 공유 인증은 간선 후보에 등장하는 대상 중 평균 60%를 획득했다. 평균 중심은 74%, 최소 포함 공(MEB) 중심은 69%, 원점 중심은 60%였다. 공유 인증은 평균 중심과 MEB 중심보다 앞섰지만 원점 중심과 같았다. 절감 효과는 대상을 7%만 획득한 한 벤치마크에 집중됐다. 미리 정한 실행 시간 가설과 달리 선별 실행은 회당 0.510초 더 느렸다(데이터셋 군집 기준 95% 구간 [+0.248, +0.772]). 균일한 마이크로배치로 다시 인코딩했을 때 최적해가 유지된 것은 인코더와 데이터셋 조합 8개 중 5개뿐이었다. 온라인 실행은 120건 중 45건에서 점수가 거의 같은 후보를 두고 미리 전부 인코딩한 캐시와 결과가 달랐다.
원문 초록
Embedding-based one-to-one association is common in vision and data integration: detections are associated with tracks and records are linked across databases. Such pipelines often solve a sparse optional assignment whose edge scores add a cheap term to an inner product of neural embeddings. When target embeddings are costly, one can acquire them selectively and stop once a certificate proves that the current assignment is optimal. We give such a certificate for unit-norm embeddings. It bounds the unknown part of every reassignment by a support function and maximizes the resulting robust gains with a second sparse assignment; a shared owner-centred bound dominates any fixed-centre triangle bound. We make precise what is certified when network features are not batch-invariant: the realized values of the acquired rows and every unit-ball completion of the rest, not a second forward pass in a different batch. Auditing against a separately batched cache tests a different property; on our first pilot it produced a spurious $2.49\times10^{-6}$ objective failure. We audit the corrected protocol on four public text entity-matching benchmarks with two frozen encoders; no image data is used. All 96 certificate simulations and 120 online selective timings were exact on their own realization (largest objective gap $6.82\times10^{-13}$). At group size 8 the shared certificate acquires on average 60% of candidate-active targets, against 74% (mean centre), 69% (MEB) and 60% (zero centre): it beats the mean and MEB centres but not the zero centre, and savings concentrate in one benchmark (7% acquired). The prespecified runtime claim is contradicted: selective execution is +0.510 s slower per run (dataset-cluster 95% interval [+0.248, +0.772]). Uniform-microbatch re-encodings preserved the optimum in only 5 of 8 encoder-dataset cells, and 45 of 120 online runs disagreed with an eager cache at near-ties.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.19770v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.