Hessian matrix

• 어떠한 다변수 함수 $f(x_{1}, x_{2}, …, x_{n})$ 에 대하여 $f$ 의 Hessian matrix는 아래와 같다.

• Hessian matrix는 함수의 이차미분(second derivative)을 나타낸다. 즉, Hessian은 함수의 곡률(curvature) 특성을 나타내는 행렬이다.
• Hessian을 최적화 문제에 적용할 경우 second-order Taylor expansion을 이용하여 p 근처에서 함수를 2차 항까지 근사화 시킨다.

• Hessian은 또한 critical point의 종류를 판별하는데 활용될 수 있다.
• 어떤 함수의 일차미분이 0이 되는 점을 critical point(stationary point)라고 하며, 함수의 극점(극대, 극소), saddle point등이 여기에 해당한다.
  • 고등수학의 미분에서 $f’(x)=0$ 이 되는 지점을 의미
• 어떤 다변수 함수를 최적화하기 위해 극점(극대, 극소)를 찾기 위해서는 먼저 그 함수의 일차미분인 gradient가 0이 되는 지점(critical point)를 찾는다.
• 하지만 이렇게 찾은 critical point가 극대인지 극소인지 saddle point(변곡점)인지 구분하기 위해서는 이차미분값을 이용해야 하며, 이 때 Hessian을 사용할 수 있다.
• 그 구체적인 방법은 어떤 함수의 critical point에서 계산한 Hessian 행렬의 모든 고유값(eigen value)에 따라 달라진다.
  • eigenvalue가 모두 양수인 경우: 해당 지점에서 함수는 극소값을 갖는다 (아래로 볼록)
  • eigenvalue가 모두 음수인 경위: 해당 지점에서 함수는 극댓값을 갖는다 (위로 볼록)
  • eigenvalue가 음과 양이 섞여있는 경우: 해당 지점에서 함수는 변곡점을 갖는다 (아래 볼록과 위로 볼록이 교차)
• Hessian 행렬은 대칭행렬(symmetric matrix)이므로 항상 고유값(eigenvalue) 분해가 가능하며 서로 수직인 n개의 고유벡터를 갖는다.
  • 단, Hessian이 대칭행렬이 되기 위해서는 $\partial x \partial y = \partial y \partial x$ 와 같이 편미분의 순서가 바뀌어도 그 결과가 동일해야 한다
  • 그러기 위해선 f가 해당 지점에서 2차 미분이 가능하고 연속이어야 한다.
• 이미지에서 Hessian은 gradient의 경우와 마찬가지로 이미지 $I(x, y)$ 를 $(x, y)$ 에서의 픽셀의 밝기를 나타내는 함수로 보고 아래와 같이 계산 가능하다

• [참고글]

https://darkpgmr.tistory.com/132

프로세스 강제종료

• 코드 실행중 Ctrl+c 로도 프로세스가 중단되지 않는 경우 사용한다
• 1. GPU코드인 경우 nvidia-smi로 해당 프로세스의 PID를 알아낸다.
• 1. kill -9 PID 또는 kill -15 PID로 프로세스 종료

다중 그래픽카드 중 하나만 사용하기

• 여러 그래픽카드가 꽂혀있는 경우, 코드 내에 병렬작업처리 코드가 존재하더라도 아래의 명령어로 해당 그래픽카드만 사용 가능하다
• 새로운 터미널마다 새로 설정 해줘야 한다
• export CUDA_VISIBLE_DEVICES=GPU_NUMBER
  • ex. export CUDA_VISIBLE_DEVICES=0
• 다중 GPU로 돌아가려면 모든 gpu의 번호를 적어주면 된다
  • ex. export CUDA_VISIBLE_DEVICES=0,1

SCP 파일 전송

• 파일을 전송하는 두 pc에 모두 scp가 깔려있어야 한다.
• 1. 보내려는 파일 또는 폴더가 존재하는 디렉터리로 이동
• 1. scp -r 보낼폴더,파일명 수신PC_ID@IP_ADDRESS; 수신PC저장위치
     • ex. scp -r ./test han@123.456.789.10; /home/user/test

SSH 접속

• 커널 상 server pc에 접속할때 사용
• ssh 접속PC_ID@IP_ADDRESS
• 다음으로 pw 입력
  • ex. ssh han@123.456.789.10

우분투 시간 동기화

• grub를 이용한 윈도우/우분투 동시 설치 환경에서 윈도우 시간이 다르게 설정되는것을 막는다.
• timedatectl set-local-rtc 1

Bashrc 오타로 인한 명령어 먹지 않는 경우

• 터미널에 export PATH=/usr/bin:/bin 입력
• vim ./bashrc 들어가서 오타 다시

