Today I Learned

📝 상세 정리 # 이제 순차적 프로세서 (SEQ)를 먼저 만들 것이다. 각 클록사이클에서, 완전한 명령어를 처리하는 모든 단계를 수행한다. 그래서 느릴 것이다! 4.3.1 Organizing Processing into Stages # 일반적으로, 명령어 처리에는 여러 연산이 수반된다. 우리는 그 모든 명령어가 일관된 단계 시퀀스를 따르도록 하고싶다. 과정은 다음과 같다 Fetch PC를 메모리주소로 사용하여 명령어 바이트 읽기 icode / ifun / 레지스터 지정자 / valC 등을 읽기 valP는 다음 명령어 주소 = PC의 값에 읽은 명령어의 길이를 더한 값 Decode 레지스터파일에서 최대 두개의 연산자를 읽어서 valA / valB 제공 Execute 명령어에 의해 지정된 연산을 수행하거나, 메모리 참조의 주소를 계산하거나, 스택포인터를 증가/감소하는 등. 이 값을 valE라고 한다. 조건 플래그가 설정 / 평가하는것도 여기 Memory 메모리에 데이터를 쓰거나 메모리에서 데이터를 읽어오기 그 값을 valM이라고 한다. Write back 최대 두개의 결과를 레지스터 파일에 쓰기 PC update PC를 다음 명령어 주소로 업데이트. 프로세서는 위 과정을 무한히 반복한다. 예외가 발생할때 정지한다 halt / 유효하지 않은 명령어 / 유효하지 않은 주소 등 보다 완전한 설계에서는 예외처리 모드에 진입해서 특수 코드를 실행 과정이 되게 많게 느껴지지만, 저렇게 전체 흐름을 유사하게 해야 하드웨어의 양을 최소화하고 복잡성을 줄일 수 있다. 서로 다른 명령어가 가능한 많은 하드웨어를 공유하도록 한다거나.. 하드웨어에서 논리블럭을 중복하는 비용은 소프트웨어에서 코드블럭을 중복하는거보다 훨씬 비싸니까! 4.3.2 SEQ Hardware Structure # 모든 Y86-64 명령어들은 위의 6단계의 연속으로 조직화할 것이다. 하드웨어적으로 위의 6단계는 어떻게 구성되는가? Fetch PC 레지스터를 이용해서 명령어 바이트 읽기, valP 계산 Decode 레지스터 파일의 두개의 읽기포트를 통해 valA, valB를 동시에 읽는다. Execute 명령어 유형에 따라 arithmetic / Logic ALU 유닛을 다양하게 사용한다. 그중에 입력중 하나에 0을 더하여 출력으로 전달하는 더미 adder도 있다! CC (Condition Code Register) 세개의 조건 코드 비트를 보유함 새로운 값은 ALU에 의해 계산되고, 조건부 이동 명령어를 실행할 때 목적지 레지스터를 업데이트할지를 계산함. 점프같은것도 마찬가지. Memory 메모리의 워드를 읽거나 씀. 명령어 메모리와 데이터 메모리는 그림에서는 다르게 그리지만, 결국 하나의 메모리에 엑세스하는것임 Write back 레지스터파일의 두개의 쓰기 포트로 데이터를 작성 포트 E는 ALU의 계산 결과를 쓰기 위해, 포트 M은 데이터 메모리에서 읽은 값을 쓰기 위해 사용 그림으로 나타낼때 관례 클럭 레지스터는 흰색 직사각형 (SEQ에서는 PC가 유일한 크럭 레지스터이다) 하드웨어 유닛은 연한 파란색 사각형 제어 로직 블럭은 회색 둥근 사각형 와이어 이름은 흰색 원 (라벨) 워드는 중간두께 선, 바이트는 얇은선, 단일비트는 점선 4.3.3 SEQ Timing # SEQ는 조합기와 두가지 형태의 메모리 장치(클록 레지스터, 랜덤 액세스 메모리)로 구성된다. 조합기는 시퀀싱이나 제어 없이, 입력이 변경될때마다 논리게이트 네트워크를 통해 전파된다. 랜덤 엑세스 메모리에서 데이터를 읽어오는 과정은 주소 입력에 기반하여 계산된다고 봐도 된다. 레지스터 파일에서는 합리적이고, 더 큰 회로에서도 특수한 클록 회로를 이용해서 이를 모방할 수 있다. 써있는 말이 좀 복잡한데, 그냥 회로 관점에서 어차피 쓰기도 클록 엣지에서만 일어나고, 읽기는 주소를 넣으면 데이터가 나오는 과정이니까 조합 논리 블록이랑 다를게 없다는 말인 것 같다. 명령어 메모리는 명령어 읽기 전용으로만 사용되므로, 이 유닛 자체를 조합기로 생각할 수 있다. 이렇게 생각하면, 시퀀싱에 대해 명시적으로 제어가 필요한건 PC, 조건코드 레지스터, 데이터 메모리, 레지스터 파일 4가지가 남는다. 이들은 클록신호 하나를 통해 제어되고, 레지스터에 값을 로드하고 랜덤액세스 메모리에 값을 쓰는 타이밍을 트리거한다. PC는 매 클록 사이클마다 새로운 명령어 주소를 로드하고, 조건코드 레지스터는 OPq에서만 로드되고, 데이터메모리는 rmmovq, pushq, call에서만 쓰이고… 레지스터 파일의 쓰기 포트는 매 사이클마다 두개의 프로그램 레지스터를 업데이트할 수 있지만, 특수 레지스터 ID인 0xF를 포트주소로 사용해서 쓰기가 없도록 할 수 있다. 이러한 클록ing는 시퀀싱을 제어하는데 꼭 필요한 것들이다. 원칙: No reading back 프로세스는 명령어 처리를 완료하기 위해 해당 명령어에 의해 업데이트 된 상태를 읽을 필요가 없다.

