190117 백준 알고리즘 문제풀기

|

Baekjoon 알고리즘 문제풀기

요즘 논문을 쓰고있다보니.. 시간이 잘 나지 않는다. ㅠㅠ

[2750], [2751] 수 정렬하기, 수 정렬하기 2

문제

  • N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램 작성

정답

a = int(input())
nums = []
for j in range(a):
    b = int(input())
    nums.append(b)
nums = sorted(nums)
for j in range(a):
    print(nums[j])

변경사항 확인하기/과거의 버전으로 돌아가기

|

변경사항 확인하기

  • 지금까지 버전 만드는 방법을 살펴봄
  • 버전을 만든것의 좋은점
    • 차이점, 과거 시점의 내용을 알 수 있음
    • 과거로 돌아 갈 수 있음
  • git log -p를 통해 각각의 커밋과 커밋 사이의 소스의 차이점을 확인 할 수 있음
    • ---+++로 이전 버전과 현재 버전을 알 수 있음
      • /dev/null은 없던 파일이 생성 되었단 것을 의미
    • -(빨간색)와 +(초록색)로 어떤 내용이 추가/삭제되었는지 알 수 있음
  • 각각의 commit은 자신의 고유의 ID가 존재함.
    • git log 쳣을 때, commit 옆에 적인 복잡한 값이 그 commit의 고유 ID임
    • git log ID 하면 해당 commit 이전의 메시지만 볼 수 있음
  • 두 commit(version)의 차이를 확인하고 싶은 경우
    • git diff ID1..ID2 적으면 ID1 commit과 ID2 commit의 차이를 보여줌
    • git log -p와 동일하게 -+로 소스의 차이점을 볼 수 있음
  • f1.txt 파일을 수정하여 내용을 변경한 후
  • git diff를 치면 현재 변경 된 상태를 확인 가능
    • line1: -f1.txt : 이전내용 line2: +f1.txt : 변경된 내용 으로 확인 가능
  • git add f1.txtgit diff를 치면 아무 내용이 보이지 않음
    • git diff는 stage area에 올라가지 않은 코드에서 변경된 사항에 대해서만 출력함

과거의 버전으로 돌아가기

  • git reset ID --hard: ID의 commit(version)으로 돌아갈 수 있음
    • 해당 ID 이후의 commit 내용을 완전히 삭제하여 git log 를 해도 기록이 남지 않음
    • 잘못 된 commit에 대해 시간을 되돌려서 없던일로 해버린다고 이해하면 됨
  • git revert ID: ID의 해당 commit(version) 내용을 취소하고, 그 내용을 새로운 버전으로 만듦
    • 해당 ID 이후의 commit 내용은 남아있고 그 commit을 취소하고 다시 이전 버전으로 돌렸다는 기록이 남음
    • 잘못 된 commit에 대해 해당 commit이 취소된 이력이 하나 더 생기게 됨
  • revert와 reset은 어떨 때 사용?
    • 이미 push 한 상태라면 reset은 사용 불가능
    • push 된 후에는 revert만 사용 가능하며, 여기서 발생하는 충돌은.. 잘 풀어나가는 수밖엔 없다고 한다..
    • push는 신중하게 해야 한다고 한다.

Mean Average Precision(mAP) on Object detection

|

Mean Average Precision(mAP) on Object detection

Object detection에서는 모델의 성능(정확도)을 주로 Mean average precision(mAP)를 통해 확인한다. mAP가 높을수록 정확하고, 작을수록 부정확하다. 그런데 보통 모델의 mAP의 측정 해당 데이터셋별(PASCAL VOC, MS COCO 등등..)로 잘 짜여진 코드가 많이 있어서 알고리즘적으로 어떻게 계산되는지 자세히는 알지 못했다.

이번 글에서는 mAP에 대해 보다 자세히 알아보기 위한 공부를 한 내용을 정리했다.

  • 기본적으로 mAP는 다른 recall 값에서의 평균 최대 precision으로 정의

