0. Abstract

• Object Detection을 Bounding Box와 연관 Class 확률에 대한 Regression 문제로 제안
• 하나의 Neural Network가 전체 이미지에서 한 번의 Evaluation으로 바로 Bounding Boxes와 Class Probabilities를 Predict함
• 모든 Detection 과정이 하나의 Neural Network만으로 이루어지기 때문에 end-to-end optimize가 가능함
• Base YOLO Model은 실시간으로 1초에 45 frame을 처리할 수 있음
• 더 작은 버전인 Fast YOLO는 1초에 155 frame을 처리할 수 있음
  • 그럼에도 다른 실시간 Detection Model의 2배의 mAP를 달성
• SOTA Detection Model과 비교했을 때 Localization Error는 더 크지만 Background에 대한 False Positive는 감소함
• YOLO는 Object의 여러 Representation을 학습할 수 있음
• 자연 이미지에서 예술 작품 같은 다른 도메인으로 Generalization할 때, DPM, R-CNN을 포함한 다른 Detection Model을 Outperform함

1. Introduction

• 인간은 잠깐 보는 것만으로도 이미지의 객체가 무엇인지, 어디있는지, 어떻게 상호작용하는지 알 수 있음
• 인간의 시각 시스템은 빠르고 정확함
  • 의식적 노력 없이 운전과 같은 복잡한 작업을 수행하게 해줌
• 빠르고 정확한 객체 탐지 알고리즘은 컴퓨터로 하여금
  • 전용 센서 없이 차량 운전
  • 사용자에게 실시간 정보 전달
  • 다목적, 반응형 로봇 시스템의 가능성 개방
  • 그 외 다양한 등의 작업을 가능하게 함
• 현재의 객체 탐지 시스템은 Classifier를 Detection을 위해 사용함
• 객체를 탐지하기 위해, 객체에 대해 Classifier를 사용하고, 여러 위치와 크기의 객체를 평가함
• DPM과 같은 시스템은 슬라이딩 윈도우 방식으로 이미지 전체 공간을 Classifier로 탐색함
• R-CNN과 같은 보다 최신의 방식들은 Region Proposal 방식을 사용해
  • 우선 잠재적인 Bounding Box를 생성하고 해당 Box들에 Classifier를 실행함
  • 분류 후, Bounding Box들을 후처리하고 중복 탐지 결과를 제거함
  • 그리고 이미지 내의 다른 객체들을 기반으로 Box들의 점수를 매김
• 이러한 복잡한 파이프라인은 느리고 최적화하기 어려움
  • 각각의 구성 요소가 따로 훈련되어야 하기 때문
• 우리는 객체 탐지를 하나의 회귀 문제로 재구성함
  • 이미지 픽셀에서 직접 Bounding Box 좌표와 Class 확률을 동시에 얻어내는
• 우리의 시스템을 이용하면 이미지에 무슨 객체가 어디에 있는지 알기 위해 한 번 만 봐도 됨(YOLO)

YOLO의 장점

• YOLO는 굉장히 간단함
  • 하나의 Convolution 신경망이 여러개의 Bounding Box와 Class 확률을 동시에 예측함
  • 전체 이미지에서 학습하고 직접 탐지 성능을 최적화함
  • 이 통합 모델은 전통적 객체 탐지 모델과 비교해 더 많은 장점을 가지고 있음

1. YOLO는 매우 빠름
   • 탐지 문제를 회귀 문제로 구성하여 복잡한 파이프라인 필요 없음
   • 테스트 시 새 이미지에 대해 우리의 신경망을 실행했음
   • 우리의 기본 모델은 45 frame/sec의 속도를 기록함, Titan X GPU 위에서 Batch processing 없이
     • 빠른 버전의 모델은 150 frame per sec
   • 실시간 스트리밍 비디오를 25 ms 이하의 지연 시간으로 처리 가능
   • 다른 실시간 시스템보다 두 배 높은 mean average precision을 기록
