Binary Search Tree 이진탐색과 연결리스트를 결합한 자료구조이다. 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE average case : O(log n) (평균 높이 : log n) worst case : O(n) Search 루트에서 시작. k를 찾을 때 key[x]>k 이면 x의 왼쪽 subtree에서 search key[x] 그냥 삭제 Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결 Case3: 자식노드가..
hashing dictionary (key, value)를 implementing insert, search, delete 연산의 average-case : O(1) find minimum과 같은 sort연산은 비효율적이다. dictionary dynamic-set data structure. 동적으로 크기가 변한다. operation : insert, search, delete hash table key : hash function의 input. U : universe of keys. 모든 가능한 키의 집합 K : actual keys. 딕셔너리에 매칭된 실제 키 Hash Table을 만들 때 U를 저장할 필요 없다. |k|=n의 사이즈를 테이블로 만든다. 하지만 좁은 장소에 여러개를 저장해야하므로 h..
NER? NE(개체명) 을 R(인식) 하는 작업. 문자열 안에서 NE의 위치를 알아내고 사전정의한 카테고리에 따라 알맞게 분류하는 작업 즉, NE를 인물, 장소, 시간 이라 하면 문장 안에서 인물, 장소, 시간을 나타내는 명사를 찾아내는 것이다. input : 문자열, output : 단어별로 해당되는 태그 -> multi class 분류 작업 NE 태깅 시스템 1. BIESO 개체명이 시작할 때 : B 토큰이 개체명 중간에 있을 때 : I 토큰이 개체명의 마지막에 있을 때 : E 하나의 토큰이 하나의 개체명 : S 토큰이 개체명이 아님 : O 2. BIO 1번에서 E와I 통합, S와 B통합 NER 접근법 1. 규칙 기반 접근 2. 사전 기반 접근 3. 기계학습 접근 More Info https://gi..
Markov Property → A → B → C → 연쇄해서 사건이 일어나므로 특정 상태의 발생 확률은 그 전 상태의 확률값으로 구할 수 있다. 단어 등장확률 계산하면 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 나는, 오늘 ) X P(마셨다 | 나는, 오늘, 커피를) 뒤로 갈 수록 확률을 계산하기 어려워짐 → 마르코프 특성 적용 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 오늘) X P(마셨다 | 커피를) → P(현재|이전) : bigram but, 특정 상태의 확률값을 구하기 쉽지 않음 이전의 모든 확률을 구하는것은 불가능. → 미래의 상태는 오직 현재 상태의 영향만 받는다 라고 가정 Markov Chain Mar..
LM(Language Model) 언어라는 현상을 모델링 하고자 단어 시퀀스에 확률을 할당하는 모델 단어들로 모르는 단어를 예측 문장이 적절한지 판단 통계를 이용한 방법(SLM, 전통적 접근 방식)과 인공신경망(GPT, BERT...)을 이용한 방법이 있다. 목적 : 기계 번역, 오타 교정, 음성 인식 등 에서 언어 모델을 활용하여 보다 적합한 문장을 찾아낼 수 있다. CLM(Conditional Language Modeling) 다음 단어의 등장 확률 (W: 단어 시퀀스, w: 단어 하나, n개의 단어 등장) 단어 시퀀스의 확률 P(W) = P(w1, w2, w3, ...wn) 다음 단어 등장 확률 P(wn | w1,w2,...,n-1) 전체 단어 시퀀스 W의 확률 전체 단어 시퀀스 W의 확률은 모든 ..
seq2seq? 번역기에서 대표적으로 사용되는 모델이다. RNN을 기반으로 만들어진 모델이다. seq2seq구조 seq2seq는 인코더와 디코더로 구성된다. 입력문장을 받는 RNN셀 : 인코더, 출력문장을 내보내는 RNN셀 : 디코더 인코더 : 입력 문장의 단어들을 순차적으로 입력받은 후 이를 압축해서 하나의 벡터로 만든다. 이 벡터를 context vectgor라고 한다. 인코더는 압축된 벡터를 디코더로 전송한다. 디코더 : 인코더에서 받은 context vector를 받아서 번역된 단어를 하나씩 순차적으로 출력한다. 토크나이징 된 단어들이 인코더 RNN셀의 입력이 되고 이 셀의 마지막 시점의 hidden state를 RNN셀로 넘겨주는데 이것이 컨텍스트벡터이다. 컨텍스트벡터는 디코더RNN셀의 첫번째 ..
트랜스포머? 2017년 구글이 발표한 "Attention is all you need"의 논문에서 나온 딥러닝 모델이다. 기계번역의 발전과정은 다음과 같다. RNN -> LSTM -> Seq2Seq -> Attention -> Transformer 최근 모델인 GPT, BERT는 Transformer 아키텍쳐를 기본으로 한다. Seq2Seq 2개의 RNN 신경망으로 구성된 seq2seq 모델은 인코더-디코더 구조로 구성되어있는데, 인코더는 입력 시퀀스를 하나의 벡터로 압축하고 디코더는 이 벡터를 통해 출력시퀀스를 만든다. 하지만 고정된 크기의 context vextor를 사용해서 한 벡터로 압축해야하기 때문에 입력 시퀀스의 일부가 손실되는 한계가 존재했다. 2021.04.09 - [자연어처리NLP] - ..
❓ 이 글 왜 씀? 토이프로젝트로 킹받즈 라는 웹사이트를 만들었는데 블로그도 쓰고 공부도 하고 웹사이트 업그레이드도 시켜볼 겸 쓰기로 함 주의 아직 완성 글 아님 아래 사이트에 oauth 업데이트도 아직 안했음 글 다 쓰고 할 예정 👇 그 웹사이트 https://takingprize.com 별걸 다 시상하는 킹받즈 🏆오늘도 수고한 친구에게 특별한 상을 주세요! takingprize.com sns 공유를 목적으로 만든 웹사이트이니만큼 모바일 웹 기준으로 UI를 잡았다. Oauth에 대한 개념, 코드 구현의 예시는 다 이 사이트로 설명 할 예정 📌 Oauth의 개념 Open Authorization의 약자로 인터넷 사용자들이 비밀번호를 제공하지 않고, 다른 웹사이트 상의 자신들의 정보에 대해 웹사이트나 애플..
