평가

머신러닝을 이용하여 모델 구현 후 결과가 좋은 모델인지 평가 하기 위해 각 모형이 얼마나 좋은 지 말해주는 점수가 필요하다.

대표적으로는 프리시즌(Precision)과 리콜(recall)이 있다.

프리시즌(Precision) - 정밀도

• 정의 : Positive라 예측한 사례 중 TruePostive 비율

• 점수 구하는 공식 : TruePositive / ( TruePositive + FalsePsitive )

리콜(Recall) - 재현율

• 정의 : True라 예측한 사례 중 TruePositive 비율 

• 점수 구하는 공식 : TruePositive / ( TruePositive + TrueNegative )

에러

• ErrorType1 : 실제로는 False인데 Positive로 예측한 사례

• ErrorType2 : 실제로는 True인데 Negative로 예측한 사례

• 경우에 따라 ErrorType 1, 2 중 더 치명적인 Error가 다를 수 있음

예)

• ErrorType1이 더 치명 적인 경우 : 중고 자동차를 구입 할때 좋은 자동차라 예측하고 구매하였지만 좋지 않은 자동차였을 경우. (좋은 중고 자동차를 나쁘다 판단하여 안사면 손해는 없지만 나쁜 중고자동차를 좋다고 판단하여 구매하면 손해가 크다)

• ErrorType2가 더 치면 적인 경우 : 암 진단시 건강한 사람이라고 예측 하였는데 암 환자인경우

• 예시에서 볼 수 있듯이 경우에 따라 적절한 평가 지표를 사용해야 한다.

• 프리시즌과 리콜 외에도 Accuracy, Kappa 등의 지표가 있다.

1. 협업 필터링

- 도메인 지식 필요없음

- 제품 종류가 많아 추천이 잘된다.

2. 컨텐츠 기반

- 도메인 지식 필요 

- 다양한 메타데이타 (구성하기 어려울 수 있음)

3. 협업필터링 + 컨텐츠기반

4. 차원 축소

5. 평가 방식

- 정확도 (평점 예측)

- 만족도 (클릭율, 구매율)

결론 : 일반적인 이야기

알고리즘 스터디

조합탐색(combinatorial search)

11.1 도입

조합탐색

• 완전탐색을 포함해 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘
• 탐색 공간(search space) 부분답과 완성된 답의 집합
• 목표 : 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 함.

조합탐색 최적화 기법

• 가지치기(pruning) : 탐색 과정에서 최적해로 연결될 가능성이 없는 부분을 잘라낸다. 
  예) 외판원 문제를 추는데, 길이가 10인 경로를 이미 찾아냈다고 하면, 더이상 탐색하지 않고 탐색을 중단하는 것

• 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐용법을 이용해 적당히 좋은 답을 우선 찾아낸다.

11.2 조합 탐색 기법들

여행하는 외판원 문제(TSP)를 푸는 완전탐색 알고리즘에 기법들을 적용하면서 변화하는 수행 속도를 관찰해본다.

• 입력파일 
  소행, 중형, 대형, 초대형 네가지 입력. 
  각각 n=12, n=16, n=20, n=24 크기의 입력 20개씩을 가지고 있으며 각 입력은 2차원 평면세 n개의 점을 임의로 배치하고 이들 사이의 거리를 재서 만듬

목표는 이 동적 계획법 알고리즘 보다는 더 빨리 답을 얻는 것

- 입력이 커질수록 수행시간이 급격히 증가하는 것을 볼 수 있다. 
- 만약 컴퓨터의 메모리가 모자랐다면 결국 가상 메모리를 사용 해야 했을 테고, 결과적으로 상상할 수 없을 정도로 느려졌을 것이다.

조합 탐색 뼈대의 구현

코드 11.1 TSP를 해결하는 완전 탐색의 구현