2. YOLO는 이미지 전체를 처리함
   • Sliding Window나 Region Proposal과 다르게, 이미지 전체를 고려함
     • 암묵적으로 class들이 보이는 그대로의 맥락 정보를 사용함
     • Fast R-CNN, 우수한 탐지 모델은, 전체 맥락을 보지 않기 때문에 배경 Patch에 대해 실수함
   • YOLO 모델은 Fast R-CNN에 비해 절반 수준의 배경에 대한 에러를 기록함
3. YOLO는 객체의 일반화된 representation을 학습함
   • 자연 이미지를 학습하고 미술 작품에서 평가할 때,
     • YOLO는 DPM이나 R-CNN 등의 다른 우수한 탐지 방식을 outperform함
   • YOLO는 매우 일반화를 잘하기 때문에 새로운 도메인이나 입력에 대해 성능이 급격히 낮아질 확률이 적음

• 그러나 YOLO는 여전히 최신의 객체 탐지 모델에 비해 정확도 면에서 뒤처짐
• 빠르게 객체를 인식할 수 있지만, 특히 작은 객체의 위치를 정확하게 파악하는데 어려움이 있음
• 이러한 Trade-off는 Experiment에서 다뤄보겠음

24.08.27 Abstract

24.09.04 Introduction

논문 읽어보기도 시작하기로 했습니다

제 굉장한 단점인 

제대로 시작하고 싶어하는 점

을 회피하면서도 진도를 잘 나가고자 하여 

우선 Abstract들만 먼저 읽고 리뷰를 해보고자 합니다.

첫 논문은 ImageNet Classification with Deep Convolutional Neural Networks 입니다

0. Abstract

- 1.2 million images를 분류하기 위해 대규모 deep convolution neural net을 학습시킴
- 1000개의 class로 이루어진 ImageNet LSVRC-2010 contest의 image dataset
- 해당 test data에서 SOTA보다 좋은 성능인 37.5% & 17.0%(top1 & top5 error rates)를 기록
- Neural network의 구조는 다음과 같음
    - 60 million개의 parameters
    - 650,000개의 neurons
    - 5개의 convolutional layers
    - max-pooling layers
    - 3개의 fully-connected layers
    - 최종 분류를 위한 1000-way softmax
- 학습을 더 빠르게 하기 위해
    - Non-saturating neurons을 사용하고
    - GPU에 효율적인 convolution operation을 구현하였음
- Fully-connected layers에서의 overfitting을 줄이기 위해
    - “dropout” regularization method를 사용했음
    - 굉장히 효과적이라고 증명되어있음
- 이 Model의 변형한 버전을 ILSVRC-2012 competition에 출전 시킴
    - 15.3% Top-5 error rate을 달성하여 우승(2위는 26.2%)

Linear Classification

지난 시간

• 이미지를 여러 카테고리 중 하나로 라벨링
• 가까이 있는 것들의 라벨을 활용하는 kNN Classifier
• 몇 가지 단점
  • 모든 학습 데이터를 기억, 저장 → 메모리 공간 비효율적
  • 테스트 이미지 분류 시 모든 학습 이미지와 비교 → 계산량과 시간 많이 소요

Overview

• Score Function: 데이터를 클래스 스코어로 매핑
• Loss Function: 예측한 스코어와 실제 라벨과의 차이를 정량화

Parameterized mapping from image to label scores

• D 차원의 벡터인 학습 데이터 N개
• K개의 서로 다른 클래스(카테고리)

Linear Classifier

$$ f(xi,W,b)=Wxi+b $$

• x는 모든 픽셀이 [D x 1] 모양을 갖는 하나의 열 벡터
• W는 [K x D] 차원의 행렬
• b는 [K x 1] 차원의 벡터
• D개의 데이터가 함수로 들어와 K개의 숫자가 출력
• Wx 행렬곱 한 번으로 10개의 서로 다른 분류기를 병렬로 계산하는 효과
• 파라미터 W,b는 우리가 조절 가능
• 올바르게 맞춘 클래스가 틀린 클래스보다 더 높은 스코어를 갖도록 조절
• 학습이 끝나면 학습데이터는 필요없이 Parameter만 남음
• 테스트 분류 시 행렬곱 한 번과 덧셈 한 번만 필요

