본문 바로가기
[Algorithm] 백준 BOJ 2606 바이러스 python 파이썬 그래프 실버 3 Private 난이도 : ♥♥♥♡♡ 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import sys n = int(sys.stdin.readline().strip()) m = int(sys.stdin.readline().strip()) graph = dict() for i in range(n): graph[i+1]=[] for i in range(m): a,b=map(int, sys.stdin.readline().strip().split()) graph[a].append(b) graph[b].append(a) ..
[Day41] Movie Rec 5. Recommendations with Side-information Limitation of Collaborative Filtering CF는 기본적으로 user-item interaction matrix가 주어졌을 때, 이로부터 사용자와 아이템 간의 숨겨진 패턴을 찾아내고 이를 추천에 활용한다. 하지만 실제로 이런 가정이 성립하지 않는 추천도 존재한다. cold-start interaction data가 충분하지 않아서 user-item의 latent vector를 잘 학습할 수 없게 되는 cold-start problem이 존재한다. 새로운 사용자에게는 most popular item이 추천되는 현상이 일어난다. 그래서 이를 보완하기 위해서 item의 side-information을 활용하는 content-based 추천을 사용하면 된다. temporal evolut..
[Day41] Movie Rec 4. Collaborative Filtering (2) Deep Learning-based Collaborative Filtering 추천시스템에서 DL 모델의 장점 Nonlinear Transformation을 활용해서 복잡한 user-item interaction을 포착한다. 강력한 representation learning 능력을 가지고 있기 때문에 feature engineering에 많이 노력하지 않아도 된다. 비디오, 사진, 음성 등다양한 heterogeneous(여러 다른 종류들로 이뤄진) 정보를 포함할 수 있다. sequence modeling이 가능하다 다양한 network 구조들을 쉽게 결합할 수 있다. 추천시스템에서 DL 모델의 한계 어떤 weight가 어떤 의미를 갖는지 해석할 수 없다. 많은 양의 데이터가 성능을 위해 필요하다. 하이퍼..
[Day40] Movie Rec 3. Collaborative Filtering (1) Memory-based Collaborative Filtering 사용자나 아이템간의 similarity에 근거하고 있는 방법 이를 활용하여 rating prediction과 top-K ranking에 모두 적용될 수 있다. Similarity Metrics Jaccarrard similarity 집합들간의 포함관계 Cosine similarity 서로 다른 두 벡터 간의 각 거리 Pearson similairity cosine similarity와 유사하지만 평균을 뺀 잔차값을 다룬다 Memory-based CF for Rating Prediction memory기반 CF를 rating prediction에 적용할 때는 휴리스틱 룰을 사용한다. 사용자가 아이템에 부여할 평점은 다른 유사한 사용자가 직접..
[Day40] Movie Rec 2. Research Directions and Resources Interesting Reseasrch Directions SOTA RecSys 연구의 근간이 되는 논문들을 살펴보자 Matrix Factorization 사용자와 아이템의 저차원 표현을 학습한다. 명시적인 아이템이나 사용자의 feature를 사용하지 않고도 잠재적인 표현을 학습하기 때문에 latent factor model이라고 한다. R이라는 상호작용 matrix를 $\gamma_U$와 $\gamma_I$로 분해했을 때 $\gamma_U$의 한 행은 유저의 preference를 의미하고 $\gamma_I$의 한 열은 아이템의 특징을 의미한다. $\gamma_U$와 $\gamma_I$를 같은 공간상에 도식화 했을 때, 각 축이 의미하는 것은 장르, 나이 등 하나의 의미를 갖는 축이 된다. explici..
[Day40] Movie Rec 1. 추천 시스템 개요 및 대회 소개 추천 시스템 소개 사용자가 사용한 아이템에 대해 제안을 제공하는 소프트웨어 도구나 기술 일상생활에서 접하고 있는 다양한 개인화된 서비스의 일종 목적 사용자의 선호를 모델링하고 이를 통해 비즈니스 목표를 달성하는 것 사례 netflix, facebook, alibaba Personalized Education : 지식 수준 모델링을 해서 학습 컨텐츠 제공 Personalized Healthcare : 질병 진단, 의약품 처방 이력을 종합해서 미래의 질병 예측 기존 ML 방법론과의 차이 사용자와 아이템의 로그 데이터를 바탕으로 사용자가 좋아할만한 아이템을 추천한다. 기존 ML 지도학습의 하나인 Logistic Regression으로 수행해보자 $$rating(user,item) = f(user,item)=W..
[Algorithm] 백준 BOJ 2212 센서 python 파이썬 그리디 골드 5 Private 난이도 : ♥♥♥♡♡ 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net import sys n=int(sys.stdin.readline()) k=int(sys.stdin.readline()) sensor = list(map(int, sys.stdin.readline().split(' '))) sensor = sorted(list(sensor)) print('정렬된 sensor', sensor) if n 아쉬운 부분. while len(length) != k +1 : len..
[Day38] Bandit for Recommendation 10-2 : MAB 알고리즘 심화 : Thompson Samling, LinUCB Thompson Sampling 각 action에 대해 reward를 계산할 때 확률 분포를 사용한다. 주어진 k개의 action각각이 베타 분포를 따른다고 가정하고 확률분포를 업데이트한다. 베타 분포 두 개의 양의 변수 $\alpha$와 $\beta$로 표현할 수 있는 확률분포이며 0~1사이의 값을 갖는다. $$Beta(x\mid \alpha, \beta) = \frac{1}{B(\alpha, \beta)}x^{\alpha-1}(1-x)^{\beta-1}$$ B($\alpha, \beta$)는 $\alpha$와 $\beta$에 의해 정해지는 베타함수 $\alpha$와 $\beta$값에 따라 확률분포의 모양과 sampling되는 값이 달라진다. 예시 각각의 아이템 별 추정치를 계산할 때 어떻게 베타분포를..

티스토리툴바