const double INF = le200;
const int MAX = 30;
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시간의 거리를 저장하는 배열
// 지금까지 찾은 최적의 해
doubel best;
void search(Vector<int>& path, vector<bool>& visited, double currentLength){
    int here = path.back();
    // 기저 사례 : 전체 도시를 모두 순회했을 경우 종료
    if(path.size() == n){
        best=min(best, currentLength+dist[here][0]);
        return;
    }
    for(int next = 0; next < n; ++next){
        if(visited[next]==true) continue;
        push.push_back(next);
        visited[next]=true;
        search(path, visited, currentLnegth + dist[here][next]);
        visited[next]=false;
        path.push_back(next);
    }
}
void solve(){
    best = INF;
    vector<int> path = vector(1,0);
    Vector<bool> visited = vector(n, false);
    visited[0]=true;
    search(path, visited,0);
    return best;
}

• 이와 같은 단순한 알고리즘의 수행 속도는 어떨까? search가 만드는 경로의 수는 (n-1)!개.
• 11!는 약 4천만 정도되므로 소형 입력은 그럭저럭 풀수 있다.
• 중형 입력 경로는 12*13*14*15 ~ 30,000 배 는다. -> 풀기 불가능

최적해보다 나빠지면 그만두기

간단한 가지치기 : 지금까지 찾은 가장 좋은 답 이상일 경우 중단 
if(best <= currentLength) return;

간단한 휴리스틱을 이용한 가지치기

• 휴리스틱(heuristic) : 경험에 의거한 문제 풀이 기법. 사람이 어림짐작으로 문제를 푸는 과정을 알고리즘으로 옮긴 것이 휴리스틱이라고 생각하면 얼추 비슷하다.

• 과소평가(underestimate)하는 휴리스틱, 난관적인 휴리스틱(optimistic heuristic) 낙관적인 휴리스닉

휴리스틱 함수 작성하기

• 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작적으로 돌아가도 된다.
• 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 된다.

단순한 휴리스틱 함수 구현

코드 11.2 단순한 휴리스틱을 이용한 가지치기의 구현

가까운 도시부터 방문하기

코드 11.3 가까운 정점부터 방문하는 최적화의 구현

지나온 경로를 이용한 가지치기

코드 11.4 지나온 경로를 이용하는 두 가지 가지치기 전략의 구현

MST 휴리스틱을 이용한 가지치기의 구현

코드 11.5 MST 휴리스틱의 구현

마지막 단계 메모이제이션하기

코드 11.6 부분적으로 메모이제이션을 사용하는 최적화의 구현

// 남은 도시의 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
const int CACHED_DEPTH = 5;
// dp(here, visited)=cache[here][남은 도시의 수][visited]
map<int,double> cache[MAX][CACHED_DEPTH+1]
/// here : 현재 위치
// visited : 각 도시의 방문 여부 
// 일 때, 나머지 도시를 모두 방문하고 시작점으로 돌아가는 최단 경로의 길이를 반환한다.
double dp(int here, int visited){
    // 기저사례 : 더 방문할 도시가 없으면 시작점으로 돌아간다.
    if(visited == (1<<n)-1) return dist[here][0];

    // 메모이제이션
    int remaining = n - __builtin_popcount(visited);
    double& ret = cache[here][remaining][visited];
    if(ret > 0) return ret;
    ret = INF;

    // 다음 도시를 하나씩 시도한다.
    for(int next = 0; next < n; ++next){
        if(visited & (1<<next)) continue;
        ret = min(ret, dp(next, visited + (1<<next)) + dist[here][next]);
    }
    return ret;
}

void search(vector<int>& path, int visited, double currentLength) {
// 생략
// 기저 사례 : 남은 도시 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
    if(path.size() + CACHED_DEPTH >= n){
        best = min(best, currentLength + dp(path.back(), visited));
        return;
    }
    // 생략
}
double solve(){
    // 생략
    // cache 초기화
    for(int i = 0; i < MAX; ++i)
        for(int j = 0; j <= CACHED_DEPTH; ++j)
            cache[i][j].clear();
    // 생략
}

전문적 TSP 해결 기법들

• 여기서 소개한 알고리즘은 TSP를 해결하기 위한 방법과는 거리가 멈
• 실제로는 TSP만을 해결하기 위해 고안된 프로그램들 정수계획법, 선형계획법 등을 사용함.

출저 : 알고리즘 문제 해결 전략