Daily Arxiv

전 세계에서 발간되는 인공지능 관련 논문을 정리하는 페이지 입니다.
본 페이지는 Google Gemini를 활용해 요약 정리하며, 비영리로 운영 됩니다.
논문에 대한 저작권은 저자 및 해당 기관에 있으며, 공유 시 출처만 명기하면 됩니다.

Shapley Revisited: Tractable Responsibility Measures for Query Answers

Created by
  • Haebom

저자

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

개요

본 논문은 데이터베이스 팩트들의 질의 응답 기여도를 정량화하는 책임 측정값으로 협력 게임 이론에서 유래한 섀플리 값을 사용하는 기존 연구의 한계를 지적한다. 기존의 섀플리 값 기반 접근 방식은 비수치 질의에 대해 데이터 복잡도 측면에서 #P-hard 문제를 야기한다는 단점을 가지고 있다. 따라서 본 논문은 합리적인 책임 측정값을 재검토하고, 직관적인 특성을 만족하는 새로운 책임 측정값 계열인 가중 최소 지원 합(WSMS)을 제시한다. WSMS의 정의는 간단하며 섀플리 값 공식과 명백한 유사성이 없지만, 모든 WSMS 측정값은 적절히 정의된 협력 게임의 섀플리 값으로 볼 수 있다는 것을 증명한다. 또한, WSMS 측정값은 모든 합집합 연언 질의를 포함한 광범위한 질의에 대해 다루기 쉬운 데이터 복잡도를 가진다. 마지막으로, WSMS 계산의 결합 복잡도를 더 탐구하고 다양한 연언 질의 하위 클래스에 대한 (비)다루기 쉬움 결과를 확립한다.

시사점, 한계점

시사점:
기존 섀플리 값 기반 책임 측정의 #P-hard 문제점을 해결하기 위한 새로운 접근 방식인 WSMS 제시.
WSMS는 직관적이고 다루기 쉬운 데이터 복잡도를 가짐.
WSMS가 섀플리 값으로 표현될 수 있음을 증명하여 이론적 기반을 마련.
다양한 질의 클래스에 대한 WSMS 계산의 복잡도 분석 제공.
한계점:
WSMS의 계산 복잡도가 모든 질의 클래스에서 다루기 쉽지는 않음 (특정 연언 질의 하위 클래스에서의 (비)다루기 쉬움 결과 제시).
WSMS가 섀플리 값과의 관계를 밝혔으나, 섀플리 값의 모든 특성을 만족하는 것은 아닐 수 있음. (명시적 언급은 없지만, 새로운 측정 방법이므로 기존 방법과의 차이점에 대한 추가적인 논의가 필요할 수 있음.)
👍