IR Chapter2 Modeling - 1

전형적인 정보 검색 시스템은 문헌을 색인하고 검색하기 위해 색인어를 사용한다.
색인어는 명사들로 이루어진 키워드(연관 용어들의 집합)라고 할 수 있지만, 일반적으로 텍스트 내에 나오는 어떠한 단어들도 색인어라고 불리울 수 있다. 색인어를 사용한 검색은 문헌의 의미와 사용자 정보 요구가 색인어 집합을 통하여 자연스럽게 표현될 수 있다는 생각에 근거하고 있다. 이 색인어를 이용한 검색은 간단하지만, 크게 2가지 문제를 야기한다.
1) 문헌 또는 사용자 요구의 많은 의미가 단어 집합으로 바뀌면서 그 의미의 상당 부분을 소실하기 때문에 문제의 과도한 단순화라는 문제를 일으킨다. 실제로 웹 검색의 결과들이 적절한 질의 형성을 하지 못하는 사용자의 경우에 상당히 불만족스러워하게 되는 예들은 자주 보는 현상이다.
2)또 다른 문제는 어떤 문헌이 연관된 것이고 어떤 문헌이 비연관된 것인가를 예측하는 문제로서 소위 랭킹 알고리즘(검색된 문헌을 순서화하는 순위 작업)과 관계된 것이다.

정보 검색은 크게 축적(ad hoc)과 여과(filtering)로 분류할 수 있다.
전형적인 정보 검색 시스템에서는 새로운 질의가 들어와도 시스템 내부에 축적된 문헌들은 상대적으로 변함이 없는데 문헌을 축적하고 이에 대해 검색 결과를 보여주는 시스템을 ad hoc이라고 부른다.
여과 작업은 사용자의 질의가 상대적으로 정적이고 새로운 문헌이 시스템에 들어왔다 분배되는 동작 모드를 말한다. 이 여과 작업을 위해서는 사용자의 기호도를 기술한 사용자 프로파일(user profile)이 만들어지고, 새로 입력된 문헌을 이 profile과 비교하여 특정 사용자의 관심 사항과 연관된 문헌을 제공한다. 이 선택된 문헌들의 순위까지고 제공하는 filtering의 변형을 routing이라고 부른다. 일단 여과 작업에서 가장 중요한 부분은 순위화가 아니라 사용자 기호에 근거한 프로파일 작성 부분이다. 이 프로파일을 효과적으로 작성하기 위한 방법으로 사용자로 하여금 직접 키워드 집합을 쓰게 하기도 한다. 그러나 새로운 관심 영역에서 적절한 키워드를 알기는 어렵기 때문에 좀더 정교한 방법으로 제시되는 방법은 먼저 사용자가 관심 키워드 집합을 작성하고 이에 연관된 문헌들이 제공됬을때 실제로 관련이 있는지에 대한 정보를 피드백해 주는 것이다.

정보 검색 모델은 순위 결정 알고리즘에 따라 분류된다. 정보 검색 모들은 다음과 같은 특성으로 정의된다.
정의
정보 검색 모델은 다음과 같은 /D, Q, F, R(qi, di)/ 4개의 구성 요소로 정의된다.
(1)D : 소장된 문헌에 대한 논리 표현의 집합
(2)Q : 사용자 정보 요구에 대한 논리 표현의 집합인 질의. 즉, Query.
(3)F : 문헌 표현, 질의와 이들의 관계를 모델링한 틀
(4)R(qi, di) : D와 Q의 원소인 질의 qi, 문헌 dj를 연관시켜 주는 순위 결정 알고리즘.
모델을 정의하기 위해서 우선, 문헌과 사용자 요구의 표현을 고려해야 하며, 이 표현이 결정되면 이들을 모델링할 틀을 구상한다. 이틀에서는 순위화 함수가 포함되는데, 예를 들면 전통적인 불리안 모델에서는 문헌집합과 표준적인 집합 연산자로 구성되며, 전형적인 벡터 모델에서 이 틀은 t 차원의 벡터 공간과 벡터 계산을 위한 표준 선형 대수 연산자로 구성되고, 확률 모델은 집합, 표준 확률 연산과 베이즈 정리로 구성된다.

IR Chapter 1

