기초 공부

머신러닝(machine learnig)

• Cross Validation은 무엇이고 사용이유는 무엇인가요

• 회귀 / 분류시 알맞은 metric은 무엇일까요?

  • 회귀에 적합한 metric

    • MSE(평균 제곱 오차, 이상치(outlier)를 잡아내는 데 효과적임)
    • MAE(평균 절대값 오차, 변동치가 큰 지표와 낮은 지표를 같이 예측하는 데 효과적임)
    • RMSE(MSE에 Root를 씌운 값)
    • RMAE(MAE에 Root를 씌운 값)
    • RSS(예측값과 실제값의 오차의 제곱합)
    • R2(앞서 설명한 metric이 데이터의 크기에 의존한다는 단점을 해결하기 위해,R2는 1-(RSS/전체 분산)입니다. R2는 회귀 모델의 설명력을 표현하는 지표로써, 그 값이 1에 가까울수록 높은 성능의 모델이라고 할 수 있습니다. R2의 식에서 분자인 RSS의 근본은 실제값과 예측값의 차이인데, 그 값이 0에 가까울수록 모델이 잘 예측을 했다는 뜻이므로 R2값이 1에 가까워지게 됩)

  • 분류에 적합한 metric

    • Accuracy (클래스의 개수가 불균형할 경우 신뢰도가 떨어진다는 단점)
    • Precision
    • Recall
    • F1 socre(Precision과 Recall의 가중 조화평균 값)

• 정규화를 왜 해야할까요? 정규화의 방법은 무엇이 있나요?

• Local Minima와 Global Minima에 대해 설명해주세요.

  • Local Minima: 경사하강법을 사용할 때 경사도가 0이지만 최소점은 아닌 지점
  • Global Minima: 경사하강법을 사용할 때 경사도가 0이고 최소점인 지점

• 인공신경망(deep learning이전의 전통적인)이 가지는 일반적인 문제점은 무엇일까요?

  • gradient vanishing/exploding, XOR 함수 학습 불가능

• L1, L2 정규화에 대해 설명해주세요

• Precision 설명

  • TP/(TP+FP) => 정답인 검출결과 수 /모델이 예측한 모든 검출 결과(whole detections) 수

• Recall 설명

  • TP/(TP+FN) => 정답인 검출 결과 수/정답(ground truth) 수

• Detection 에서 mAP 구하는 방법

  • Recall과 Precision을 confidnence 간격만큼 구하여 AUC 커브를 구한다.
  • 구한 AUC 커브 그래프의 면적을 구분 구적법을 통하여 mAP를 산출한다.

딥러닝(deep learning)

• 딥러닝은 무엇인가요?

  • 신경망(Neural Networks)를 기반으로한 레이어가 깊은 층으로 구성된 학습 방법

• Cost Function과 Activation Function은 무엇인가요?

  • Cost Function란 실제 목표값과 예측값의 오차를 산출하는 함수
  • Activation Function란 어떠한 신호를 입력받아 이를 적절한 처리를 하여 출력해주는 함수. 이를 통해 출력된 신호가 다음 단계에서 활성화 되는지를 결정

• 오버피팅일 경우 어떻게 대처해야 할까요?

  • 모델의 복잡도(Complexity)를 낮추기 위해서 파라미터 수를 줄인다.
  • 정규화 기법을 활용한다 ex) Drop-out, L1/L2 norm, Batch normalization(배치 단위로 수행되어서 정규화 효과를 줌)

• Local Minima 문제에도 불구하고 딥러닝이 잘 되는 이유는?

  • 탐색된 Local Minima가 Global Minima 만큼의 적은 에러율 가지고 있으며 다수 존재하기 때문임

• Cross Entropy

  • 오답일때 로스값을 무한대로 보낼수있다.

• MSE

  • 오답이더라도 로스의 최대값은 1이다.

컴퓨터 비전(computer vision)