파일 소유권자 바꾸기

• 간혹 sudo로 생성된 파일의 소유권자가 root로 설정되는 경우가 있다.
• sudo chown username:group filename/directory 으로 변경 가능하다
  • ex. sudo chown han:han test.py

Ubuntu 디렉터리별 남은 저장공간 확인하기

• 우분투 티렉터리의 남은 용량 확인을 위해 아래의 명령어를 입력한다
• df: 모든 디렉터리에 대한 남은공간의 크기를 출력
  • 하지만 읽기 힘들다
• df -h: 모든 디렉터리에 대한 남은공간의 크기를 출력하되, 사람이 읽기 편한 GiB 단위로 출력하여준다.
• df -h 디렉터리: 해당 디렉터리의 남은 공간을 확인 할 수 있다.
  • ex. home 디렉터리의 남은 공간을 확인하고 싶은 경우
    • 1. home 디렉터리 위치에서 df -h . 입력
    • 1. 아무 디렉터리에서 df -h /home/username

CH4. 연결 리스트 (Linked list) 2-3

4-3 연결 리스트의 정렬 삽입의 구현

• 리스트에 정렬 기준을 등록
  • 새로운 노드가 정렬 기준에 맞춰 알맞은 자리에 연결되게 됨

정렬기준 설정

• 정렬기준이 되는 함수를 등록하는 SetSortRule 함수
  • 정렬기준이 되는 함수가 별도로 정의되고, 해당 함수를 함수 포인터를 이용하여 리스트에 등록해주는 역할
• SetSortRule 함수를 통해 전달된 함수정보 저장을 위한 LinkedList의 멤버 comp
  • 함수 포인터 comp에 등록될 함수는 정렬 기준을 정의하는 함수(사용자의 목적 및 필요에 의해 임의대로 정의됨)
• comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수
  • comp의 반환값에 의존하여 데이터를 알맞은 위치에 저장
• SetSortRule 함수가 호출되어 정렬의 기준(함수)이 리스트 멤버 comp에 함수가 등록되면 SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 리스트에 저장(새로운 노드를 기존의 노드 사이에 연결)
  • SInsert 함수는 LInsert 함수 내에서 comp의 정의 여부에 따라 SInsert 또는 FInsert가 호출되어 리스트에 데이터 저장(새로운 노드가 연결됨)
    • SInsert: comp 함수가 정의 된 경우 comp의 규칙에 맞게 새 노드를 기존의 노드 연결 사이에 연결시킴
    • FInsert: comp 함수가 정의되지 않은 경우 새 노드를 기존의 노드 연결의 맨 앞에 연결

SetSortRule 함수와 멤버 comp

• SetSortRule 함수내에서 plist->comp = comp;로 comp의 주솟값을 갖는, 정렬 기준을 정의한 함수의 주소를 plist의 정렬 기준(comp)으로 등록
• LInsert 함수 내에서 정렬 기준인 comp의 정의 여부에 따라 FInsert 또는 SInsert로 새로운 노드를 생성 후 기존 노드에 연결시킴

SInsert 함수

• 필기 스크린샷에 잘못된 부분이 있음
  • 리스트에 새로운 데이터의 추가는 노드의 앞쪽에 되므로 실제 비교시에는 비교 할 값과 비교 당할 값 두개만 알면 됨
  • 필기에는 비교 할 값과 비교 당할 두 값을 필요하다고 해 놓음(잘못된것!)
• 새 노드를 생성
• 새로운 포인터 변수인 pred를 정의하고, 이것을 입력된 리스트의 head가 가리키는 노드로 정의
  • 리스트가 처음 참조되는 경우라면 head는 dummy 노드를 가리키므로 pred 또한 dummy 노드를 가리키게 됨
• 왜 pred 포인터는 입력된 리스트 plist의 head가 가리키는 노드를 가리킬까? (pred = plist->head;)
  • 정렬을 정의하는 함수, 즉 comp 함수에는 인자로 (비교 할 숫자, 비교 당할 숫자)가 들어가게 됨
    • 따라서 comp 함수와 수 비교를 통해 비교 할 숫자가 비교 당할 숫자보다 작으면 무조건 비교한 숫자를 갖는 노드의 앞에 노드가 추가됨
  • 하지만 노드를 연결하는 순간에는 연결할 부위의 이전 노드의 주소와 이후 노드의 주소 두 주소를 알아야 연결 할 수 있음!
    • 새 노드->next = 기존 자리 노드->next , 기존 자리 노드->next = 새 노드 주소 순서로 노드의 연결이 이루어짐
  • 다음 노드의 주솟값은 현재 노드->next 멤버 변수를 통해 알 수 있지만, 현재 노드 이전 주소의 값은 알 수 없음
  • 따라서 pred가 이전 노드(그림에서 2가 아닌 dummy부터 시작해야)를 가리켜야 새 노드 연결이 가능해짐
    • pred가 이전 노드를 카리키면 다음 노드는 pred->next 로 정의 가능
    • 그 사이 새 노드 newNode를 newNode->next = pred->next;, pred->next = newNode; 순서로 연결하여 리스트 완성

