📝 상세 정리 # 그동안 C언어의 추상화 층을 살펴봤다! 5장에서 컴파일러의 특성을 알면, 효율적인 코드에 대해 더 잘 이해하게 될 것이다. 프로그램이 다른 메모리 영역에 데이터를 저장하는 방법을 알게 되었다. 12장에서 런타임 스택에 프로그램 변수가 있는지, 동적 할당된 데이터 구조에 있는지, 글로벌 프로그램 데이터 일부에있는지 더 공부할 것이다. 프로그램은 명령어들의 시퀀스로 표현되며, 명령어 각각은 단일 동작을 수행한다. 컴파일러는 상이한 데이터 구조를 생성/동작/제어 등 여러가지를 위해 다수의 명령어를 사용한다. C에서는 경계 검사가 부족하기 때문에 버퍼 오버플로우를 조심해야 한다. C++은 C와 유사하게 컴파일되지만, 자바는 완전히 다른 방식으로 작동한다. 자바 바이트코드라고 불리는 특별한 바이너리 코드가 된다. 이는 가상 머신을 위한 머신 레벨의 프로그램이지만, 하드웨어에서 직접 구현되지 않는다. 인터프리터가 이를 시뮬레이션하여 바이트 코드를 처리한다. 이는 같은 코드가 여러 기계에서 실행될 수 있지만, 우리가 고려한 C같은 경우는 x86-64 기계에서만 실행된다는 단점이 있다. ❔질문 사항 # 🔗 참고 자료 #
📝 상세 정리 # Floating-Point Code 부동소수점 아키텍쳐는 어케 동작할라나 부동소수점 값이 저장되고 엑세스되는 방법 부동소숫점 데이터에서 작동하는 명령어 부동소수점 값을 함수에 전달하고 반환하는데 사용되는 컨벤션/관례 함수 호출 중 레지스터가 보존되는 방법에 대한 규약 SSE는 128비트, AVX는 256비트, AVX-512는 512비트.. %xmm0, %xmm1등의 어셈블리 코드가 나오면 현대적인 레지스터다! %rax, %rbx, %rsp, … %r15랑은 아예 별개. 위치도 다른듯? 연산 방식 자체가 보수방식 / 지수가수 방식으로 다르니까 다른 장치에서 SIMD도 가능하다! 3.11.1 Floating-Point Movement and Conversion Operations vmovss / vmovsd / vmovaps / vmovapd 같은 명령어들이 있다 코드 최적화 지침은 32비트 데이터는 4바이트 정렬을, 64비트 데이터는 8바이트 정렬을 만족하도록 권장하지만 안그래도 동작은 한다 정수 mov과 같은 방식으로 웬만하면 동작한다! GCC는 스칼라 이동 연산을 xmm 레지스터 - 메모리 사이에서만 수행한다. xmm 레지스터 사이에서 전송하기 위해선 vmovaps나 vmoapd 안에있는 a는 aligned, 정렬을 의미한다 float float_mov(float v1, float *src, float *dst){ float v2 = *src; *dst = v1; return v2; } 위 코드는 다음과 같이 번역된다. v1 in %xmm0, src in %rdi, dst in %rsi 1 float_mov: 2 vmovaps %xmm0, %xmm1 Copy v1 3 vmovss (%rdi), %xmm0 Read v2 from src 4 vmovss %xmm1, (%rsi) Write v1 to dst 5 ret Return v2 in %xmm0 ``` vmovaps, vmovss를 둘다 확인할 수 있다! float -> 정수에서는 잘 반올림해서 들어감 정수 -> float에서는 신기하게도 뒤에 피연산자가 3개 들어간다 이때 두번째 피연산자는 상위 바이트에만 영향을 미쳐서 무시해도 된다 일단 두번째 연산자는 결과가 들어갈 레지스터의기 기존 값을 의미한다. 웬만한 연산에서 두번째 피연산자와 세번째 목적지 피연산자는 같다 float -> float에서 조금 이상한 코드가 생성된다 상위비트를 다시 활용하지 못하게 하기 위함 가짜 의존성 이전의 상위 비트값을 써야될때 값을 기다리게 하지 않기 위해, 그냥 덮어버린다 single -> double, double -> single 둘다 마찬가지 3.11.2 Floating-Point Code in Procedures 크아악 프로시져다 언제나 그랬듯 XMM 레지스터를 이용해서 float 인수들을 함수로 전달하고 반환받고 한다 x86-64에서는 다음과 같은 관습이 관찰된다 최대 8개의 float arg가 xmm0~7로 전달되고, 더 필요하면 스택 사용 float 반환은 xm0에서 모든 XMM 레지스터는 caller-saved. 이후에 호출된놈이 맘대로 바꿔도 됨 double f1(int x, double y, long z); 위의 예에서, %edi에 x, %xmm0에 y, %rsi에 z 3.11.3 Floating-Point Arithmetic Operations double funct(double a, float x, double b, int i){ return a*x - b/i; } 위 코드는 다음과같이 번역된다. a in %xmm0, x in %xmm1, b in %xmm2, i in %edi 1 funct: The following two instructions convert x to double 2 vunpcklps %xmm1, %xmm1, %xmm1 3 vcvtps2pd %xmm1, %xmm1 4 vmulsd %xmm0, %xmm1, %xmm0 Multiply a by x 5 vcvtsi2sd %edi, %xmm1, %xmm1 Convert i to double 6 vdivsd %xmm1, %xmm2, %xmm2 Compute b/i 7 vsubsd %xmm2, %xmm0, %xmm0 Subtract from a*x 8 ret Return ``` 3.11.4 Defining and Using Floating-Point Constants 정수 연산과 달리 AVX float 연산은 immediate value로 연산할 수 없다. 대신 컴파일러는 임의값에 대해 스토리지를 할당하고 초기화하고, 메모리로부터 값을 읽는다. double cel2fahr(double temp){ return 1.8 * temp + 32.0; } 과 같은 함수가 있다면, 이는 다음과 같이 바뀐다. double cel2fahr(double temp) temp in %xmm0 1 cel2fahr: 2 vmulsd .LC2(%rip), %xmm0, %xmm0 Multiply by 1.8 3 vaddsd .LC3(%rip), %xmm0, %xmm0 Add 32.0 4 ret 5 .LC2: 6 .long 3435973837 Low-order 4 bytes of 1.8 7 .long 1073532108 High-order 4 bytes of 1.8 8 .LC3: 9 .long 0 Low-order 4 bytes of 32.0 10 .long 1077936128 High-order 4 bytes of 32.0 ``` .LC2의 위치로부터 1.8을 가져오고, .LC3에서 32.0을 판독해오는 것으로 보인다. 3.11.5 Using Bitwise Operations in Floating-Point Code 비트연산을 float에서도 사용할 수 있다! vxorps, vxorpd, vandps, vandpd 근데 float에서 비트연산은 진짜 왜하지? 레지스터를 0으로 초기화하고 싶을 때 자기 자신을 xor하기 부호 반전 / 절댓값화 맨앞 MSB 만지기 (x<0 ? 0:x)과 같은 경우 (RELU) 3.11.6 Floating Point Comparison Operations 아무래도 수를 비교는 해야겠지 ucomiss / ucomisd S1와 S2 비교 늘 그랬듯 ZF, CF, PF를 설정한다 하나라도 NaN이면, 세 플래그를 다 킨다! 3.11.7 Observations about Floating-Point Code AVX2가 float에 대해 정수랑 비슷하지만, 훨씬더 다양한 명령어와 형식을 포함하는걸 알 수 있었다. 또한 패킹된 데이터에 병렬연산을 수행해서 더 빠르게 실행시킬수도 있다. 요새 gcc가 해주더라 ❔질문 사항 # 🔗 참고 자료 #
📝 상세 정리 # 데이터와 머신레벨 코드를 지금까지 따로 살펴보았다 이제부터는 합쳐서 확인해보자 이건 포인터 단위로 공부할 것이다. 버퍼 오버플로우도 연구해보자 스택 저장량이 실행마다 다를 수 있는 경우? 를 확인해보자 3.10.1 Understanding Pointers 모든 포인터는 associated type이 있다. 어떤 object를 가리키는지 나타내는 것 객체가 타입 T를 갖는 경우, T의 포인터는 타입 *T를 갖는다. 타입 *T의 포인터는 **T이다. 그냥 * 라고 쓰면 일반 포인터를 반환한다. 이 포인터 유형은 기계코드의 일부는 아니지만, 오류를 방지하기 위해 C가 제공하는 추상화임 모든 포인터의 값은 일부 객체의 주소를 가리킨다 NULL(0)일때 빼고 (아무데도 가리키지 않음) 포인터는 &연산으로 생성된다 기계코드에서는 주로 leaq로 나타내지더라 포인터는 *연산으로 역참조된다. 지정된 주소로 저장하거나 지정된 주소로부터 검색한다. 배열과 포인터는 밀접한 관련이 있다. 배열의 이름은 마치 포인터 변수인 것처럼 참조된다. 포인터를 캐스팅할 때, 그 유형은 바뀌지만 그값은 바뀌지 않는다. 하지만 스케일링을 바꿀 순 있다 EX) p가 char * 유형의 포인터인 경우 (int *) p+7은 p+28을 계산하고, (int *) (p+7)은 p+7을 계산한다. 포인터는 함수를 가리킬 수도 있다. int fun(int x, int *p); int (*fp)(int, int *); fp = fun; int y = 1; int result = fp(3, &y); 함수 포인터의 값은 함수의 기계코드 표현에서 첫번째 명령어의 주소이다. 3.10.2 Life in the Real World: Using the GDB Debugger gdb는 GNU 디버거 ㅋㅋ bomb lab 풀면서 이미 써봤지롱 3.10.3 Out-of-Bounds Memory References and Buffer Overflow C는 배열 참조에 대한 임의의 경계 검사를 수행하지 않는다 저장된 레지스터값 반환 주소와 같은 상태 정보 로컬 변수 이 모든것들이 스택에 저장된다 근데 이건 심각한 프로그램 오류를 초래할 수도 있다!! Out of bound 배열 요소에 작성하는것으로! 그리고 이상태로 레지스터를 다시 가져오거나 ret 명령어를 하려고 하면 터질 수 있다. 이런걸 Buffer Overflow라고 한다. 문자열을 유지하기 위해 스택 상에 일부 문자 배열에이 할당되지만, 그 크기가 넘어간 경우 char *gets(char *s){ int c; char *dest = s; while((c = getchar()) != '\n' && c != EOF) *dest++ = c; if(c == EOF && dest == s) return NULL; *dest++ = '\0'; return s; } void echo(){ char buf[8]; gets(buf); puts(buf); } 이런 코드가 있다고 하자! 그런데 이 코드는 입력이 크기인 8을 넘는지 안넘는지 알 수 있는 방법이 없다…. 어셈블리로도 봐볼까? void echo() 1 echo: 2 subq $24, %rsp Allocate 24 bytes on stack 3 movq %rsp, %rdi Compute buf as %rsp 4 call gets Call gets 5 movq %rsp, %rdi Compute buf as %rsp 6 call puts Call puts 7 addq $24, %rsp Deallocate stack space 8 ret Return ``` - 스택 포인터에서 24를 빼서 할당하고, 맨위에 저장하고.. - rsp를 rdi에 적어놔서 gets / puts 둘다에도 쓸 수 있게 하고 - buf가 그러면 8바이트를 쓰니까, 뒤에 16바이트는 안쓴다. - 사용자가 7개 문자 입력 (종료문자열까지 8개) 까지는 문제가 없겠지만… 이를 넘어가면? - 0-7: buf에 잘 들어감 - 9-23: 비어있는 스택공간 - 24-31: Return address - 32+: caller에 저장된 값들 버퍼 오버플로우는 버그가 터지는것도 문제지만.. 원하지 않는 행동을 마음대로 할 수 있다면? 이것이 컴퓨터 네트워크를 통해 시스템의 보안을 공격하는 가장 일반적인 방법 이를 Exploit code라고 한다. 뭐 암튼 보안을 잘해야한다는 이야기 3.10.4 Thwarting Buffer Overflow Attacks 버퍼 오버플로우가 문제가 되니까 현대 컴파일러와 운영체제는 이를 막는 메커니즘을 구현하기 시작했다 Stack Randomization 시스템 내에 익스플로잇 코드를 삽입하기 위해서 공격자는 코드에 대한 포인터뿐만 아니라 코드 모두를 주입해야함. 또한, 해당 문자열이 들어갈 스택/메모리 주소도 알아야된다!! 역사적으로, 이는 예측 가능성이 높았다. 공격자가 공통 웹서버에서 사용하는 스택 주소를 찾았다면? 많은 머신에서 작동하는 공격을 만들 수 있었다. 그러니까, 스택의 위치를 각 프로그램의 실행마다 다르게 하자. 많은 머신이 같은 코드를 실행하더라도, 모두 상이한 스택 주소를 사용할 것이다. alloca함수같은걸 이용해서 프로그램 시작시 스택상에 랜덤한 값을 할당한다 이 값은 충분한 변동을 얻을수 있을정도로 커야하지만, 낭비하지 않을만큼 작아야하는.. 당연한말 간단하게는 이렇게 확인 가능하다 int main(){ long local; printf("local at %p\n", &local); return 0; } 이렇게 하면 언제나 같은 값을 가지지 않음을 확인할 수 있다. 이는 현재 리눅스 시스템에서 표준 관행이다. 하지만 이는 어느정도의 공격을 막을 수는 있지만 공격자가 정말 힘내면 다른 주소를 가진 공격을 반복적으로 시도해서 브루트포스로 극복 가능하다. Stack Corruption Detection 스택이 손상되었을 때를 감지하면 되지 않을까? echo함수는 local buffer의 경계를 초과할 때 터졌었다 C에서는 배열의 경계를 넘어서 쓰기를 방지할 수 있는 좋은 방법이 없다. 대신 프로그램은 그러한 쓰기가 어떠한 해로운 영향을 미치기 전에 뭔가가 발생한적 있는지를 검사할 수 있다. 이는 버퍼 오버런을 검출하기 위해 생성된 코드에 스택 보호자로 알려진 메커니즘을 통합한다 (?) 임의의 로컬 버퍼와 나머지 스택들 사이에 특별한 canary 값을 지정하는 것 이는 guard값이라고도 하며, 프로그램이 실행될 때마다 무작위라서 공격자가 그것이 무엇인지 쉽게 결정할 수 없다. 레지스터를 복원하고 돌아가기 전에, 프로그램은 이 canary가 변경되었는지 안됐는지 확인한다. 아하, 예전에 bomb lab에서 봤던 %fs:40이 이거였구나!!! Limiting Executable Code Regions 공격자가 실행 가능한 코드를 시스템에 삽입하는 능력을 제거하는 것 그중 한가지 방법은 실행 가능한 코드를 메모리 영역에 저장하는것을 제한하는 것 예를 들어, 컴파일러에 의해 생성된 코드가 있는 부분만 실행 가능하게 하고, 나머지 부분은 읽기 및 쓰기만 허용하도록 제한할 수 있겠다. 가상 메모리공간은 페이지당 2048 / 4096바이트임. (9장에서 배울 것) 하드웨어는 프로그램 / 운영체제 등한테 액세스 형태를 지정하는 메모리 보호를 지원함 많은 시스템들은 읽기 / 쓰기 / 실행에 대한 제어를 허용한다. 역사적으로 x86은 읽기 및 실행을 1비트 플래그로 병합하여, 읽기가 가능하면 실행도 가능했다. 스택쪽도 읽어야하기때문에 스택의 바이트도 실행이 가능했다 하지만 이제 64비트 프로세서에서는 AMD도 인텔도 이를 분리하기 시작햇다. 이 세가지 기술들은 프로그래머의 노력도, 수행 오버헤드도 적다. 개별적으로 취약성 수준을 낮추고, 조합해서 더 좋기도 하다. 하지만 불행히도 컴퓨터를 공격하는 방법들은 여전히 존재하고, worm과 바이러스들은 계속 공격해나간다. 3.10.5 Supporting Variable-Size Stack Frames 지금까지는 컴파일러가 스택에 얼만큼을 할당해야하는지 미리 결정할 수 있었다. 하지만 일부 기능은 요구하는 스택 메모리의 양이 달라질 수 있다! 예를들어, alooca 등의 임의 크기의 바이트를 스택에 할당하는 거라던지, 가변 크기의 로컬 어레이를 선언하던지 따라서, 나중에 함수로 돌아갈때 스택 포인터의 위치가 어디였는지를 기억하기 위해, 이를 프레임 포인터마냥 %rbp에 저장해두자!! 그러면 %rsp가 얼마나 크더라도 함수 return시 어디로 돌아가야하는지는 확실하다. 이건 기계코드에 leave라고 있다. ❔질문 사항 # 왜 8바이트가 아닌 24바이트를 땡겼지? -> 16바이트 단위로 rsp를 맞추기 위해 Stack Randomization, Stack Canary 모두 컴파일 시간에 결정된거 아닌가? 랜덤값이? 같은 컴파일된 바이너리파일을 실행하면 결국 일어나는일은 언제나 같은건가? -> ㄴ.ㄴ fs:40같은데 들어이있는 값은 맨날 다르다 그래도 RNG같은 코드가 박혀있는거 아닌가? -> 맞긴 한데, 간단한 rand()급이 아니고 마우스 움직임 / 하드웨어 인터럽트등 다양한 불규칙적 신호들을 모아서 무작위화한다. 스택에서 printf같은걸로도 못읽게 첫번째 바이트를 0x00(NULL)로 설정해서 문자열 함수 등도 방어한다! 🔗 참고 자료 # CSAPP
📝 상세 정리 # C는 서로 다른 유형의 객체를 결합해서 데이터 유형을 생성하기 위한 두가지 어쩌구.. struct, union 3.9.1 Structures 다른 유형의 객체를 단일 객체로 그룹화하는 데이터 유형 structure 내의 다른 컴포넌트는 이름으로 참조됨 모든 구성요소가 메모리의 연속 영역에 저장되고, structure에 대한 포인터가 첫번째 바이트의 주소 Array랑 비슷하다! 컴파일러는 각 필드의 바이트 오프셋을 들고있고.. 그걸로 잘 왔다갔다 참조 3.9.2 Unions 단일 객체를 여러 유형에 따라 참조할 수 있도록 함 이게 무슨소리지? struct에서 char, int[2], double이 있다면 char: 01, int: 412, double: 16~24바이트로 총 24바이트 메모리 사용 사이공간은 패딩 Union이었다면 가장 큰것에 맞춰서 그저 8바이트 사용 그때그때 char / int / double로 읽는 것 근데 그럼 이걸 왜쓰냐? 한번에 char / int / double 중 여러 값을 동시에 가지지 않을떄! 책에 나온 예제는 리프노드에만 값이 있는 이진 트리 구조체 왼쪽노드 포인터, 오른쪽노드 포인터, double 2개를 가진다고 해보자 struct는 32바이트, Union이라면 잘 묶어서 16바이트로 처리 가능 다음 예시를 보자. double uu2double(unsigned word0, unsigned word1) { union { double d; unsigned u[2]; } temp; temp.u[0] = word0; temp.u[1] = word1; return temp.d; } 이때 word0 = 0x12345678, word1 = 0x9abcdef0 이라고 하면 temp에는 Little Endian일때 78 56 34 12 f0 de bc 9a Big Endian일땐 12 34 56 78 9a bc de f0 가 저장된다. 이를 d로 읽을 때 Little Endian에서는 0x9abcdef012345678 Big Endian에서는 0x123456789abcdef0 으로 해석하게 된다. (d를 읽을때도 endian 신경썽하니까!!) 3.9.3 Data Alignment 일부 객체들에 대한 주소는 2, 4, 8등의 배수여야함을 요구하는 애들이 있다 이래야 하드웨어 설계가 단순화된다 8의 배수로 정렬되어있으면 메모리 한번만 참조하면 되지만, 아니라면 앞뒤로 분할되어 있는곳에 두번 참조해야할 수도 있음 x86-64는 데이터의 정렬에 관계없이 올바르게 작동하지만, 인텔은 메모리 시스템 성능 향상을 위해 정렬할것을 권고하고 있음 정렬 권장사항은 다음과 같다 K = 1 : char K = 2 : short K = 4 : int, float K = 8 : long, double, char * 아하, 이게 bool 정적 배열보다 bitset이 빠른 이유구나!! 알아서 SIMD를 지원하면서 채워주는거구나!! 그리고 이걸 패딩이라고 하겠구나! .align 8 어셈블리에서 다음과 같은 코드가 있으면, 그 뒤따르는 데이터가 8의 배수읜 주소로 시작될 것을 보장한다. struct S1 { int i; char c; int j; } 가 있다고 가정하면, 4 / 1 / 4 바이트를 쓰는게 아니라 4 / 1 + 3(패딩) / 4 바이트를 쓴다. 결과적으로 j는 오프셋 8을 가지며 전체 구조 크기는 12바이트이다. 또한, 컴파일러는 S1 유형의 포인터 p가 4바이트 정렬을 만족하는지 확인해야한다. ❔질문 사항 # 일부 객체들에 대한 주소는 2, 4, 8등의 배수여야함을 요구하는 애들이 있고, 이래야 하드웨어 설계가 단순화된다 하드웨어 설계가 단순화된다는건 뭘까? 또한, 컴파일러는 S1 유형의 포인터 p가 4바이트 정렬을 만족하는지 확인해야한다. 안에 있는 원소들 중 K의 최댓값을 기준으로 하나? 🔗 참고 자료 # CSAPP
📝 상세 정리 # 야호! 자연어처리의 세계로 들어왔다! 문제의 본질은 컴퓨터가 우리의 말을 이해하게 만드는 것 2.1 자연어 처리란 우리가 평소에 쓰는 말을 자연어라고 한다. 자연어 처리 (NLP)는 이 자연어를 처리하는 분야. 컴퓨터가 우리말을 이해하게 만들자 우리의 말은 문자로 구성되며, 말의 의미는 단어로 구성된다. 단어는 의미의 최소단위이다. 따라서 컴퓨터에게 단어의 의미를 이해시키는게 중요하다. 그 방법으로는 시소러스를 활용한 기법 통계 기반 기법 추론 기반 기법 (word2vec) 2.2 시소러스 단어의 의미를 나타내기 위해, 사람이 직접 단어의 의미를 정의해보자. 표준국어 대사전처럼 각각의 단어에 그 의미를 설명해 넣을 수 있을까? EX) 자동차 원동기를 장치하여 그 동력으로 어쩌구 시소러스는 유의어 사전으로, 뜻이 같은 단어나 비슷한 단어를 한 그룹으로 묶은 것 동의어 / 유의어 상위와 하위, 전체와 부분 등 더 세세한 관계까지 정의해둔 경우도 있다. 이 그래프 구조를 단어 네트워크라고 생각하고, 컴퓨터한테 가르칠 수 있지 않을까? WordNet 자연어 처리에서 가장 유명한 시소러스 그런데 이런 시소러스에도 문제가 있는데.. 시대 변화에 대응하기 어렵다 사람을 쓰는 비용은 크다 단어의 미묘한 차이를 표현할 수 있다 2.3 통계 기반 기법 이제부터는 말뭉치(corpus) 를 이용할 것 대량의 텍스트 데이터 맹목적으로 수집한거 말고, 연구나 어플리케이션을 위해 수집한 것 말뭉치 안에는 자연어에 대한 사람의 지식이 충분히 담겨있다고 볼 수 있다! 자연어 처리에는 다양한 말뭉치가 이용되는데 위키백과나 구글뉴스등도 되고 셰익스피어나 나츠메소세키씨 작품이라던지 일단 한번 연습을 해보자. 전처리 텍스트 데이터를 단어로 분할하고 그 분할된 단어들을 단어 ID 목록으로 변환하는 일 단어의 분산 표현 색을 코발트블루/싱크레드처럼 이름붙일수도 있지만, RGB기호로 나타낼 수도 있을 것이다 심지어 그쪽이 색을 더 정확하게 명시할수도 있고, 3개의 성분으로 간결한 표현도 된다 관련성 여부도, 정량화하기도 쉽다!! 그렇다면 단어도 이렇게 벡터로 표현할 수 있을까? 이를 단어의 분산 표현 이라고 하자 분포 가설 많은 연구들과 기법들이 있었는데, 그 뿌리는 다음과 같다. 단어의 의미는 주변 단어에 의해 형성된다 이를 분포 가설이라고 한다. 이는 단어 자체에는 의미가 없고, 그 단어가 사용된 맥락이 의미를 형성한다는 것을 내포한다. 앞으로 맥락이란 주변에 놓인 단어들을 가리킬 것이다. 윈도우 크기가 k라면 좌우 k단어씩, v[idx-k:idx+k+1] 을 의미한다. 일단 먼저 주변 단어를 세어보는 방법이 자연스럽게 떠오른다! 이를 통계 기반 기법이라고 하자. id값의 종류를 크기로 하는 벡터를 id에 대해 연결해서, $N^2$ 행렬을 만들 수 있다. 이를 동시발생 행렬이라고 하자. 이제 벡터 사이 유사도를 측정하자. 내적.. 유클리드거리.. 등등 모두 쓸 수 있겠지만 우리는 코사인 유사도를 이용하자. $\text{similarity}(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x} \cdot \mathbf{y}}{||\mathbf{x}|| \, ||\mathbf{y}||} = \frac{x_1 y_1 + \cdots + x_n y_n}{\sqrt{x_1^2 + \cdots + x_n^2} \sqrt{y_1^2 + \cdots + y_n^2}}$ 이때 ${||\mathbf{x}||}$는 노름이다. 값은 -1에서 1 사이가 나온다. 이걸로 내림차순을 하든 뭘하든 해서 유사도를 계산할 수 는 있지만… 말뭉치가 작으면 문제가 많다. 2.4 통계 기반 기법 개선하기 두 단어를 그냥 이렇게 생으로 하면.. 문제가 깊다 the car의 the같이 괘씸한 놈이 존재함 점별 상호정보량 (PMI) $\text{PMI}(x, y) = \log_2 \frac{P(x, y)}{P(x)P(y)}$ $P(x), P(y), P(x, y)$ 는 각각 x가 일어날 확률, y가 일어날 확률, 동시에 일어날 확률 이 PMI값이 높을수록 관련성이 높다 이는 동시발생 행렬을 이용해서 다시 쓸 수 있는데 $= \log_2 \frac{\frac{C(x, y)}{N}}{\frac{C(x)}{N} \frac{C(y)}{N}} = \log_2 \frac{C(x, y) \cdot N}{C(x) C(y)}$ 하지만 이때 동시발생횟수가 0이면 $log_2 0$ 을 계산해야한다는 문제가 있다… 따라서 양의 상호정보량을 사용하자. $= \text{PPMI}(x, y) = \max(0, \text{PMI}(x, y))$ 0 이상의 실수로 표현하는게 가능해졌다! 거대한 문제가 생겼다 단어가 $N$개면 차원 또한 $N$개가 된다!!! 심지어 대부분은 0이다 차원 감소 물론 중요한 정보는 최대한 유지하면서 차원을 줄여야한다. sparse한 행렬/벡터를 중요한 축을 잘 찾아서 dense한 행렬/벡터로 만들어야 한다 특잇값분해(SVD) 임의의 행렬을 세 행렬의 곱으로 분해 $\mathbf{X} = \mathbf{U}\mathbf{S}\mathbf{V}^T$ $\mathbf{U}, \mathbf{V}$는 직교행렬 $\mathbf{S}$는 대각행렬 근데 이게 시간복잡도가 $O(N^3)$이라서, Truncated SVD같은걸 이용하기도 한다. 특잇값이 작은걸 버리는 방식 PTB 데이터셋 본격적인 적당한 말뭉치를 이용해보자! 여러가지 전처리는 좀 해두셨다 희소한 단어를 <unknown>으로 바꾸기 구체적인 숫자르 N으로 수정하기 각 문장의 끝에 <eos> (end of sentence) 추가하기 결과가 재밌다! 신기하네 2.5 정리 우리는 단어의 의미를 벡터로 인코딩하는데 성공했다! 와! 심지어 SVD를 이용해서 차원을 감소시키고 더 좋은 벡터를 얻어냈다! 와!! ❔질문 사항 # 윈도우를 이용해서 하면, 문법적인것 (굴절어, 교착어 등)에 대한 정보가 손실되지 않나? I say hello와 hello say I가 같은 의미를 가지게 되니까. 직교행렬을 공부하자 선형대수를 공부해야한다 ㅁㄴㅇㄹㅁㄴㅇㄹ 🔗 참고 자료 #