논문 13-38C-02-09 한국통신학회논문지 '13-02 Vol.38C No.02 http://dx.doi.org/10.7840/kics.2013.38c.2.208 라그랑지기법을쓴영공간기반선형판별분석법의변형기법 호우위시, 민황기 *, 송익호, 최명수 **, 박선 **, 이성로 *** Transformation Technique for Null Space-Based Linear Discriminant Analysis with Lagrange Method Yuxi Hou, Hwang-Ki Min *, Iickho Song, Myeong Soo Choi **, Sun Park **, Seong Ro Lee *** 요 약 부류안분산행렬의특이성때문에선형판별분석은작은표본크기문제에쓰기에알맞지않다. 이에선형판별분석을확장하여작은표본크기문제에서좋은성능을갖는영공간기반선형판별분석이제안되었다. 이논문에서는라그랑지기법을바탕으로하여, 영공간기반선형판별분석을써서특징을추출하는문제를선형방정식문제로바꾸는과정을제안하였다. Key Words : feature extraction, Lagrange method, null space-based linear discriminant analysis ABSTRACT Due to the singularity of the within-class scatter, linear discriminant analysis (LDA) becomes ill-posed for small sample size (SSS) problems. An extension of LDA, the null space-based LDA (NLDA) provides good discriminant performances for SSS problems. In this paper, by applying the Lagrange technique, the procedure of transforming the problem of finding the feature extractor of NLDA into a linear equation problem is derived. Ⅰ. 서론 선형판별분석법은 (linear discriminant analysis: 줄여서, 선판분 ) [1] 패턴인식문제에서자료의특징을추출하는방법들가운데가장널리쓰이는방법의하나이다. 하지만자료의차원 가자료의수 보다큰패턴인식문제에서는부류안분산행렬의 (within-class scatter) 특이성 (singularity) 때문에선판분을쓸수없다는문제가있다. 여기서, 부류의개수를 라할때 인패턴인식문제를작은표본크기 (small sample size) 문제라고부른다. 작은표본크기문제에서도선판분을쓸수있도록하기위해서, 선판분을바탕으로하여몇가지 이논문은교육과학기술부의재원으로한국연구재단이선정하여지원하는중견연구자지원사업 2012-0005622 와, 지식경제부의재원으로정보통신산업진흥원이지원하는대학 IT 연구센터지원사업과제 NIPA-2012-H0301-12-2005 를수행하여얻은결과가운데하나입니다. 주저자 : 한국과학기술원전기및전자공학과통계학적신호처리연구실, hyyyx@sejong.kaist.ac.kr, 정회원 교신저자 : 한국과학기술원전기및전자공학과통계학적신호처리연구실, isong@sejong.kaist.ac.kr, 종신회원 * 한국과학기술원전기및전자공학과통계학적신호처리연구실, hkmin@sejong.kaist.ac.kr ** 목포대학교정보산업연구소, mschoi@mokpo.ac.kr, 정회원, sunpark@mokpo.ac.kr, 정회원 *** 목포대학교정보전자공학과, srlee@mokpo.ac.kr, 정회원논문번호 :KICS2013-01-035, 접수일자 :2013 년 1 월 14 일, 최종논문접수일자 : 2013 년 2 월 19 일 208
논문 / 라그랑지기법을쓴영공간기반선형판별분석법의변형기법 관련기법들이제안된바있다 : 주성분분석에 (principle component analysis) 선판분을응용하여더한방법 [2], 직접선판분 (direct linear discriminant analysis) [3], 영공간기반선판분 (null space-based linear discriminant analysis: 줄여서, 영선판분 ) [4,5], 직교선판분 (orthogonal linear discriminant analysis) [6], 그리고주파수회귀판별분석법이 (spectral regression discriminant analysis) [7] 대표적인방법들이다. 이가운데, 영선판분방법은일반적으로좋은패턴인식성능을가지고있지만그복잡도가높다는문제가있다. 영선판분을써서특징을추출하는문제를더간단히풀고자, 큐알인수분해 (QR factorization) 기법과 [8] 고유값분해 (eigen-decomposition) 기술을바탕으로한기법이 [9] 각각제안된바있다. 이논문에서는라그랑지 (Lagrange) 기법을써서, 영선판분을써서특징을추출하는문제를선형방정식문제로바꾸는과정을보인다. Ⅱ. 영공간기반선형판별분석법 패턴인식에서, 부류패턴인식문제는일대다 (one-versus-all) 방법으로 [10], 두부류패턴인식문제 개로바꿀수있기때문에, 이논문에서는두부류패턴인식문제만을다룰것이다. 선형특징추출기는 로널리표현된다. 여기서, 는입력이고, 벡터 는선형판별벡터라고 (linear discriminant vector: 줄여서, 선판벡 ) 부르며, 스칼라 는바이어스이다. 이제, 자료 와그표식 들의집합을 이라가정하자. 문제를간단히하기위해, 자료 가정렬되어있어서표식벡터 처럼쓸수있다고하자. 이때, 는 모든원소가 인 행렬이다. 영선판분은, 제한조건이 일때선판벡 이이고 (Euclidean norm), (2) 는차수가 (rank) 인 부류사이분산행렬이며 (between-class scatter), (3) 은차수가 min 인 부류안분산행렬이다. 여기서, (4) 는 자료행렬이고, 부류 은부류 의가리킴수집합이며, (5) 는부류 의표본평균벡터이다. 또한, 은 의원소들의개수이다. 일단선판벡 이정해지면, 바이어스 은 으로얻을수있다. (6) Ⅲ. 라그랑지기법을써서선형방정식문제로바꾸기 먼저, 에서 이기때문에, (1) 을 (7) arg max (1) 을얻는문제이다. 여기서, 는유클리드길 arg min (8) 로다시쓸수있다. 여기서, 209
한국통신학회논문지 '13-02 Vol.38C No.02 (9) (18) 이고 (10) 임을 (15) 에서알수있다. 라그랑지기법을써서앞과비슷하게몇단계거치고나면, 제한조건이 (14) 인문제 (17) 을 이다. 또한, 제한조건 을 (11) arg min (19) 로다시쓸수있다. 여기서, (12) 처럼쓸수있다. 식 (19) 에보인목적함수를 에대해미분한값을 으로두면, (20) 이다. 이제, (8) 과 (11) 에나타난문제의라그랑지함수를 임을알수있다. 여기서, (13) 으로둘수있다. 이때, 벡터 는라그랑지곱수이다 (multiplier). 라그랑지함수 을 와 에대해서각각편미분한값이 이되도록만들면, 이고, (21) (22) (14) 와 (15) 를얻을수있다. 이제 (14) 와 (15) 를써서, 라그랑지함수 (13) 을 (16) 으로다시쓸수있다. 따라서, 제한조건이 (11) 인문제 (8) 을제한조건이 (14) 인문제 arg min (17) 로다시쓸수있고, 이때 와 의관계는 이다. 여기서, 은 단위행렬이고, (23) 은응답벡터이다. 이제, (10) 과 (18) 에서 (24) 이고, (1) 에서 이기때문에스칼라 의값이 ± 수있다. 그러므로, 임을알 ± (25) 이다. 곧, 선형방정식 (20) 를풀어 를얻으면 210
논문 / 라그랑지기법을쓴영공간기반선형판별분석법의변형기법 선판벡 을얻을수있다. 벡터 가 의영공간과직교하지않으며, 가완전계수행렬이라는조건에서 (20) 를얻었음을새겨두자. 한편, 가 의영공간과직교할때는, (26) 이늘 이기때문에 (1) 의풀이가없다. 다만, 가특이행렬일때에는, 작은양수 를써서 를완전계수행렬 로바꾸는방법을 ( 섭동법 ) 써서 를얻을수있다. Ⅳ. 벡터 얻기식 (20) 을써서바로 를얻는방법은 쯤의곱셈이든다 [11]. 계산량을줄 이기위해, 바로얻는방법대신에다음방법으로 를얻어보자. 식 (14) 에서 이므로, 행렬 (27) 이 (28) 을만족시킴을쉽게알수있다. 이제, 보다큰실수 를생각하면행렬 은양정치이기때문에, 촐레스키분해를써서 (28) 을풀면 의해를얻을수있다. 이렇게 를얻으면직접얻는것보다복잡도가더낮을것이라는것을예상할수있다. Ⅴ. 맺음말이논문에서는라그랑지기법을써서, 영공간기반선형판별분석법을써서특징을추출하는문제를선형방정식문제로바꾸었다. 이렇게얻어진선형방정식문제를풀어특징추출기를얻는과정은, 원래의문제를풀어특징추출기를얻는과정보다복잡도가더낮을것으로기대한다. 참고문헌 [1] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2nd ed., John Wiley and Sons, 2001. [2] P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, Eigenfaces vs. fisherfaces: Recognition using class specific linear projection, IEEE Trans. Patt. Anal., Mach. Intell., vol. 19, no. 7, pp. 711-720, July 1997. [3] H. Yu and J. Yang, A direct LDA algorithm for high-dimensional data with application to face recognition, Patt. Recogn., vol. 34, no. 10, pp. 2067-2070, Oct. 2001. [4] L.-F. Chen, H.-Y. Mark Liao, M.-T. Ko, J.-C. Lin, and G.-J. Yu, A new LDA-based face recognition system which can solve the small sample size problem, Patt. Recogn., vol. 33, no. 10, pp. 1713-1726, Oct. 2000. [5] D.-U. Cho, U.-D. Chang, Y.-G. Kim, Y.-J. Song, J.-H. Ahn, and B.-H. Kim, 2D direct LDA algorithm for face recognition, J. Korean Inform., Comm. Soc., vol. 30, no. 12C, pp. 1162-1166, Dec. 2005. [6] J. Ye and T. Xiong, Computational and theoretical analysis of null space and orthogonal linear discriminant analysis, J. Mach. Learn. Res., vol. 7, no. 7, pp. 1183-1204, July 2006. [7] D. Cai, X. He, and J. Han, SRDA: An efficient algorithm for largescale discriminant analysis, IEEE Trans. Knowl., Data Eng., vol. 20, no. 1, pp. 1-12, Jan. 2008. [8] D. Chu and G. S. Thye, A new and fast implementation for null space based linear discriminant analysis, Patt. Recogn., vol. 43, no. 4, pp. 1373-1379, Apr. 2010. [9] R. Huang, Q. Liu, H. Lu, and S. Ma, Solving the small sample size problem of LDA, Proc. Int. Conf. Patt. Recogn., pp. 29-32, Quebec, Canada, Aug. 2002. [10] R. Rifkin and A. Klautau, In defense of one-vs-all classification, J. Mach. Learn. 211
한국통신학회논문지 '13-02 Vol.38C No.02 Res., vol. 5, no. 1, pp. 101-141, Jan. 2004. [11] G. W. Stewart, Matrix Algorithms Volume I: Basic Decompositions, Society for Industrial and Applied Mathematics, 1998. 호우위시 (Yuxi Hou) 2001년 2월시안교통대학교전기및전자공학과공학사 2005년 2월시안교통대학교전기및전자공학과공학석사 20012년 8월한국과학기술원전기및전자공학과공학박사 2012년 8월~현재한국과학기술원전기및전자공학과박사후연구과정 < 관심분야 > 특징추출, 패턴인식, 신호처리, 기계학습민황기 (Hwang-Ki Min) 2004년 2월한국과학기술원전기및전자공학과공학사 2006년 2월한국과학기술원전기및전자공학과공학석사 2006년 3월~현재한국과학기술원전기및전자공학과박사과정 < 관심분야 > 신경회로망, 기계학습, 패턴인식송익호 (Iickho Song) 1982년 2월, 1984년 2월서울대학교전자공학과공학사 ( 준최우등 ), 공학석사 1985년 8월, 1987년 5월펜실베니아대학교전기공학과공학석사, 공학박사 1987년 3월 1988년 2월벨통신연구소연구원 1988년 3월 현재한국과학기술원전기및전자공학과조교수, 부교수, 교수 1995년 1월 현재한국통신학회논문지편집위원대한전자공학회, 한국음향학회, 한국통신학회평생회원, IET 석학회원, IEEE 석학회원 < 관심분야 > 통계학적신호처리와통신이론, 신호검파와추정, 이동통신 최명수 (Myeong Soo Choi) 2000년 2월목포대학교전자공학과공학사 2002년 2월목포대학교전자공학과공학석사 2009년 2월목포대학교전자공학과공학박사 2009년 3월목포대학교해양텔레매틱스기술개발센터박사후연구원 2009년 12월~현재목포대학교정보산업연구소연구전임교수 < 관심분야 > 디지털통신시스템, USN, 배열신호처리, 임베디드시스템박선 (Sun Park) 1996년 2월전주대학교전자계산학과이학사 2001년 2월한남대학교정보통신학과공학석사 2007년 2월인하대학교컴퓨터정보공학과공학박사 2008 2009년호남대학교컴퓨터공학과전임강사 2010년전북대학교인력양성사업단박사후과정 2010년 12월 현재목포대학교정보산업연구소연구전임교수 < 관심분야 > 정보검색, 데이터마이닝, 데이터베이스, 해양IT정보융합디지털통신시스템, 이동및위성통신시스템, USN/ 텔레미틱스응용분야, 임베디드시스템이성로 (Seong Ro Lee) 1987년 2월고려대학교전자공학과공학사 1990년 2월한국과학기술원전기및전자공학과공학석사 1996년 8월한국과학기술원전기및전자공학과공학박사 1997년 9월~현재목포대학교공과대학정보전자공학과교수 < 관심분야 > 디지털통신시스템, 이동및위성통신시스템, USN/ 텔레매틱스응용분야, 임베디드시스템 212