웹을 이용한 사용자의 작업은 크게 2가지로 볼 수 있다.
검색과 브라우징이 그것이다.
검색이란, 사용자 질의를 통해 웹 상의 연관된 문헌들을 찾는 작업을 말한다.
브라우징이란, 빈약하게 정의된 그러나 내재적으로 광범위한 관심을 가진 경우 문헌 집합이 사용자의 기호에 따라 이리 저리 튈 수 있는 것을 얘기한다. 예를 들면 축구에 관심있는 나는 축구라는 검색어를 시작으로 브라질 축구 교실에 관한 문헌을 읽고, 세계 기행에 관한 글을 읽고, 한비야의 글을 읽을 수 있다. 이러한 초기 목적이 명확하게 정의되어 있지 않으면서 시스템 사용 중에 목적이 바뀔 수도 있는 것이 브라우징이다.

textual affect sensing

text에서 감정을 찾는 방법은 크게 다음의 4가지 방법으로 분류할 수 있다.
Keyword spotting, lexical affinity, statistical natural language processing, 그리고 hand-crafted
model이다. 이 네 가지 방법의 장단점에 대해서 자세히 살펴보자.

1.Keyword spotting
Keyword spotting 방법은 감정을 분명하게 드러내는 단어들(예를 들면 happy, sad같은)을 text에서 찾아내고 이를 통해 text에 담겨진 감정을 찾는 방법이다.
이와 관련한 연구 중에 Elliot's affective Reasoner라는 연구가 있었다. 이 연구에서는 198개의 강한 감정이 드러나는 단어들을 정의하고 extremly, somewhat같은 정도를 나타내는 단어와 did that, wanted to같은 힌트나 근거가 담긴 말들을 찾아 text의 감정을 분석한다.
다른 연구로는 Ortony's affective Lexicon이라는 연구가 있었다. 이 연구에서는 자주 사용되는 감정언어들을 그룹화하였다.
이런 Keyword spotting 방법은 다음과 같은 두가지 문제를 안고 있다.
첫번째는, 부정이 포함될때 인식하기 어렵다는 점이다.
예를 들면, I am happy라는 말은 행복하다고 인식하지만
I am not happy at all. 같은 말은 인식이 용이 하지 않다는 점이다.
특히 우리나라 말처럼 부정의 말이 여러 방법으로 사용되는 경우엔 더욱 어려울 수 있다.
두번째는, 두드러진 감정 언어가 실제 text의 감정이 아닐 수도 있고, 두드러진 감정 언어를 사용하지 않고 감정을 표현하는 문장이 많다는 점이다.
예를 들면 '동생은 나에게 화해를 원했지만, 나는 기쁘게 법정으로 향하기를 결심했다.'라는 문장은 고소의 대상이 누가 되느냐에 따라 감정의 해석은 천차 만별이 될수 있다. 기쁘게 라는 단어는 반어적인 용도로 쓰였을지도 모른다.
이런 문제들을 지녔음에도 불구하고 쉽게 알고리즘을 구현할 수 있고 부담이 없는 장점이 있기 때문에 종종 사용된다.

2.Lexical affinity
Lexical affinity는 임의의 단어에 특정한 감정의 확률적 affinity를 정하는 방법이다.
예를 들면, accident라는 단어는 75% 정도가 negative affect를 가리키는 용도로 쓰인다고 assign될 수 있다. 따라서 이러한 확률적 affinity가 단어마다 미리 정해져야 하는데, 이를 위해 linguistic corpus들로 부터 train되어 진다.
이 방법은 keyword spotting보다 약간 복잡하지만, 조금 향상된 성능을 보여준다.
이 방법 역시 2가지 단점을 보인다.
첫번째는, 순수하게 Lexical affinity를 word-level에서 사용하면, 부정문이나 다른 의미로 사용된 경우에서 오작동을 할 수 있다.
예를 들면, I avoided an accident같은 부정의 의미를 담고 있는 문장에서 적절한 감정을 잡아내지 못한다. 또한 I met my girlfriend by accident 같은 다른 뜻으로 사용된(우연히라는) 경우에 대해서도 적절하게 대처하지 못한다.
두번째는, lexical affinity probabilities가 사용된 source(text)의 장르 등에 의해 bias되는 영향이 있다는 점이다. 이로 인해 domain에 상관없는 모델을 만들기가 어렵기 때문에 재사용 가능한 모델을 개발하기란 대단히 힘이 든다.

