::고려대학교 DMQA 연구실::

Lab. Activity

 

 

 

Lab. Activity>Seminar  

Twin Support Vector Machine (발표자: 이한규)

작성자 관리자 작성일 2016-10-21 오전 1:58:31
내용

발표자 Summary

 

이한규
일반적으로 알려진 SVM은 1개의 margin을 최대화 하는 hyperplane을 찾고 이를 통해 분류 또는 예측을 진행한다. 그러나 오늘 진행한 TWSVM은 1개의 데이터셋으로부터 2개의 hyperplane을 찾는 것을 목적으로 한다. 제안된 방법론에서 equation은 기존의 svm과 유사한 형태로서, 기존 모든 클래스 정보를 활용해서 boundary를 설정하는것과는 달리 각 클래스 정보만을 활용하여 특정 클래스를 잘 설명하는 line(or hyperplane)을 찾게 된다. 또한 제약식에서는 다른 클래스의 정보를 활용하여 찾은 line이 다른 클래스와는 최소 거리를 유지하도록 하게 된다. 따라서 각 군집화와 유사한 형태로 각 클래스를 관통하는 line(or hyperplane) 2개가 나타나며, 새로운 데이터를 각 line(or hyperplane)과의 거리를 측정해서 가까운 클래스로 분류가 된다. 본 논문은 2개의 hyperplane을 찾는 SVM 관련 논문중 초기에 발표된 논문으로 SVM이지만 margin을 최대화 한다기 보다는 두 클래스를 잘 설명하는 line(or hyperplane)을 찾는 군집화라고 볼 수 있다. 저자는 kernel trick을 사용한 non-linear TWSVM 또한 제안했는데 실험 결과 기존 SVM보다 향상된 정확도를 나타냈다. 또한 각 범주별로 작은 QP문제를 풀기때문에 이론적으로는 기존 SVM보다 약 4배 빠른 성능을 보였다. 2007년에 발표된 논문으로 이후 TWSVM을 개선한 TBSVM, LSTSVM등 다양한 방법들이 제안되었으며, multi class classification을 위한 논문 또한 다양하게 발표되고 있다.

 

청취자 Summary

 

유재홍
금일 세미나는 Twin Support Vector Machine (TWSVM)을 주제로 진행되었다. 기존의 SVM 알고리즘은 분류 경계선을 기준으로 마진의 너비가 같다는 것을 바탕으로 분류를 수행한다. 하지만, 이러한 경우, 개별 클래스의 분포 패턴이 완벽하게 반영되지 못할 뿐만 아니라,  노이즈에 대해 비교적 취약하다는 한계점을 가지고 있다. 이를 극복하기 위해서 Twin Support Vector Machine라는 알고리즘이 제안되었다. 이 기법은 특정 분류 경계선을 바탕으로 마진이 도출되는 것이 아니라, 각 클래스 별로 구분할 수 있는 개별 경계선이 도출된다. 이를 통해 클래스 별 분류 패턴이 보다 적절하게 반영될 수 있고 이를 통해 분류 성능이 향상될 수 있을 것이라고 생각된다. 또한, 커널 트릭을 적용하게 되면 비선형 패턴으로 분포되어 있는 경우에 대해서도 보다 잘 분류할 수 있다고 하는데, 현재 연구 중에 있는 커널함수를 적용해본다면 흥미로운 결과를 얻을 수 있을 것이라고 생각된다.

 

곽민구
금일 세미나는 Twin Support Vector Machine에 대해서 진행되었다. 세미나 앞부분에서는 SVM에 대한 간략한 리뷰를 진행하였으며, 이를 토대로 TWSVM에 대한 내용을 설명하였다. 비록 SVM이라는 이름이 붙었지만 TWSVM은 support vector를 사용하지 않는다. SVM은 두 클래스를 구분하는 평면의 마진을 최대화하는 최적화식을 푸는 과정을 통해 최적의 분류기를 구축하는 반면, TWSVM은 SVM과 목적식이 유사하나 결국 각 클래스를 잘 설명하는 두 가지의 직선을 찾는 것에 목적이 있다. 세미나 중간에 가장 많이 나왔던 질문이 "결국 두 평면이 확장되었을 때는 만나게 되는데 그때 발생하는 오분류의 해결"에 관한 것이었다. 비록 kernel trick을 사용을 한다고 하더라도, 고차원에서 구한 평면 또한 만나게 될 것인데 이에 대한 문제해결은 다른 논문을 더 찾아보는 것도 좋을 것이라는 생각이 든다. 덧붙여, 예전에 김영훈 연구원이 발표했던 exemplar group이랑 컨셉이 유사하다는 느낌을 받았다.

 

