밀당의 영어 문장 분석 방법과 유사도
이 글은 밀당 영어에서 사용하는 영어 문장 분석 방식과 분석을 토대로 문장 사이의 유사도를 측정하는 방법에 관해 기술합니다.
문장 분석을 하는 이유
밀당 영어에서는 영어 문장과 단어, 문법을 분석하여 데이터에 기반한 학습을 제공합니다. 분석된 문장과 단어, 문법은 데이터의 형태로 저장되고 있습니다. 문장을 분석하여 단어들을 추출하여 저장하고, 문장의 어떤 문법적 요소가 들어있는지 tagging 합니다. 이 중에서 문장을 어떻게 분석하고 활용하는지와 분석된 문장들의 유사도를 구해봅시다.
밀당 영어의 문장 분석 방식
밀당 영어 콘텐츠의 영어 문장 분석은 Google 자연어 처리 엔진으로 어떤 문장 구조와 단어를 가졌는지 자동으로 파악하며 어떤 문법적 요소를 가졌는지 수동으로 tagging 합니다. 특히 영어의 문장 구조에서는 한국어와 달리 어순이 지배적인 역할을 합니다. 자연어 처리 엔진에서 이러한 영어의 어순을 종속성 트리 형태로 받아서 문장 구조를 파악하고 분석할 수 있습니다.
Google 자연어 처리 엔진
단어에 대해
문장을 분석할 때, 단어의 내부 구조를 분석하는 것이 중요합니다.
Google 자연어 처리 엔진은 단어의 내부 구조(형태론) 및 문장 내 역할(구문)에 대한 정보를 제공합니다.
형태론
형태론은 단어의 내부 구조를 연구하는 것입니다. 단어 내 구성 요소(어간, 어근, 접두사, 접미사 등)가 어떻게 정렬 또는 수정되어 다양한 의미를 만들어내는지에 초점을 맞춥니다. 예를 들어 가산명사 끝에 ‘-s’ 또는 ‘-es’으로 복수형을 나타내고 동사 뒤에 ‘-d’ 또는 ‘-ed’를 추가하여 과거형을 나타냅니다.
영어에서는 ‘격’을 나타내는 접사가 부족하여 각 단어의 역할을 표시하기 위해 문장 내 단어 순서에 더 많이 의존합니다. 그 결과, 형태론적 분석은 출발 어에 크게 의존하여 해당 언어 내에서 무엇이 지원되는지 이해해야 합니다.
구문
문구와 문장의 구조에 대한 연구입니다. 구문 및 형태론은 서로 문법적 관계를 나타내지만, 언어마다 이 둘이 사용되는 방법은 다릅니다.
Google 자연어 처리 엔진에서는 형태론적 정보를 ‘partOfSpeech’에, 그리고 단어 간 구문적 관계는 ‘dependencyTree’에 반환합니다.
품사
‘partOfSpeech’ 필드는 좀 더 명확한 형태론적 정보와 품사 정보를 가진 일련의 하위 필드를 포함합니다.
해당 하위 필드
- tag : 간단한 품사 태그를 사용하여 품사를 표시하며 대략적인 구문 정보를 제공합니다.
- number : 단어의 문법적 수를 나타냅니다.
- person : 단어의 문법적 인칭을 식별합니다. 예를 들어 ‘I/ me’는 FIRST ( 화자 )입니다.
- gender : 명사의 문법적 성을 나타냅니다.
- case : 단어의 문법적 격과 문구 또는 문장에서 그 역할을 나타냅니다.
- tense : 시간 속에서 동사가 차지하는 위치를 기준으로 하는 동사의 문법적 시제를 나타냅니다.
- aspect : 동사의 문법적 상, 동사의 행동이 진행되는 곳에서 시간 흐름의 특성에 초점을 맞춘 필드
- mood : 행동에 대한 태도를 나타내는 동사의 서법을 의미합니다.
- voice : 행동과 주어/목적어 간의 관계인 동사의 문법적 태를 나타냅니다. 주어가 행동을 수행하거나, 행동의 영향을 받는 것 등을 나타냅니다.
- reciprocity : 단어의 상호관계를 나타냅니다. 상호관계란 대명사가 같은 문장의 다른 곳에 있는 명사구에 해당한다는 것을 의미합니다.
- proper : 명사가 고유명사의 일부인지를 나타냅니다.
종속성 트리
‘dependencyTree’ 필드에서는 각 토큰에 대해 해당 토큰이 수식하는 다른 토큰을 식별하며 이 토큰과 헤드 토큰 사이의 구문 관계를 분석합니다. 이는 label필드에 저장됩니다. 그뿐만 아니라 0부터 시작되는 offset 값을 사용하여 단어의 색인을 지정합니다.
‘headTokenIndex’ 필드를 통해 어떤 단어와의 구문 관계를 나타내는지 지칭합니다.
모든 종속성 트리는 문장의 주동사에 해당하는 label : ROOT 요소를 포함합니다. ROOT 단어의 ‘headTokenIndex’는 자신의 색인입니다.
밀당 영어에서는 추가로 데이터를 저장하고 있습니다
- wordId : 분석된 단어를 밀당 영어의 word id를 tagging합니다.
- basicWord : 단어의 기본형을 나타냅니다. 예를 들어 복수형이라면 단수형으로 나타냅니다.
- tokenIndex : 단어 자신의 offset입니다.
아래의 문장의 종속성 트리의 Label들 예시입니다.
아래는 문장을 단어 끼리의 종속성 트리를 밀당영어에서 나타낸 자료입니다.단어의 품사와 종속성 트리를 이용하여 문장의 구조와 단어의 형태를 한눈에 파악할 수 있습니다.
문장의 구조
밀당 영어의 문장 구조는 한 노드가 단어 단위인 트리 형태로 존재합니다. Node의 데이터는 단어의 형태소를 나타냅니다. Edge는 단어와 단어 사이의 구문 관계를 나타냅니다.
구문 분석이 완료된 문장과 트리를 펼친 예시
문장 유사도를 측정하는 이유
다양한 콘텐츠 제공 및 추천을 위해서 문장과 문장 사이의 관계가 필요합니다. 학습자들에게 효율적인 컨텐츠 제공을 위해서는 이미 알고 있는 문법이나, 문장 구조를 제공하는 것보다 알고 있는 문법이나 문장과 비슷한 콘텐츠도 제공해야 합니다. 비슷한 문장이나, 한 문장의 요소를 포함하는 문장들을 구하기 위해서는 문장 유사도를 구할 필요성이 있습니다.
문장 유사도를 통해 문장들 사이의 관계를 나타내고 정형화된 문장 구조들을 기준으로 문장 집단들을 만든다면, 다양한 콘텐츠 제공 및 추천이 가능해집니다.
문장 유사도의 종류
문장의 유사도는 Text와 Structure로 구분하여 구할 수 있습니다. Text에 따른 유사도는 대표적으로 두 문장에서 같거나 다른 단어들의 출현 빈도로 얼마나 유사한지 구합니다.
하지만 Structure는 두 문장의 구조가 얼마나 유사한지 구합니다. 단어가 달라도 품사가 같다면, 유사도는 올라갑니다. 이는 영어의 문법적 요소들이 얼마나 유사한지로 생각할 수 있습니다.
밀당 영어에서는 문장들의 문법적, 구조적 feature를 기준으로 문장 집단을 얻기 위하여 Structure 유사도를 먼저 구하기로 했습니다.
트리를 어떻게 비교하는가
종속성 트리는 많은 정보를 담고 있습니다. Node 사이의 종속 관계, ROOT로부터의 거리 등 고려해야 할 데이터들이 많습니다. 그중에서 가장 중요한 데이터로 효율적으로 사용해야 합니다.
예를 들어, Tree를 문자열로 나타내어 비교하는 방식이나, 두 트리에서 단어들의 교집합을 구하고 벡터 형식으로 나타낼 수도 있습니다.
저희가 비교하는 트리는 구문 분석으로 Node(단어)들의 종속성과 특성이 들어간 트리입니다.
따라서 단어와 단어 사이의 종속성을 비교하고, 단어의 특성(품사)을 비교해야 합니다.
유사도 알고리즘 선택
Node mapping
단어 하나하나가 어느 단어에 종속되어 있는지, 단어의 형태소는 무엇인지, 그 단어가 위치하는 곳을 비교합니다.
밀당 영어의 저장된 문장의 데이터 중 단어의 label과 parent의 label 그리고 트리에서의 level를 단어 하나의 데이터로 처리합니다. 하나의 트리는 이러한 노드 데이터의 배열입니다. 두 트리에서 동일한 노드들의 수를 기준이 되는 트리의 노드 수로 나누어줍니다.
이 방식은 Google Natural Language API에서 추출한 데이터를 사용합니다. 데이터 전처리 과정은 단어들을 트리 구조로 나타내고 비교할 수 있는 배열로 변경하는 것입니다.
과정 및 결과
아래 두 문장을 예시로 비교합니다. 비교는 두 문장에 대해 양방향으로 비교합니다.
두 문장을 트리로 나타내면, 아래와 같습니다. 노드들이 같은 Level인지 같은 부모를 가지고 있는지, 같은 Label인지 비교합니다.
ROOT을 부모로 가지는 label : ATTR, P, NSUBJ가 모두 같은 Level에 있습니다. 추가로 두 번째 Level에도 같은 부모를 가지고 같은 label을 가지는 노드(DET)가 있습니다.
첫 번째 문장의 구조가 확장된 경우가 두 번째 문장이므로 첫 번째 문장은 두 번째 문장에 대해 100% 일치합니다.
반면에 두 번째 문장은 ROOT을 제외한 총 6개 노드 중 4개의 노드만 첫 번째 문장과 일치합니다. 따라서 66.67%의 유사도를 가지게 됩니다.
추가적인 예시
이항 분기 거리
이진 트리로 변환
간단한 트리로 예시를 들어보겠습니다.
- 임의 노드의 첫 번째 자식은 노드의 왼쪽 자식으로 그려줍니다.
- 임의 노드의 바로 옆 형제 노드는 노드의 오른쪽 자식으로 그려줍니다.
모든 노드에 대해 위와 같은 과정을 반복합니다.
일반 트리에서 이진 트리로 변환 후 단어 하나가 어떤 단어들과 연관되어 있고, 어디에 위치되어 있는지 비교합니다.
이진 트리에서의 노드 하나의 데이터 세트
[ label, left label, right label, preorder position, postorder position ]으로 나타냅니다. 각각 자신의 노드와 자식 노드 그리고 전위, 후위 순회를 돌았을 때의 좌표를 나타냅니다. 노드의 위치를 일반 트리보다 비교적 정확하게 알 수 있습니다.
preorder position, postorder position
Tree traversal 기법을 사용하여. 방문 순서로 노드의 위치를 알 수 있습니다. 전위 순회와 후위 순회를 사용하여 2차원 위치 좌표로 나타내었습니다.
비교 방식
두 트리의 데이터 세트가 포함되는지 아닌지에 따른 요소값을 트리 당 1차원 벡터로 나타냅니다.
먼저 두 트리의 속성들을 합쳐준 후 각각 벡터로 나타냅니다.
두 트리를 모두 포함한 1차원 배열에 대한 두 개의 1차원 벡터가 존재합니다. 두 벡터의 차를 구하여 유사도를 나타낼 수 있습니다.
이항 분기 거리의 단점
기존의 존재하던 노드 사이의 정보가 이진 트리로 변하면서 손실이 발생할 수 있습니다. 또한 일반 트리에서는 하나의 단어를 제외하면 유사도가 100%인 문장들을 이진 트리로 변환할 시 하나의 단어 때문에, 모든 노드의 위치 좌표가 바뀌게 됩니다. 따라서 너무 정확한 위치를 구하려다가 오히려 정보를 놓치게 되는 일이 발생합니다.
아래의 두 이진 트리가 있습니다. 이 두 트리는 ATTR 노드를 제외하면 100% 동일한 트리가 될 것입니다. 하지만 하나의 노드가 추가되어 20~25%의 유사도를 나타냅니다.
1.'The sun rises'
Nodes = [ROOT, 1, 4], [NSUBJ, 2, 3], [DET, 3, 1], [P, 4, 2]
2. 'Another cause is humans.'
Nodes = [ROOT, 1, 5], [NSUBJ, 2, 4], [DET, 3, 1], [ATTR, 4, 3], [P, 5, 2]
Tree to string
일반 트리나 이진 트리의 데이터를 문자열로 변환한 뒤 두 문자열이 같은지 비교하거나 Levenshtein Distance를 사용하여 유사도를 측정하는 방법입니다.
먼저 트리를 문자열로 변환하는 방법에는 많은 방법이 있습니다.
Leaf node를 제외한 node들을 자식 수 만큼 나열하는 NPS, LPS 방법과 node와 children을 순차적으로 나열하는 ENPS, EPS, INPS, IPS 방법이 있습니다.
NPS : Leaf node의 parent를 index를 순서대로 나열합니다.
LPS : NPS방식에서 index대신 Node의 데이터가 들어갑니다.
ENPS: 순서대로 자기 자신과 parent의 Index를 나타냅니다.
EPS: ENPS방식에서 Index대신 Node의 데이터가 들어갑니다.
실제로 사용한 방법은 IPS방법을 변형한 방법을 사용하였습니다. 아래와 같은 문장 구조 트리가 있습니다. 저희는 Node mapping에서 사용했던 데이터를 기반하여 문자열로 변환하였습니다. 바로 노드의 Level, Label, 종속성입니다. Level 0부터 노드의 Label과 자식을 문자열 형태로 나타냅니다.
예시
같은 Level의 Node의 Label과 children을 나열하는 기준은 오름차순입니다. 아래와 같은 문자열로 변환됩니다.
모든 트리에 포함되는 ROOT를 제외한 나머지 노드를 Level과 Parent를 기준으로 나열합니다.
Root 즉 Level 0의 자식인 PREP와 TITLE을 먼저 나열합니다.
그 후 Level 1의 PREP를 나타내고 그의 자식을 나열합니다(오름차순). TITLE과 POBJ 노드 또한 마찬가지입니다.
tree_str = 0PREP TITLE 1PREP POBJ 1TITLE NUM 2POBJ AMOD
위와 같이 변환된 문자열을 가진 문장들을 그룹화하면, 밀당 영어의 문장 구조를 한눈에 파악할 수 있습니다. 그룹화는 문장 구조를 기준으로 같은 문장의 ID로 묶습니다.
아래와 같이 그룹화된 JSON으로 저장됩니다.
문장 그룹화 결과
현재 밀당 영어에서 학습에 주로 활용되는 핵심 문장의 개수는 32만여 개입니다.
이 중 총 발현된 문장 구조의 수는 157,384개입니다.
뚜렷한 문장 구조를 구하기 위해 동일한 문장 구조를 가지는 문장이 10개 이상인 문장 구조를 보면, 전체의 0.7% ( 1,116개 )입니다.
그리고 103,067개 ( 65.4% )는 동일한 구조를 가진 문장이 하나만 존재하는 독립적인 문장 구조입니다.
문장 그룹화의 문제점
결과를 살펴보면 문장이 하나만 존재하는 그룹이 무려 65.4%를 차지합니다. 이는 그룹화가 아니라 분류입니다.
만약 이대로 문장 구조를 학습자에게 제공을 한다면, 학습자가 밀당의 모든 문장 구조를 학습하기 위해선 최소 65.4%는 하나의 문장으로 해당 구조를 학습해야하고, 전체 문장 구조를 모두 학습하기 위해선 15만여개의 그룹을 학습하여야합니다.
문장 구조는 단어가 아닙니다. 현재의 문제를 단어의 관점으로 살펴보면 ‘see’라는 단어를 배울 때, ‘saw’, ‘seen’과 다른 단어라고 배우는 것과 같습니다.
5형식 문장 구조를 예로 든다면
Tom allows friends to visit him과 Let’s call me Jay는 같은 형식이지만 다른 구조라고 하는 것과 같습니다.
Solution
해결 방안은 문장 구조를 유사도에 따라 군집화 하는 것입니다.
문장 그룹화는 정형화 되어있는 영어의 특정 형식을 구하는 것보다, 더 복잡한 문장 구조들의 관계를 나타냅니다.
해당 군집의 문장 구조는 군집 내에서 가장 기본 단위의 구조가 될 것입니다. 기본 단위의 구조를 학습하면 해당 구조에서 파생된 다른 문장 구조들을 학습자에게 제공할 수 있습니다.
그렇다면, 학습해야하는 전체 문장 구조의 절대적인 양은 감소하여 학습에 따른 성취도가 더욱 향상될 것입니다. 또한 하나의 문장 구조에 대해 얼마나 학습 했는지 나타낼 수 있습니다.
결과
두 문장을 살펴보면, ‘the’와 ‘his’의 Label을 제외하고는 모두 동일합니다. 비교 방식에 따라 유사도에 어떤 차이가 있는지 살펴보겠습니다.
Chefs add a new dish to the menu.
I saw a new computer in his room.
Binary — children
이진 트리 비교 방식 중 Root을 포함한 노드의 Label, Children을 비교합니다. 위 두 문장 중 다른 점은 the와 his이지만, 두 단어를 자식으로 두는 단어까지 비교하면 두 문장 중 다른 부분은 the menu와 his room입니다.
따라서 7/9 * 100 = 77.8%의 유사도를 나타냅니다.
Binary Distance( BRV )
두개의 Binary 비교 방식을 합친 방식입니다. 같은 Label 및 Children을 가지고 있어도 노드의 위치가 다르면 결과에 반영하지 않는 방법입니다. 결과를 살펴보면, 자식과 위치를 모두 고려했을 때 다른 노드는 his room, the menu입니다.
따라서 결과는 77.8%의 유사도를 나타냅니다.
Node mapping
Root 노드를 제외한 두 트리의 노드를 비교합니다. 두 문장 모두 8개의 노드 중 7개는 동일하다는 결과가 나오므로
7/8 * 100을 통해 87.5%라는 결과가 나옵니다.
Binary — pre, post
이진 트리 비교 방식 중 Root을 포함한 노드의 Label, 위치를 비교합니다. Root을 포함하면 총 노드의 개수는 9개입니다. 노드의 위치는 모두 동일하지만, 하나의 노드의 Label이 다르므로
8/9 * 100 = 88.9%의 유사도를 나타냅니다.
최종적으로 선택한 방법
저희는 Node mapping과 Tree to string을 사용하였습니다. Google Natural Language API의 데이터를 최대한 활용하면서 효율적으로 유사도를 측정하는 방법과, Tree를 문자열로 변환하여 같은 구조를 가지고 있는 문장끼리 그룹화를 하였습니다.
문장 구조를 설립하려면, 전제 문장의 구조를 모두 파악하고 같은 구조를 가진 문장의 ID를 가지고 있어야합니다. 따라서 문장 구조가 같은 것끼리 그룹화 하는 방법으론 Tree to string을 사용하였습니다.
앞으로의 방향성
그룹화를 개선된 방향으로 모두 마친다면 학습한 문장을 통해 어떠한 문장들을 학습할 수 있고, 더 높은 난이도의 문장을 학습하기 위해서 필요한 다른 문장들을 추천해줄 수 있습니다. 또한 학습자에게 필요한 문장이 가장 많은 콘텐츠를 제공할 수 있을 것입니다.
예를 들어 문장 구조 A, B, C를 학습한 학생은 D 문장 구조를 해석할 수 있을 것입니다. 혹은 A, B 문장 구조를 학습한 학생에게 D 문장을 추천해줄 수 있을 것입니다. 만약 D 문장 구조가 해석이 안된다면, C 문장 구조를 추천해줄 수 있을 것입니다.
데이터 팀에서 동료를 찾고 있습니다!
밀당 영어가 최근 급성장하여 에듀테크 유니콘이 되기 위해 새로운 시스템을 개발하고 있습니다. 데이터를 바탕으로 학생의 상태를 명확하게 파악하고 학습의 효율을 높이기 위한 다양한 연구를 하고 있습니다. 새로운 도전을 즐기시는 분들과 함께 하면 교육의 혁신을 더욱 빠르고 멋지게 이룰 수 있을 것 같습니다!
Reference
Efficient Similarity Search for Tree-Structured Data( Guoliang Li, Xuhui Liu, Jianhua Feng, and Lizhu Zhou) : July 2008
Similarity Evaluation on Tree-structured Data( Rui Yang Anthony K. H. Tung ) 2005
Google Cloud Natural Language — 형태론 및 종속성 트리
