--> Word2Vec에 대해서 보긴 봤는데 어떻게 단어 간 유사도가 계산되는지에 대해서는 자세히 다루지 않았었다. 나는 그게 너무 궁금했기에 Embedding이라는 주제를 잡고 간단하게 살펴보게 되었다.
- Ex. 남자와 여자를 표현하는 벡터를 만든다고 할 때 각각 [1,0][0,1]로 만드는 방법.
- Ex. 단어 '강아지'는 '귀엽다', '예쁘다', '애교' 등의 단어가 함께 등장.
--> 분포 가설에 따라 해당 내용을 가진 텍스트를 벡터화한다면 저 단어들은 의미적으로 가까운 단어가 됨. --> 단어 간 유사도를 계산할 수 있음.
지효님의 알고리즘 강의
오늘의 주제: 비선형 자료구조
비선형 자료구조에는 그래프, 트리가 있음.
그래프(G)
- 수학적 용어.
- 목적: 연결성을 나타내주는 자료 구조. 상호작용을 나타냄.
- 구성요소: G(그래프) = (V(정점집합/ vertex), E(간선집합/ edge))
그래프에서 알아야 할 용어들
- 정점: 어느 지점.
- 간선: 정점을 이어준 선.
- degree: 어떤 정점으로부터 연결되어있는 개수.
- 경로(path): 어떤 u 에서 v까지 갈 수 있는 것.
- 사이클(cycle): 자기 자신으로 돌아올 수 있는 경로가 있는 것.
- 트리(tree): 사이클이 없는 그래프. 어떤 정점을 가도 자기 자신으로 돌아오는 사이클이 존재하지 않음.
- 부분 그래프(sub gragh): 그래프가 주어졌을 때 부분을 정해주는 것.
- 가중치(weight): 간선에 정보를 표현해 줄 수 있음. 얼마나 중요한지 크기가 어떤지.(Ex. 지도상이라면 정점과 정점 사이의 거리를 표현수 있음.)
- 방향: 간선을 표현할 때 아무것도 표시하지 않을수 있지만 방향성을 표시해줄 수 있음. (-->, <--, <-->)
- 루프: 자기 자신으로 바로 돌아오는 것.
- forest: 트리 구조가 연결된 것. 떨어져 있을 수 있음. 부분 그래프가 여러 개일 수 있음.
그래프의 분류 --> 조건에 따라서 알고리즘이 달라짐.
- 가중치에 대해서 분류하기: 가중치가 있을 수도 있고 없을 수도 있음. 크기의 대소 비교가 없으면 다 같다고 생각할 수 있음.
- 방향에 대해서 분류하기: 방향이 있을 수도 있고 없을 수도 있음. 방향이 있으면 그 방향으로만 갈 수 있음을 알려줌.
- 연결성에 대해서 분류하기: 모든 것이 연결된 경우가 있고 forest처럼 연결이 되지 않은 경우가 있음.
그래프의 구성요소
- 데이터: V집합, E집합
- 구조: 비선형 --> 모든 자료구조를 만들 수 있음.(스택, 큐, 배열...) = 모든 자료 구조의 일반화가 가능.(연결성과 관련이 있음.)
- 연산: V, E에 관한 것.
그래프의 구현
가장 기본적인 구현방법(naive)에는 뭐가 있을까? mapping?, 좌표에 점 찍기?, 연결리스트?, 딕셔너리?
--> V = {v1, v2, v3, ... vn}, E = {(v2, v3)}로 간단히 표현할 수 있음.
--> 하지만 기본적인 구현방법은 비효율적임. 찾을 때 오래 걸림.그래서 그 대안으로 나온 것이 인접행렬 인접 리스트임. --> 인접은 어떤 기준점에 대해서 연결되어있다고 알려주는 것.
인접 행렬은 행렬을 그리고 연결된 지점에 표시하는 것.
인접 리스트는 연결리스트와 같음. 각 정점에 있어서 간선들이 연결된 것을 표현해주는 것.
각각의 구현 살펴보기: 메모리를 얼마나 사용할까? (공간복잡도 계산)
- (조건) |V| = n, |E| = m, degree(V_E) = d
- naive: |V|의 공간복잡도는 n, |E|의 공간복잡도는 m --> O(n+m)
- 행렬: O(n^2)
- 리스트: 양방향일 경우, O(n+m(간선의 개수))/ O(n^2)으로 해도 됨.
- O(m) = O(n^2)
그래프의 연산(찾아가서 추가, 삭제할 부분만 보기 --> 수정한 총 연산을 세면 됨.)
Insert
1. 정점 하나를 추가하는 경우
- naive: O(1) --> 아무데나 붙이면 됨.
- 행렬: O(n^2) --> 늘리는 것보다 행렬이 작을 때는 행렬을 늘릴 수 없으니 새 행렬을 만들어서 값을 복붙해줘야함.
- 리스트: O(1) --> 리스트 끝에 붙이면 됨.
- 간선을 추가하는 경우
- naive: O(1)
- 행렬: O(1)
- 리스트: O(n) or O(d)
Delete
1. 독립된 정점 하나를 삭제하는 경우
- naive: O(1)
- 독립되지 않은 정점을 삭제하는 경우 --> 연결된 간선도 삭제해줘야 함.
- naive: 정렬해놓은 것이 아니니 다 찾아봐야해서 O(n+m)
- 행렬: 배열을 n-1로 다시 잡거나 사용하지 않는다고 표시하거나 0 혹은 -1로 표시함.
--> O(1) ~ O(n^2) --> 구현방식에 따라 달라짐.- 리스트: k번째를 삭제하는 경우, 어딨는지 모르니까 다 찾아봐야 함. --> O(sum d) or O(n+m)
- 간선을 하나만 삭제하는 경우
- naive: 위치가 어딨는지 찾아봐야 하니까 O(m)
- 행렬: 그 부분에 대해서 없다고 해주면 되니까 O(1)
- 리스트: O(d)
Find
아이효 3 2021.03.20
<개발 과정>
데이터 수집 --> 데이터 전처리 --> 모델링 --> 학습/테스트(피드백을 받고 다시 모델링으로) --> 출시
AI는 데이터에 있는 정보들을 학습하는 것. 데이터를 수집할 때 인터넷에 데이터는 여러 형태로 존재.
그 형태는 JSON, XML, CSV와 같은 형태로 존재.
(JSON: 딕셔너리처럼 되어있어서 처리/ 전송이 편리, XML: web, CSV: 엑셀처럼 분석하기 좋게 정리됨)
데이터 전처리는 모델에 데이터를 넣기 전에 하는 모든 작업들.
전처리의 목표는 모델에 들어가는 입력을 만들어주는 것.
..--> 모델이 가장 잘 학습할 수 있도록 (모델에 잘 들어갈) 모델의 입력을 만들어주는 것.
....--> 가중 중요한 모델의 목표는 task의 성능을 높히는 것.
......--> 그러기 위해사는 데이터 정보를 학습해야 함.
........--> 데이터 정보를 학습한다는 것은 데이터 분포(모양)를 학습(모방)하는 것.
(+ 추가: 데이터가 있어야 파라미터 공간도 정의할 수 있음.)
(+ 추가: 분류문제에서 두 그룹을 분류해주는 직선 y=wx+b를 찾는다고 했을 때, b와 w을 찾아주는 공간을 생각해볼 수 있음. 이것이 파라미터 공간. --> 가장 잘 분류하는 w을 찾았을 때 y 축을 acc으로 둔다면 w가 가장 잘 표현된 x축을 중심으로 정규분포가 그려질 것.)
머신러닝/ 딥러닝은 가장 좋은 것 찾기(최적화 문제)이고, 데이터를 가장 잘 설명할 수 있는 파라미터(수식)를 찾는 것이 가장 중요.