• Faster-RCNN의 장단점은?

  • 장점
    • 2 stage 모델로 정확도가 높다.
  • 단점
    • 하나의 CNN을 통해서 Feauture를 추출하고 RPN 활용하여 region proposal을 수행했지만 역시나 그 때문에 느리다.

• YOLO의 장단점은?

  • 장점
    • 1 stage 모델로서 속도가 매우 빠르다.
    • 이미지 전체를 두고 판단한다.
    • 물체의 일반적인 표현을 학습한다.
  • 단점
    • 그리드 영역 보다 더 작은 물체 대한 위치 파악이 어렵다.
    • 앵커 기반의 모델이기 때문에 데이터가 불균형할 경우 성능 저하의 가능성이 있다.

• CenterNet 특징?

  • 물체마다 단 하나의 Keypoint인 중심점(Center Point)을 측정함.
  • grouping 과정이나 post-processing 과정(ex. NMS)들이 필요 없게 되고, 단 하나의 Anchor를 가짐

• Yolov4 와 Yolov3의 차이(링크1,링크2)

  • Yolov3의 백본은 Darknet53
  • Yolov4의 백본은 CSPDarknet53
  • Yolov4의 경우 Yolo3의 augmentation을 이어받으면서 Mosaic, Self Adversarial Training 등을 활용했다.
  • Yolov4==Yolov3+CSPDarknet53+SPP+PAN(Path Aggregation Network)+BoF+BoS

• CAM(Class Acitviation Map)은 무엇인가요?

  • Feature map과 GAP을 통해서 연결된 특정 클래스 아웃풋의 웨이트값을 곱해해 합한 값을 각 클래스마다 구한 히트맵

• Grad-CAM(Generalized-Class Acitviation Map)은 무엇인가요?

  • 기존의 CAM은 GAP이 꼭 필요로 했지만 Grad-Cam은 Feature Map와 특정 클래스 Output 간의 Gradient 구하고 Feature Map을 곱하여 산출한 히트맵

• One-stage 와 Two-stage detector 차이

  • Two Stage
    • region proposal 알고리즘 통해서 물체가 있을만한 영역을 찾아낸다.
    • 제안된 영역들을 분류(classfication)한다
  • One Stage
    • region proposal과 분류(classification)을 동시에 처리한다.

• NMS(Non Maximum Suppression)최적화 방법

  • for 루프를 SIMD를 활용하여 벡터화(vectorize)시키면 속도를 크게 향상

C++

• 오버라이딩이 무엇인가

  • 부모 클래스부터 정의된 함수를 자식 클래스에서 함수를 재정의

• 오버로딩이 무엇인가

  • 함수명이 같고 매개 변수의 타입이나 개수가 다른 함수를 정의

• 객체 지향의 대표적인 특징 5가지

  • 상속, 다형성, 캡슐화, 정보 은닉, 추상화

• virtual 함수에 대해서 설명해보시오

  • 부모 클래스(상속되지 않은 클래스) 내에서 선언되어 자식 클래스에 의해 재정의되는 맴버 함수
  • 실행시간(Runtime)에 함수의 다형성(Polymorphism)을 구현하는데 사용

• 가상 소멸자에 대해서 설명해보시오

  • 객체의 소멸자를 부르기 위해서 사용하는 것으로 virtual로 선언된 소멸자를 가상 소멸자라고 한다.
  • 가상 소멸자가 호출되면, 상속 계층구조상 가장 아래에 존재하는 자식 클래스의 소멸자가 호출되고 부모 클래스의 소멸자가 순차적으로 호출.

• 스택과 힙의 차이

  • 스택
    • 예약된 로컬 메모리 공간
    • 함수 호출과 반환이 일어남
    • 메모리를 할당 및 해제할 필요가 없음
  • 힙
    • 전역 메모리 공간
    • 비어 있으면서 연속된 메모리를 블록을 찾아야함
    • 프로그래머가 메모리 할당 및 해제를 직접해야함