도형록
금일 세미나는 twin support vector machine에 대해 진행되었다. Twin SVM은 두 개의 클래스를 나누는 데 있어 하나의 hyperplane을 학습하는 대신, 각 클래스를 대표할 수 있는 평면들을 만들어 클래스를 분류하는 방식이다. 이런 접근 방식을 통해 계산복잡도를 줄일 수 있다고 한다. 기본 개념은 feature space상에서 클래스 내의 관측치들과 직선거리가 가장 가까운 평면을 결정하되, 다른 클래스와의 거리를 일정 값 이상으로 유지하는 평면을 찾는 것이다. 분류 성능 또는 실제 계산 속도면에서 향상이 있을지는 의문이 들었지만, 클래스를 대표하는 hyperplane을 구한다는 접근 방식이 신선했다. 이는 클러스터링 등에 사용되는 개념과 비슷하다고 생각하는데, 일종의 data description method로 변형될 수 있는 가능성이 있는 것 같다. Twin SVM과 비슷한 연구로 classification을 위한 support vector data description 관련 연구를 접한 기억이 있다. 각각의 클래스에 OCC 알고리즘은 SVDD를 적용하되, 다른 클래스를 최대한 포함하지 않도록 boundary를 구축하는 방법으로 기억한다. 간단하고 재미있는 아이디어이지만 일반적인 classifier에 비해 어떤 이점이 있는지는 고민해봐야 할 것 같다.

 

이상민
TwinSVM은 비평행한 고유의 hyperplane을 갖는다는 면에서 SVM과 큰 차이가 있다. 이진분류 문제를 예로 들 때, 두 class를 분류하는 hyperplane 중 margin을 가장 최대화 하는 기존 SVM과 다르게, 각 class의 분포를 가장 잘 표현하는 hyperplane을 탐색하되 상대 class의  support vector까지의 margin을 고려한다. 이론적으로는 기존 SVM 대비 시간 복잡도를 O(m^3)->O(m^3/4) 4배 가까이 줄일 수 있는 장점이 있다고 기술하고 있다. 또한 해당 논문들에서는 특정 데이터에 대해서는 TwinSVM의 성능이 높을 수 있음을 실험을 통해 선보이기도 했다. 하지만 일반적으로 시간도 복잡도 면에서 최악의 실행시간을 나타내는 빅오에 들어가는 상수 부분은 과감하게 무시한다. 즉, 충분히 큰 관측치에 대해서는 O(m^3)과 동일할 수 밖에 없어서 4배가 줄어들었다는 식의 논리는 통하지 않는다. 그러므로 시간 복잡도면에서는 기존 SVM 대비 큰 의미가 없어 보인다. 또한, 이진분류 문제에서 TwinSVM의 장점이 있다는 근거를 찾기에는 희박해보인다. 비평행 hyperplane을 갖는 모델의 특성이 overlapped data를 잘 나눈다 등의 특별한 강점은 없어 보인다. 단, multi-class classification 문제에서는 one-against-others 접근방식에 따라 분류 시에 각 class를 타 class로부터 가장 잘 분류하는 여러 개의 hyperplane을 가질 수 있으므로 더욱 성능을 높이는데 강점이 있을 것을 보인다. 특히 일반 프로젝트 수행 시 다중 클래스로 분류해야 하는 일정 수준의 사이즈를 가진 dataset에 대해서 SVM보다 좀 더 빠른 수행속도와 함께 유사하거나 좀 더 나은 성능 정확도를 요한다면 유용하게 활용할 수 있지 않을까 싶다. 데이터 크기와 흥미로운 주제에 대해서 소개해준 이한규 연구원에게 감사하며, 개인적인 연구와 프로젝트 진행에 큰 진보가 있기를 바란다.

 

