복습용 블로그

다익스트라 알고리즘은 그래프의 한 점에서 모든 점까지의 최단 경로를 구하는 알고리즘입니다. (반드시 최단 경로만은 아니고 특정 조건에 해당하면 최소 거리 구하는 것 대신 해당 조건을 넣으면 됩니다.) 다익스트라 알고리즘 동작 과정은 다음과 같습니다. 1. 그래프가 주어지고, 시작점과 직접적인 연결이 없는 노드의 경우, 거리를 infinite 으로 지정한다. (아직 모른다고 침) 2. 시작점에서 가장 가까운 노드를 고른다. 3. 시작점에서 해당 노드와의 거리 (dist[x]) 와 해당 노드와 연결된 각 노드 간의 거리 (arr[x][y]) 가 기존 시작점에서 y 노드까지 거리보다 작으면 업데이트하고 해당 노드로 방문한다. (dist[x] + arr[x][y] 업데이트) 4. 방문하지..

위상정렬은 DAG (방향성 있고, 비순환 그래프) 에서 방향성에 따라 탐색을 진행시키는 정렬 방식입니다. 예를 들어 그래프가 아래와 같을 때 1부터 시작한다면 1 다음 탐색될 노드는 2,3 2 다음 탐색될 노드는 5이지만 아직 4가 끝나지 않았으므로 보류 3 다음 탐색될 노드는 4 4 다음 탐색될 노드는 5 => 1 2 3 4 5 순으로 탐색이 진행되는 정렬 방식입니다. 위상정렬은 DAG에서 일의 순서를 정해야 하는 문제 등에서 주로 사용됩니다. 방향성을 일의 처리 순서로 보는 것입니다. 위상정렬은 다음과 같이 이루어집니다. 1. 각 노드의 in degree 를 구한다. 2. in degree 가 0 인 노드를 큐에 넣는다. 3. 큐에 있는 노드를 대상으로 탐색을 하면서, 해당 노드와 연결된 노드의 in..

알고리즘 복기용 메모 binary search : 정렬되어 있는 상태에서 특정 값의 위치를 찾는 검색 알고리즘 절반 위치씩 쪼개면서 검색을 하기 때문에 복잡도는 O(log N) 구현하고자 하는 것 : 중복 가능한 배열이 오름차순 정렬 가정 1. 찾고자 하는 값이 없을 때는 해당 값이 있다면 있어야 할 위치를 리턴 2. 찾고자 하는 값이 있고, 중복된 값이라면 가장 첫 번째 인덱스를 리턴 3. 찾고자 하는 값이 단일 값이라면 해당 인덱스를 리턴 중복이 없다 + 타겟이 존재한다는 기본적인 binary search의 경우, 단순히 left, right +-1 을 해주면서 target을 만나면 끝내는 식으로 진행하면 된다. ( while(left target) { res = 0; return res; } if(..

Prompt Tuning은 아래 논문에서 소개된 내용입니다. https://arxiv.org/pdf/2104.08691.pdf Prefix Tuning과 유사한 방식으로, 각 task 별로 기존 LLM 의 일부를 fine tuning 하여 학습한다는 내용입니다. Prompt Tuning에 대한 huggingface 튜토리얼은 아래와 같습니다. https://huggingface.co/docs/peft/main/en/task_guides/clm-prompt-tuning Prompt tuning for causal language modeling 🤗 Accelerate integrations huggingface.co 해당 내용을 바탕으로 RAFT의 twitter_complaints 데이터셋에 대해 해당 트..

P-Tuning은 아래 논문에서 처음 소개되었습니다. https://arxiv.org/pdf/2103.10385.pdf 논문 제목이 GPT Understands, too 인데 그 이유는 GPT 모델의 경우, 논문이 나온 당시 GPT 모델은 NLI (Natural Language Inference), AE (Aspect Extraction) 등 텍스트 간의 추론에서 성능이 모자랐었지만, 이는 해당 모델이 이해하도록 prompt를 구성하는 것이 어렵기 때문입니다. 따라서 P-Tuning은 prompt를 GPT가 이해하기 쉽게 Tuning 한다는 의미를 갖습니다. 논문에 나온 해당 그림처럼 Prompt Encoder 부분을 이용해 GPT가 더욱 prompt를 잘 이해하도록 입력 자체를 변환시키겠다는 것이 해당..