Precision, recall and IoU

Precision

  • Precision은 모델의 출력이 얼마나 정확한지를 측정하는 것.
  • 즉, 모델이 예측한 결과의 Positive 결과가 얼마나 정확한지를 나타내는 값.

Recall

  • Recall은 모델의 출력이 얼마나 Positive 값들을 잘 찾는지를 측정하는 것.

Precision과 Recall의 수학적 정의

  • 예를 들어, 암 진단의 경우에 대해 Precision과 Recall은 다음과 같이 정의 됨.
    • $TP$: 실제 암 세포들의 개수
    • $total \; positive \; results$: 암세포라고 판단 된 결과
    • $total \; cancer \; cases$: 전체 암 세포들의 개수
  • Object detection의 관점에서 보자면, recall과 precision의 관계는 아래와 같이 정의 가능

IoU (Intersection over union)

  • 2개 영역 사이의 중첩되는 정도를 측정.
  • 이는 Object detector가 실제 Ground truth와 예측 결과(Prediction)가 얼마나 정확히 겹치는지를 계산하여 예측이 얼마나 잘 되는지를 측정.
views
IoU의 정의

Average precision (AP)

  • AP를 계산하는 간단한 예제를 살펴보자.
    • 데이터셋에는 총 5개의 사과가 있음
    • 모델이 사과에 대해 예측한 모든 결과를 수집하고 예측 신뢰 수준(predicted confidence level)에 따라 순위를 지정하여 나열
    • 두 번째 열은 예측 결과가 올바른지 여부를 나타냄
    • 예측이 정확하다고 판단(Correct=True)하는 기준은 Ground Truth(GT)와의 IoU가 50%가 넘는 경우($IoU\geq 0.5$)
views
  • 위의 표에서 3번 Rank의 결과에 대한 Precision 및 Recall 값을 계산 해 보자.
    • Precision은 TP의 proportion으로 $\frac{2}{3}=0.67$ 이 된다.
    • Recall은 possible positives 외의 TP의 비율이므로 $\frac{2}{5}=0.4$가 된다.
  • Recall 값은 더 많은 모델의 예측값들(predictions)을 포함시킬수록 더 좋아지지만, precision은 이로 인해 증/감하게 됨.
  • 아래에서 recall 값에 따른 precision의 변화 관계를 볼 수 있음.
views
Precision-recall graph
  • AP의 idea는 precision-recall 그래프(오랜지색 선) 아래 영역을 찾는 것으로 개념적으로 볼 수 있음.
  • 위의 그래프는 recall인 $\hat{r}$ 값이 0, 0.1, 0.2, …, 0.9, 1.0 일때의 값에 대한 plot이며, precision 값은 $recall \geq \hat{r}$ 일때의 최대 precision 값으로 대체 된 것.
  • 다음으로, Recall 값의 오른쪽에서 가장 큰 값들을 찾아 그 값끼리 이은 최대 precision 값을(초록색 선) 찾음.
views
Precision-recall graph
  • AP(average precision)는 아래의 11개의 recall 값들에 의해 최대 precision 값의 평균을 취함으로써 계산 할 수 있음.
    • Recall 값이 0에서 1까지 0.1 단위로 커지면서
  • 위 수식의 계산은 precision-recall 그래프에서 녹색 곡선 아래의 총 면적을 구하는 것과 유사하며, 그 값을 11로 나눈 값.
  • 보다 정확한 정의는 아래와 같음

  • $p_{interp}(0.7)$ 은 아래의 노란색 상자에서 최대값을 갖게 됨.
    • recall 값이 0.7일때 갖을 수 있는 precision의 최대 값일 때의 recall 값은 0.8이 됨.
    • 그래서 그래프에서 최대 precision일 때의 recall 값이 0.8임