• 새 노드가 들어갈 위치를 찾기 위한 반복문
  • while문 조건의 pred->next != Null
    • pred->next == Null을 만족하는 경우는 맨 마지막 노드를 가리키는 경우임
    • 해당 조건을 만족하면 맨 마지막 노드를 만족하면 비교하는 수는 비교했던 그 어느 수(리스트 내의 모든 유효Data)보다도 큰 수므로 맨 마지막에 연결되어야 함
  • while문 조건의 plist->comp(data, pred->next->data) != 0
    • comp함수는 두 수의 대소를 비교
    • data < pred->next->data 일 때 return 0, data > pred->next->data 일 때 return 1
    • data < pred->next->data 을 만족할때 0이 반환되므로 while문을 빠져나와 노드를 연결하게 됨

정렬의 핵심인 while문

comp의 반환 값과 그 의미

정렬의 기준을 설정하기 위한 함수의 정의

• 연결 리스트의 함수 포인터는 함수 포인터 사용의 아주 좋은 예시가 됨
  • 보통 잘 사용하지 않지만 연결 리스트에서의 새 노드 추가시 (새로운 데이터의 입력) 함수 포인터를 이용하면 손쉽게 조건에 따른 데이터의 추가를 정의할 수 있음

CH4. 연결 리스트 (Linked list) 2-3

4-2 단순 연결 리스트의 ADT와 구현

구현 할 더미 노드 기반 연결 리스트

• 연결 리스트의 3대 요소 -> head, tail, current
• 머리에 새 노드를 추가하되 더미 노드가 없는 경우, 첫 번째 노드와 두 번째 이후 노드의 추가 및 삭제 방식이 달라지게 됨
  • 별로 좋지 못한 방식(매 노드마다 일관된 처리 모습을 보이느게 좋음)
• 이 단점을 없애기 위해 dummy node 적용
• dummy node는 실제 유효한 data를 담지 않으며 생성 동시에 초기화 과정에서 달게 됨
• 두 번째 노드부터 유효 data를 입력하게 되므로 일관된 동작 가능하게 됨
  • 코드가 매우

• “DLinkedRead.c”에서 head = (Node*)malloc(sizeof(Node));를 통해 간단하게 더미 노드 추가 가능
  • head 포인터가 내용이 빈 메모리 주로를 저장하게만 하면 됨
  • 이를 기반으로 삽입, 삭제, 참조 등의 연산을 하는 코드만 좀 더 세련되게 수정하면 됨
    • 불필요한 분기를 없애는 과정
• head node가 dummy node이므로 두 번째 node부터 첫 번째 유효한 데이터가 입력되게 됨

/**** 데이터를 입력 받는 과정 ****/
while(1)
{
  printf("자연수 입력: ");
  scanf("%d", &readData);
  if(readData < 1)
    break;

  /*** 노드의 추가과정 ***/
  newNode = (Node*)malloc(sizeof(Node));
  newNode->data = readData;
  newNode->next = NULL;

  /*
  if(head == NULL)
    head = newNode;
  else
    tail->next = newNode;
  */
  tail->next = newNode;

  tail = newNode;
}
printf("\n");

• 첫 번째 노드는 dummy 노드이므로 첫 번째 데이터가 들어있는 두 번째 node부터 데이터를 출력하게 됨

/**** 입력 받은 데이터의 출력과정 ****/
printf("입력 받은 데이터의 전체출력! \n");
if(head == NULL) 
{
  printf("저장된 자연수가 존재하지 않습니다. \n");
}
else 
{
  cur = head; 
//	printf("%d  ", cur->data);   // 첫 번째 데이터 출력

  while(cur->next != NULL)    // 두 번째 이후의 데이터 출력
  {
    cur = cur->next;
    printf("%d  ", cur->data);
  }
}
printf("\n\n");

• 메모리의 해제 또한 동일하게 두 번째 노드 이후로 삭제
• 연결 리스트가 완전히 삭제 되어야 하는 경우 dummy 노드 또한 삭제가 되어야 함
• 아래의 코드는 불 필요한 노드에 대한 삭제이므로 dummy node를 삭제하지 않음