📝 상세 정리 # 4.2.0 하드웨어 상에서 전자 회로는 비트들 상의 함수를 계산하고 / 상이한 종류의 메모리 요소들에 비트들을 저장하기 위해 사용된다. 논리값 1은 1볼트 내외의 고전압, 0은 0볼트 내외의 저전압으로 표현한다. 디지털 시스템을 구현하기 위해서는 다음과 같은 세가지 주요 구성 요소가 필요하다. 비트에 대한 함수를 계산하기 위한 조합 로직 비트를 저장하기 위한 메모리 요소 메모리 요소의 업데이트를 위한 클록 신호 4.2.1 Logic Gates 논리 게이트는 디지털 회로의 기본 컴퓨팅 요소이다. bool값에 대한 and, or, not 연산 && & / || | 차이 && || 는 논리연산자 -> 결과는 0 or 1 & |는 비트연산자 -> 결과는 각 비트에 대해 수행한 값 논리게이트는 항상 활성화 되어있다. 입력값이 변경되면 잠시후에 그에따라 출력이 수정될 것 4.2.2 Combinational circuits and HCL Boolean Ecpressions 다수의 논리 게이트를 네트워크로 조립하면서 우리는 조합 회로로 알려진 계산 블록을 구성할 수 있다. 이때 몇가지 제한이 있는데 모든 논리 게이트의 입력은 다음 세가지중 정확히 하나에 연결되어야 한다. 시스템 입력(1차 입력) 일부 메모리요소의 출력 일부 논리게이트의 출력 둘 이상의 논리 게이트의 출력은 함께 연결될 수 없다. (?wire 를 상이한 전압을 향해 구동시켜서 회로 오동작을 야기할 수 있다.) 아하, 이게 무슨소린가 했는데 두 출력부를 연결하면 하나가 1, 하나가 0이었다면 연결될때 좀 곤란해진다! 전원과 접지가 만나는것도 이슈고. 네트워크는 비순환적이어야 한다. 루프는 네트워크에 의해 계산된 함수에 모호성을 야기할 수 있다. 4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions 큰 논리 게이트 네트워크를 조립함으로써 우리는 훨씬 더 복잡한 함수를 계산할 수 있다. word 단위로 연산해야지! 정수, 주소, instuction 코드, 레지스터 식별자 등 4~64비트 범위의 수많은 word가 있을 것 앞으로 그림으로 나타낼때 점선은 비트단위, 중간크기 실선은 word단위 4.2.4 Set MemberShip HCL에서 or연산이 붙어있는 코드는 in 명령어를 사용할 수 있다. 4.2.5 Memory and Clocking 조합회로는 본질적으로 어떤 정보도 저장하지 않는다. 하지만 순차회로가 필요해지면, 우리는 비트로 표현되는 정보를 저장하는 장치를 도입해야 한다. 이는 새로운 값이 장치에 로드될 때를 결정하는 주기적인 신호인 단일 클럭에 의해 제어된다. 클록 레지스터는 개별 비트 / 워드를 저장함 랜덤 액세스 메모리는 주소를 사용해서 읽거나 쓸 단어를 선택하면서 여러 워드를 저장함 대표적으로 가상 메모리 시스템, 레지스터 파일 등 아무튼 이 두가지 레지스터를 각각 하드웨어 레지스터 / 프로그램 레지스터라고 하자. 레지스터 파일은 내부 저장장치를 갖기에 조합회로가 아니다. 아하, 이게 종합적으로 무슨말인지 천천히 읽으면서 이해해보자. 결국 값을 저장할 일은 분명히 생긴다. 전에 계산한 결과를 활용하던가 해야할 수 있으니까. 잘 알듯이 그걸 저장하는 부분은 CPU의 레지스터다. CPU에 달려있는 그 친구를 하드웨어 레지스터라고 부르자. 그러면 저장을 어떻게 구현하는가? CPU에서는 안에서 D-플립플랍이라는걸 이용해서, 안에 전류를 가두는 방식을 사용한다. 가두는 타이밍은 클록 신호 (0-1 진동신호)가 켜지는 그 타이밍이다. X86-64에는 총 16개의 레지스터가 있으니까, 하드웨어 레지스터는 총 16개가 필요하다. 그리고 이것들에 대한 묶음을 레지스터 파일이라고 한다. 왜 묶어서 보관하는가? 그건 16개에 대해 모든 ALU에 다는게 에바기 때문이다. 위에 MUX, 선택기마냥 이 레지스터에서도 비트마스킹 결과처럼 연산해서 값을 얻어내는게 회로로 구현하기 훨씬 더 쉽다. 따라서 그 보드 위의 레지스터를 하드웨어 레지스터, 그리고 우리가 쓰는 %rax같은걸 프로그램 레지스터라고 한다. ❔질문 사항 # 루프는 네트워크에 의해 계산된 함수에 모호성을 야기할 수 있다. 왜? AND / OR 같은 회로들로 루프를 만들면 전압이 진동하는게 아니라 중간에서 멈춰버린다!

