728x90 반응형 cs24635 [CS246] Bandits (4) - Thompson Sampling Thompson Sampling: Probability-Based Bandit Algorithm Thompson sampling은 각 행동이 최적인 확률에 비례하여 세션을 arm에 할당한다.결과분포는 집합 \( \{ 0, 1 \} \) 으로 가정한다.이는 각 행동은 성공($1$) 또는 실패($0$)를 의미한다.그리고 확률 \( \theta \) 로 동전을 던지면 이 동전은(동전의 결과는) 베르누이 분포를 따른다.그리고 \( \theta \)를 추정하기 위해 \( 0 \)과 \( 1 \)의 개수를 세어간다. \( k \)개의 arm이 있고, 각 arm의 파라미터를 \( \theta_i \)라 하자.즉 \( \boldsymbol{\theta} = ( \theta_1, \theta_2, \dots, \thet.. 2024. 10. 26. [CS246] Bandits (3) - UCB1 Algorithm UCB: Upper confidence sampling algorithm Confidence Intervalsconfidence interval(신뢰구간)은 특정 확률로 평균이 있다는 확신할 수 있는 값의 범위이다.단순 확률로 해석하기 어렵다. 필요하면 아래 신뢰구간(confidence interval)과 신용구간(credible interval)을 참고.https://trivia-starage.tistory.com/175 [Bayesian Learning] Frequentism vs BayesianismIntroduction to Bayesian 통계적 방법으로 빈도주의(frequentism)과 베이지안(bayesianism)이 있고 이 둘의 차이를 정리해보았다. 빈도주의 관점 (Frequentism).. 2024. 3. 6. [CS246] Bandits (2) - Epsilon-Greedy Algorithm Epsilon-Greedy AlgorithmAlgorithmFor $t=1:T$ 동안 다음의 단계로 Explore/Exploit를 결정한다.$\epsilon_t = O(\frac{1}{t})$. $\epsilon_t$는 time $t$가 지날때마다 $1/t$로 감소한다$\epsilon_t$의 확률로 Explore: arm은 uniformly at random하게 선택하고, 선택된 arm을 탐색$1-\epsilon_t$의 확률로 Exploit: empirical mean이 가장 높은 arm을 선택한다. Auer et al. 에 따르면, 적절한 $\epsilon_t$를 고르면 다음이 성립한다고 한다.\[ R_T = O(k \log T) \Rightarrow \cfrac{R_T}{T} = O\left( \cf.. 2024. 2. 27. [CS246] Bandits (1) - Problem Settings Multi-Armed Bandit: Learning through Experimentation세상에는 탐색을 통해 특정 전략을 수립할 필요가 있다.구글 광고:광고 수익을 최대화 하고 싶어한다. 과거에는 pay by impression(CPM) 전략을 사용했으나 광고 효과(effectiveness)는 알 수 없었다는 점이 문제였다. 현재는 pay per click(CPC) 전략을 사용하고 있으며 기대수익(expected revenue)를 찾는 것이 핵심이다.query $q$에 대하여 광고 $a$의 기대수익은 다음과 같이 계산된다.\[ E[\text{revenue}_{a, q}] = P(\text{click}_a | q) \cdot \text{amount}_{a,q} \]$q$의 $a$의 입찰(bid)는 $.. 2024. 2. 23. [CS246] Counting Frequent Elements in a stream Exponentially Decaying Window: Finding Frequent Recent Items from StreamMotivation이번 포스팅에서는 2가지 문제에 관심을 갖는다.(1) Finding most common elements(2) Finding most common recent elements Example최근 영화 중에서 가장 많이 예매된 것은?(Amazon과 같은) 전자상거래의 stream data 중에서 최근 판매된 인기 상품은?(Twitter, 이제는 X) SNS에서 최근 가장 활발한 유저는? Sliding Window: What is "recent"?어떤 기준으로 최근(recent) 정보를 반영할 수 있을까?가장 기본적으로 떠오르는 생각은 sliding window이다.. 2023. 12. 28. [CS246] Flajolet-Martin (FM) Algorithm: Counting Distinct Elements from Data Stream Flajolet-Martin (FM) Algorithm: Counting Distinct Elements from Data StreamProblem Definitiondata stream은 크기가 $N$인 집합으로 간주할 수 있다.Applicationswebsite에 방문하는 (unique한) 유저 수는 얼마인가?web crawling으로 얻은 website에 존재하는 word의 수는?지난 주에 판매한 상품 품목(distinct products) 개수는?Real ProblemObvious approach: dictionary 자료구조를 이용한다. (key:element, value: counting)그러나 우리는 (data stream의 크기에 비해) 매우 적은 저장공간만 가진다. (limited wor.. 2023. 12. 22. 이전 1 2 3 4 ··· 6 다음 728x90 반응형