/**** 메모리의 해제과정 ****/
if(head == NULL) 
{
  return 0;    // 해제할 노드가 존재하지 않는다.
}
else 
{
  Node * delNode = head;
  Node * delNextNode = head->next;

//	printf("%d을(를) 삭제합니다. \n", head->data);
//	free(delNode);    // 첫 번째 노드의 삭제

  while(delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
  {
    delNode = delNextNode;
    delNextNode = delNextNode->next;

    printf("%d을(를) 삭제합니다. \n", delNode->data);
    free(delNode);    // 두 번째 이후의 노드 삭제
  }
}

• Dummy node의 추가를 통해 코드가 전반적으로 간결해지고 깔끔해짐

정렬 기능 추가된 연결 리스트의 구조체

• 노드 구조체는 기존과 동일
  • 리스트의 일부로써 정의된 구조체
• 구조체 표현을 통해 여러가지 연결 리스트를 관리 할 수 있게 됨
  • 구조체 선언 후 다양한 이름의 다양한 구조체를 관리 가능

정렬 기능 추가된 여결 리스트 헤더파일

• typedef List를 통해 List로 선언하여 기존 main코드(Chapter3)를 재활용 가능하게 됨

더미 노드 연결 리스트 구현: 초기화

• plist->head = (Node*)malloc(sizeof(Node));를 통해 더미 노드를 생성

더미 노드 연결 리스트 구현: 삽입

• If문을 통해 정렬 기준의 유무를 구별하고, 정렬 기준이 있다면 정렬 기준을 따르고(SInsert) 없다면 앞부분에 추가(FInsert)
• FInsert 함수에서 분기가 사라진 것을 확인 할 수 있음
  • 분기가 적어 가독성이 좋아지고 코드가 깔끔해짐
• 새로운 데이터를 추가함에 있어서 첫 번째 노드/n 번째 노드에 상관없이 동일한 삽입과정을 거친다는 것이 더미 노드 기반 연결 리스트의 장점

더미 노드 연결 리스트 구현: 참조

• LFirst를 통해 첫 번째 유효 데이터의 반환
  • cur가 유효한 첫 번째 node를 가리키게 하고 cur가 가리키는 값을 반환하면 됨
  • before 포인터는 node의 삭제를 진행하기 위해 필요
  • before 포인터는 cur 포인터가 다음 칸으로 옮겨 갈 때 필요(중간에 거쳐가야 주소를 잃어버리지 않음)
    • 기본적으로 cur의 바로 앞의 node를 가리킴
• LNext를 통해 2번째부터의 node의 값을 참조
  • 우선 cur에 before가 가리키던 주소를 넣고, cur에 cur->next 멤버 주소를 집어넣음

더미 노드 연결 리스트 구현: 삭제

• 항상 선 pointer 변경(이동) 후 값을 반환하는 process를 따름
  • cur pointer가 직전 참조된 유효 data를 가리키도록
  • 이를 위해 before가 존재
  • LR은 연속 2번 호출 불가(원칙상)
• LF->LN->…의 함수 호출을 통해 현재 4라는 값이 반환(참조)된 상태
• 삭제 후 cur과 before가 같은 node를 가리키고 있음
  • 그냥 이 상태로 둬도 상관이 없음
    • 이유?: LRemove는 바로 직전 참조 node의 삭제하므로
    • 이로인해 원칙상 LR 연속 2번 호출 불가
    • • LR의 2회 연속 호출은 일반적인 경우가 아님
    • • LF/LN 이후 1회의 LR 호출 가능
• before 포인터는 LF/LN 호출 시 해당 함수 내에서 다시 reset되므로 구지 설정해줄 필요 없음
  • LF/LN에서 plist->before = plist->cur; 로 함수 내에서 가장 먼저 초기화됨!
  • LR 이후 LF/LN은 무조건 호출되게 되어있음!
• cur 포인터는 LF/LN 함수 내에서 초기화시 필요하므로 재설정이 필요
  • LF/LN에서 before의 초기화에(plist->before = plist->cur;) 사용됨

• LRemove는 backup용으로 별도의 rpos 포인터와 삭제 후 값 반환을 위한 rdata 변수가 필요
• before는 전으로 옮기지 않아도 됨
  • 구지 옮기려면 코드가 불필요하게 길어질 뿐더러 어차피 옮겨도 LF/LN 호출 시 다시 초기화되므로 불필요

더미 기반 단순 연결 리스트 한데 묶기

• Chapter3의 함수와 내용 동일
  • main함수 하나도 안바뀌어도 header 파일과 typedef만 바꿔도 그대로 사용 가능
• 하지만 새 노드 추가시 head에 추가되므로 결과가 역순으로 출력
  • 이를 위해 별도의 정렬 삽입 알고리즘을 추가하여 헤더를 추가할 수 있도록 함
  • 다음 챕터에서…