Simple recursive algorithms, 함수를 호출하면 그 내부에 다시 자기 자신을 호출하는 방식으로 정의된 함수
풀이의 Key point
-"정답을 찾은 경우", "다음을 호출해야하는 경우", "그만두어야하는 경우" 3가지 설정을 잘 해야함
-subproblem의 solution을 적절히 조합해서 본래문제의 solution으로 만들어야함
Backtracking algorithms, depth-first recurisve search, 주로 constraints satisfaction problem에서 사용, 각 지점마다 constraints을 만족하는 경우만을 헤아리면서 전체 solution을 찾아나선다. 진행 도중 진척이 없으면 직전 지점을 돌아와 남은 가능성을 시도한다. 따라서 depth-first search방식이다.
Divide and conquer algorithms, 본래 문제를 작은 문제로 나눠서(분할) 해결(정복)하고 조합하여 본래 문제의 해를 찾는 방식, 즉 (분할,정복,조합)을 따른다. 따라서 Top-down방식으로 구성. Subproblems가 reuse가 되지 않을 때를 Divide and conquer라 하고, reuse한다면 Dynamic programming algorithm이 된다.(Optimal substructure를 따른다면)
풀이의 Key point
-
Dynamic programming, Overlapping Subproblem(solutions to subproblems can be stored and reused in a bottom-up fashion), Optimal Substructure(Optimal solution contains optimal solutions to subproblems)의 성질을 요구한다. 즉 Dynamic programming은 remember past results and uses them to find new results. 특히 optimization problems에 사용한다. remember and reuse를 기법을 memoization이라 한다.
풀이의 Key point
-문제의 환경(시간/메모리)제한에 따라 Top-down/Bottom-up을 골라야 한다.
-각 과정상 subproblem의 솔루션을 알필요가 없다면 table을 만들지 않아도 괜찮
-
Greedy algorithm, 매 순간 최적의 해를 찾아 최종적인 최적해에 도달하는 기법으로 2가지를 만족해야 한다. Greedy choice property(매 순간 최적의 해를 구할 때, 이전에 어떤 choice를 했는지는 고려해도 되지 않는 상황 혹은 비슷하게현재 최선의 선택을 할 때 미래에 무슨 선택을 할지 고려하지 않아도 되는 상황)와 optimal substructure의 성질을 띌 때 Greedy algorithm으로 해결한다. Greedy algorithm은 optimization problem에서 global optimum을 주지않을 수도 있지만, 계산 편리상 global optimum에 근사하는(혹은 global optimum이 될 수도 있어서)방식으로 자주 쓰인다.
풀이의 Key point
-
Branch and bound algorithms, optimization problem(예를 들어 feasible region R에서 f(x)의 최솟값을 찾는 문제)에서 R을 A/B로 나누어(branch), 각 subregion에서의 upperbound/lowerbound(bound)를 계산한다. 이 때 A의 lowerbound가 B의 upperbound보다 크다면 A를 폐기처분한다(pruning). Bound로 인해 pruning이 얼마나 효율적으로 되냐가 관건.
Brute force algorithms, 모든 경우의 수를 다 해보는 것
풀이의 Key point:
-모든 가능한 경우의 수를 헤아릴 것
-각 경우마다 해결법을 정의할 것
-위의 2개가 시간/메모리 내에 해결되는 지를 문제 풀이 방향을 잡을 때 계산해야함
Randomized algorithms, 문제를 품에 있어서 random number를 사용하는 알고리즘, 마치 quick sort에서 pivot으로 사용할 random number를 선택하는 과정.
-----------------------------------------------
알고리즘 문제의 유형에 대해 알아보자.
Decision problem:Search for a feasible solution.(Yes/No)
Optimization problem:Search for the best solution.
Enumeration problem:Find all feasible solutions.
Decision problem에서
P problem:the set of decision problems solvable in polynomial time by a DTM(Deterministic Turing Machine)
NP problem:the set of decision problems solvable in polynomial time by a NTM(Nondeterministic Turing Machine)
(NP는 Nondeterministic, Polynomial의 N과P)
NP-hard problem:the set of problems that every NP problem is reducible to in polynomial time.
NP-complete problem:the set of NP and NP-hard problem.(즉 NP인데 not NP-hard가 존재)
co-NP problem:the set of problems whose complement is NP.
P인 문제
NP and not P인 문제
not NP and not P인 문제
NP-hard and not NP인 문제
NP-complete인 문제
NP and co-NP인 문제
not NP and not co-NP인 문제
비고:
-DTM과 NTM의 주된 차이는 transition이 전자는 function 후자는 relation, 즉 가능한 action이 not unique
-reduce한 다는 것이 마치 4점짜리 문제를 2점짜리로 reduce한다는 어감이지만 사실은 반대의 의미임
-NP가 not P인 문제로 오해해서는 안된다.
-----------------------------------------------
Graph, 문제의 상황을 점과 간선으로 표현하여 해결
풀이의 Key point
-node, edge, weight를 문제 상황에 mapping을 잘해야 함
-unweighted인 경우 dict_[node_i] = [node_i1, node_i2, ...] 형태로 문제 상황을 표현
-weighted인 경우 dict_[node_i] = [[node_i1, weight_i1], [node_i2, weight_i2],...] 형태로 문제 상황을 표현
-node x node size의 matrix(list of list)로 나타낼 수 있지만, space complexity가 O(V**2)로 메모리가 많이 필요
-격자형태의 경우 node별 연결된 node를 다 구해두지 않고, dx,dy를 통해 on-the-fly 방식으로 사용할 수도 있다.
DFS(Depth First Search), node에서 depth가 증가하는 방향으로의 search하는 방식
풀이의 Key point
-Graph정의
-node별 search했는지 확인용 배열
-dfs 재귀함수
BFS(Breadth First Search), node에서 1-depth로 가능한 nodes를 먼저 search하는 방식, 따라서 최단비용/시간 문제해결에 사용된다.
풀이의 Key point
-Graph정의
-node별 search했는지 확인용 배열
-queue
-while문
-문제 조건에 따라
-각 node마다 다른 정보를 담는다면 그 정보를 포함하여 Graph정의, queue에 node와 정보를 함께 담기 등
# 하지만 /과 *는 함수 정의할 때 optional이다. 하지만 적어준다면 call할 때 각 argument를 어떻게 받아야만 하는지 바로 이해할 수 있다.
def func(a,/):
# 즉 func은 반드시 positional argument로 call해야한다.
# func(a=3)는 "got come positional-only arguments passed as keyword arguments:'a'" ERROR
# def func(a)였다면 func(a=3), func(3) 모두 작동함
def func(*,a):
# func(3), "func takes 0 positional arguments but 1 was given" ERROR
# func(a=3)은 동작함
def func(a,/,b,*,c):
# func(1,2,c=3), func(1,b=2,c=3) 모두 동작함
# 즉 b는 positional/keyword 어떤 형태로든 받을 수 있음
def func(a,/,b=3,*,c):
# func(1,3,c=3), func(1,b=3,3), func(1,c=3) 모두 같은 동작함
# Positional-only인 a외에는 모두 default value 설정 가능
def func(a,b,*args, c):
# 입력을 여러개 받으면 args가 variadic variable인데 어디까지가 args이고 c인지를 알 수가 없는 형태
# 정의는 되지만 call하면 ERROR발생
def func(a,b,*args, c=4):
# 여러개 positional arguments를 받으면 a,b외 나머지는 args로, c는 4
# c를 4가 아닌 다른 값으로 사용하려면 반드시 keyword argument형태로 입력해줘야한다.
def func(a, **kwargs):
# **kwargs를 추가해줌으로써 함수를 정의할 때 여러개의 argument를 받을 수 있게 정의 가능
# func(**{'a':1, 'b':2})를 call하면 func내부에서 a=1이고 kwargs={'b':2}가 된다. 즉 kwargs(dictionary)를 unpack하여 함수 정의에 쓰였던 argument에 value를 assign하고, 함수 정의에 없던 argument는 kwargs가 갖고 있는다.
-함수를 call할 때 무조건 positional로 입력을 받아야할 때, /을 사용하여 강제를 하자.
(예를 들면 function을 call하는 입장에서 parameter name을 몰라야할 때)
-함수를 call할 때 keyword argument형태로 입력해야 사용자가 편리할 때 *을 사용하여 keyword argument를 강제하자.
(예를 들면 parameter의 순서보다는 parameter name이 의미가 있어서 입력을 할 때 함수를 좀 더 이해할 수 있을 때)
-함수를 정의할 당시에 가변적인 argument를 받아야하는데 parameter name이 유의미하지 않다면 *args를 사용
-함수를 정의할 당시에 가변적인 argument를 바다야하는데 parameter name이 유의미하다면 **kwargs를 사용, 이 때 kwargs로 받을 때 다른 argument name과 충돌하는 key-value를 받으면 multiple value assign ERROR발생
-함수를 정의를 어케하든 call할 때 **kwargs를 사용하여 argument에 value assign가능
추천 시스템 모델을 개발하고 나면, offline metric을 통해 먼저 성능을 가늠해본다.
여기서는 각 offline metric의 정의와 장점, 단점, 단점보완법 등을 알아보자.
상황:
tester는 주어진 기간에 구매한 상품set이 존재하고 B = set(bitem_1, bitem_2, ..., bitem_N])
recommendation engine은 각 tester마다 추천 상품 list가 존재 R = [ritem_1, r_item2, ..., ritem_K]
Hit rate
-유저마다 Top-k recommendation에서 hit한게 존재하면 hit += 1
-#hit/#user
-고객의 내역 중 time-axis가 존재한다면
-train/test를 특정 time으로 나눠 계산 가능
-혹은 고객별 first J data를 활용하여 train후 J+1부터를 test로 삼아 계산 가능
-time-axis가 존재하지 않는다면 leave one out cross validation 사용
장점:
-해석이 아주 간편함
-time-axis가 존재하지 않을 때, 계산량은 많으며 굉장히 낮은 값을 가짐
단점:
-rank-unaware방식
ARHR
-Average Reciprocal Hit Rate
-sum(1/rank)/#user
장점:
-rank를 고려하지만...
단점:
-first의 rank만 고려함
P@K
-Precision at K
-R의 first K개 중 relevant items의 개수 비율
-Decision-support measure
ex)
B = set([티셔츠, 반바지])
R = [음료수, 거울, 티셔츠, 반바지]
P@1 = 0/1 # [음료수](1) 중에 set([티셔츠, 반바지])가 존재하는 개수(0)
P@2 = 0/2 # [음료수, 거울](2) 중에 set([티셔츠, 반바지])가 존재하는 개수(0)
P@3 = 1/3 # [음료수, 거울, 티셔츠](3) 중에 set([티셔츠, 반바지])가 존재하는 개수(1)
AP@K
-Average Precision at K
-P@1, P@2, ..., P@K의 평균
-Decision-support measure
장점:
-ranking에 sensitive하다, R 내에서 순서를 바꾸면 score값이 바뀜
-stable, R 내에서 순서를 "조금"만 바꾸면 AP@K값도 "조금"만 바뀜
-ranking이 높은 item이 큰 weight를 갖는다.
-recall-oriented factor가 존재, 즉 tester의 모든 relevant items를 고려해서 AP@K값이 나온다.
단점:
-해석이 어렵다, 이 숫자가 0.03이라고해서 즉각적인 해석이 되지 않는다. 게다가 기본적으로 작은 값들을 가질 때가 많은데, 프로젝트 보고서를 작성할 때 높으신 분에게 이 숫자를 보여주면 기겁할 수 있으니 PM들이 다른 수치가 없냐고 묻는다. 그럴 때엔 다른 수치를 대체하여 사용하거나, 비슷한 도메인에서의 paper에서의 metric을 들고와서 부연설명을 하는게 필요하다.
(즉 MAP는 관련이 있다vs없다 지만, DCG형태는 관련이 x(float)만큼 있다. 형태의 관점)
-
단점
-Bad recommendation에 대해서 penalty 부과를 하지 않는다. 대안책으로 bad에 대해 negative score(원래는 zero score를 부과하지만)를 부과하면 해결이 된다. 이 때 전반적으로 score가 낮아지는 경향을 띄며, precision이 recall보다 중요할 때 사용
-다 맞힌 NDCG@3과 다 맞힌 NDCG@5를 생각하면, 후자가 더 높은 점수여야하는데 보정이 안된다. 이 때, 전자는 missing 2 target으로 생각하고 minimum relevance를 설정하여 부과하여 전자도 NDCG@5로 계산하면 보정이 된다.
(즉 더 높은 k에 대해서 더 잘맞춘 경우 점수가 더 높게 설정이 필요)
MAE
-Mean Absolute Error
-tester마다 B의 rating과 R의 predicted rating간의 차이의 합(의 평균, 이 때 평균낼 때는 B 중에서도 tester가 rating한 상품들의 개수가 분모로 간다.)
-Error metrics
특징:
-모든 user를 만족할 필요 없을 때 사용, 즉 몇몇 유저에게는 bad recommendation이 등장할 수 있음
-여러 tester에 대해 MAE를 구할 때, 각 유저마다 상품마다 차이를 구하고, 개별tester기준으로 평균을 하는 이유는, 한 user에게 비교적 predict이 우수했음에도 불구하고 error계산하는 상품이 많았다면, 단순히 error값이 커지기 때문, 즉 all users contribute equally하기 위함
-전체 tester들의 B 중에서 rating한 items가 많은 경우, 그 중 popular item과 not popular item이 존재하는 경우 popular/not popular 으로 divide해서 측정하기도 한다. 이는 popular item이 not popular보다 prediction power가 높기 때문에, 비교적 not popular item이 얼마나 예측력을 가지는 것을 따로 보기 위함(long-tail item에 대한 평가)
-Error metrics이기 때문에, 모든 items를 동일한 weight를 갖고 error 측정, 즉 ranking이 중요하지 않은 형태, 즉 not rank-aware metric으로 Top-k recommendation 관점에서는 부적절
-Recommendation system을 평가할 때는 각 tester마다의 MAE를 구하고 전체 tester에 대해 평균
MSE, RMSE
-Mean Squared Error, Root Mean Squared Error
-Error metrics
특징:
-큰 error는 더 큰 error로 해석하기에, bad recommendation이 등장하지 않아야하는 조심스러울 때 유용
-여러 tester에 대해 MSE/RMSE를 구할 때, 각 유저마다 상품마다 차이를 구하고, 개별tester기준으로 평균을 하는 이유는, 한 user에게 비교적 predict이 우수했음에도 불구하고 error계산하는 상품이 많았다면, 단순히 error값이 커지기 때문, 즉 all users contribute equally하기 위함
-전체 tester들의 B 중에서 rating한 items가 많은 경우, 그 중 popular item과 not popular item이 존재하는 경우 popular/not popular 으로 divide해서 측정하기도 한다. 이는 popular item이 not popular보다 prediction power가 높기 때문에, 비교적 not popular item이 얼마나 예측력을 가지는 것을 따로 보기 위함(long-tail item에 대한 평가)
-Error metrics이기 때문에, 모든 items를 동일한 weight를 갖고 error 측정, 즉 ranking이 중요하지 않은 형태, 즉 not rank-aware metric으로 Top-k recommendation 관점에서는 부적절
-MSE는 단위가 rating의 제곱, RMSE는 rating과 같음
-Recommendation system을 평가할 때는 각 tester마다의 MAE를 구하고 전체 tester에 대해 평균
# ES에 존재하는 모든 index가져오기 curl -X GET 'localhost:9200/_cat/indices?v'
# ES에 새로운 index만들기 curl -X PUT 'localhost:9200/newindex?pretty' # ?pretty는 response를 예쁘게 보여주기 위한 옵션
# ES에 새로운 document만들기
curl -X PUT 'localhost:9200/newindex/info/1?pretty' -H 'Content-Type: application/json' -d '{"name":"SAMPLE"}'
*-index는 newindex, type은 info, id가 1인 document를 추가하는 예제
*-d는 --data-binary의 축약어로, 추가할 데이터를 받음
*-d에 들어갈 데이터는 반드시 double quote를 사용해야함 ""
*newindex라는 이름의 index가 없었으면 새로 만듦
*info라는 이름의 type이 없었으면 새로 만듦
*-id를 생략하면 임의의 문자열로 들어감, 즉 newindex/info/?pretty......형태로 쓰다면
*_source에 입력한 data가 박히게됨
# ES에 새로운 document만들기 from data.json file
curl -X PUT 'localhost:9200/newindex/info/1?pretty' -H 'Content-Type: application/json' -d @data.json
# ES에 한 index 내에 있는 모든 documents 조회
curl -X GET 'localhost:9200/newindex/_search?pretty'
# ES에 모든 index에 있는 모든 documents조회
curl -X GET 'localhost:9200/_all/_search?pretty'
# ES에 (index, type, id)를 이용하여 document조회
curl -X GET 'localhost:9200/index/type/id?pretty'
# ES에 (index, type, id)를 이용하여 document조회하는데, 특정 key만 조회
curl -X GET 'localhost:9200/index/type/id?pretty&filter_path=_source' # _source만 조회
curl -X GET 'localhost:9200/index/type/id?pretty&filter_path=_source.name # _source내 name만 조회
# ES에 (index, type, id)에 해당하는 document update
curl -X PUT 'localhost:9200/index/type/id?pretty' -H 'Content-Type: application/json" -d '{"name":"UPDATED_SAMPLE"}'
*-_source내 name의 값이 바뀌어 짐
*-_version이 +1됨
(_seq_no는 해당 index에서 operation이 발생한 횟수를 가리킴)
(_version은 해당 document를 update한 횟수를 가리킴)
(_primary_term, _seq_no, _version 3개를 통해 document를 uniquely identify가능)
# ES에 CRUD를 하는 파이썬 코드
mygit...
# Elasticsearch 시스템 구조에 대한 요약
-용어정리
-색인(indexing):데이터가 검색될 수 있는 구조로 변경하기 위해 원본 문서를 검색어 토큰들로 변환하여 저장하는 일련의 과정
-인덱스(Index, indices):색인 과정을 거친 결과물, 또는 색인된 데이터가 저장되는 저장소
-검색(search):인덱스에 들어있는 검색어 토큰들을 포함하고 있는 문서를 찾는 과정
-질의(query):사용자가 원하는 문서를 찾거나 집계 결과를 출력하기 위해 검색 시 입력하는 검색어 또는 검색 조건
-Elasticsearch는 대용량 데이터의 증가에 따른 scale out과 데이터 무결성을 유지하기 위한 클러스터링을 지원
-클러스터-노드(마스터, 마스터후보, 데이터)
-노드란 Elasticsearch에 저장소 단위
-하나의 index는 여러개의 노드에 분리되어 저장됨, 이 분리된 단위를 샤드(shard)라 함
-마스터 노드는 index의 metadata, 클러스터 상태, 샤드의 위치 등의 정보를 저장하는 역할, 클러스터마다 1개 존재
-마스터 후보 노드(master eligible node)는 현재 마스터 노드가 죽으면 마스터 노드 역할을 대행, 마스터 후보는 항시 마스터 노드와 정보를 공유하고 있기 때문에 가능
-데이터 노드가 샤드들을 저장
-먼저 생성된 샤드를 primary shard라 함, 복제본을 replica라 함(index를 생성할 때 별도 설정 하지 않으면 ES version 7.0이상부터는 샤드1개로 구성, 그 미만 버전은 5개의 shard로 구성)
-먼저 생성된 샤드라는 것이 index가 1개가 5개의 shard로 분리되고 각각 replica샤드가 생겨 총 10개 샤드면, 앞선 5개의 샤드들을 primary shards라 한다.
-만약 index가 5개의 shard로 구성되어 있다면, 각 샤드마다 복제본도 반드시 생기고, 여러 node에 골고루 분배되며 각 노드마다 다른 샤드(즉 1번 샤드와 1번 복제본이 한 노드에 있는 것을 막으며)가 들어가게 저장->이는 데이터 무결성을 위한 과정, 만약 하나의 노드가 유실이 된다면 그 노드에 존재하던 원본 샤드의 복제본은 다른 노드에서 원본 샤드로 승격되고 복제본을 새로이 만들어서 다른 노드에 분배, 만약 유실된 노드안에 복제본의 샤드가 있으면 다른 노드에 있던 원본 샤드를 통해 복제본을 만들어 분배)
-document에서 _primary_term은 해당 document를 포함하는 index가 저장된 여러 primary shard중 몇번째 shard에 document가 저장되어있는지를 가리킴