arXiv:1605.00596

Graph Clustering Bandits for Recommendation

Shuai Li, Claudio Gentile, Alexandros Karatzoglou

제출 2016-05-02

원문 초록

We investigate an efficient context-dependent clustering technique for recommender systems based on exploration-exploitation strategies through multi-armed bandits over multiple users. Our algorithm dynamically groups users based on their observed behavioral similarity during a sequence of logged activities. In doing so, the algorithm reacts to the currently served user by shaping clusters around him/her but, at the same time, it explores the generation of clusters over users which are not currently engaged. We motivate the effectiveness of this clustering policy, and provide an extensive empirical analysis on real-world datasets, showing scalability and improved prediction performance over state-of-the-art methods for sequential clustering of users in multi-armed bandit scenarios.

함께 살펴볼 논문

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

arXiv:2610.01533v1cs.AI공통 태그 Clustering, Recommendation Systems

흑백의 이분법을 넘어: 그래프 기반 시맨틱 ID(GrIS)를 통한 시맨틱 및 협업 신호의 균형

Neither Black nor White: Balancing Semantic and Collaborative Signals with Graph-Informed Semantic IDs (GrIS)

생성형 추천을 위한 시맨틱 ID(Semantic ID, SID)에 관한 기존 연구들은 SID 구축을 표현 학습(representation learning) 문제로 취급하여, 아이템을 양자화된 잠재 공간으로 인코딩하고 코드를 읽어내는 방식을 취합니다. 본 논문에서는 이러한 관점이 본질적이지 않다고 주장합니다. SID 구축은 본질적으로 재귀적 클러스터링(recursive clustering) 문제이며, 이렇게 정의하면 클러스터링할 자연스러운 대상은 노드가 시맨틱 콘텐츠를 담고 에지가 협업 신호(collaborative signal)를 전달하는 그래프가 됩니다. 즉, SID 할당은 계층적 그래프 분할(hierarchical graph partition)이 됩니다. 이러한 재구성을 통해 기존 접근 방식을 대체하기보다는 포괄하는 통합 프레임워크인 그래프 기반 시맨틱 ID(Graph-Informed Semantic IDs, GrIS)를 도출합니다. RQ-VAE 및 RQ-KMeans는 그래프가 비어 있는 특수한 경우로 환원되며, 이는 콘텐츠 전용 양자화가 지금까지 하나로 뭉쳐져 있던 두 축인 그래프 구축과 재귀적 분할 알고리즘으로 이루어진 더 큰 설계 공간의 한 단면에 불과함을 보여줍니다. 본 연구에서는 두 가지 대조적인 구현체를 탐색합니다. 하나는 미분 가능한 그래프 풀링(pooling)을 통해 계층적 할당을 수행하는 RecDMoN이고, 다른 하나는 그래프 인식 아이템 표현과 그래프 재구성 목적 함수를 통해 RQ-VAE를 확장하는 RQ-GAE입니다. 여러 실제 데이터셋에서 GrIS는 협업 필터링(CF) 인식 최신 기술(SOTA) 대비 일관되게 향상된 성능을 보여주며, Hit@10에서 최대 +52%의 성능 향상을 달성합니다. 그래프 구축과 분할이 명시적이고 개별적으로 구성 가능한 컴포넌트이기 때문에, 두 축 중 어느 한쪽의 개선점이라도 결합하여 체계적으로 평가할 수 있습니다.

arXiv:2609.27594v1cs.LG공통 태그 Clustering, Multi-Armed Bandits

클러스터 인식 스케칭을 통한 효율적인 선형 밴딧

Efficient Linear Bandits via Cluster-Aware Sketching

본 논문에서는 유한한 아암 집합(finite arm set)을 갖는 고차원 환경에서 선형 밴딧(linear bandit)의 계산 효율성 문제를 연구합니다. 선형 밴딧에서는 특징(feature) 벡터의 차원 $d$가 증가함에 따라 매 업데이트 라운드마다 $O(d^2)$의 계산 비용이 증가하게 됩니다. SOFUL과 같은 전통적인 스케칭(sketching) 기반 방법들은 고정된 크기의 행렬 스케칭을 통해 계산량을 줄이지만, 데이터의 스펙트럼 꼬리(spectral tail)가 두껍고 스케치 크기가 적절히 선택되지 않을 때 무의미한 선형 후회(linear regret)를 초래할 위험이 있습니다. 후회 수렴(convergence)을 보장하고 계산 비용을 효과적으로 줄이기 위해, 우리는 클러스터링 메커니즘을 도입하고 클러스터 스케치 선형 밴딧(CS-LB) 알고리즘을 제안합니다. 제안하는 방법은 스펙트럼 꼬리 취약점 없이 강건한 서브리니어 후회(sublinear regret)를 보장하도록 각 클러스터 내에서 전체 공분산 정보를 보존하고, 각 클러스터에 센티널(sentinel)을 할당하여 클러스터 전환을 수행하며, 조정 가능한 스케치 크기 $l<d$를 통해 라운드당 업데이트 계산량을 $O(l^2d)$로 줄입니다. 합성 데이터셋에 대한 실험은 제안된 방법이 효율성과 후회 간의 유리한 절충(trade-off)을 일관되게 유지함을 보여줍니다.

arXiv:2607.22935v1cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

정적·시간 가변 노출 하한을 갖는 불일치 반올림 공정 밴딧

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

