[책 요약] 비전공자도 이해할 수 있는 AI지식_Ch8. 내비게이션

Ch8. 내비게이션 - 티맵은 어떻게 가장 빠른 길을 알까

---

<내비게이션, 당신의 스마트한 운전 비서>

 

내비게이션 사용이 일상화가 된 이유?

1. 미국이 정확한 GPS 신호를 민간에 개방
   : 1970년에 군사적 목적으로 24개의 GPS 위성을 쏘았지만, 적국의 사용을 우려하여 일부러 100m 이상 오차 나도록 만듦.
   : 2000년 클린턴 정부 때 이 오차를 없앰
2. 실시간 교통정보 + 머신러닝
   : 실시간 교통정보와 머신러닝이 연동되며 최적의 경로 안내 가능. 
   : 머신러닝 도로상황 예측 ex. 해당 구간이 막힐지, 언제 출발하면 막히지 않을지 등을 예측 가능해짐.

국내 업체가 경쟁력이 뛰어난 이유?

: 지도는 도로의 상황 변화를 계속 반영해야 함
→ 해외 업체가 국내에 진출하기 어려움. 수시로 현장을 조사하며 변경된 정보를 지도에 반영해야 함.

 

---

<오컴의 면도날 법칙>

 

매개변수가 많으면 좋은 모델일까?

• 매개변수가 많아질수록 정교한 모델을 만들 수 있음.
• 하지만 매개변수가 많다고 항상 좋지는 않은데 이유는 아래와 같음 
  • 계산이 복잡해짐
  • 학습 데이터가 훨씬 더 많이 필요
  • 과적합(Overfitting)에 빠질 수 있음 → 학습된 데이터에만 너무 맞춰져 있어 범용적으로는 오히려 정확도가 떨어짐.

 

오컴의 면도날

: 면도날로 도려내듯 단순한 모델이 최선이라는 원칙

: '경제성의 원리', '단순성의 원리'라고 불리우기도 함
: 여러 가설 중 가장 단순한 것이 대개 진실에 가까울 가능성이 높다고 가정

 

---

<예측을 좌우하는 데이터>

• 학습 데이터에 특정 케이스가 없는 경우: 특정 케이스에 대한 예측 불가
• 학습 데이터에 불균형이 있는 경우: 비중이 적은 케이스에 정확도가 떨어짐

 

---

<의사결정나무, 단순한 모델의 힘>

 

의사결정나무

: 조건에 따라 분기하는 모델
: 엔트로피를 낮추는 순으로 조건을 분기함. 즉, 복잡도와 불확실성을 빠르게 줄이는 방향으로.

 

---

<랜덤 포레스트, 대중의 지혜를 발휘하다>

랜덤 포레스트(Random Forest)

: 나무를 만들기 전에 데이터를 무작위로 추출 → 나무가 여러 개 모여 숲을 이룬다는 의미
: 똑똑한 의사결정나무 하나가 만드는 결과가 아닌, 평범한 100개의 나무가 내린 정답을 모두 종합하는 것.

---

<그레이디언트 부스팅, 정답과 거리를 줄여나가다>

 

잔차(Residual)

: 오차와 비슷한 개념이지만, 전체에 대한 오차가 아닌 샘플의 오차를 의미하는 통계학의 개념 (오차보다 작은 개념)
: 잔차를 줄이면 모델이 정교화됨.

 

그레이디언트 부스팅

: 잔차의 기울기를 줄인다는 의미
: 의사결정나무 하나에서 실수를 바로잡는 새로운 나무를 만드는 과정을 오류가 최소화할 때까지 계속 반복함.

: 랜덤 포레스트보다 훨신 뛰어나서 웬만한 오류는 모두 걸러내는 매우 높은 정확도를 보임.
: '캐글'이라는 데이터과학 경진대회에서 가장 많이 쓰이는 머신러닝 모델.

 

---

<데이크스트라 알고리즘, 최단 거리 탐색의 비밀>

 

데이크스트라 알고리즘

: 최단 경로를 찾은 알고리즘 중 가장 유명

: 현재 위치에서 목적지까지 가능한 경로를 모두 찾은 후, 최단 경로를 택하는 알고리즘

: 하지만 모든 경로를 찾는 데에 시간이 오래 걸린다는 단점이 존재.

 

---

<모든 내비게이션이 채택한 A* 알고리즘>

 

A* 알고리즘 (에이스타 알고리즘)

: 데이크스트라 알고리즘의 확장판.

: 꼭 필요한 경로만 탐색하여 탐색 횟수를 대폭 줄임

: 도착지에서 출발지로 거꾸로 이동하는 시간도 계산에 포함하여 애초에 도착지에서 먼 곳은 탐색을 하지 않음.(양방향 경로를 합산)

: 서울-부산 등 먼 거리일수록 불필요한 경로를 제외하여 빠르게 탐색 가능

: 시중의 모든 내비게이션은 A* 알고리즘을 응용하여 최적 경로를 계산하고 있음.

 

---

<내비게이션, 경로 안내 그 이상의 것>

 

브라에스 역설

: 새로 만든 도로에 차량이 몰려, 교통 정체가 오히려 도로 개통 이전보다 악화되는 현상

ex. 명절에 티맵을 쓰던 차량이 모두 국도로 몰리면서 오히려 국도에 극심한 정체가 발생.

→ 차량이 적절히 분산되도록 모든 차량에 동일한 최적 경로를 제공하는 것이 아닌, 다양한 경로를 제시할 필요가 있음.