박영준
오늘 세미나는 한규형이 Twin SVM이라는 주제로 진행했다. SVM의 마진은 항상 분류 경계선에 평행하게 생성이 된다. 이 경우 데이터의 분포에 따라 평행한 마진이 적절하지 않을 수 있다. Twin SVM에서는 SVM의 formulation을 빌려와 서로 평행하지 않은 비대칭의 마진을 생성할 수 있는 방법론을 제안했다. Twin SVM은 기존 SVM 보다 이론적으로 4배가 빠른 성능을 보이며, 실제 데이터를 이용한 실험에서도 보다 좋은 성능을 나타냈다. 하지만 더욱 중요한것은 이 연구가 시발점이 되어 평행하지 않은 마진을 갖는 SVM에 대한 연구가 지속되고 있다는 점이라고 생각한다. 최조에 제안된 Twin SVM에서는 평행하지 않은 마진을 생성해 내지만 이를 직접적으로 통제할 수 없다. 하지만 최근의 연구에서는 더 정교한 formulation으로 마진도 통제할 수 있게 되었다. 향후 한규형이 하는 Overlap Class 분류 연구에 Twin SVM이 어떤 효과를 가져다 줄지 궁금하다.

 

최우식
SVM의 일반적인 틀 중 하나는 어떠한 하나의 hyperplane을 생성하였을 때 그 hyperplane에 의하여 각 클래스가 얼마나 분리되는지를 나타내는 지표인 margin을 최대화한다는 것이다. 오늘 세미나에서 소개된 twin SVM (TWSVM)은 이러한 틀을 깨는 방법이다. 간단하게는 각각의 클래스 별로 클래스를 잘 설명하는 hyperplane을 생성하여 그 hyperplane이 다른 클래스의 데이터로부터 최대한 멀어지도록 하는 것이라 할 수 있다. Hyperplane을 생성하는 원리나 방법에 대해서는 자세히 공부를 해야 알 수 있겠지만, 커널을 생성하거나 SVM의 최적화 문제를 해결하는 것에서는 관측치의 수가 계산 시간에 상당히 영향을 주는데 이 방법을 통해 계산 시간을 감축할 수 있다는 점에서 큰 도움이 될 수 있겠다. 정확도 등의 성능은 실제로 연구실에서 다루고 있는 데이터에 대하여 적용해보고 평가하는 것이 좋을 것이라 생각된다.

 

박찬희
SVM에 대한 기본 개념과 두 개의 서포트백터를 이용한 새로운 SVM 기법을 설명한 세미나였다. 기본적인 SVM에서는 마진을 최대화 시키는 결정경계를 찾고 새로운 관측치를 분류한다. TWSVM은 결정경계를 찾는 대신, 각 클래스에 대응하는 hyperplane을 찾는다. 새로운 관측치와 각 클래스의 hyperplane과의 거리를 계산해 가까운 hyperplane에 해당하는 클래스를 할당하게 된다. TWSVM은 이진분류에 특화된 분류기로 불 수 있고, 실험결과 기존 SVM 모델에 비해 짧은 계산시간을 이용하여 비슷한 분류성능을 보여준다. TWSVM 이후 서포트백터들로 이루어진 hyperplne을 찾는 v-TWSVM이 제안되었고, 기존 TWSVM 에 비해 높은 분류성능을 보여주었다. TWSVM 또한 노이즈 문제를 해결하기 위해 soft margin을 이용하는데, 이때 파라미터에 따라 변하는 모델의 안정성이 문제가 될 수 있다. 이후 제안된 boosting TWSVM은 기존 모델의 안정성을 높이는데 기여하였다.

 

