트리 커널

Tree kernel

머신러닝에서, 트리 커널은 보다 일반적인 개념의 긍정-확정 커널을 트리 구조에 적용하는 것이다.그들은 자연 언어 처리에서 응용 프로그램을 찾는데, 이 응용 프로그램은 기계 학습 파싱이나 문장의 분류에 사용될 수 있다.

동기

자연어 처리에서는 유사성을 위해 나무 구조(예: 파스 나무)를 비교할 필요가 있는 경우가 많다.그러한 비교는 나무의 특징 벡터의 도트 제품을 계산함으로써 수행될 수 있지만, 이러한 벡터는 매우 큰 경향이 있다: NLP 기술은 두 단어에 대한 단순한 의존 관계가 수백만 개의 특징의 벡터로 인코딩되는 지점에 도달했다.[1]형상 벡터가 있는 나무와 같은 복잡한 구조를 나타내는 것은 비현실적일 수 있다.잘 설계된 커널은 이러한 트리의 특징 벡터를 명시적으로 계산하지 않고도 트리에서의 컴퓨팅 유사성을 가능하게 한다.더욱이 커널 방법은 머신러닝 작업(예: SVM )에서 널리 사용되어 왔으며, 따라서 많은 알고리즘이 커널과 기본적으로 작동하고 있거나 커널화를 처리하는 확장자를 가지고 있다.

예로는 문장의 분류(예: 다른 유형의 질문)가 있다.[2]

예

선거구는 "고양이는 쥐를 먹는다"라는 문장의 파스 트리를 사용한다.
위와 같은 문장에서 "쥐는 고양이를 먹는다"는 말이 있다.

여기 선거구 나무에 적용된 나무 알맹이의 두 가지 예가 제시되어 있다. "고양이는 쥐를 먹는다."와 "고양이를 먹는다"라는 문장이 있다.이 예에서 "A"와 "a"는 동일한 단어이며, 대부분의 NLP 응용 프로그램에서는 동일한 토큰으로 표현될 것이다.

이 두 커널의 관심사는 동일한 계산 복잡성에 대해 매우 다른 세분성(부분집합 트리 커널이 하위 트리 커널보다 훨씬 미세하게 배열됨)을 보인다는 것이다.둘 다 시간 O(T12. T [3])로 재귀적으로 계산할 수 있다.

하위 트리 커널

선거구 트리의 경우, 하위 트리는 노드와 그 모든 하위 트리(예: [NP [D] [A]] [N[mouse]]는 두 트리의 하위 트리)로 정의된다.단자는 하위 트리로 간주되지 않는다(예: [a]는 하위 트리가 아니다).하위 트리 커널은 주어진 두 트리 사이의 공통 하위 트리 수를 카운트한다.

이 예에서는 다음과 같은 7개의 공통 하위 트리가 있다.

[NP [D [a] [N [cat]]],
[NP [D [a] [N [마우스]]],
[N [마우스]],
[N [cat]],
[V [eats]],
[D [a] (두 번 나타날 때 두 번 계산함).

부분 집합 트리 커널

부분 집합 트리는 하위 트리보다 더 일반적인 구조다.기본적인 정의는 동일하지만, 부분집합 트리의 경우 잎이 단자가 될 필요는 없다(예: [VP [V] [NP]는 두 트리의 부분집합 트리임). 그러나 여기서는 너무 단일 노드가 나무로 간주되지 않는다.이러한 보다 일반적인 정의 때문에 하위 트리보다 하위 트리, 공통 하위 트리보다 공통 하위 트리 수가 더 많다.

이 예에서는 54개의 공통 서브셋 트리가 있다.7개의 공통 하위 트리와 기타 하위 트리를 더하기:

[NP [D] [N] (두 번 계산),
[VP [V [eats] [NP]]...

참고 항목

메모들

  1. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). Non-projective Dependency Parsing using Spanning Tree Algorithms. HLT–EMNLP.
  2. ^ Zhang, Dell; Lee, Wee Sun (2003). Question classification using support vector machines. SIGIR.
  3. ^ Collins, Michael; Duffy, Nigel (2001). Convolution kernels for natural language. Advances in Neural Information Processing Systems.

참조

  • 준선, 민장, 츄임탄.자연어를 위한 트리 시퀀스 커널
  • 알레산드로 모스키티자연어 학습을 위한 나무 커널 만들기

외부 링크