Multiclass learning with N-division output coding : a case study on face recognition = 출력코딩을 이용한 다중 클래스 학습 : 얼굴인식 사례 연구
저자
발행사항
서울 : Graduate School, Yonsei University, 2004
학위논문사항
학위논문(박사) - - Graduate School, Yonsei University : Dept. of Computer Science 2004.2
발행연도
2004
작성언어
영어
주제어
발행국(도시)
서울
형태사항
xv, 155장 : 삽도 ; 26 cm.
일반주기명
지도교수: Hyeran Byun.
소장기관
얼굴 인식은 순차적 증가 학습을 요구하는 응용 중의 하나이다. 왜냐하면, 인식 대상의 수가 미리 정해져 있지 않고 수시로 변할 수 있기 때문이다. 이러한 이유로, 복잡한 학습과정을 요구하지 않는 학습방법이 주로 사용되어져 왔다. 그러나, 기존의 학습 방법은 복잡한 얼굴영상을 표현하기 위한 능력에 한계가 있다. Support Vector Machines (SVM) 은 구조적 위험 최소화로 설명되는 통계적 학습 이론에 기반 한 복잡하고 정교한 분류기이다. 이에 따라, SVM은 높은 일반화 능력으로, 다양한 패턴인식 문제에서 좋은 결과를 보여 주고 있다. 그러나, SVM은 기본적으로 이진 분류 문제에 한정되어 있다.
출력 코딩 방법은 이러한 상황에서 성공적인 대안이 될 수 있다. 본 방법은 SVM을 다중 클래스 문제에 적용하기 위한 일반적 방법으로, 또한 증가 학습을 요구하는 얼굴인식과 같은 응용을 위한 학습 방법으로 사용될 수 있다. 출력 코딩 방법은 다중 클래스 문제를 풀기 위한 범용 형태로 다음과 같이 설명될 수 있다. 복잡한 다중 클래스 문제는 보다 쉬운 이진 문제들로 분할된다. 분할된 이진 문제에 대한 각 이진 분류기의 출력을 종합 하여 최종 클래스를 결정한다. 출력 코딩 방법에는 OPC, All-Pairs, ECOC가 대표적이다. ECOC는 이진 분류기에 다양한 클래스를 중복 학습하여, 일부 기반 이진 분류 결과의 오류에도 무관한 분류를 가능하게 한다.
ECOC에 근본을 둔 많은 연구들이 수행되어져 왔다. 그러나, 최근 일반화된 ECOC의 정립과, 일반화 성능이 높고 비선형 결정 경계 생성이 가능 한 SVM의 출현 이후, 상황은 변해 가고 있다. 전통적인 ECOC 이론은 중복 학습에 주로 기반을 두고 있는데, 이것은 이진 코드 표현에 의해 정의된다. 그러나, 일반화된 ECOC는 이진 코드를 고집하지 않을 뿐더러, 기반 분류기로써 SVM을 사용할 수 있게 되었다. SVM은 신되도 값으로써 이진 출력이 아닌 실수 출력을 갖는데, 이것은 클래스 구분 정보로 매우 유용하다. 따라서, ECOC를 재조명하여 새로운 내부 특성을 밝힐 필요가 있다.
본 논문에서는, ECOC 관점에서 새로운 OPC 기반 코딩 방법을 제안하고, 출력 코딩 방법의 문제 복잡도를 측정하기 위한 새로운 측정치를 정의한다. 기존의 대표적인 방법인 OPC, All-Pairs와 제안한 방법에 대한 비교.분석 실험을 통해, 성능이 ECOC의 근간 관점인 중복 학습 보다 문제 복잡도에 더 의존적임을 밝힌다. 또한, 새로운 출력 코딩 설계 시 고려해야 할 사항을 제시한다.
본 논문에서는, 새로운 출력 코딩 방법으로, N-Division 방법을 제안한다. 제안 방법은, 널리 사용되면서 서로 상반적인 특성을 가지고 있는, OPC와 All-Pairs의 일반화 형태를 갖는다. 제안 방법은 주어진 문제를 N 등분 하는 방법으로, N 은 문제 복잡도와 무의미 출력 문제를 조절하는데 사용될 수 있다. N 을 조절함으로써, OPC나 All-Pairs보다 향상된 특성을 보유하면서 동시에 성능 향상을 달성할 수 있다. 제안 방법의 통찰력을 제공하기 위해, 무의미 출력과 관련하여 새롭게 정의한 머신 관련성과, 문제 복잡도와 관련하여 사용한 분할 마진에 대하여, 기존 방법들과의 비교·분석 실험을 수행한다. 분석을 통해, 문제 복잡도와 무의미 출력 문제 간의 적당한 균형을 이루기 위해서, 분할 수 N 이 2 또는 3이 바람직 함을 제시한다.
기존의 대부분 출력 코딩 설계에서는, 선 분할 방식을 따른다. 선 분할 방식이란, 주어진 데이터의 특성을 고려하지 않고, 분할 방식을 결정하는 것이다. 따라서, 분할 방식의 특성 이해는 이들에 의해 학습된 이진 학습기들의 출력 이후에나 가능하다. 최근에, 후 분할 방식에 대한 접근이 시도되고 있다. 이러한 접근법은 성능 향상 뿐 아니라, 잠재적인 좋은 특성을 얻을 수 있었다고 보고되고 있다.
본 논문에서는, N-Division 방법의 틀 안에서, 후 분할 방식을 제안한다. 주어진 문제를 N 등분 하는 단계에서, 군집 기법을 이용한 데이터 기반 접근법을 제안하고, 주어진 클래스를 순차적으로 등분 하는 기본 접근법과의 특성 비교·분석을 수행한다. 이를 통해, 데이터 기반 방식이 일반화 성능과 관련된 문제 복잡도 측면 및 성능 향상을 위한 다중 클래스 시스템의 주요 관건인 에러 상관도 측면에서 모두, 기본 접근법 보다 매우 우수하다는 것을 밝힌다.
본 논문에서는, 제안 데이터 기반 N-Division 을 얼굴 인식에 적용하기 위하여, PCA 특성에 기반을 둔 군집 알고리즘을 제안하여, 차원 저주 문제를 야기하는 얼굴 영상의 고차원 문제를 해결한다. 얼굴 인식 실험을 통해, 제안 데이터 기반 방법이 기본 방법 보다 우수한 성능을 보인다. 또한, 제안 방법을 얼굴 인식에 적용하는 경우, 학습 시간 복잡도 측면에서 이득을 얻을 수 있음을 보인다. 실험을 통해, 얼굴 인식과 같이 클래스의 수가 많고 학습 데이터가 적은 경우, 하나의 이진 학습기가 모든 클래스를 학습하는 OPC 계열의 출력 코딩 방식이 적합함을 보인다. 이론적인 분석 결과, OPC 방법의 학습 시간 복잡도는 클래스의 수가 늘어날수록 기하 급수적으로 증가한다. 그러나, 제안 N-Division 방법은 OPC와 대등한, 또는 보다 우수한 성능을 보이면서도 학습 시간 복잡도가 기하 급수적으로 증가하지 않는다.
결론적으로, 본 논문에서는 데이터에 기반 한 새로운 출력 코딩 방법을 제안하였고, 제안 방법이 SVM을 다중 클래스 분류기 확장 및 증가 학습 방법을 요구하는 얼굴 인식과 같은 응용에 효과적으로 적용할 수 있음을 확인하였다.
Face recognition is a required application for incremental learning because it does not fix the number of classes in advance. However, it can be changed on demand, so a lazy learning method that does not need training phase is used in the matching stage. Unfortunately, a simple lazy learning algorithm has limited representation capacity for handling complex facial images. Support Vector Machines (SVM) is a complex elaborate classifier based on structural risk minimization rooted in the statistical learning theory. Accordingly, the support vector machine can provide a good generalization performance to pattern recognition problems. However, the support vector machine basically deals with a two-class classification problem.
The output coding method can act as a successful alternative to these cases. It can be used for both extending SVM to multiple classifiers and for applications that need incremental learning, such as face recognition. This is a general framework for solving a multiclass problem and can be described as follows: a complex multiclass problem is decomposed into a set of binary problems which then reconstructs outputs of binary classifiers for each binary problem. The following classifiers are used in base output coding methods: One Per Class (OPC), All-Pairs and Error Correcting Output Code (ECOC) in output coding methods. The ECOC method consists of several dichotomizers with class redundancy to obtain robustness when some dichotomizers fail.
A large amount of research on output coding methods are based on the ECOC. However, this has been changed after the advent of a generalized ECOC that differs from the conventional ECOC, and the advent of a binary support vector machine that can produce a complex nonlinear decision boundary with a good generalization performance. The theory of conventional ECOC is mainly based on the overlapped learning of classes. This can be guaranteed by binary codes that both specify the binary machines in which classes are involved for training itself and provide a similarity measure for the decision. However, the generalized ECOC does not insist on the binary codes, and SVM can produce real valued confidence output that can be useful for discriminating information. Therefore, it is necessary to analyze ECOC again and then provide some insights into them.
This dissertation compares and empirically analyzes certain properties of the representative output coding methods, such as OPC, All-Pairs, and our proposed OPC-based methods with respect to ECOC concepts, and we observed that the performance depends more on problem complexity than on overlapped learning. Afterwards, we make some proposals concerning the design of new output coding methods.
This dissertation proposes N-Division decomposition with a specifically tailored decoding. The proposed N-Division is a generalized form of OPC and All-Pairs where N is the tradeoff between problem complexity and the risks of nonsense outputs. By controlling N, we can achieve a more promising performance than OPC or All-Pairs with relatively small machine complexity. To provide insights into our proposed method, this dissertation compares problem complexity among different output codings and defines machine relevance related to the nonsense output problem. From the analytical results of the problem complexity and machine relevance, we deduce that choosing 2 or 3 for N is desirable to obtain a reasonable balance between the nonsense outputs and the risk of the problem complexity.
Most prior research focused on performing a prior decomposition. With their approach, the decomposition can be fixed without considering the properties of a given dataset. The impact of output codes on the inferred decision rules can be experienced only after learning. Recently, a slight advance in this research has appeared in some literature, which reported that these methods had greater potential gains as well as improved accuracy.
This dissertation proposes a data-driven approach (clustering based division) in the framework of the N-Division. This approach divides classes into subgroups after considering the property of a given dataset. For insight into the data-driven approach, this dissertation demonstrates that the data-driven approach has good properties such as a low level of problem complexity and a low level of error correlation. Here, problem complexity is related to generalization performance, and error correlation is a major issue of multiple classifier systems for improving the performance.
This dissertation proposes a grouping algorithm to adopt the N-Division to face recognition to overcome the curse of the dimension problem due to the high dimensional feature space of facial images. The algorithm is motivated by the property of Principal Component Analysis (PCA). We observed that the recognition accuracy of the data-driven approach was better than that of a basic approach. From the experiments, we deduced that OPC-like methods could achieve better performance than All-Pairs-like methods on problems such as face recognition, where the number of classes is large and the training sample size for each class is small. Hence, the proposed N-Division method can benefit in the aspect of the training time complexity in face recognition. From theoretical analysis of training time complexity, as the number of classes increases, the training time complexity of OPC are significantly increased; however, that of N-Division does not increase dramatically while achieving recognition performance comparable or superior to OPC.
We confirmed that the proposed data-driven N-Division method can be effectively applied to both extending support vector machine to multiple classifiers and to the applications that need incremental learning, especially for face recognition.
분석정보
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)