김영훈
오늘 세미나에서는 Twin SVM에 대해서 배울 수 있었다. 이 Twin SVM은 기존의 SVM과 유사한 성능을 내면서도 계산 복잡도를 4배 가량 줄인 방법이다. 기존의 SVM이 Margin을 최대화하는 하나의 평면을 찾는 방법이었다면 Twin SVM은 각 범주를 잘 설명하는 평면을 각각 찾아주는 방법이다. 범주별로 모델을 각각 세우기 때문에 관측치에 3승에 비례하는 계산 복잡도를 갖는 SVM에 비해 4배 가량의 복잡도 감소 효과를 가져올 수 있다. 실제 분류 성능이 SVM과 비슷한 것을 보았을 때 더 효과적인 방법이라고 생각이 되었다. 한 가지 든 생각은 평행하지 않은 평면으로 경계면을 만들 경우에 두 경계면이 결국에는 만나게 되고 만나고 나서의 분류 결과가 상식적이지 않은 것 같다. 일반적인 SVM의 경우에는 한 경계면을 기준으로 분명하게 두 개의  범주가 나뉘게 되는데 소개된 방법은 일정 구간이 지나고 나면 두 개의 범주가 나뉘는 공간이 교차되게 되서 일반적인 상식과는 배치되는 결과를 보이는 것 같다. 약간 이해가 안 되는 부분이 있긴 하지만 고정관념을 깨는 효과적인 방법론이 인상적이었다.

 

손지은
이진 분류를 위한 Twin support vector machine (TWSVM)에 대한 내용을 다루었다. 일반적인 SVM에서는 margin을 최대화시키는 하나의 linear classifier를 구하게 된다. 제안 방법은 이진 분류를 위해 각 class에 속하는 관측치들과의 거리 제곱합을 최소화시키는  두개의 hyperplane (linear classifier)를 구하였다. 또한 기존 SVM과 마찬가지로 노이즈가 포함 데이터를 고려하기 위해  slack variable을 추가하여 hyperplane을 구축하였다. 하지만 TWSVM에서는 두개의 hyperplane이 서로 평행하지 않으므로 실제데이터 분석시 hyperplane이 서로 겹칠 수 있는 문제가 발생할 수 있을 것으로 예상된다. SVM에 대해 새로운 관점으로 접근한 연구로써 이진분류 문제에서 어떻게 linear classifier를 구축할 수 있을지에 대해 깊게 생각해볼 수 있는 기회였다.

 

이슬기
오늘 세미나는 Twin support vector machine을 주제로 다루었다. 기존 SVM은 각 범주간 마진을 최대화 하는 결정경계를 찾는 최적화 식을 구축한다. 이때 마진은 평행한 형태인데, 이번 세미나에서는 마진의 평행성에 대한 의문을 가지고 최적화식을 수정한 방법에 대해 논의하였다. 결과적으로 각 범주마다 하나의 linear regression 결과와 비슷한 선을 찾는 것이 목적이 되는 것이었고, 새로운 데이터에 대한 분류는 그 대표선과의 거리를 구하여 더 짧은 거리로 정하는 방식이다. 아이디어적인 측면에서는 그럴 수 있겠다는 생각이 들었지만, 과연 제안한 방법이 기존 SVM이 해결 못하는 문제를 해결한다고 보기는 어렵다고 생각이 들었다. 데이터분포 형태가 복잡하더라도 커널기법을 사용하기 때문에, 마진이 평행한지 안한지가 얼마나 분류성능을 올릴 수 있을지에 대한 의구심이 든다. 세미나에서 소개한 연구를 시작으로 많은 연구들이 진행되었다고 했는데, 이를 좀 살펴보고 이 방법이 본질적으로 어떤 문제를 해결하는지 확인해보아야겠다.

 