📝 상세 정리 # $2^N$개의 정수 배열 $A$가 주어진다. 이때 $\forall x$ 에 대해 $F(x)$를 $\sum\limits_{i \subseteq x}{A[i]}$ 라고 정의하자. 이는 $x\&i = i$ 인 $i$들에 대해 $A[i]$의 합을 의미한다. 위와 같은 문제를 어떻게 풀 수있을까? 브루트포스 # 느리지만, 다음과 같은 브루트포스로 계산할 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ for(int i = 0; i < (1<<N); i++){ if((mask&i) == i){ F[mask] += A[i]; } } } 위 식을 그대로 옮긴 것에 가깝다. 시간복잡도는 ${(2^N)}^2 = 4^N$이다. 조금 더 나은 풀이 # 두번째 반복문에 대해, 바깥쪽 반복문에서 켜지지 않은 비트에 대해서도 반복을 도는것은 너무 아깝다. 따라서 다음과 같이도 한번 시도해볼 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ F[mask] = A[0]; for(int i = 0; i < (1<<N); i = (i-1)&mask) F[mask] += A[i]; } 시간복잡도 증명이 어려워보인다. 이는 $\sum\limits_{k = 0}^N{\binom{N}{K}2^K} = 3^N$ 이라고 한다. Sum over Subsets DP # 위의 방식에서 병목은 어디에서 나타날까? 어떤 $x$의 비트가 $K$개가 꺼져있을 때, $A[x]$는 $2^K$개의 마스크에 의해 방문된다. 이 반복적인 재계산을 줄여야한다. S(mask, i) 정의 # 위 병목을 피하기 위해 새로운 상태를 하나 정의해보자. $S(mask, i)$는 $mask$의 부분집합들 중, $mask$와 하위(오른쪽) $i$개 비트(0~i-1번 인덱스)에서만 다른 것을 의미한다. 예를 들어, $S(110, 2) = \{100, 110\}$이다. 오른쪽 두개 비트에서 다를 수 있는데, 부분집합이어야 하므로 $111$같은건 안된다. 이 정의를 이용하면, 어떤 집합도 서로 겹치지 않는 $S(mask, i)$들의 합집합으로 나타낼 수 있게 된다. 점화식 유도 # 점화식은 다음과 같이 두가지로 정의할 수 있겠다. $mask$의 $i$번째 비트가 $0$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0$만을 가질 수 있으므로 $S(mask, i) = S(mask, i-1)$ $mask$의 $i$번째 비트가 $1$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0, 1$ 모두 가질 수 있으므로 $S(mask, i) = S(mask, i-1) \cup S(mask \oplus 2^i, i-1)$ 따라서 이를 코드로 나타내면 다음과 같다. for(int mask = 0; mask < (1<<N); mask++) DP[mask] = A[mask]; for(int i = 0; i<N; i++){ for(int mask = 0; mask < (1<<N); mask++){ if(mask & (1<<i)) DP[mask] += DP[mask ^ (1<<i)]; } } 계산 결과 DP에 들어있는 값은 해당 비트마스킹의 부분집합의 합이다. 시간복잡도는 그대로 보이듯이 $O(N2^N)$이다. N차원 누적합 # https://blog.queuedlab.com/posts/sos-dp 를 참고하면, 이를 $N$차원 누적합으로도 해석할 수 있다. 하이퍼 수열과 하이퍼 쿼리 문제에서 $N$차원 누적합 아이디어는 써본적이 있었는데, 이것이 SOS DP와 같다는 것이 신기하다. 앞으로는 포함배제에서 뭔가 줄이고싶으면 한번씩은 의심해보는걸로? imos-hanbyul Trick # 이와 비슷한 내용을 https://qwerasdfzxcl.tistory.com/35 여기서 본적이 있다. 지금 당장은 이해하기 귀찮으므로 이해한 내용은 나중에 추가하겠다. ❔질문 사항 # 🔗 참고 자료 # https://codeforces.com/blog/entry/45223 https://blog.queuedlab.com/posts/sos-dp https://qwerasdfzxcl.tistory.com/35

