선형 바이너리 SVM 구현 (지원 벡터 머신)

Question

간단한 선형 SVM이 가장 좋다고 생각하는 고차원 이진 데이터 (텍스트)의 경우 간단한 SVM 분류기를 구현하고 싶습니다. 직접 구현하는 이유는 기본적으로 그것이 어떻게 작동하는지 배우고 싶기 때문에 라이브러리를 사용하는 것이 내가 원하는 것이 아닙니다.

문제는 대부분의 튜토리얼이 "2 차 문제"로 해결 될 수있는 방정식으로 올라가지 만 실제 알고리즘을 보여주지 않는다는 것입니다! 그렇다면 내가 공부할 수있는 매우 간단한 구현을 지적 할 수 있습니까?

정말 감사합니다!

Answer 1

일부 의사 코드 순차적 최소 최적화 (SMO) 방법은이 백서에서 John C. Platt에 의해 찾을 수 있습니다. 순차적 최소 최적화를 사용한 지원 벡터 머신의 빠른 교육. 연구 및 교육 목적을 위해 개발 된 SMO 알고리즘의 Java 구현도 있습니다.SVM-Java).

QP 최적화 문제를 해결하기 위해 일반적으로 사용되는 다른 방법은 다음과 같습니다.

• 제한된 컨쥬 게이트 그라디언트
• 내부 포인트 방법
• 활성 세트 방법

그러나이 것들을 이해하려면 일부 수학 지식이 필요하다는 점에 유의하십시오 (Lagrange Multipliers, Karush – Kuhn -tucker 조건 등).

Answer 2

커널 사용에 관심이 있습니까? 커널이 없으면 이러한 종류의 최적화 문제를 해결하는 가장 좋은 방법은 다양한 형태의 확률 적 구배 출신을 통한 것입니다. 좋은 버전이 설명되어 있습니다 http://ttic.uchicago.edu/~ shai/papers/shalevsisr07.pdf 그리고 그것은 명백한 알고리즘이 있습니다.

명시 적 알고리즘은 커널과 함께 작동하지 않지만 수정할 수 있습니다. 그러나 코드와 런타임 복잡성 측면에서 더 복잡 할 것입니다.

Answer 3

liblinear와 libsvm에서 비 선형 SVM을 살펴보십시오.

Answer 4

다음 논문 "Pegasos : SVM에 대한 Primal 추정 하위 그라디언트 솔버"는 11 페이지의 상단은 Kernels의 Pegasos 알고리즘을 설명합니다. http://ttic.uchicago.edu/~nati/publications/pegasosmpb.pdf

그것은 좌표 하강과 하위 등급의 하강의 하이브리드 인 것으로 보입니다. 또한 알고리즘의 6 행이 잘못되었습니다. 술어에서 y_i_t의 두 번째 모양은 대신 y_j로 대체되어야합니다.