이 문서에서 말하는 Completeness, Soundness 는 알고리즘 혹은 입출력 시스템에 대한 것이다.
- Completeness: 모든 정답 사례를 찾아낼 수 있다.
- Soundness: 어떠한 오답 사례도 정답 사례로 잘못 판단하지 않는다.
어떠한 알고리즘이 완전하다, 건전하다라고 말하는 것을 이해하기 위해서는 true, false & positive, negative 개념을 먼저 이해하면 더 쉽게 이해할 수 있다.
- true positive = 참이라고 예측했고 실제로도 참인 경우
- false positive = 참이라고 예측했으나 실제로는 거짓인 경우
- false negative = 거짓이라고 예측했으나 실제로는 참인 경우
- true negative = 거짓이라고 예측했고 실제로도 거짓인 경우
(맞췄으면 true, 틀렸으면 false, 알고리즘이 주장한 값이 참이면 positive, 거짓이면 negative 임)
이걸 이해한 채로 예를 들어보겠다.
A, B, C, D, E, F라는 6명의 사람이 있고,A, B, C는 거짓말 쟁이,D, E, F는 정상인이라고 하자. 우리는전체 사람들 중에서 정상인을 찾을 수 있는 알고리즘을 구현해야 한다.
우리가 만든 알고리즘인 완전하려면 (Completeness), 이 알고리즘은 반드시 D, E, F 가 정상인임을 찾아낼 수 있어야 한다. 단, 이 것이 A, B, C 를 거짓말쟁이라고 지적할 수 있음을 의미하는 것은 아니다. 즉, 완전하지만 건전하지 않은 알고리즘이라면, A, B, C 중 한 명 이상을 정상인으로 잘못 판단하게 된다. (false positive)
우리가 만든 알고리즘이 건전하려면 (Soundness), 이 알고리즘은 A, B, C 를 거짓말쟁이라고 잘못 판단하지 않는다. 단, 이 것이 D, E, F 기 모두 정상인이라고 밝힐 수 있음을 의미하지는 않는다. 즉, 건전하지만 완전하지 않은 알고리즘이라면, D, E, F 중 한 명 이상을 거짓말쟁이라고 잘못 판단하게 된다. (false negative)
따라서, 알고리즘이 완전하면서도 건전하다면 (Completeness and Soundness), 어떠한 잘못된 판단을 내리지 않는다.
| Completeness | Soundness | 알고리즘의 출력 |
|---|---|---|
| O | O | D E F 정상인, A B C 거짓말쟁이 (잘못된 판단 없음) |
| O | X | A D E F 정상인, B C 거짓말쟁이 (A 에 대해서 false positive) |
| X | O | E F 정상인, A B C D 거짓말쟁이 (D 에 대해서 false negative) |
※ 기존 블로그 글 연결: https://thinkpro.tistory.com/163 (2020.07.14)