Interpreting a linear classifier

• 가중치에 따라 스코어 함수는 이미지의 특정 위치에서 특정 색깔을 선호하거나 선호하지 않거나를 구분

Analogy of images as high-dimensional points

• 이미지를 고차원 열벡터로 펼쳤기 때문에 각 이미지를 고차원 공간 상의 하나의 점으로 비유 가능
• [D x 1] 모양의 벡터로 펼쳤다면 D개의 차원 공간 상의 한 점
• 즉시 이해가 되지 않아서 쉬운 비유를 해봄
  • 열벡터 [2,3]는 x, y축 (2,3)에 대응 가능
  • 열벡터 [1,4,-2]는 x, y, z축 (1,4,-2)에 대응 가능
  • 열벡터 [3,0, … , 4]는 x1, x2, … ,xD축 (3,0, … ,4)에 대응 가능
  • 이해 됐음
• 각 이미지를 2차원 공간에 표현한다면
  • 스코어 값이 0이 되는 선이 있고, 선의 바깥 / 안쪽이 스코어가 양 / 음의 방향으로 선형 증가하는 구역
  • W의 각 행이 각각 클래스를 구별하는 분류기
  • W의 하나의 행을 바꾸면 해당하는 선이 다른 방향으로 회전
  • bias b는 해당 선이 평행이동
  • bias가 없다면 xi = 0이 들어왔을 때 파라미터에 상관없이 스코어가 0
  • 모든 분류들이 원점을 지나게 됨

Interpretation of linear classifiers as template matching

• parameter W의 각 행은 클래스별 템플릿에 해당
• 이미지의 각 클래스 스코어는 각 템플릿과 이미지의 내적을 통해 비교
• 해당 비교, 계산한 스코어를 기준으로 라벨링
• Linear classifier가 템플릿 매칭을 하고있고 학습을 통해 템플릿이 배워짐
• Nearest Neighbor와 비슷한 것을 하고 있으나 각 클래스마다 이미지 한 장을 사용하는 개념
• Lecture Node의 예시에서 horse 템플릿은 머리가 두 개인 말로 보임
  • 왼쪽, 오른쪽을 보는 말의 이미지들이 섞여있음
  • car 분류기는 붉은 색을 띄는데, 학습 데이터에 빨간색 자동차가 더 많기 때문으로 보임

Bias trick

• 두 가지 parameter bias와 Weight을 매번 동시에 표현하기 번거로움

• W의 맨 왼쪽 열에 bias 열을 추가하고, 입력데이터 x의 맨 아래 행에 상수 1로 이루어진 행을 추가

Image data preprocessing

• 입력 데이터를 정규화
• 이미지 전체에 대한 평균 값을 구한 다음 각 이미지에서 이를 빼 이미지의 픽셀이 대략 [-127 ~ 127]의 범위를 가지도록 함
• 입력 데이터(특성)을 스케일링하여 [-1 ~ 1]의 범위를 갖도록 함

Loss Function

• 각 이미지를 틀린 클래스로 분류한 결과에 대한 불만족을 Loss Function으로 측정
• 훈련 데이터의 분류 작업을 잘 수행하지 못하면 높은 Loss를, 잘 수행하면 낮은 Loss를 나타냄
• 이 Loss를 줄이기 위해 가중치를 조절

Multiclass Support Vector Machine Loss Function

• 올바른 클래스 분류의 score가 틀린 클래스 분류의 score보다 margin “Delta” 이상 큰 값을 가지도록 원함

$$ L_i = \sum_{j \neq y_i} \max(0, s_j - s_{y_i} + \Delta) $$

• 올바른 분류의 score가 Delta 만큼 큰 값을 가져야 loss가 0
• 해당 식을 가중치 행렬의 행을 이용한 식으로 변환