• malloc, new의 차이점

  • malloc은 C의 <stdlib.h> 헤더 파일에서 지원하는 함수로, 인자로 할당할 size를 받는다. 기본적으로 void* 형태의 포인터를 return 하기 때문에 할당할 포인터 자료형에 맞게 casting이 필요하다. 메모리 해제는 free() 사용 한다.
  • new는 C++ 자체에서 지원하는 키워드(연산자)로 따로 헤더 파일이 없다. malloc과는 다르게 할당할 객체의 크기를 알아서 게산하여 heap에 할당하기 때문에 크기(size)를 입력할 필요가 없다. 또한 객체 생성시 생성자를 자동으로 호출하기 때문에 생성과 초기화가 동시에 이루어진다. 메모리 해제는 delete 키워드를 사용한다.

• 차이점

  • malloc은 헤더 파일이 필요하지만 new는 그렇지 않다.
  • malloc은 size를 인자로 받고 자료형 포인터에 따라 캐스팅을 필요로 하지만, new는 할당할 타입과 같은 포인터 변수로 받기만 하면 된다.
  • malloc과 달리 new는 생성자를 자동으로 호출하게 된다. 따라서 new는 생성과 동시에 초기화가 이루어진다. 반면에 malloc은 메모리 공간만 확보할 뿐이다.

• 가상 함수(virtual)의 동작 원리

  • 기존의 함수는 정적 바인딩 형태로, 컴파일 시간에 호출 된다. 이미 호출 되어야 하는 함수의 주소를 알고 있기 때문이다. 하지만 가상 함수와 같이 런타임 시점에서 동적 바인딩을 통해 호출될 함수의 주소를 결정해야하는 경우가 있다. 그런 경우 사용하는 키워드가 virtual이다.
    1. 어떤 클래스의 함수가 virtual로 선언되어 있다면, 해당 클래스의 가상 함수 주소를 보관하는 vtable이 만들어진다. 가상함수 테이블은 객체가 아닌, 클래스에 생성됨을 주의하라
    2. 객체를 생성하게 되면 가상 함수 테이블을 가리키는 포인터 변수가 생성된다. 이 포인터는 각 클래스에 해당하는 가상함수 테이블을 가르키기 때문에, 포인터를 통해 각 타입에 맞는 함수의 주소를 동적으로 찾을 수 있다.

• 얕은 복사(Shallow copy)와 깊은 복사(Deep copy)

  • 얕은 복사는 한 객체의 모든 멤버 변수의 값을 복사한다. 깊은 복사의 경우에는 그 뿐 아니라 포인터 변수가 가리키는 모든 객체에 대해서도 시행한다.
    예를 들면 같은 클래스의 객체 A,B가 있다고 할때, A에는 int형 멤버 변수 a1, a2가 존재하고, 다른 객체를 참조하는 포인터 ptr이 있다고 할때, 얕은 복사는 새로 생성한 객체에 a1, a2를 각각 복사하되, 포인터 ptr가 가리키는 객체는 동일하게 유지된다.
    즉 원본과 복사본이 가리키는 ptr은 같은 객체를 가리키게 되는 것이다. 이러한 방식이 얕은 복사이다.
    반면 ptr이 가리키는 객체의 모든 멤버 변수를 복사해서 새로이 복사된 객체의 포인터에 새로 할당되면,
    원본, 복사본이 ptr이 가리키는 주소는 다르지만, 객체의 구성은 동일하게 된다. 이러한 방식은 깊은 복사이다.

