원문 초록
We consider an oracle that processes a limited batch of records at a time and clusters those that refer to the same real-world entity. We study how to interrogate such an oracle to resolve entities in a dataset whose size is far larger than a single batch, and where no batch is guaranteed to contain all records of any given entity. We aim at a pay-as-you-go approach, to have full control over the costs (the number of oracle consults), while achieving the highest possible recall at every step. We formally cast this problem as batched entity resolution, prove that selecting optimal batches is NP-hard, and provide an optimal solution under a natural condition on entity sizes. Finally, we evaluate our approach on six datasets and show its superiority over state-of-the-art baselines.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.24407v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
비용 효율적 공간 전사체학을 위한 능동적 스팟 선택 벤치마킹
Benchmarking Active Spot Selection for Cost-Efficient Spatial Transcriptomics
공간 전사체학(spatial transcriptomics, ST)은 조직 맥락에서 유전자 발현을 측정하지만, 촘촘한 캡처 그리드는 비용이 많이 들 수 있으며 형태학적으로 유사한 영역을 반복적으로 샘플링할 수 있다. 대부분의 능동 학습(active learning) 전략은 범주형 레이블과 독립 표본을 위해 개발되었다. 우리는 발현 벡터가 고차원·연속이고 후보들이 공간적으로 상관된 ST에서, 균일 Random 샘플링 대비 능동 학습에 대한 후향적 pool 기반 벤치마크를 수행한다. 완전 프로파일링된 공개 ST 코호트 두 개를 사용해 후보 발현 벡터를 마스킹하고, 불확실성 기반 Monte Carlo 드롭아웃(MC-dropout) 및 temporal output discrepancy(TOD), 다양성 기반 CoreSet 및 TypiClust 영감 선택으로 다회차 선택을 시뮬레이션한다. 환자 수준 교차 검증 하에서 fold 전체 학습 spot 풀의 5%, 10%, 30%, 50%에서 160개의 완료된 구성을 비교하며, 별도의 전체 레이블 기준(reference)을 둔다. 각 예산 내에서 전략들은 선택 일정, 형태-발현 예측기, 최적화 프로토콜을 공유한다. 슬라이드 내 유전자별 평균 Pearson 상관계수(PCC), 발현 클러스터 일치, Moran's I 충실도를 평가한다. HER2 양성 유방암에서 네 가지 능동 전략의 Random 대비 pooled mean PCC 차이는 5%, 10%, 30%, 50%에서 각각 -0.0176, -0.0117, +0.0056, +0.0057이었다. 피부 편평세포암(cutaneous squamous cell carcinoma, cSCC)에서는 5%에서 세 전략이 Random보다 낮았고, 10%에서는 네 전략 모두 Random보다 낮았다. HER2 양성 유방암에서 CoreSet과 MC-dropout은 가장 작은 두 예산에서 Random보다 PCC는 낮지만 발현 클러스터 일치는 더 높았으며, 이 패턴은 cSCC에서는 재현되지 않았다. 보고된 고정 학습 horizon 하에서, 평가된 능동 전략들은 작은 예산에서 Random을 일관되게 개선하지 않으며, 순위는 평가 지표에 따라 달라진다.
DRP-FLR: 스마트 그리드 유연 부하 조절을 위한 수요 반응 잠재력의 데이터 기반 평가
DRP-FLR: Data-Driven Assessment of Demand Response Potential for Flexible Load Regulation in Smart Grids
AI 워크로드와 재생에너지 자원의 급속한 증가는 전력 시스템의 수급 불균형을 악화시켜, 효율적 배분을 위해 설계된 기존 부하 조절 방식이 부적절해지게 하며, 스마트 그리드에서 부하 제어 가능성을 확보하기 위한 수요 반응(DR) 메커니즘의 필요성을 촉발한다. 그러나 기존 DR 중심 접근법은 전기 요금 또는 거주자 편의성 최적화에만 초점을 맞추어 시스템 수준의 균형에 대한 이점이 제한적이다. 다른 접근법들은 이질적 에너지 개체의 다양하고 동적인 소비 패턴을 간과하여 상당한 과조절 또는 저조절을 초래한다. 따라서 우리는 DRP-FLR을 제안한다. 첫째, DRP-FLR은 외생적 지식(예: 개체 정보, 예측 시점)을 역사적 부하 표현에 임베딩하여 정확한 단기 부하 예측을 달성한다. 다음으로, 역사적 부하 곡선을 클러스터링하여 개체별 부하 패턴 프로파일을 구성하고, 예측된 부하와 패턴 프로파일을 매칭하여 DR 잠재력을 추정한다. 마지막으로, DRP-FLR은 유연 부하 조절을 혼합 정수 최적화 문제로 공식화하고 MILP 솔버로 이를 풀어 DR 활용, 참여자 경제적 이익, 재생에너지 수용을 공동으로 최적화하면서 수급 균형과 경제적 실현 가능성을 강제한다. 지역 그리드와 캠퍼스 마이크로그리드에서의 실험은 DRP-FLR이 조절 편차를 36.63%-91.87% 감소시키고 참여자 이익을 평균 44.66% 개선함을 보여준다.
확장 가능한 양자 향상 의료 이미지 분할을 위한 슈퍼픽셀 기반 QUBO
Superpixel-Based QUBO for Scalable Quantum-Enhanced Medical Image Segmentation
이차 무제약 이진 최적화(QUBO)는 의료 컴퓨팅 문제를 위한 강력한 프레임워크로 부상했다. 이진 결정 변수는 임상적 선택을 자연스럽게 표현하므로, QUBO 공식화는 양자 어닐링(quantum annealing) 하드웨어에 잘 맞다. 그러나 근본적인 확장성(scalability) 과제가 실용적 배포를 제한한다. 문제 크기는 입력 차원에 따라 급격히 증가하여 계산 병목을 만들고, 응용을 단순화된 시나리오로 제한한다. 본 논문은 계층적 문제 축소를 통해 이 과제를 해결하며, 이는 의료 이미지 분할에서 입증된다. 픽셀 수준 QUBO 공식화는 256×256 이미지에 65,000개 이상의 변수를 생성하여, 기존 접근법이 42×42 해상도로 다운샘플링하고 픽셀 정보의 97%를 버리도록 만든다. simple linear iterative clustering(SLIC)을 사용해 픽셀을 지각적으로 의미 있는 영역으로 묶는 슈퍼픽셀 기반 QUBO 프레임워크를 제안하고, min-cut과 smoothness 목적함수를 결합한 영역 인접 그래프(RAG) 위에서 분할을 QUBO로 공식화한다. INbreast 유방촬영 유방암 영상에 대한 검증 결과, 분할 품질이 4.2% 향상되었음(평균 IoU 0.76 대 0.73)을 보였으며, 계산 속도는 33배 향상(0.67초 대 21.97초), 문제 크기는 97.3% 감소(1764에서 48 변수)하였다. 이는 모두 다운샘플링된 버전이 아닌 전체 해상도 영상을 처리하면서 달성되었다. 축소된 문제 크기는 또한 현재 양자 어닐러의 연결성 한계 내에 잘 들어맞아, 역사적으로 양자 하드웨어에서 픽셀 수준 QUBO 분할의 직접 배포를 막아온 임베딩(embedding) 오버헤드를 제거한다.
KeySI: 인간 피드백 기반 텍스트 임베딩 튜닝을 위한 상호작용 프레임워크
KeySI: An Interaction Framework for Tuning Text Embeddings Based on Human Feedback
대규모 텍스트 분석 작업에서는 하류 분석을 위해 텍스트 코퍼스를 임베딩하는 데 사전학습된 언어 모델이 자주 사용된다. 그러나 이러한 모델은 도메인 특화 의미를 포착하는 데 어려움을 겪을 수 있으며, 이를 적응시키려면 일반적으로 대량의 라벨 데이터와 학습 파이프라인 구현에 필요한 기술적 전문성이 요구된다. 최근 접근법들은 문서 투영에서의 시각적 상호작용이 모델 튜닝을 위한 학습 신호로 인간 피드백을 포착할 수 있음을 보여주었다. 그러나 이러한 방법들은 문서 수준 피드백을 기반으로 동작하며, 효과적인 피드백을 제공하려면 사용자가 개별 문서를 열어 평가해야 한다. 본 논문에서는 키워드 기반 개념 명세를 통해 특징 수준 피드백을 가능하게 하는 상호작용 프레임워크 KeySI를 제안한다. 사용자는 추출된 키워드를 개념을 나타내는 그룹으로 구성하여 피드백을 지정하며, KeySI는 이를 후속 튜닝을 위한 문서 수준 지도 신호로 변환한다. 키워드를 주요 상호작용 매체로 사용함으로써 KeySI는 수동 문서 검토 및 라벨링의 필요성을 줄이고 임베딩 모델 적응의 진입 장벽을 낮춘다. 우리는 코퍼스가 주어졌을 때 대표 키워드를 선별하고, 차원 축소를 통해 키워드와 문서 임베딩을 시각화하며, 키워드 그룹의 대화형 명세를 허용하고, 시스템 피드백을 통한 반복적 정제를 지원하는 프로토타입 구현을 제시한다. 사용자 연구, 사용 시나리오, 정량 실험을 통해 KeySI를 평가하며, 사용자 의도 포착 및 임베딩 정렬 개선에서의 효과를 입증한다.
실시간 군중 추적을 위한 증분 최적 할당
Incremental Optimal Assignment for Real-Time Crowd Tracking
밀집 군중에서의 다중 객체 추적은 매 비디오 프레임마다 검출과 궤적 간의 이분 할당 문제를 풀어야 한다. 고전적인 헝가리안 알고리즘은 이를 $O(N^3)$ 시간에 해결하지만, 수백 명의 사람이 있는 대규모 장면에서는 병목이 된다. 우리는 군중 추적 비용 행렬의 블록 희소(block-sparse) 구조를 활용하는 \emph{증분} 할당 알고리즘을 제안한다 — 각 군중 클러스터 내부에서는 조밀하고, 클러스터 간에는 거의 0에 가깝다. 헝가리안 알고리즘과 동일한 최적 $N \times N$ 할당을 계산하지만, 증분 전략을 통해 수행한다: 한 번에 한 사람씩 추가하며, $n-1$단계 이후 이중 잠재(dual potentials)가 $(n-1)\times(n-1)$ 부분 문제에 대해 \emph{정확히 최적}이라는 사실을 활용한다 — 이는 헝가리안 알고리즘이 $N$번의 외부 반복 동안 유지하는 중간 실행 가능성(intermediate feasibility)보다 엄격히 더 강한 조건이다. 따라서 각 새 단계는 인증된 최적 시작점에서 단 한 번의 증강 경로(augmenting path) 탐색만 필요하다. 이는 반복적인 전체 행렬 스캔을 피하면서 동일한 전역 최적 결과를 보장한다. 대각 재정렬 불변(diagonal-reordering invariant)은 데이터 구조를 컴팩트하고 캐시 친화적으로 유지한다. $N \in [200, 5000]$ 범위의 사람들이 밀집 클러스터로 구성된 현실적인 군중 벤치마크에서, 우리 알고리즘은 헝가리안 기준선 대비 \textbf{3.7--6.5$\times$} 속도 향상을 달성하며, 헝가리안과 동일한 증명 가능한 최적 매칭을 생성한다. 속도 향상은 $N$에 따라 증가하며 $N=3000$을 넘어서도 안정적으로 유지되어, 경기장 출구나 대규모 공공 행사와 같은 대규모 군중 장면에 특히 적합하다.
벡터 검색을 위한 Cluster with Auctions
Cluster with Auctions for Vector Search
대규모 근사 최근접 이웃(approximate nearest neighbor) 검색은 인덱싱을 위해 파티셔닝에 일반적으로 의존한다. 데이터베이스 벡터가 클러스터로 파티셔닝되고, 각 쿼리에 대해 프로빙(probing) 함수가 스캔할 클러스터를 선택한다. 쿼리 프로빙 함수와 데이터베이스 파티션은 별개의 개체로 취급되는 경우가 드물며, 대부분의 기법은 데이터베이스 벡터와 동일한 할당 함수를 사용해 쿼리를 배정한다. 이는 특히 데이터베이스와 쿼리 분포가 다를 때 최적이 아니다. 본 논문은 균형 잡힌 데이터베이스 파티션과 신경망 기반 프로빙 함수를 공동으로 학습함으로써 이 한계를 해결하는 CwA(Cluster with Auctions)를 제안한다. CwA는 쿼리 분포에 대해 검색 성능을 직접 최적화하며, 목적 함수를 최소화하기 위해 (i) 프로빙 함수의 신경망에 대한 경사하강법과 (ii) 데이터베이스 벡터에 대한 클러스터 할당의 대규모 조합 최적화, 두 단계를 번갈아 수행한다. 후자는 파티션을 설계상 균형화하는 병렬화 가능한 경매(auction) 알고리즘으로 해결한다. CwA의 확장성을 더 높이기 위해, 파티션의 세분성을 높이는 클러스터의 데카르트 곱(Cartesian product)으로 방법을 확장한다. 데이터베이스와 쿼리 분포가 다른 경우, CwA는 동일한 재현율에서 최신(state-of-the-art) 방법 대비 최대 4.7$\times$의 처리량(throughput)을 달성한다. 분포 내(in-distribution, ID) 설정에서도 CwA로 학습한 단순한 선형 프로빙 함수조차 경쟁하는 딥 신경망 기법들보다 우수한 성능을 보인다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.