3.Statistical Natural Language Processing
Statistical Natural Language Processing은 감정에 대해서 주석이 달린 text들의 corpus들을 이용해 training하는 machine learning algorithm을 이용하는 것이다.
이 방법은 keyword spotting에서 처럼 감정을 명확히 전달하는 단어들의 affective valence(valence는 정도라고 해석하면 될 듯 하다)를 learning하며 lexical affinity에서 처럼 임의의 단어에 대한 valence역시 learning되고 구두점 같은 요소들에 대해서도 learning하여 많은 feature들을 통해 적절한 감정 인식을 수행할 수 있다.
그러나 이러한 statistical 한 방법 때문에 문장 단위의 감정 해석에는 문제가 있다. 적어도 한 문단에서 페이지 단위의 글에서 뽑아낼 수 있을 정도의 정보가 필요하기 때문이다.
이를 이용한 방법으로는 Goertzel's Webmind 프로젝트나 Cellia Ovesdotter의 Emotions from text등을 들 수 있다.

4.Hand-Crafted Models
Dyer와 Schand와 같은 사람들은 affect sensing을 깊은 통찰력에 관한 문제로 보았다. 특히 Dyer의 DAYDREAMER는 affective state를 인간의 필요, 목적, 욕구에 대한 심리학적 이론들을 토대로 hand-crafted model로 모델링하였다. 이러한 모델들은 text 분석에 있어서 깊은 통찰력을 요구한다. 이러한 모델링 방식은 최신의 semantic parsing 기법들이 제공할 수 있는 정보들 보다는 보다 더 깊은 통찰력을 요구한다.

최근엔 이러한 4가지 문제의 접근 방식과는 전혀 다른 방식으로 text로 부터 emotion을 찾아내려는 연구가 있다. Hugo 등이 제안한 A model of textual affect sensing using real-world knowledge가 대표적인 것이다.
이 연구는 글자 그대로, 우리가 알고 있는 상식(common sense)을 통해서 sentence로 부터 emotion을 찾아 내자는 목표를 가진다. MIT에 있던 그들은 MIT내의 ConceptNet이나 Open Mind Common Sense와 같은 프로젝트를 통해서 이와 같은 영감을 가진 것으로 보인다.
먼저 OMCS database에서 Ortony's Affective Lexicon이 밝힌 emotion을 두드러지게 나타내는 단어들을 통해서 emotion grounds라는 subset을 만들어 낸다. 이 단어들은 어떤 문맥에서도 비교적 비슷한 의미를 갖기 때문에 emotion grounds라고 하기에 부족함이 없다는 이유이다.
subset을 만들어낸 이후에는 text로 부터 감정을 뽑아내기 위한 분석을 수행할 수 있는 commonsense affect model이라는 것을 만들어 적용한다. 이것은 commonsense affect model이 서로 경쟁하고 보완하는 모델들의 집합일 수 있을 것이라는 생각에서 나온 것이다.(이 부분의 이해가 약간 석연치 않아 잘못 이해하고 있는 듯 하지만...)이러한 모델들은 공통된 구조화된 entry들을 갖고 있으며, 각각은 다음과 같은 형태의 값을 갖는다. 이 값들은 0.0 이상의 값을 갖는다.
[a happy, b sad, c anger, d fear, e disgust, f surprise]
또한 모델들은 다음과 같다.
1) Subject-Verb-Object-Object Model
예로 Getting into a car accident can be scary를 생각해보자.
->Model ==> Subject : 일반 사람, Verb : get into, Object1 : car accident, Object2 : ...
value ==> 0 happy, 0 sad, 0 anger, 1.0 fear, 0 disgust, 0 surprise
로 된다. 이때 negation은 subject, object, verb의 수식어구로 처리되고 multiple SVOO가 있는 경우는 휴리스틱한 방법으로 가장 적절한 것들만 남기고 나머지는 버린다.
이 모델의 장점은 문장 단위의 event context를 그대로 보존한다는 점에서 정확성 측면의 강점이 있다.
2) Concept-level Unigram Model
3) Concept-level Valence Model

4) Modifier Unigram Model
Moldy bread is disgusting, Fresh bread is delicious와 같은 문장에서 보이는 것처럼, 부사구가 감정을 전달하는데 중요한 역할을 하는 경우가 있다는 점에 주목한 모델이다.