• volatile 이란

  • volatile이란 컴파일러에게 해당 변수의 값이 외부에 의해 바뀔수 있음을 알려주어 최적화를 방지한다. 해당 변수는 운영체제, 하드웨어, 혹은 다른 스레드에 의해 변경될 수 있음을 컴파일러에게 알려주어 프로그래머라 작성한 방식 그대로 동작하도록 만든다.
    ex) 포인터 변수에 값을 중복 할당시, 컴파일러가 중복된 과정을 제거할 수 있지만 중복할당의 로직이 중요한 요소인 경우 최적화를 수행하지 못하도록 하는 것이 volatile이다.

자료구조

배열(Array)

• 정적으로 필요한 만큼한 원소를 저장할 있는 공간이 할당. 각 원소의 주소는 연속적으로 할당
• 인덱스(index)를 통해 O(1)에 접근 가능
• 삽입, 삭제는 O(N)
• 지정된 개수를 초과하는 경우 배열의 크기를 재할당한후 복사해야함

링크드 리스트(Linked-list)

• 선형적으로 노트(Node)들이 연결된 자료구조
• 크기 제한이 없다(Heap 용량이 충분하다면)
• 다음 노드에 대한 참조를 통해 원소를 접근 (O(N))
• 노드의 삽입, 삭제 강점을 가짐(O(1))

벡터(Vector)

• 동적으로 크기가 조절되는 배열
• 배열이 가득 차는 겨우 알아서 그 크기를 2배로 할당하고 복사를 수행
• 재할당에 걸리는 시간은 O(N)이지만, 자주 일어나는 일이 아니기 떄문에 접근 시간은 O(1)

스택(Stack)

• LIFO 방식
• 원소의 삽입, 삭제가 한쪽끝에서만 이루어진다. 이부분을 top이라고 함
• 함수 호출시 지역 변수, 매개변수 정보를 저장하기 위한 공간인 스택으로 사용

트리(Tree)

• Cycle이 없는 무방향 그래프를 트리라고함
• 완전 이진트리 기준으로 높이는 logN이 됌
  • 중위 순회: 루트를 2번째 탐색(left-root-right)
  • 전위 순회: 루트를 1번쨰 탐색(root-left-right)
  • 후위 순회: 루트를 3번째 탐색(left-right-root)
  • 레벨 순서 순회: 노드를 레벨 순서로 방문, 이는 BFS와 동일하므로 큐를 통해 구현할 수 있음

이진탐색트리(BST)

• 노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽 노드의 값보다 큰값으로 구성됌
• 이상적인 상황에서의 탐색/삽입/삭제 모두 O(logN)
• 편항되는 경우에는 최악 O(N) => 모든 값이 정렬되서 입력 된 경우

큐(Queue)

• FIFO 방식
• 원소의 삽입과 삭제가 다른 부분(끝- 처음)에서 일어난다.
• FIFO 운영체제, 은행 대기열 등

우선순위 큐 (Priority Queue)

• FIFO가 아니라 데이터를 근거로 우선 순위를 판단, 우선 순위가 높은 것을 먼저 가져옴
• 구현 방법 3 가지 (배열, 연결리스트, 힙(heap))

1. 배열

   • 간단하게 구현이 가능
   • 데이터 삽입 및 삭제 과정 중 O(N)(한칸씩 당기거나 밀어야됌)의 비효율 발생
   • 삽입의 위치를 찾기 위해 배열의 모든 데이터를 탐색(우선 순위가 가장 낮은 경우)

2. 연결 리스트

   • 삽입, 삭제는 O(1)
   • 마찬 가지로 삽입 위치를 찾기 위한 비효율 발생

3. 힙

   • 위의 2가지 조건을 충족할 수 있다. 주로 힙을 사용하여 우선순위큐를 구현함
   • 힙은 완전이진트리의 성질을 만족하기 떄문에 1차원 배열로 표현이 가능함. 이를 통해 leaf node에 O(1)에 접근이 가능함
   • 루트 인덱스에 따라 left, child 노드의 인덱스를 계산 가능
     (root가 0이면 left=2*index+1, right=2*index+2, root가 1이면 left=2*index+1)
   • 데이터의 삽입은 트리의 leaf 노드로 부터 시작됨.
   • 삽입후 heapify 과정을 통해 힙의 모든 부모-자식 노드의 우선 순위에 맞게 설정한다(부모의 우선 순위는 자식의 우선순위보다 커야함)
   • 삭제 root 노드를 삭제하게 됌(우선 순위가 가장 큰 것)
   • 삭제 후 마지막 leaf 노드를 루트 노드로 옮긴 뒤 heapify 과정을 수행함