📝 상세 정리 # 지금까지 살펴본 신경망은 피드포워드 유형의 신경망이다. 이는 흐름이 단방향인 신경망을 말한다. 하지만 이에는 시계열 데이터를 잘 다루지 못한다는 단점이 있는데… 따라서 여기서 순환 신경망이 등장한다. 5.1 확률과 언어 모델 # 5.1.1 word2vec을 확률 관점에서 바라보다 $t$번째 단어를 타깃으로, 그 전후 단어를 맥락으로 취급해보자. CBOW모델은 $w_{t-1}, w_{t+1}$로부터 $w_t$를 추측하는 일을 수행할 것이다. 이 확률을 수식으로, $P(w_t | w_{t-1}, w_{t+1})$ 로 나타낼 수 있겠다. 그런데, 맥락이 좌우대칭이 아니어도 되지 않나? $P(w_t | w_{t-1}, w_{t-2})$같은걸 생각해보자. 이걸 어따 써먹지? 5.1.2 언어 모델 언어 모델은 단어 나열에 확률을 부여한다. 단어 $w_1, w_2, \cdots , w_m$이 있다고 해보자. 이들이 순서대로 출연할 확률은 $P(w_1, \cdots, w_m)$이다. 이는 분해해서 다음과 같이 쓸 수 있다. $P(w_1, \cdots, w_m) = P(w_m | w_1, \cdots, w_{m-1}) \cdots P(w_2 | w_1) P(w_1)$ 5.1.3 CBOW 모델을 언어 모델로? $P(w_1, \cdots, w_m) = \prod\limits_{t = 1}^mP(w_t|w_1, \cdots, w_{t-1} \approx \prod\limits_{t = 1}^mP(w_t | w_{t-2}, w_{t-1})$ 맥락을 두개 단어로 한정! 이를 2층 마르코프 연쇄라고도 볼 수 있겠다. 하지만 고정 길이의 한계로, 대답하기 곤란한 문장들이 생긴다. Tom was watching TV in his room. Mary came in to the room. Mary saind hi to $w$ 또한, 은닉층에서 평균내는 특징상 단어 순서가 무시된다. 그렇다면 평균내지 말고 은닉층에서 연결해볼까…? 그러면 맥락의 크기에 비례해 매개변수가 너무 커진다. 5.2 RNN이란 # Recurrent Neural Network 재발하다 / 주기적으로 일어나다 / 순환하다라는 뜻 5.2.1 순환하는 신경망 순환하다? 반복해서 되돌아가다? 이를 위해선 어떤 닫힌 경로가 필요하다. ![[Pasted image 20260203151615.png]] 이때 $x_t$를 입력 받는데, $t$는 시각을 의미한다. $x_t$는 벡터이다. 예를 들어 문장 (단어 순서)를 다루는 경우 각 단어의 분산 표현(단어 벡터)가 $x_t$가 된다. 이것이 순서대로 하나씩 RNN에 입력되는 것. 위의 순환 과정을 펼치면 다음과 같다. ![[Pasted image 20260203151754.png]] 이제 여태까지의 피드포워드 신경망과 비슷하게 보인다! 하지만, 이제는 다수의 RNN계층 모두가 실제로는 같은 계층이라는 차이가 있다. 이 계산의 수식은 다음고 같다. $h_t = tanh(h_{t-1}W_h + x_t W_x + b)$ $x$를 $h$로 변환하기 위한 가중치 $W_x$ RNN 출력을 다음 시각의 출력으로 변환하기 위한 가중치 $W_h$ 편향 $b$ 세가지가 존재한다. 행렬 곱을 계산하고, 그 합을 계산해서 쌍곡탄젠트함수를 먹인다. 그 결과가 시각 $t$의 출력 $h_t$가 된다. 이는 다른 계층을 향해 위쪽으로 출력되는 동시에, 다음 시각의 RNN계층을 향해 오른쪽으로도 출력된다. $h_t$는 $h_{t-1}$에 의해 계산되므로, RNN 계층을 상태를 가지는 계층, 혹은 메모리가 있는 계층이라고 한다. 5.2.3 BPTT ![[Pasted image 20260203152426.png]] 순환 구조에서도 똑같이 오차역전파법을 수행할 수 있다. 이를 시간 방향으로 펼친 신경망의 오차역 전파법이란 뜻으로 BPTT(BackPropagation Through Time) 라고 한다. 하지만 시계열 데이터의 시간 크기가 커지는것에 비례해서 BPTT가 소비하는 컴퓨팅 자원이 늘어난다는 단점이 있다… 기울기도 불안정해지고 5.2.4 Truncated BPTT 큰 시계열 데이터를 처리할때는 신경망 연결을 적당한 길이로 끊자. 작은 신경망 여러개로 만들자! 이것을 Truncated BPTT라고 한다. 사실 제대로 구현하려면, 순전파는 그대로 두고 역전파만 끊어야 한다. 그리고 그 잘린 단위로 학습 ![[Pasted image 20260203153224.png]] 1000개 깊이의 RNN계층이라도 10개단위로 학습하도록 이렇게 자를 수 있다! 이 하나의 단위를 블록이라고 하자. 5.2.5 Truncated BPTT의 미니배치 학습 ![[Pasted image 20260203153906.png]] 두번째 미니배치를 학습 넣을 때 데이터를 시작 위치로 옮겨서 다시 순서대로 데이터를 제공해야 한다. 5.3 RNN 구현 # 구현구현 5.4 시계열 데이터 처리 계층 구현 # 구현구현 5.5 RNNLM 학습과 평가 # 5.5.1 RNNLM 구현 5.5.2 언어 모델의 평가 언어 모델의 예측 성능을 평가하는 척도로 퍼플렉서타를 이용한다. Perplexity, 혼란도 이는 확률의 역수값 이는 직관적으로 분기 수로 해석할 수 있다. 입력데이터가 여러개라면? $L = -\frac{1}{N}\sum\limits_{n}\sum\limits_{k}t_{nk}\log y_{nk}$ $\text{perplexity} = e^L$ 5.6 정리 # 이번 장의 주제는 순환 신경망 이를 이용해 데이터를 순환시켜서, 과거 -> 현재 -> 미래로 데이터를 흘려보낸다. 이를 이용해서 언어 모델을 만들었고, 이는 단어 시퀀스에 확률을 부여하고 다음에 출연할 단어의 확률을 계산한다. 이론적으로는 아무리 긴 시계열 데이터라도 RNN의 은닉상태에 정보를 기억하게 할 수 있지만, 실제로는 잘 학습하지 못하는 경우가 많다. 다음장에서 LSTM, GRU등을 알아보겠다. ❔질문 사항 # 미니배치를 만들 때, 문장의 시작이 아닐 때도 있지 않을까? 그러니까, 미니배치에 넣기 좋게 문장이 생긴 데이터가 아닐 경우가 더 많을 것 같은데… 🔗 참고 자료 #