views
  • 본 예시에서, $AP=(5\times 1.0 + 4\times 0.57+2\times 0.5)/11$ 로 계산 됨.
    • Recall이 0 ~ 0.4 일 때 최대 precision은 1.0
    • Recall이 0.5 ~ 0.8 일 때 최대 precision은 0.57
    • Recall이 0.9, 1.0 일 때 최대 precision은 0.5
views
  • mAP(mean average precision)는 모든 클래스에 대해 각각 위의 연산을 반복하고, 그 값들의 평균을 의미.
  • 다양한 데이터셋에 대해 종종 AP라고 불림.

PASCAL VOC Challenge에서의 AP(Average Precision)

  • PASCAL VOC는 object detection에서 널리 사용되는 데이터 셋
  • PACAL VOC Challenge의 경우, 모델의 예측과 ground truth의 IoU가 0.5보다 크면($IoU>0.5$) 모델의 예측이 올바르게 되었다고 판단
  • 그러나 모델이 동일한 객체에 대한 중복 탐지결과를 출력 할 경우 첫 번째 출력을 positive로, 나머지를 negative로 계산.
  • PASCAL VOC의 mAP는 위의 AP 계산 방법과 동일

MS COCO mAP

  • SOTA(State of art) object detector 모델들은 주로 MS COCO에 대한 mAP 결과만을 제공하는 경향이 있음
  • MS COCO는 PASCAL VOC의 단일 IoU값 계산과는 다르게($IoU>0.5$) 다중 IoU에 대한 평균값을 계산
    • Minimum IoU는 positive match를 위해 고려됨
  • AP@[.5:.95]는 0.05의 단계 크기로 0.5부터 0.95까지의 IoU에 대한 평균 AP에 해당함
  • MS COCO competition의 경우 AP는 80개의 카테고리에서 10개 이상의 IoU에 대한 평균값으로 경쟁.
    • AP@[.50:.05:.95]: 0.5에서 0.95까지 단계 크기 0.05씩 커지며 계산
  • 다음은 YOLO V3 object detector의 MS COCO 에 대한 mAP 실험 결과임
views
  • 위의 실험 결과에서 mAP@.75는 IoU=0.75 기준일 때 계산 된 mAP 값을 의미함.

  • [참고 글]

https://medium.com/@jonathan_hui/map-mean-average-precision-for-object-detection-45c121a31173

http://darkpgmr.tistory.com/162

쉘 스크립트(shell script) 작성, 명령어 알아보기

|

쉘 스크립트(shell script) 작성, 명령어 알아보기

딥러닝 모델을 학습시키다 보면 중간중간 파라미터를 바꿔줘야 할 때가 생긴다. 이 때 가장 요긴하게 쓸 수 것이 쉘 스크립트다. 본 글에서는 쉘 스크립트를 만들고 실행 시키고, 유용한 명령어들을 간단하게 정리한다.

쉘 스크립트 작성

  • touch filename.sh로 쉘 스크립트 파일 생성
  • 첫 줄에 #!/bin/bash를 적고, 그 밑에줄부터 내용을 쓴다.
    • 스크립트 파일을 bash 쉘로 실행시킨다는 의미.
    • 구지 #!/bin/bash을 적지 않아도 실행이 되지만, 그것은 리눅스(우분투)배포판이 기본적으로 bash 쉘로 설정되어 있기 때문.
    • #!/bin/bash를 작성하는 것이 쉘 파일임을 미리 알려주는것이므로 다른 쉘간의 오류를 방지 할 수 있음!
    • #!/bin/bash, #!/bin/sh 둘 다 혼용이 가능함(둘중 하나만 적으면 됨)
  • 작성 예시

#!/bin/bash
echo 'Hello, World!'

파일 쓰기/읽기 권한 주기

  • 기본적으로 생성 된 쉘 스크립트는 파일 쓰기 권한이 없다.
  • sudo chmod +x script_filename.sh로 읽기/쓰기 권한을 준다.

실행 시

  • 해당 스크립트가 존재하는 디렉터리에서 ./script_filename.sh로 실행 시킨다.

간단한 명령어들

