Assignments 1-2

정강민·2022년 1월 26일
0

EECS-498-007

목록 보기
1/1

Github

PyTorch에서 알고리즘을 구현할 때 가능하면 파이썬의 루프는 피하는 것이 좋다.

Nearest Neighbor

가장 간단한 이미지 분류 알고리즘으로, 모든 트레이닝 데이터를 암기한 다음 테스트 이미지와 가장 유사한 트레이닝 이미지를 찾아 분류하는 방식이다.
유사도를 계산하기 위해 각 픽셀값의 거리를 측정하는데, 이때 사용되는 거리 측정법 중 하나가 L1 거리(L1 distance)이다. 각 픽셀별로 차이를 구해 절댓값을 취한 값을 모두 더하는 방법이다.

알고리즘의 시간 복잡도

훈련 과정상수 시간(O(1))이 소요
테스트 과정은 테스트 데이터를 모든 트레이닝 데이터와 일일이 비교해야 하므로 데이터 개수 N에 비례하는 선형 시간(O(N))이 소요되어 속도가 매우 느리다. 그리고 오른쪽 그림처럼 단순히 색과 모양이 비슷한 이미지를 유사하다고 판단하기 때문에 실제 대상을 제대로 분류하지 못한다는 단점이 있다.


결정 경계(Decision Boundaries)를 매끄럽게 만드는 방법

  • 이웃의 수를 1개가 아닌 K개로 늘리고 다수결 투표로 카테고리를 결정하는 것
  • K개의 이웃을 사용하므로 이러한 알고리즘을 K-Nearest Neighbors
  • K = 3일 때를 보면 K = 1일 때보다 경계가 부드럽고 이상치의 영향이 줄었다.
  • 하지만 K가 1보다 커지면 그림의 흰색 영역처럼 모든 카테고리가 동점을 이뤄 어느 쪽으로도 분류되지 않는 부분이 발생


거리 측정법(Distance Metric)조정

  • L1 (맨해튼) 거리 대신, L2 (유클리드) 거리를 사용하면 결정 경계가 좀 더 반듯해진 것을 볼 수 있다. 둘 중 어느 것이 더 좋다고 단정지을 순 없지만, 적절한 거리 측정법을 사용하면 다양한 유형의 데이터에 K-Nearest Neighbor를 적용할 수 있다.

위의 거리 계산 구현은 훈련 및 테스트 세트에 중첩된 파이썬 루프를 사용하기 때문에 상당히 비효율적이다.

PyTorch에서 알고리즘을 구현할 때 가능하면 파이썬의 루프는 피하는 것이 좋다. 대신에 모든 루프가 PyTorch 함수 안에서 발생하도록 당신의 계산을 구현하는 것이 더 바람직하다. 파이토치 함수는 여러 스레드를 사용하여 효율적으로 반복할 수 있도록 내부적으로 최적화될 수 있기 때문에 일반적으로 파이썬에서 사용자 자신의 루프를 작성하는 것보다 훨씬 빠를 것이다. 이것은 특히 GPU를 사용하여 코드를 가속화할 때 중요합니다.

당신의 코드에서 탐색 루프를 제거하는 과정을 벡터화라고 한다. 때로는 원래 루프로 작성된 코드를 벡터화하는 것이 직설적일 수 있다. 거리 계산 기능의 속도를 향상시키기 위해 벡터화를 사용할 것이다.

거리 계산을 벡터화하기 위한 첫 번째 단계로, 훈련 데이터에 대해 단일 Python 루프만 사용하는 다음 구현을 완료하십시오.

profile
DA/DA/AE

0개의 댓글