코딩스뮤:)

[NLP] 단어 표현 방법(Word Representation)

자연어처리에서 사용하는 단어의 표현 방법 국소 표현(Local Representation) 국소표현이란? 해당 단어 그 자체만 보고, 특정값을 매핑하여 단어를 표현하는 방법 국소표현의 종류 One-hot vector N-gram Count Based Bag-of-Word, BoW(DTM) : 단어의 빈도수를 카운트하여 단어를 수치화하는 표현 -> Bow란? 분산 표현(Continuous Representation) 분산 표현이란? 분산 표현 방법은 그 단어를 표현하고자 주변을 참고하여 단어를 표현하는 방법 분산 표현의 종류 Prediction Based Word2Vec(FastText) : 예측을 기반으로 단어의 뉘앙스를 표현 -> Word2Vec란? Doc2Vec: Word2Vec에서 확장된 개념 Co..

[NLP] 단어 표현 방법 : Bag-of-Word Model(Bow)

Bag-of-Word(BoW) Model 기계학습 알고리즘(MLA)을 자연어 처리 테스크에 사용할 때, 입력값인 텍스트는 그 자체로는 사용할 수 없다. 이산적인(discrete)한 텍스트 즉, 문자열을 연속적인(continuous) 모델이 연산할 수 있도록 숫자로 바꾸어주는 과정이 필요하다. 만약 문서 분류 작업(document classification task)을 수행한다고 했을 때, 각 문서는 예측 알고리즘의 input 값에 해당하며 분류 즉, 클래스 레이블이 output값이다. 알고리즘은 input값을 숫자로 이루어진 벡터들로 받으며, 따라서 문서를 고정된 크기의 벡터로 변환하는 작업이 필요하다 기계학습을 위해 텍스트로 이루어진 문서들을 백터화하는 간단하고 효과적인 방법은 Bag-of-Words ..

[ML] 사이킷런 클래스 SGDClassifier : 선형분류

SGDClassifier란? SGD(Stochastic Gradient Descent)를 이용한 정규화된 선형 분류 모델 계산값을 기반으로 계산값이 0보다 작으면 -1, 0보다 크면 1로 분류한다 이진 선형 분류기는 선, 평면, 초평면을 이용해 2개의 클래스를 구분하는 분류기이다 SGD(Stochastic Gradient Descent)란? NN(Neural Network)의 가중치(Weight)를 조정하는 과정에서 보통 경사하강법(Gradient Descent)을 사용한다. 이는 네트워크의 파라미터를 p라고 했을 때, 네트워크에서 내놓는 결과값과 실제 값 사이의 차이를 정의하는 손실 함수(loss function, 혹은 비용함수(cost fuction))의 값을 최소화하기 위해 기울기를 이용하는 것이다..

최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA)란? LCA란 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v거나 v의 조상인 노드들 중 가장 깊은 노드이다 예를들어, 아래의 트리에서 노드 4와 3의 LCA는 1번 노드이다 다른 예로는 노드 9, 14의 LCA는 2번 노드이며, 노드 3, 13의 LCA는 3번 노드이다 여기서 한가지 사실을 알 수 있는데 노드 u,v와 이들의 LCA w의 관계이다 u,v의 최단 경로는 u-w-v 형태라는 것이다 이를 아래의 트리에서 빨간 경로로 확인할 수 있다 따라서, 트리 문제에서 최단경로를 빠르게 찾길 원한다면 가장먼저 LCA를 생각해봐야 한다 LCA 구현 방법 1. 노드 u,v 가 서로 만날때까지 부모노드를 따라서 두 노드를 옮겨 보는 방법 : 선형 탐색 두..

단절점(Articulation Point), 단절선(Articulation Bridge)

단절점(Articulation Point)이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나눌 수 있는 정점을 단절점이라고 한다 아래의 그래프에서 하이라이트된 정점들이 A-point이다 단절점 구하는 방법 단절점을 구하기 위해서는 먼저 단절점의 특성에 대해 알아야 한다. 어느 한 정점이 단절점이라면, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않아야 한다 예를 들어 5번 정점이 단절점이라고 생각해보자. 5번 정점을 제거하더라도 인접노드인 4, 6을 우회로(4-8-6)로 연결되어 있으므로 5번은 단절점이 될 수 없다 이번에는 4번 정점이 단절점이라고 생각해보자 4번 정점을 제거하게 되면 (2,3) 과 (5,8)은..

세그먼트 트리 Segment Tree

세그먼트 트리란? 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 빠르고 간단하게 구할 수 있는 자료구조 세그먼트 트리에서 노드들의 의미 리프 노드 : 배열의 구 수 자체 리프 노드를 제외한 다른 노드 : 왼쪽 자식과 오른쪽 자식의 최솟값 또는 합을 저장 n = 10인 경우 세그먼트 트리는 다음과 같다 트리 만들기 세그먼트 트리는 포화 이진 트리에 가깝기 때문에 배열에 모든 값이 대부분 가득 차게 됨 따라서 배열로 트리를 만들어 사용 이 경우 임의의 노드의 인덱스가 i일 때 왼쪽 자식의 인덱스는 2*i 오른쪽 자식의 인덱스는 2*i + 1 세그먼트 트리의 구현(C++) #include #include #include using namespace std; // arr : intial a..

강한연결요소 : Strongly Connected Component

강한연결요소 : Strongly Connected Component Concept 방향 그래프 G의 임의의 노드 쌍 u,v에 대해 u->v, v->u로 가는 경로가 존재하면 G는 Strongly Connected 되었다고 한다 따라서 G의 u->v 로 가는 경로가 있을 때, 엣지의 방향을 정반대로 바꾼 transpose G에도 u->v로 가는 경로가 있다면 두 노드 사이에 사이클이 있어 SCC를 만족한다 Kosaraju's Algorithm #include #include #include #include #define MAX 10001 using namespace std; int n, out_len; bool check[MAX], check2[MAX]; vector r[MAX], r2[MAX]; stac..

위상 정렬 Topological Sort

위상 정렬(Topological Sort)이란? 정렬 기준이 '위상'으로 여기서 위상이란 진입차수(incoming edge의 수)를 의미한다 위상 정렬의 특징 - Directed Acyclic Graph(DAG)에서만 가능 - 즉, 방향을 가지며 싸이클은 형성하지 않는 그래프를 말한다 - 보통 일의 순서를 정하는 알고리즘에서 많이 사용됨 위상 정렬 알고리즘 각 노드의 위상(incoming edge의 수)를 저장 위상이 0인 노드를 큐에 푸쉬 큐가 빌 때까지 아래 과정 반복 큐에서 노드를 꺼내 해당 노드와 연결된 노드의 간선을 모두 제거(동시에 연결된 노드의 위상을 하나씩 낮춰줌) 큐에서 꺼낸 노드를 위상정렬에 넣어줌 위상이 0인 노드를 큐에 푸쉬