주석 처리

  • 한 줄 주석 처리는 해당 줄 맨 앞에 #을 붙여서 주석 처리한다.
  • 여러 줄 주석 처리는 주석 시작 부분에 :<<'END', 주석의 끝에 END를 적어서 주석 처리한다.

변수 선언

  • 변수를 선언하여 내부 기본적인 연산이 가능하다.
    • 변수 선언시에는 공백이 없이 선언되어야 한다.
    • a = 1 (x), a=1(O)

변수 및 글자 출력

  • echo '내용'으로 출력한다.

명령어 처리

  • 명령어는 터미널에 치는 명령어를 그대로 치면 된다.
  • 단, 한 번에 하나의 명령어를 수행하게끔 맨 끝에 ;을 붙인다.
  • 예를 들어, hello.py 라는 파일을 실행 시키고 싶은 경우

#!/bin/bash
python3 hello.py;

  • 만약 여러개의 파일을 순차적으로 실행시키고 싶은 경우 대괄호({})로 명령어를 묶는다.
  • 예시

#!/bin/bash
echo '다중 파일 순차 실행'
{
python3 hello1.py;
python3 hello2.py;
python3 hello3.py;
}

  • [참고 글]

http://one2many.tistory.com/15

190114 백준 알고리즘 문제풀기

|

Baekjoon 알고리즘 문제풀기

[1193] 분수찾기

문제

  • 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같이 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 정의
  • 입력 N에 대해 N번째 분수를 구하는 프로그램 작성

  • 너무 어렵게 푼 듯 하다.
  • 우선 몇 번째 그룹에 속해있는지 구하고, 그 그룹의 첫 번째 항의 순서를 구한 후 그룹 내의 결과 찾아 출력하는 형식이다.
  • 그 그룹의 첫 번째 항을 구할 때 계차수열의 합의 공식을 사용하였다.
    • 각 그룹의 첫 번째 순서는 1, 2, 4, 7, 11, …의 순서를 보인다.
    • $a_{n+1}=a_{n}+n$ 이므로, $b_{n}=a_{n+1}-a_{n}$ 으로 정의하고 $a_{n+1}-a_{n}=n$ 이므로 $b_{n}=n$ 이 성립한다.
    • 따라서 $a_{n}=a_{1}+\sum_{k=1}^{n-1}b_{k}=1+\sum_{k=1}^{n-1}k$ 의 관계가 성립한다.
    • 합의 공식에 따라 계산을 하면,
    • $a_{n}=a_{1}+\sum_{k=1}^{n-1}b_{k}= 1+\sum_{k=1}^{n-1}k \ =1+\sum_{k=1}^{n-1}k= 1+\frac{(n-1)\times n}{2}$
    • ∴ $a_{n} = \frac{(n-1)}{2}\times n +1$

정답

def find_group(n):  # 입력된 숫자가 몇 번째 그룹에 속해있는지를 찾는다.
    cnt = 0
    if n==1:
        return 1
    else:
        for j in range(1, n+1):
            cnt += 1
            n -= j
            if n == -cnt:
                return cnt-1
            elif n<0:
                return cnt

num = int(input())
group = find_group(num)
odd = group % 2 # 홀/짝별로 숫자배열이 달라지므로 다른 연산이 필요하다.
nums = [] # 해당 그룹의 숫자들을 저장한다.
if odd==1:
    temp = group
    for j in range(1, group+1):
        string = str(temp) + '/' + str(j)
        nums.append(string)
        temp -= 1
else:
    temp = group
    for j in range(1, group+1):
        string = str(j) + '/' + str(temp)
        nums.append(string)
        temp -= 1
init_num = int((group-1) * group / 2 + 1) # 앞에서 정의된 일반항으로 해당 그룹의 첫 번째 순번이 몇 번으로 시작하는지를 찾는다.
plus = num - init_num # 완성 된 분수 그룹에 몇 번째 숫자인지를 정의한다.
print(nums[plus])