강성현
오늘 소개된 Twin SVM은 기본적으로 이진 분류기로 볼 수 있다. 먼저 두 개의 클래스 중에서 한쪽의 데이터만을 활용하여 초평면(혹은 직선)을 결정한다. 간단하게 PCA나 최소제곱법 방식으로 한 클래스의 초평면을 구할 수도 있겠지만, Twin SVM에서는 자신의 클래스에 대한 오류는 줄이면서 다른 클래스에 대한 차이는 벌릴 수 있는 목적식을 통해 초평면을 구한다. 같은 방법으로 다른 클래스에 대해서도 동일한 방법으로 초평면을 산출한다. 마지막으로 새로운 데이터가 들어오면 각각의 초평면에서 가까준 쪽의 클래스를 새로운 데이터의 클래스로 결정한다. Twin SVM은 각 클래스의 초평면을 구하는 과정에서 각 클래스로 나뉜 서브 데이터셋을 활용하기 때문에 모든 데이터를 활용하는 SVM 대비 연산속도가 빠른 장점이 있다. 초평면을 구할 때 다른 클래스의 데이터를 고려하는 가중치를 정할 수 있으므로 각 클래스가 겹쳐진 데이터에서도 전통적인 SVM보다 분류 성능이 우수할 것으로 생각된다. 특히 장점으로 생각되는 것은 다중 클래스 분류 문제가 아닐까 생각된다. 기본적으로 이진 분류기이지만 본인과 본인이 아닌 2개 클래스로 구분하여 모든 클래스의 대표 초평면을 구할 수 있기 때문이다. 각 초평면에서 가장 가까운 클래스로 결정되기 때문에 해석도 매우 직관적이다. 다중 클래스 분류 문제에서 전통적인 SVM 성능과 비교한 결과는 금일 소개되지 않았는데 이를 파악해 본다면 유익할 것으로 생각된다.

 

정영재
한규 형의 Twin Support Vector Machine (TWSVM)이란 제목의 세미나를 들었다. 최근 눈에 띄었던 논문 제목이 TWSVM을 이용하여 Supervised, Semi-Supervised, Unsupervised에 사용한 논문이였기 때문에 이번 세미나에 특히 더 관심이 생겼다. 논문을 직접 읽어보지 않아서 그 방법이 무엇인지 궁금했기 때문이다. TWSVM은, 2 class classification 기준으로, 기존 SVM과 다르게 Hyperplane을 1개가 아닌 2개를 생성한다. 따라서, Twin SVM이란 이름을 가지게 된 것 같다. Twin SVM에서 Hyperplane을 2개 만들어서 정확도 면에서 무엇이 좋은지는 잘 모르겠다. 하지만, 계산량이 기존 SVM보다 4배이상 빠르다고 하니, 계산량 측면에서 좋을 것 같다. 또한 Semi supervised 방식으로 사용될 경우, 어느 데이터를 포함시킬 것인지에 관하여, 각 Class를 잘 설명하는 Hyperplane과 가까운 data를 선택하는 것을 기준으로 삼는다면 기존 SVM보다 더 좋은 성능을 보일 것 같다. 이번 세미나를 통해 Twin SVM이 무엇인지 개략적으로 알 수 있어서 좋았다. 또한 이번 발표 때, SVM에서 Kernel에 대한 예시 그림이 다른사람에게 설명하기 좋을 것 같아서 향후 필요할 때 요긴하게 써야겠다.

 

 

강현구

오늘 세미나는 Twin Support Vector Machine(TWSVM)을 주제로 진행되었다. 기존 SVM은 서로 다른 클래스에 속한 데이터를 잘 분류하는 하나의 분류선을 찾는 것이라면, TWSVM은 각 클래스의 데이터를 잘 설명할 수 있는 초평면(일종의 회귀선)을 클래스의 개수만큼 찾는 것이다. 이진 분류 문제의 경우, 기존 SVM에서 margin을 각각 찾는 것이라고도 볼 수도 있는데, 이는 기존 SVM의 margin은 항상 평행한 반면에 TWSVM에서 구한 초평면은 서로 평행하지 않을 수 도 있다. 새로운 데이터를 분류할 때는 각 초평면으로부터의 거리를 기준으로 한다. 하지만 한편으론 서로 다른 초평면(혹은 margin)이 서로 평행하지 않기 때문에 서로 만나고 교차하게 될 경우엔 어떤 문제가 발생할 지 확인해볼 필요가 있다. 해당 논문에 의하면 시간 복잡도가 1/4 가량 줄어드는 것을 확인할 수 있는데, 이는 다중 클래스 분류 문제의 경우 큰 장점이 될 수 있다고 생각한다. 

 

 




이전글
다음글

(136-713) 서울시 성북구 안암로145 고려대학교 자연계캠퍼스 신공학관 211호 | TEL.02-3290-3769
고려대학교 산업경영공학과 데이터마이닝 및 품질애널리틱스 연구실. All Right Reserved. 개인정보처리방침