📝 상세 정리 # 지금까지 컴퓨터 시스템을 기계어 수준으로만 보았다. 프로세서는 두 수를 더하는 것 같은 원시적인 연산을 수행해야 한다는것을 안다. 명령어는 1바이트 이상의 시퀀스로 이진 형태로 인코딩 되는것도 안다. 특정 프로세스에 의해 지원되는 명령어들 및 그 인코딩들을 ISA (Instruction set Architecture)라고 한다. 인텔 IA32, x86-64, ARM프로세서 패밀리 등 다른 패밀리들은 다른 ISA를 가진다. 한 종류의 기계에 대해 컴파일 된 프로그램은 다른데서 실행되지 않는다. 단일 패밀리 내에는 다양한 프로세서 모델이 있다. 이 또한 컴파일러 작성자와 프로세서 설계자 간의 개념적 추상화 레이어라고 볼 수 있다! 이 장에서 배울 것 프로세서 하드웨어의 설계 (간략히) 간단한 명령어 셋 정의하기 (Y86-64) 디지털 하드웨어 디자인에 대한 몇가지 배경 기본 빌딩 블록들 자체, 그리고 그들이 어떻게 연결되어있는지 하드웨어 시스템의 제어 부분을 설명하기 위한 언어인 HCL (Hardware Control language) 순차적 동작에 기초한 Y86-64 프로세서 파이프라인을 적용한 프로세서 (5단계 분류) ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # ISA를 정의하는 것은 컴포넌트들, 명령어들, 인코딩, 프로그래밍 컨벤션 세트 등을 정의하는 것을 포함한다. 4.1.1 Programmer-Visible State Y86-64 프로그램의 각 명령어는 프로세서 상태의 일부를 판독하고 수정할 수 있다. 이를 프로그래머 가시화 (programmer-visible) 상태라고 한다. programmer은 어셈블리 코드에서 프로그램을 작성하는 사람 혹은 컴파일러를 의미함 Y86-64의 레지스터는 x86-64와 비슷하게 %rax %rbx… %r14까지 있다. 각 레지스터는 64비트 word를 저장하고, %rsp는 스택 포인터로 사용되고… 정보 조건 코드는 ZF, SF, OF 3가지가 존재한다. PC (Program Counter)은 현재 실행중인 명령어의 주소를 보유한다. 메모리는 프로그램과 데이터를 모두 유지한다. 가상 주소를 사용하여 참조 메모리 위치를 프로그램할 것 4.1.2 Y86-64 Instructions 우리가 만들 Y86-64 ISA는 x86-64의 서브셋이다. 8바이트 정수 연산만을 포함 더 적은 어드레싱 모드 더 작은 연산 세트 8바이트만 하니까, 그냥 word라고 불러도 된다! movq는 ir, rr, mr, rm movq 4가지가 있다. i는 immediate값, r은 레지스터, m은 메모리 정수연산은 addq, subq, andq, xorq 4가지로, 레지스터 데이터에만 동작하도록 할 것이다. 물론 ZF, SF, OF도 설정해야한다. 점프 명령어는 jmp, jle, jl, je, jne, jge, jg 7가지가 있다. 조건부 이동에는 cmovle, cmovl, cmove, cmovne, cmovge, cmovg 6가지가 있다. call은 스택에 return address를 push하고 jump한다. pushq, popq도 물론 있다. hlt이 나오면 상태코드가 HLT로 설정된 상태에서 프로세서가 정지된다. 4.1.3. Insturction Encoding 각 instuction에는 어떤 필드가 필요한지에 따라 1~10바이트가 필요하다. 모든 insturction은 유형을 식별하는 초기 바이트가 있는데, 여기서 위의 4비트는 코드부분, 아래 4비트는 함수 부분이다. 코드부분은 0 ~ 0xB 까지의 범위를 가진다. 함수부분은 관련 instuction이 같은 코드부분을 공유할 때만 유의하다. (OPq 등) jmp는 0x70이어야하는것처럼. 뒤의 1바이트는 레지스터 식별자이다. x86-64와 일치하게 하겠다. 뒤의 8바이트는 상수 word 영역이다. 일부 명령어는 길이가 1바이트뿐이 안되지만 피연산자가 필요하거나 상수파트가 필요하거나 하면 커진다. x86-64와 마찬가지로 다 Little Endian이다!! 예를 들어 rmmovq %rsp, 0x123456789abcd(%rdx)는 rmmovq -> 40, %rsp %rdx -> 42, 상수는 리틀엔디안 처리되어 40 42 cd ab 89 67 45 23 01 00 으로 인코딩될 것이다. 4.1.4 Y86-64 Exceptions 실행 프로그램의 전체 상태를 나타내는 상태 코드도 있다. 모두 정상인 AOK halt를 만난 HLT 잘못된 주소를 만난 ADR 잘못된 instruction을 만난 INS 4.1.5 Y86-64 Programs Y86-64는 x86-64와 달리 immediate 값을 이용한 연산이 안되기때문에, 레지스터에 로드하고 사용한다. “.“로 시작하는 word는 어셈블러에게 코드를 생성하는 주소를 조정하거나 데이터의 일부 단어를 삽입하도록 지시하는 어셈블러 지시이다. “.pos 0"은 어셈블러가 주소 0에서 시작하는 코드를 생성하기 시작해야 함을 나타낸다. 38 # Stack starts here and grows to lower addresses 39 .pos 0x200 40 stack: 이와같이 스택주소를 지정해서 더 낮은주소로 확장되도록 설정할 수도 있다. 7 # Array of 4 elements 8 .align 8 9 array : 10 .quad 0x000d000d000d 11 .quad 0x00c000c000c0 12 .quad 0x0b000b000b00 13 .quad 0xa000a000a000 배열의 시작을 나타내며, 8바이트 정렬이 이루어져 있다. 이와 같이 Y86-64를 생성하기 위한 우리의 도구는 어셈블러이기에 우리는 컴파일러, 링커, 런타임 시스템 위임 등의 작업을 수행해야 한다. 4.1.6 Some Y86-64 Instruction details pushq 명령어는 스택포인터를 모두 8만큼 감소시키고 레지스터 값을 메모리에 저장한다. 그렇다면 pushq %rsp는? 1 .text 2 .globl pushtest 3 pushtest: 4 movq %rsp, %rax Copy stack pointer 5 pushq %rsp Push stack pointer 6 Popd %rdx Pop it back 7 subq %rdx, %rax Return 0 or 4 8 ret x86-64에서, 위 코드는 언제나 0만을 반환한다. 이는 4만큼 땡기기 전의 기존 %rsp값을 push하는것을 의미한다. 1 .text 2 .globl poptest 3 poptest: 4 movq %rsp, %rdi Save stack pointer 5 pushq $0xabcd Push test value 6 popq %rsp Pop to stack pointer 7 movq %rsp, %rax Set popped value as return value 8 movq %rdi, %rsp Restore stack pointer 9 ret 해당 코드도 언제나 0xabcd만을 반환한다. 이는 또한 %rsp에 값을 넣고 %rsp를 움직임을 의미한다. ❔질문 # 인코딩된 바이트에 따라 해석해서 간단한 연산만으로 복잡한 프로그램이 돌아간다는건 알겠는데, 그래서 프로세서가 실제로 바이너리 코드들을 어떻게 연산하는거지? 프로세서는 바이너리 코드를 해석하는게 아니라 실제로 바이너리 코드가 흐르는 길 자체를 물리적으로 열고 닫는다. 예를 들어 addq %rax, %rdx과 같은 인코딩이 들어오면, 제어 유닛에서 더하기를 담당하는 ALU를 키고, %rax과 %rdx의 통로를 열어서 결국 결과값에 해당하는 전압 패턴을 얻는다.