$$ L_i = \sum_{j \neq y_i} \max(0, \mathbf{w}_j^T \mathbf{x}i - \mathbf{w}{y_i}^T \mathbf{x}_i + \Delta) $$

Regularization

• 만약 W 행렬이 모든 예시를 정확히 분류한다면 loss는 0
• 이러한 W는 여러개 존재 가능하며, W에 1 이상의 실수를 곱한 가중치 행렬은 모두 loss가 0임
• 가중치가 커지면 학습 데이터에 대한 과적합 우려
• 가중치 행렬에 대한 패널티를 적용하여 가중치가 과도하게 커지는 것을 방지

$$ R(W) = \sum_{k} \sum_{l} W_{k,l}^2 $$

• 가중치 행렬 W의 각 가중치 값들을 제곱한 뒤 더함
• 이를 regularization loss라 하며, 이를 반영한 최종 loss는 아래와 같음

$$ L = \frac{1}{N} \sum_{i} \sum_{j \neq y_i} \left[ \max \left(0, f(\mathbf{x}i; \mathbf{W})j - f(\mathbf{x}i; \mathbf{W}){y_i} + \Delta \right) \right] + \lambda \sum{k} \sum{l} W_{k,l}^2

$$

• 모든 데이터에 대해서 각 이미지의 loss들의 평균과 가중치 행렬의 패널티를 합한, 해당 데이터셋의 최종 multiclass support vector machine loss
• Lambda는 가중치 행렬의 크기를 조절하는 hyperparameter

Practical Considerations

• data loss의 Delta와 regularization loss의 Lambda는 서로 tradeoff
• lambda가 커져 가중치가 커지면 class score간의 차이가 커져 delta값을 넘기기 쉬워짐
• 그렇기 때문에 결국 유일한 조절 변수는 regularization strength인 lambda

Softmax Classifier

• Softmax classifier는 각 class score가 해석 어려운(SVM)값이 아닌 확률로 표현

Summary

• 이미지 픽셀에서 class score를 구하는 score function을 정의
  • 이는 가중치 W와 bias b에 의존함
• kNN Classifier와 다르게 학습 데이터는 학습 이후 폐기 가능하며, parameter만 학습하여 새 테스트 이미지에 대해서는 한 번의 행렬곱 연산만 필요함 → Parametric Approach
• bias trick: bias vector를 W 행렬에, x input 데이터에 1 상수 행을 추가하여 bias 열벡터 덧셈 연산을 skip, 편리성 증가
• SVM과 Softmax 두 classifer의 loss function을 define하고 올바른 분류임을 잘 나타내는지를 확인

https://cs231n.github.io/classification/

https://aikorea.org/cs231n/classification/

Image Classification

• Computer Vision에서 해결해야할 문제
  • Viewpoint variation
  • Scale variation
  • Occlusion
  • Deformation
  • Illumination condition
  • Background clutter
  • Intra-class variation
• 완전한 Imane classification pipeline
  • Input + Learning + Evaluation

Nearest Neighbor Classifier

• L1 Distance

• L2 Distance

• L2거리는 L1거리에 비해 두 벡터간의 차이가 커지는 것에 민감

→ 하나의 큰 차이 보다 여러 개의 적당한 차이를 선호

k-Nearest Neighbor Classifier

• 학습 데이터에서 가장 가까운 k개의 이미지를 찾아 테스트 이미지의 라벨에 투표
• k=1인 경우 원래의 Nearest Neighbor Classifier
• k가 커질수록 Outlier에 강인하고 분류 경계가 부드러워짐

Hyperparameter Tuning을 위한 Validation Set

• Hyperparameter를 조정하기 위해 Test Set을 사용하면 절대 안됨
• Overfit: Test Set에서는 잘 동작하도록 Hyperparameter가 Tuning 되어있지만 실전에서 Model을 Deploy할 때 성능이 낮아짐
• Test Set을 마지막에 사용해야 분류기의 Generalization된 성능을 잘 평가할 수 있는 척도로 활용
• Validation Set: Training Set을 두 개로 쪼갬, 가짜 Test Set
• Cross-validation: Validation set을 여러개 만들고 iteration하며 성능 평가
• Training Set의 50 ~ 90%를 학습용, 나머지는 검증용
• Validation Set의 크기는 Hyperparameter의 개수에 영향 받음