해시 테이블

• 키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장되는 자료구조
• key-value 쌍으로 이루어짐
• 해시 함수를 통해 입력받은 key를 정수 값로 대응시킴
• 충돌(collision)에 대한 고려가 필요함
• hash function을 사용하여 index를 버킷의 배열로 계산
• 효율적인 탐색을 위한 자료 구조

해싱 충돌 해결책

1. 개방형 주소(Open Address) 방법

   (1). 선형 조사법(linear probing)

   • 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
     ex) ht[k],ht[k+1],ht[k+2]
   • 삽입의 경우
     충돌이 ht[k]에서 일어났다면 ht[k+1]이 비어있는지를 조사, ht[k+2]를 조사
     테이블 끝에 도달하면 처음으로 이동 ,그럼에도 불구하고 시작한 위치로 돌아오면 테이블이 가득찬 경우임
   • 검색의 경우
     ht[k]에 있는 키가 다른 값이면 ht[k+1]에 같은 키가 있는지 조사
     비어있는 공간이 나오면 찾는 키가 없는 경우
     검색을 시작한 위치로 돌아오면 찾는 키가 없는겨우

   (2). 이차 조사법

   • h[k],h[k+1],h[k+4], h[k+9]
   • 선형 조사법에서 발생하는 집적화를 완화하는 효과가 있다.

   (3). 이중 해시법

   • 재해싱(rehashing)이라고도 불림
   • 충돌로 인해 비어있는 버킷을 찾을 때 추가적인 해시함수 h'()를 이용하는 방식
   • h'(k)=C-(k mod C)
   • 조사 위치
     h(k),h(k)+h'(k),h(k)+2h'(k)

2. 체이닝(Chaning)

   • 각 버킷은 고정된 개수의 슬롯 대신 유동적인 크기를 갖는 연결리스트로 구성
   • 충돌 뿐만 아니라 오버플로우 문제도 해결된다.
   • 버킷 내에서 항목을 찾을 때에는 연결 리스트를 순차 탐색
   • 순차 탐색 대신 BST(이진 탐색 트리)를 통해서 O(logN) 탐색 가능

3. 해싱의 성능 분석

   • 적재 밀도 또는 적재 비율 a: 저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율
     a=n/M

4. 맵과 해쉬맵의 차이

   • C++의 map 컨테이너는 이진탐색트리(최근에는 Red-Black Tree)사용. key 값을 이용해 트리를 탐색하게 됌
   • 따라서 원소 접근, 삽입, 삭제는 O(logN)
   • 반면에 해쉬맵은 O(1)에 접근 가능(key의 길이 제외한다면)
   • 그럼에도 불구하고 C++ 공식 STL에 지원하지 않는 이유는 Collision을 해결하기 위한 방법이 안정적이 못하기 떄문(해쉬 함수, Collision 정책에 따른 성능의 차이가 큼) => C++ 11 부터 unordered_map 컨테이너 추가, 이름이 다른 이유는 기존 코드의 새 클래스 이름에 대한 중복 때문

운영체제

프로세스(Proccess)

• 운영 체제로부터 시스템 자원을 할당받는 작업의 단위
  • 메모리에 올라와 실행되고 있는 프로그램의 인스턴스
  • 즉, 동적인 개념으로 실행된 프로그램을 의미
