728x90 반응형 스터디/데이터사이언스89 [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. 20 Ways of Encoding Categorical Features Library for Categorical Features Encoding [3]의 파이썬 패키지에 다양한 categorical encoding이 구현되어있다.import category_encoders as ceencoder = ce.BackwardDifferenceEncoder(cols=[...])encoder = ce.BaseNEncoder(cols=[...])encoder = ce.BinaryEncoder(cols=[...])encoder = ce.CatBoostEncoder(cols=[...])encoder = ce.CountEncoder(cols=[...])encoder = ce.GLMMEncoder(cols=[...])encoder = ce.GrayEncoder(cols=[...])encod.. 2024. 1. 30. Non-negative Matrix Factorization (NMF), 비음수 행렬 분해 Non-negative Matrix Factorization (NMF) and its ApplicationsBasic Concepts행렬 $V \in \mathbb{R}^{n \times m}$를 두 행렬 $W \in \mathbb{R}^{n \times r}$, $H \in \mathbb{R}^{r \times m}$의 곱으로 분해하는 방법이다. 이름에서 알 수 있듯이 $V$, $W$, $H$의 모든 원소들은 음수가 아니다.\[ V \approx HW \] Objective FunctionObjective는 다음과 같다.\[ \underset{W, H \ge 0}{\min} \| V - WH \|_F^2 \]$\| \cdot \|_F$는 Frobenius norm이다. 예를 들어 $\| A - B \|.. 2024. 1. 2. [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 5 ··· 15 다음 728x90 반응형