Nearest Neighbor Classifier의 장단점

• 장점
  1. 이해 및 구현 쉬움
  2. 학습 시 Training Set을 저장만 하면 되기 때문에 학습 시간 소요 없음
• 단점
  1. 테스트 시 모든 학습 데이터 예시들과 비교해야함

→ 우리는 보통 테스트 시 얼마나 효율적인가에 관심 있음

Summary

• Image Classification. 각 이미지 별로 한 개의 카테고리로 라벨링 되어있는 이미지들이 주어지고, 새로운 테스트 이미지들이 들어왔을 때 이 카테고리 중 하나로 분류하도록 하고 예측 값들의 정확도를 측정
• Nearest Neighbor Classifier. 여러 Hyperparameter들, k 값, 데이터 비교시 사용하는 거리 종류 L1/L2 등
• Hyperparameter를 정하기 위해 Training Set을 Training Set과 Validation Set으로 나누어 Validation Set에서 여러가지 Hyperparameter를 시험
• Training Set이 적은 경우 Cross-Validation 방식 사용
• 가장 좋은 Hyperparameter를 찾은 뒤 그것으로 실제 Test Set에 단 한 번 평가
• NN Classifier는 구현이 간단하지만 Training Set 전체를 저장해야하고 새로운 테스트 이미지 분류 및 평가 시 계산량 매우 많음

Summary: Applying kNN

• 평균 0, 표준편차 1이 되도록 데이터 전처리, 정규화
• 데이터가 고차원 데이터라면 PCA, Random Projection과 같은 차원 축소 기법 고려
• Training Set을 Train/Validation으로 분리
• 여러가지 k값에 대해, 다른 종류의 거리 함수에 대해 학습 및 평가

가장 좋은 결과를 주는 Hyperparameter들을 기록

인공지능시스템 수업 녹화강의를 보다가 궁금한 점이 생겨 알아본 내용이다

교수님께서 DFS 알고리즘의 시간 복잡도가 O(b^d)라고 말씀하셨는데

기존에 알고있던, 그리고 저번 학기 "자료구조 및 알고리즘" 수업에서 같은 교수님께서 말씀하신 O(V+E)가 아니길래

궁금해져서 찾아봤다

정말 단순히 '어라 원래 저렇게 생겼나?' 싶어서였다. 깊은 고민을 하진 않았다

- b: number of child node

- d: maximum depth

- V: number of node

- E: number of edge

stackoverflow에서 만족할만한 답변을 얻었는데, 요약하자면 다음과 같다

트리의 총 노드 수의 최대값은 1 + b + b^2 + ... + b^(d-1)로, 각 항은 각 레벨에서의 노드 수가 된다

이 식은 등비수열로 그 합은 (b^d -1) / (b-1) 공식으로 계산된다

이 식을 단순화 하면 b^d가 되고

최악의 시간복잡도는 O(b^d)가 된다

이러한 방법 대신 트리의 총 노드 수를 알고 있다면 시간복잡도를 직접 O(n)으로 표현할 수 있다

더 정확한 복잡도 계산을 위해 엣지 수를 고려할 수도 있지만 복잡도 분석에서는 일반적으로 노드의 수에 초점을 맞추는 것으로도 충분하다

결국 DFS 알고리즘의 시간복잡도 계산에 있어서 가장 중요한 것은 노드의 수이며,

O(b^d) 역시 주어진 조건 아래에서 트리의 총 노드 수를 계산하기 위한 방식이 적용된 시간복잡도임을 알 수 있었다

재밌다 그래도 조금만 더 생각해볼걸!

아래 링크를 참고 부탁드립니다

https://stackoverflow.com/questions/36479640/time-space-complexity-of-depth-first-search