• 할당받는 시스템 자원의 예
  • CPU 시간
  • 운영되기 위해 필요한 주소 공간
  • Code, Data, Stack, Heap의 구조로 되어있는 독립된 메모리 영역
• 특징
  • 프로세스는 각각 독립된 메모리 영역(Code, Data, Stack, Heap의 구조)을 할당받음
  • 기본적으로 프로세스당 최소 1개의 스레드(메인 스레드)를 가지고 있음
  • 각 프로세스는 별도의 주소 공간에서 실행되며, 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근할 수 없음
  • 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스 간의 통신(IPC, inter-process communication)을 사용해야 한다 (Ex. 파이프, 파일, 소켓 등을 이용한 통신 방법 이용)

쓰레드(Thread)

• 프로세스가 할당받는 자원을 이용하는 실행의 단위
• 특징
  • 스레드는 프로세스 내에서 각각 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유한다.
  • 스레드는 한 프로세스 내에서 동작되는 여러 실행의 흐름으로, 프로세스 내의 주소 공간이나 자원들(힙 공간 등)을 같은 프로세스 내에 스레드끼리 공유하면서 실행된다.
  • 같은 프로세스 안에 있는 여러 스레드들은 같은 힙 공간을 공유한다. 반면에 프로세스는 다른 프로세스의 메모리에 직접 접근할 수 없다.
  • 각각의 스레드는 별도의 레지스터와 스택을 갖고 있지만, 힙 메모리는 서로 읽고 쓸 수 있다.
  • 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드(sibling thread)도 그 변경 결과를 즉시 볼 수 있다.
• 장점
  • 프로그램의 응답 시간이 단축
  • 시스템의 처리율이 향상
  • 시스템의 자원 소모 감소
  • 프로세스 간 통신 방법에 비해 스레드 간의 통신 방법이 훨씬 간단함
• 단점
  • 여러 개의 스레드를 이용하는 경우, 미묘한 시간차나 잘못된 변수를 공유함으로써 오류 발생 가능 따라서 스레드 간에 통신할 경우에는 충돌 문제가 발생하지 않도록 동기화 문제를 해결해야됌
  • 프로그램 디버깅이 어려움
  • 단일 프로세스 시스템에서는 효과를 기대하기 어려움

교착상태(Deadlock)의 개념과 조건

• 교착상태(Deadlock) 란

  • 첫 번째 스레드는 두 번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리고 있고, 두 번째 스레드 역시 첫 번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리는 상황을 일컷는다.
  • 모든 스레드가 락이 풀리기를 기다리고 있기 때문에, 무한 대기 상태에 빠지게 된다. 이런 스레드를 교착상태에 빠졌다고 한다.

• 교착상태의 4가지 조건

  1. 상호 배제(mutual exclusion)
     • 한 번에 한 프로세스만 공유 자원을 사용할 수 있다.(공유 자원에 대한 접근 권한이 제한된다. 자원의 양이 제한되어 있더라도 교착상태는 발생할 수 있다.)
  2. 들고 기다리기(hold and wait) = 점유대기
     • 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가, 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구할 수 있다.
  3. 선취(preemption) 불가능 = 비선점
     • 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없다.
  4. 대기 상태의 사이클(circular wait) = 순환대기
     • 두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재한다.

• 교착상태 처리

  1. 교착 상태 예방 및 회피
     • 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
  2. 교착 상태 탐지 및 회복
     • 교착 상태가 되도록 허용한 다음에 회복시키는 방법
  3. 교착 상태 무시
     • 대부분의 시스템은 교착 상태가 잘 발생하지 않으며, 교착 상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이든다.

• 교착상태 예방

  1. 상호 배제 부정
     • 여러개의 프로세스가 공유자원을 사용할 수 있 도록한다.
  2. 점유 대기 부정
     • 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
  3. 비선점 부정
     • 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
  4. 순환대기 부정
     • 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

• 교착상태 회피
  ex) 은행원 알고리즘(Banker’s Algorithm)