위와같은 맵에서 0,0 에서 시작하여 오른쪽 맨 밑의 출구로 나가는 미로를 탈출하는데 최소한으로 움직여야하는 거리를 측정하기
한칸 움직일때마다 +1 이며, 0은 막힌공간임을 의미한다.
# 미로탈출
from collections import deque
maps=[
[1,0,1,0,1,0],
[1,1,1,1,1,1],
[0,0,0,0,0,1],
[1,1,1,1,1,1],
[1,1,1,1,1,1]
]
n,m = len(maps),len(maps[0])
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(x,y):
que = deque()
que.append((x,y))
while que:
x,y = que.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx==n-1 and ny==m-1 :
print('skip')
return maps[x][y]+1
if nx < 0 or ny < 0 or nx >= n or ny >= m : continue
if maps[nx][ny]==0:
continue
if maps[nx][ny]==1:
maps[nx][ny] = maps[x][y]+1
que.append((nx,ny))
return maps[n-1][m-1]
print(bfs(0,0))
maps
N * M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시.
구멍이 뚫려있는 부분끼리 상,하,좌,우 로 붙어있는 경우 서로 연결되어있는것으로 간주
얼음틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성하기
ex )
위와 같은 얼음틀에서는 아이스크림 3개가 생성된다고 보면 된다.
풀이 :
DFS를 이용하면서, 방문하는 순간 1로 바꾸는 것으로 한다.
# 음료수 얼려먹기
# N X M 크기의 얼음틀, 구명이 뚫려있는부분은 0, 칸막이가 존재하는 부분은 1로 표시
# 한번에 만들 수 있는 아이스크림의 개수를 출력
ices=[
[0,0,1,1,0],
[0,0,0,1,1],
[1,1,1,1,1],
[0,0,0,0,0]
]
n=len(ices)
m=len(ices[0])
def dfs(x,y):
if x<=-1 or x>=n or y<=-1 or y>= m:
return False
if ices[x][y]==0:
ices[x][y]=1
dfs(x-1,y)
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)
return True
return False
ans=0
for i in range(n):
for j in range(m):
if dfs(i,j)==True: ans+=1
ans
틀릴 수 있는 정보를 갖고 구한 엔트로피. 즉 불확실성 정도의 양이라고 할 수 있는데, 이 틀릴 수 있는 정보는 바로 머신러닝모델의 아웃풋이 있다. 모델의 아웃풋은 예측값이기에 틀릴 수 있다.
Cross Entropy is optimal entropy When ifro is from estimated probability
간단한 딥러닝 분류문제이다. 최종단에 softmax레이어가있고, 이것을 활용해 예측값을 구할 수 있다. 이것을 정답과 비교할 땐 정답값을 원-핫 인코딩으로 비교하는 형태이다. 이 과정에서 softmax값과 one-hot인코딩된 실제 값을 사용한다.
소프트맥스 값을 Q라고 하고, 실제 라벨을 P라고 했을 때 Q : Estimated Probability , P : True Probability
H(P,Q)가 크로스 엔트로피 공식이고, H(X)가 엔트로피 공식이다. 각각 클래스마다 어떤 확률로 존재하는지를 나타낸다 -> 여기서 $p_i$는 (어떠한 정보의) 확률이다.
$ log_2{1\over{q_i}}$ 는 정보의 양을 나타낸다
왜 크로스엔트로피에서 정보의 양에 $log_2$ $1\over{q_i}$ 을 사용하는걸까?
첫번쨰로 우리는 딥러닝 모델을 학습시킬때 이 예측값이 정답과 얼마나 근사한지 알고싶다. 그를 위해 실제 확률값을 사용해야한다. 단 정보의 양은 모델을 통해 온 정보의 양(예측값의 확률)을 사용해야해서 위의 log 안에 q 가 들어간것이다. 실제 정답의 확률을 사용함으로써 이 엔트로피값이 과연 실제 정답값과 얼마나 근사한지를 알 수 있게되는것이다.
틀릴 수 있는 정보를 갖고 구한 엔트로피값이다 라고 한마디로 정리할 수 있다.
KL Divergence
단순히 어떠한 모델을 설명할때, 차이가 크다-작다 보다 정확한 수치로 얼마만큼 차이난다! 라고 나타냄으로써 어떤 모델이 더 정답과 비슷하게 유추하는지 나타낼 수 있도록 하기위하여 KL Divergence를 사용한다. 이는 수치값으로 분포도를 나타낸다.
P : 정답, Qa : 모델a, Qb : 모델b
$Q_A$가 실제 정답과 상당히 비슷한 분포를 갖고있다고 할 수 있다.
KL Divergence는 실제 정답값의 분포도에서 상대적으로 얼마만큼 다른지에 대해 수치적으로 나타내는 값이다.
상대엔트로피값과 같다.
1. 항상 0과 같거나, 0보다 크다. 2. 비대칭적이다.
그렇다면 왜? 크로스엔트로피를 cost func으로 쓰고, minimize함으로써 최적화를 하는데, 왜 KL Divergence를 쓰지 않는가?
실제로, 크로스엔트로피를 쓰거나, KL Divergence를 쓰거나 같은 현상을 일으킨다.
결국 KL-Divergence 를 사용해도, Entropy(P)가 상수이므로 뒷부분이 무시되고, 크로스엔트로피를 쓰는것과 같은 효과를 발휘하는것.