Designing A learning system : Machine learning1 - 2

machine learning한 system을 설계하는 basic design isssue에 대해서 알아보기 위해서
word checker champion을 가리는 tournament에서 우승하기 위한 Machine learning program을
디자인 하는 경우를 생각해보자.

이 경우,
Task T: playing checkers
Performance measure P : percent of games won in the world tournament
Traning experience E : games played against itself.
라는 걸 먼저 염두에 두자.

소기의 목적을 달성하기 위해 먼저 무엇을 해야할까? 즉, 어떻게 해야 많이 이길 수 있을까?
그 이면에는 효과적인 머신 러닝 방법에 대한 고민과 직결되어 있다. 이러한 효과적인 머신 러닝 방법을 디자인 하기 위해서 우리가 고려해야할 것들은 다음과 같다.

1. Choosing the Traning Experience

즉, 어떤 경험을 통해 기계 학습을 한다고 할 때 어떠한 training set들이 효과적일 것인가의 대한 고민을 얘기한다. 또한 이 고민에는 training set을 이용해 기계 학습을 할 때 고려해야 할 것들에 대해서도 고민한다. 예를 들면, 몇 단계 앞의 수까지 고려하게 할 것인가.. 혹은 보드의 처음부터 기계 스스로 배우게 할 것인가 아니면 각 보드의 상태를 설정해 놓고 가장 좋은 수를 찾는 것을 trainig set으로 부터 배우게 할 것인가 등등의 것들까지 training에 관한 전반적인 고민들이 이루어 져야 한다.

2. Choosing the target function

그 다음으로는 우리가 이러한 기계학습을 통해 달성하고자 하는 목표를 design하는 것이다. 즉, checker에 있어서 우리는 게임에서 이기길 원하기 때문에 다음과 같은 형태로 target function을 디자인 할 수 있을 것이다.
만약 b가 이겼을 때의 board 상태를 나타낸다면, V(b) = 100
만약 b가 졌을 때의 board 상태를 나타낸다면, V(b) = -100
만약 b가 비겼을 때의 board 상태를 나타낸다면, V(b) = 0

3.Choosing a Representation for the target function

그 다음으로 우리는 고려해야 할 변인들을 생각하고 그것들을 이용해 target function을 수식으로 나타내야 한다.
예를 들어, board의 승리와 연관되어 있는 변수들로는 다음과 같은 것들이 있다고 하자.
검은 색 지역의 개수, x1
붉은 색 지역의 개수, x2
검은 색 왕들의 개수, x3
붉은 색 왕들의 개수, x4
붉은 색에 의해 공격 받고 있는 검은 색 지역들의 수, x5
검은 색에 의해 공격 받고 있는 붉은 색 지역들의 수, x6
이젠 이러한 변인들을 이용해 다음과 같은 target function을 디자인 할 수 있다
V(b) = w0 + w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6

4.Choosing a Function Approximation Algorithm

그 다음으로 적당한 training set을 이용해 target function의 가중치 값들을 조정하여 target function이 실제 target function과 가깝게 작동할 수 있도록 해야 한다.

5.Estimating training values

그 다음으로 test set을 이용해 target function이 어느정도 정확하게 작동하는지 performance를 체크 할 수 있어야 한다.

6.Adjusting the weights

이후 test set에서의 오류 값들을 고려하여 다시 target function의 weight값들을 보정할 수 있는 단계를 거치게 할 수 있다. 이 경우 보통 LMS 방법을 주로 사용한다.

Machine Learning1

어떤 컴퓨터 프로그램에 있어서.

어떤 종류의 업무 T에 대한,(the class of tasks)
경험들 E를 통하여,(the source of experience)
성능 혹은 성과 P를 향상 시키는 것을(the measure of performance to be improved)

learning이라고 한다.

예를 들면 checker를 하는 컴퓨터 프로그램의 경우,

checker game을 하는 업무에 대해
그 동안의 checker game의 경험을 통해
상대방을 이기는 능력의 정도(횟수)를 향상 시키는 경우를

learning이라 할 수 있다.

일반적으로 well-posed(defined) learning problem하기 위해선,
the class of tasks, the measure of performance to be improved, and the source of experience
이 세 가지를 명확하게 규정해야 한다.