최소 노출 제약은 추천, 콘텐츠 큐레이션, 규제된 할당에서 각 공급자, arm, 또는 그룹이 집계적으로만이 아니라 기간 내에 보장된 노출을 받아야 할 때 발생한다. 우리는 정확한 노출 하한을 갖는 확률적 밴딧(stochastic bandits)을 연구하고, 핵심 대상은 반올림 문제임을 보인다. 분수 공정 스케줄이 정수 pull로 실현되며, 노출 오차는 정확히 불일치 벡터(discrepancy vector)이다. 주요 기여는 시간 가변 하한을 갖는 블록 단위 모델이다. BDQ-UCB는 모든 블록 하한을 결정적으로 만족하며, horizon $T$가 아닌 비필수 예산 $R$에 의해 지배되는 공정 regret을 갖고, 높은 확률에서 regret $O(\sqrt{KR\log(KT)})$를 달성한다. MOSS 잔차(residual) 변형은 $O(\sqrt{KR})$를 달성하고, 일치하는 하한이 양의 필수 노출(mandatory exposure)에서도 minimax rate $Θ(\sqrt{KR})$를 제공한다. kl-UCB$^{++}$ 잔차 규칙은 instance-dependent 최적성을 추가한다. 이 정식화는 겹치는 그룹 하한에 필수적이다. arm별 반올림은 그룹 크기에 대해 $Ω(s)$만큼 그룹 제약을 위반할 수 있는 반면, Beck--Fiala 영공(null-space) 반올림은 블록 예산 내에서 모든 그룹 하한을 만족하며 위반을 arm degree $t$ 미만으로 유지하고, 동일한 $R$-매개변수 regret과 UCB를 결합한다. 학습된 그룹 계획에 대해, 우리는 disjoint system을 $\widetildeΘ(\sqrt{KT})$에서 닫고, 겹침 하에서 naive index 규칙이 실패하는 이유를 설명하는 이중 원장(dual-ledger) 분해를 제시하며, 초기 cover-slack 조건 하에서 pathwise feasible한 plan-sampling 규칙을 증명하고 조건부 $\widetilde O(\sqrt{KT})$ 보장을 달성하되, 조건 없는 겹침 rate는 열어둔다. 합성 하한, MovieLens-100k 장르 노출, 배포 스트레스 테스트에 대한 실험은 penalty tuning 없이 정확한 feasibility를 보여주며, tuned Lagrangian baseline과 경쟁력 있는 regret을 보인다.

arXiv:2607.22012v1cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

문맥적 밴딧을 위한 교차 도메인 오프-정책 평가 및 학습

Cross-Domain Off-Policy Evaluation and Learning for Contextual Bandits

문맥적 밴딧에서 오프-정책 평가 및 학습(OPE/L)은 과거에 기록된 로그 데이터만으로 새로운 정책을 안전하게 평가하고 학습할 수 있기 때문에 실제 시스템에서 빠르게 주목받고 있다. 그러나 OPE/L의 기존 방법들은 퓨샷(few-shot) 데이터, 결정론적 로깅 정책, 새로운 행동(action)과 같이 도전적이지만 널리 존재하는 많은 시나리오를 다룰 수 없다. 맞춤형 의료, 콘텐츠 추천, 교육, 광고 등 많은 응용 분야에서는 이러한 과제가 있는 상황에서 새로운 정책을 평가하고 학습해야 한다. 기존 방법들은 로그 데이터의 잘 알려진 분산 문제나 제한된 탐험(exploration) 때문에 이러한 상황에서 효과적으로 평가하고 최적화할 수 없다. 이러한 미해결 과제 하에서도 OPE/L을 가능하게 하기 위해, 새로운 정책이 구현될 대상(target) 도메인의 로그 데이터뿐만 아니라 다른 도메인에서 수집된 로그 데이터셋에도 접근할 수 있는 교차 도메인 OPE/L이라는 새로운 문제 설정을 제안한다. 이 새로운 공식화는 대상 병원, 국가, 기기, 사용자 세그먼트뿐만 아니라 다른 병원, 국가, 기기, 세그먼트의 과거 데이터도 활용할 수 있기 때문에 널리 적용 가능하다. 우리는 대상 및 소스(source) 데이터셋을 모두 활용하여 OPE/L을 해결하는 새로운 추정량(estimator)과 정책 그래디언트(policy gradient) 방법을 개발했으며, 실험 평가에서 이전에 해결되지 않았던 상황에서 OPE/L 성능이 실질적으로 향상되었다.

arXiv:2607.20863v1cs.IR공통 태그 Clustering, Recommendation Systems

온라인 추천을 위한 확률적 잔차 학습

Probabilistic Residual Learning for Online Recommendations

현대 추천 시스템은 일반적으로 심층 학습(DL) 모델을 기반으로 하며, 밀집 인코더(dense encoder)가 사용자와 아이템의 표현(representation)을 학습한다. 그 결과 이러한 시스템은 기반 모델의 블랙박스 특성과 계산 복잡성으로 인해 추천 성능을 체계적으로 향상시키기 어려운 경우가 많다. 이 문제를 해결하기 위해, 우리는 Probabilistic Residual Learning(PRL)을 제안한다. 이는 실제값(ground-truth)과 기본 예측(base prediction) 사이의 잔차(residual)를 모델링하여 기존 시스템의 목표 지향적 정제(refinement)를 가능하게 하는 인과적 베이지안 추천 모델이다. 구체적으로 PRL은 (1) 국소적 잔차 모델링을 위해 사용자를 확률적으로 그룹화하고, (2) 사용자 및 아이템 표현에 영향을 미치는 도메인 수준 교란 변수(domain-level confounder)를 모델링하며, (3) do-calculus를 사용하여 교란 변수에 대한 클러스터별 잔차 예측을 집계한다. 실험 결과, 플러그앤플레이(plug-and-play) 방식의 PRL이 다양한 기본 심층 학습 추천 시스템과 호환되며 성능을 향상시키는 동시에 의미 있는 사용자 클러스터를 자동으로 발견함을 보여준다.

토론

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