📝 상세 정리 # 기존의 CBOW모델은 말뭉치에 포함된 어휘 수가 많아지면 계산량도 커진다는 단점이 있었다. 이를 Embedding 계층과 네거티브샘플링이라는 새로운 손힐함수를 이용하여 개선할 것이다. 4.1 word2vec 개선 1 # 기존의 CBOW모델에서 어휘가 100만개가 된다고 가정해보자. 그렇다면 입력층은 $W_{in} = 1000000 * 100, W_{out} = 100 * 1000000$의 행렬이 된다. 심지어 원핫 벡터라 상당히 sparse한데.. 이를 Embedding 계층 도입으로 해결해보자. $W_{in}$은 Embedding으로, $W_{out}$은 네거티브 샘플링으로 해결할 것이다. 4.1.1 Embedding 계층 다시한번 어휘 수가 100만개인 상황을 상상해보자. 단어의 원핫벡터는 100만차원.. 그런데, 이 연산이 무엇을 의미하는걸까? 이는 그저 행렬의 특정 행을 추출하는 것뿐이다! 다시말해, 원핫표현으로의 변환가 행렬 곱연산은 사실 큰 필요가 없다. 가중치 매개변수로부터 단어 ID에 해당하는 행을 추출하기만 하면 된다. 해당 계층을 만들어보자. 이를 Embedding 계층이라고 하고, 단어 임베딩이라는 용어에서 유래했다. Embedding 계층에 단어의 분산 표현을 저장할 것이다. 4.1.2 Embedding 계층 구현 행렬에서 특정 행을 추출하는것은 꽤나 쉽다. $W$가 2차원 numpy 배열이라면, W[2]처럼 원하는 행을 명시하면 끝 입력층 단어가 일때도 쉽게 된다. 따라서 구현에서도 W[idx]로 인덱싱만 진행하면 된다. 역전파에서도 똑같이 전해진 기울기를 idx번째 행에 전달하면 된다. 그런데 여기서 문제가 발생한다. idx의 원소가 중복된다면? 예를 들어 입력층에서 넣은 단어인덱스 배열이 [0, 2, 0, 4]라면? 이 문제를 해결하기 위해 구현 시 dW의 층을 0으로 초기화하고 각 인덱스에 대해 더해주자. 4.2 word2vec 개선 2 # 여기서는 은닉층 이후의 처리, 즉 행렬곱과 Softmax계층의 계산 파트의 병목을 해소할 것 네거티브 샘플링을 이용할 것이다. 4.2.1 은닉층 이후 계산의 문제점 언제나 그랬듯 어휘가 100만개, 은닉층 뉴런이 100개라고 생각해보자. $W_{out} = 100 * 1000000$ 의 행렬 연산을 해서 100만 길이의 출력층을 만들고 이에 softmax 함수를 적용해서 확률을 얻어내야 한다. 4.2.2 다중 분류에서 이진 분류로 이 기법의 핵심 아이디어는 다중 분류(multi-class classification)을 이중 분류(binary classification)으로 근사하는데 있다. 100만개의 단어 중 옳은 단어 하나를 고르는 문제를, 맥락이 주어졌을 때 타깃 단어는 say 입니까? 라는 이진 분류, 즉 결정 문제로 바꿀 수 있다. 그렇다면 출력층에는 뉴런을 하나만 준비하면 된다! 따라서 연산은 $W_{out}[idx] = 100 * 1$ 로 바뀌게 되고, 길이 1의 출력층만 sigmoid를 적용하면 되게 되었다. 4.2.3 시그모이드 함수와 교차 엔트로피 오차 이진 분류 문제를 신경망으로 풀 때에는 점수에 시그모이드 함수를 적용해 확률로 변환하고 손실을 구할 때에는 손실 함수로 교차 엔트로피 오차를 사용한다. 시그모이드 함수는 앞에서 배운것과 같이 다음과 같고, $y = \frac{1}{1+e^{-x}}$ 교차 엔트로피 오차는 다음과 같다. $L = -(t\log y + (1-t)\log (1-y))$ $y$는 시그모이드 함수의 출력, $t$는 정답 레이블 $t = 1$일 때 Yes, $t = 0$일때 No 따라서 $t = 1$일때 $-\log y$가, $t = 0$일 때 $-\log (1-y)$가 출력된다 이때 역전파 계산 결과, Chain Rule로 계산을 완료하면 전달되는 오차(기울기)가 $y-t$가 된다. $t = 0$일때는 $y$가 크면 크게 학습하고, $y$가 작으면 작게 학습한다는 의미도 된다! 4.2.4 다중 분류에서 이진 분류로 ![[Pasted image 20260127170240.png]] 위의 모든 최적화를 거친 그림은 위와 같다. 여기서 출력층의 Embedding 계층과 내적 연산을 합쳐서 Embedding dot 계층으로 표현하면 조금 더 간단하게도 그릴 수 있다. Embedding dot 계층은 $h, idx$를 입력받아서 점수를 반환한다. 내적은 $\text{Score} = \sum\limits_{i=1}^d{h_i \cdot w_i} = h \cdot w_{target}$ 이라고 생각할 수 있고, 곱의 결과로 나온 벡터가 실제 정답과 얼마나 유사한지에 대한 값이라고 생각할 수 있다. 4.2.5 네거티브 샘플링 위는 정답의 예만 신경썼고, 오답의 예를 신경쓰지 않았다. 이를 어떻게 학습시키면 좋을까? 모든 오답에 대해서 이진 분류를 학습시키면 어떨까? 그렇다면 다시 어휘의 수에 연산량이 비례하게 된다…. 따라서 근사적인 해법으로, 부정적인 예를 조금만 선택하자! 이를 네거티브 샘플링이라고 한다. 4.2.6 네거티브 샘플링의 샘플링 기법 샘플링을 단순히 무작위로 할 것인가? 더 좋은 방법이 있다. 말뭉치의 통계 데이터를 기초로 샘플링하자! 자주 등장하는 단어를 많이 추출하고, 드물게 등장하는 단어를 적게 추출하자. 단어의 출현 횟수를 확률분포로 나타내고, 그 확률분포대로 단어를 샘플링하면 된다. 그런데, word2vec의 네거티브 샘플링에서는 각 확률분포에 0.75승을 하라고 권장한다. 이는 출현확률이 낮은 단어를 버리지 않게하기 위함으로, 낮은 출현율의 단어의 확률을 조금 끌어올릴 수 있다. 4.2.7 네거티브 샘플링 구현 앞과 크게 다르지 않다. 4.3 개선판 word2vec 학습 # PTB 데이터셋으로 학습해보자. 4.3.1 CBOW 모델 구현 4.3.2 CBOW 모델 학습 코드 4.3.3 CBOW 모델 평가 4.4 word2vec 남은 주제 # 4.4.1 word2vec을 사용한 애플리케이션의 예 전이 학습 한 분야에서 배운 지식을 다른 분야에 적용하는 기법 자연어 문제를 풀 때, 처음부터 학습하는 것이 아니라 위키백과나 구글 뉴스등의 큰 말뭉치로 학습을 끝낸 후, 우리가 원하는 작업에 돌입하자. 문장을 고정크기 벡터로 변환할 때에는 단어 벡터들의 합을 이용하자. 4.4.2 단어 벡터 평가 방법 우리가 얻어낸 분산 표현이 좋은지는 어떻게 평가할 수 있을까? 단어의 유사성 사람이 작성한 단어 유사도를 검증 세트로 사용해 평가하는 것 유추 문제를 이용한 평가 “king : queen = man : ?” 과 같은 문제를 출제해서 정답률로 측정 4.5 정리 # CBOW모델은 말뭉치의 어휘 수 증가에 비례해 계산량이 증가하는 문제가 있었다. 이를 Embedding계층 구현, 네거티브 샘플링 두가지 방법을 도입해서 해결하였다. 핵심은 어휘 모두를 처리하는 것이 아니라 일부 단어만을 대상으로 하는 것이다. ❔질문 사항 # yes / no 결정문제로 만들면 no가 나오면 yes가 나올때까지 돌리는건가? 근데 그러면 똑같이 시간복잡도가 $O(N)$인거 아닌가? 아하, 위는 학습에서나 나오는 이야기고, 결국 나중에 디코딩할때는 = 단어를 찾을 때는 어떤 벡터의 결과값으로 가장 가까운 단어를 찾아가는건가? 그건 어떻게 이루어지지? 벡터공간에서 가장 가까운 점 찾기가 쉽나? -> 근사 최근접 이웃 (Approximate Nearest Neighbor, ANN) 알고리즘을 이용한다. [[260127_TIL_Approximate Nearest Nighbor 알고리즘]] 🔗 참고 자료 # https://word2vec.kr/search/

📝 상세 정리 # 주어진 쿼리포인트와 매우 가까운 데이터 포인트를 찾는 알고리즘 기본적으로는 모든 노드에 대해 확인해봐야하므로 $O(N)$이다. KD-Trees Locality-Sensitive Hashing (LSH) Annoy (Approximate Nearest Neighbors Oh Yeah) Linear Scan Algorithm 이건 선형이자나 머야 ❔질문 사항 # 🔗 참고 자료 # https://dytis.tistory.com/108

📝 상세 정리 # 이번 장도 단어의 분산 표현 앞 장에서 통계 기반 기법을 이용했다면, 이번에는 추론 기반 기법을 이용하겟다. 3.1 추론 기반 기법과 신경망 # 3.1.1 통계 기반 기법의 문제점 결국 동시발생 행렬을 만들고 SVD를 적용해야하는데, 이는 큰 말뭉치에서 너무 어렵다 동시발생행렬의 크기는 $O(N^2)$ SVD 연산 시간은 $O(N^3)$ 이라 어휘가 100만개 단위로 되면 현실적으로 불가능해진다 추론 기반 기법에서는 소량(미니배치)씩 학습해서 가중치를 갱신한다. 어휘량이 많아도 가능하고 여러 GPU를 이용한 병렬 계산도 가능하다! 3.1.2 추론 기반 기법 개요 추론: 주변 단어(맥락)이 주어졌을때 빈칸에 무슨 단어가 들어가는지를 추측하는 작업 추론을 통해 신경망으로 각 단어의 출현 확률을 만들자. 3.1.3. 신경망에서의 단어 처리 신경망은 단어를 그대로 처리할 수 없으니, 원핫 벡터로 변환하자. 원핫벡터: 벡터의 원소중 하나만 1이고 나머지는 모두 0인 벡터 3.2 단순한 word2vec # 3.2.1 CBOW모델의 추론 처리 CBOW모델은 맥락으로부터 타겟을 추측하는 용도의 신경망 타겟은 중앙 단어, 맥락은 주변 단어 N개의 단어를 맥락으로 사용하기로 결정했다면, N개의 원핫벡터가 입력층이 된다. 은닉층에 들어갈 값은 여러개의 입력층의 결과의 평균이다. 첫번째 입력층의 결과가 $h_1$, 두번째 입력층의 결과가 $h_2$라면 은닉층의 뉴런은 $\frac{1}{2}(h_1 + h_2)$ 이 된다. 출력층의 뉴런 하나하나는 각각의 단어에 대응되고, 해당 단어의 점수가 나온다. 점수는 확률로 해석되기 전의 값으로, softmax함수로 확률을 얻어낸다. 은닉층의 뉴런수를 입력층의 뉴런수보다 적게 하는것이 중요하다. 이렇게 해야 은닉층이 단어 예측에 필요한 정보를 간결하게 담게 되며, 결과적으로 밀집벡터 표현을 얻을 수 있다. 단어 벡터를 은닉층에 넣어서 사람이 알아보지 못하게 되는걸 인코딩, 반대로 은닉층의 정보를 사람이 알아볼 수 있는 결과로 만드는 작업을 디코딩이라고 한다. CBOW모델은 활성화 함수를 사용하지 않는 간단한 신경망이다. 여러개의 입력층은 같은 가중치를 공유한다. 3.2.2 CBOW 모델의 학습 위에서 구한 점수에 softmax함수를 적용하면 확률을 얻을 수 있다. 3.2.3 word2vec의 가중치와 분산 표현 $W_{in}$의 가중치의 각 행은 각 단어의 분산표현에 해당하고, $W_{out}$에서는 각 단어의 분산 표현이 열 방향으로 저장된다. 행렬의 차원중 어디가 각 단어에 대응되는지 알면 직관적인듯 3.3 학습 데이터 준비 # 3.3.1 맥락과 타깃 이전에 말한대로 맥락은 주변단어, 타깃은 중앙 한단어 맥락은 여러개가 될수 있으므로 contexts라고 복수형 표현을 권장 이전에 했던것과 같이 텍스트를 단어 ID로 바꾸고, 이를 배열로 저장한다. 3.3.2 원핫 표현으로 변환 학습에 사용하기 위해 이를 원핫 벡터로 바꾼다. 8개짜리, 7종류 단어의 문장이어서 (6, 2 )의 단어 ID 벡터가있었다면 이는 단어 ID가 원핫 베겉로 바뀌며 (6, 2, 7 )의 벡터가 된다. 3.4 CBOW 모델 구현 # 간단하게 두개의 맥락을 $W_{in}$ 을 통과켜서 평균을 내고, $W_{out}$을 거쳐서 softmax를 통해 Loss를 얻어내는 모델을 구상해보자. 3.4.1 학습 코드 구현 일반적인 신경망 학습과 완전히 같다! (1장 참조) 입력층의 가중치, 즉 $W_{in}$을 꺼내봄으로 단어 ID의 분산표현을 잘 확인할 수 있다. 하지만 아직 큰 맒룽치에서는 처리속도가 느리다는 문제점이 있다. 3.5 word2vec 보충 # 3.5.1 CBOW 모델과 확률 CBOW모델을 확률 표기법으로 기술해봦. 맥락이 두개인 경우, 조건부 확률 식으로 $P(w_t | w_{t-1}, w_{t+1})$ 과 같이 나타낼 수 있다. 이를 이용해 손실함수도 간결하게 표현할 수 있다. $L = -\log P(w_t | w_{t-1}, w_{t+1})$ $L = -\frac{1}{T} \sum\limits_{t = 1}^{T}\log P(w_t | w_{t-1}, w_{t+1})$ 말뭉치 전체에 대한 식 3.5.2 skip-gram 모델 CBOW모델과 맥락과 타깃을 역전시킨 모델 중앙 단어 하나로 주변 단어를 예측하자 $P(w_{t-1}, w_{t+1} | w_t) = P(w_{t-1}| w_t) P(w_{t+1} | w_t)$ $L = -(\log P(w_{t-1}| w_t) + \log P(w_{t+1} | w_t))$ $L = -\frac{1}{T} \sum\limits_{t = 1}^{T}(\log P(w_{t-1}| w_t) + \log P(w_{t+1} | w_t))$ 단어 분산의 정밀도 면에서 skip-gram 모델이 CBOW모델보다 더 좋을 때가 많다. 하지만 학습 면에서는 cbow 모델이 더 빠르다. 손실을 맥락의 수만큼 구해야하기 때문 3.5.3 통계 기반 vs 추론 기반 통계 기반은 전체를 보면서 1회, 추론 기반은 미니배치를 보면서 일부씩 여러번 학습했다. 여러가지 추가 상황들을 생각해보자. 어휘에 추가할 새 단어가 생겨난 경우 통계기반 방법은 계산을 처음부터 다시 해야함 추론기반 방법은 학습된 가중치를 초깃값으로 추가 학습을진행하면 됨 얻게되는 분산표현의 성격이나 정밀도 의외로 단어의 유사성을 정량평가한 결과, 둘 사이에 우열은 없었음 skip-gram과 네거티브 샘플링을 이용한 모델은 동시발생행렬에서 특수한 행렬 분해를 적용한 결과와 같았다!! ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # Part I: Code Injection Attacks # 새로운 코드를 인젝션하지는 않고, string을 직접 박아넣어서 존재하는 프로시져로 꽂을것이다. void test() { int val; val = getbuf(); printf("No exploit. Getbuf returned 0x%x\n", val); } 위와 같은 코드에 직접 넣을 예정 Level 1 # void touch1() 함수로 가게 만들자. 00000000004017a8 <getbuf>: 4017a8: 48 83 ec 28 sub $0x28,%rsp 4017ac: 48 89 e7 mov %rsp,%rdi 4017af: e8 8c 02 00 00 call 401a40 <Gets> 4017b4: b8 01 00 00 00 mov $0x1,%eax 4017b9: 48 83 c4 28 add $0x28,%rsp 4017bd: c3 ret 4017be: 90 nop 4017bf: 90 nop getbuf 함수를 보니, 0x28 = 40바이트를 스택메모리에 할당하고, get함수를 부른다.