세미나 필기 | 2020년 10월 28일 Sequence Prediction with Memoization

지난 주는 중간고사 주간이어서 세미나가 없었다.

이번주는 카이스트 나오신 포스텍 컴공과 김동우 교수님의 세미나이다.

머신러닝 주제라서 좋다.

나는 오늘 세미나로 임성빈 교수님 얼굴 처음 뵀다...

(임교수님은 우리 학교 에타 네임드시다... 심지어 담당 애완견도 있으심...)

>교수님 애완견의 모습

아무튼 필기 시작

캡쳐한거 다 저작권 김동우교수님께 잇ㅆ음

(Discrete) Sequence modeling

DNA나 말 같은 거

From HMM to RNN: State transition approach

은닉 마르코프 모델이나 recurrent NN 등이 있는데 이들은 underlying state가 있다는것이 특징이다

Example: HMM for behaviour sequence prediction

Rainly, Sunny가 은닉상태가 되는 것. 이러한 은닉상태에 기반하여 결정을 내리게 된다.

그런데 문제는 이들 모델은 long term dependency는 딱히 신경쓰지 않는다.

그래서 LSTM이나 DGRU를 쓰기도 하지만 아주 긴 롱텀 의존성은 X

Part 1: Sequence prediction

진짜 세미나 페이스 개빨라 필기를 할수가 없다

Discrete sequence prediction:

Given a sequence of discrete symbols y1, ... yn-1 where y ㅌ Y and |Y|=m, predict the next symbol yn

보케뷸러리에 포함된 심벌들의 시퀀스가 주어졌을 때 그 다음 심벌이 무엇일지를 예측하는 것

시퀀스들은 반복된다고 생각할수 있으니까 예측이 가능하다

Motivation: repeating subsequences

섭시퀀스가 반복되는 경우가 많다. 예를들면 음악에서 반복되는 훅, DNA에서 자주 반복되는 섭시퀀스 등

반복되는 섭시퀀스를 가지고 장거리의존성을 반영한 예측 어케 할것인가 가 문제

Motivation: Motif

Motifs: frequently occurred subsequences

모티프 M1++++ 과 M2--+가 있다고 하자

y = ++++--+---++++가 있다고 할때 y=M1M2-M2M1인데

1. 이들 모티프를 사용하여 다음 심벌을 어케 예측하는지?

2. 시퀀스에서 이러한 (쓸만한) 모티프를 어떻게 알아보는가?

가 문제이다

How to predict the next using motifs?

y = ...---++ 이고

M1 = ++

M2 = -+-

M3 = ++-

M4 = -+++

M5 = ---

이면 이걸 가지고 그 다음 심벌 어케 구하는지???

시퀀스의 "suffix"를 고려한다. 시퀀스의 서픽스를 프리픽스로 가지고 있는 모티프를 찾으면 된다. 예를 들면 y의 서픽스 -++를 M4가 프리픽스로 가지고 있으므로 그 다음 심벌은 +가 된다고 예측할 수 있다

그러나... 어디부터를 서픽스라고 할것인지...??

y의 서픽스의 길이를 어떻게 구할지??? 길이 1의 서픽스를 고려한다면 M1이 답이 되고 길이 2의 서픽스를 고려한다면 M3이 답이 되는데... 그럼 매칭되는 모티프는 M1, M3, M4로 3개가 된다. 이 경우 각각 이어질 심벌은 +, -, +로 예측 결과가 다 다르다. 큰일이 난 것이다...

Introducing score of motif

그래서 점수 함수를 도입한다.

예를 들면 점수 함수를 g(.)라고 할 때 g(M1)=3, g(M2)=-1라고 치는 것이다.

예측되는 결과가 +라면 양수 점수, -라면 음수 점수인 걸로 한다.

그러면 M1 M3 M4를 예측했으니까 최종 결과는 sign(g(M1)+g(M3)+g(M4))가 된다.

(근데 이 점수는 어케 정하는거지?)

Is exact matching enough?

다 똑같은데 중간에 한 심벌만 다른 모티프가 있다면 어떨까?

10개 심벌짜리 모티프 중에 1개 빼고 다 맞는다고 치면 엄청 비슷하니까 그냥 쓰면 안되나?

이런것까지 어떻게 고려하면 좋을까?

Modified prediction rule

Prediction function with approximate motif matching

^yt = sign(sum(w(k)g(M) for M in all motifs)

w(k)는 뭘까? 바로 모티프와 서픽스 사이의 Hamming distance이다.

How to find good motifs?

(=what is a good score function?)

We can use any motif. We only need to assign small score for irrelevant motifs

--> Let's use all observed suffixes to construct cadidate motifs.

Then, how to find the good score/?/??

Online learning algorithm

1. empty motif set /M/={}

2. round t=(1,T): predict yt.

    - correct: go to next symbol

    - wrong: compute loss ( w(k)g(M)의 합에 비례)

        * add all possible suffizes of current sequence into motif set /M/

        * reduce a sccore of matched motif if true sumbol is negative, o.w. increase score.

=> 손실의 크기에 비례하여 점수를 조절하게 된다. (이해못함)

How to save and retrieve motifs: Suffix Tree( ST)

최대 길이 n의 모티프가 있다고 하면, worst case에서 2^n가지 모티프가 존재한다.

그래서 suffix tree 데이터 구조를 사용을 한다.

나는 데이터구조를 C인가 D인가를 맞았다. 그래서 일단 이해를 포기한다.

매칭, 인서션 컴플렉시티에서 장점이 있다는 것 같다??

Limiting depth of suffix tree automatically

그래도 우리가 심벌을 많이 관측할수록 서픽스 트리의 깊이가 리니어하게 증가하니까 문제가 된다.

그래서 서픽스 트리를 퍼포먼스가 개런티되는 한에서 truncate하는데, 언제 그러냐면 ...

요런 것들은 안전하게 빼낼 수 있다.

Theoretical result: loss bound analysis

Error bound against optimal suffix tree

큰일났다 수학이 나오기 시작했다 이해가 안 간다

[KW18] 이라고 되어있는데 리퍼런스인것같으니 나중에 원본이 뭔지 찾을 수 있다면 첨부하겠다

contributions - aPST

기존의 방식을 활용하기는 하지만, 은닉상태가 없는 모델이다.

Limitation of aPST: Insertion, Deletion

모티프와 서픽스의 차이가 해밍 디스턴스로 측정되기 때문에 길이가 같은 모티프와 서픽스만 측정할 수 있다. 인서션이 있는 등의 경우는 비슷한 시퀀스여도 측정안됨

Edit distance

그래서 에딧디스턴스를 쓸 수가 있는데, 에딧디스턴스는 한 시퀀스를 다른 시퀀스로 바꾸기 위해 최소 몇 번의 인서션 딜리션 섭스티튜션이 필요한지이다.

해밍디스턴스의 단점을 극복할수가 있다

또한 각각의 (인서션, 딜리션, 섭스티튜션) 오퍼레이션에 대해 다른 cost를 적용할 수도 있다.

How to compute edit distance

방금 동적 프로그래밍이라는 단어가 들렸는데 나는 알고리즘 A+ 맞았으니까 잠깐 안들어도 될것같다 (동적 프로그래밍이 뭐였는지 기억도 안나지만)

뭔가 재귀적으로 정의됐나본데 ... 궁금하면 나중에 위키피디아한테 물어보자

음.. 예시 하나도 이해 못했어... 음음... 좋아...

아무튼 edit distance table을 사용하여 sequence prediction을 할수가 있다고 한다...

Limitations of edit distance

context-sensitive하지가 못하다.

예를 들어 DNA에서 CATGCC 뒤에 C를 붙이는게 물리적으로 CATGCT 뒤에 C를 붙이는것보다 쉽다고 치자. edit distance로는 이걸 고려할 수가 없다.

Neural-net as a function approximator

뉴럴넷이란 결국 function estimator이다 ㅇㅇ

MotifNet: Generalised edit distance

아까부터 영국식 철자법을 쓰시는데 혹시 영국인이신가

아무튼 아까 나온 에딧디스턴스를 약간 제네럴라이즈 해서 비슷한 함수를 사용하여 뉴럴넷을 만든다.

Edit Tree

에디팅 자체의 시퀀스를 트리로 만든거 딱 보면 감올것임

이걸... 어떻게 사용했다는 건지는 전혀 이해하지 못했음

Experiments

암튼 4가지 심벌릭 음악 데이터셋으로 MotifNet을 훈련하였다

Contributions - MotifNet

aPST를 제네럴라이즈한거다.

아직도 45페이지 중에 31페이지까지밖에 못왔다 나는 지금 광치료기에 의지해서 간신히 깨어있다 어제 4시간 자고 월요일에 2시간 잤기 때문이다 잠 깨겠다고 커피 2잔 루이보스 1잔을 마셔서 지금 화장실도 몹시 가고 싶다

Open question: Memoisation as new ML paradigm

메모이제이션이 뭐더라... 나는 알고리즘 A+ 받았지만 사실 교수님이 학교 뜨기 직전 학기라서 A+을 뿌리고 가셨다 그래서 나는 사실 알고리즘을 못한다 게다가 오픈북 시험이었어

아무튼 메모이제이션 impractical하다고 판명됐지만 뉴럴넷도 과거에 impractical하다고 여겨졌었다

GPU가 발달하면서 NN도 같이 발달했으니까 메모이제이션도 새로운 파라다임이 될 수 있다고 생각하신다

그리고 시퀀스뿐만 아니라 그래프 모티프도 적용할 수 있지 않을까? 하는 거 같음

32페이지인데 세미나가 끝났는데 그 뒤는 어플리케이션이고 시간이 모자랄거같아서 안하신다고 하심

사실 궁금한데... 아쉽긴 하다

이 시점에서 임성빈교수님께 전화가 왔다...

(참고로 울 교수님은 수업하다가 전화오니까 전화선 뽑아버리심 진짜 화끈하고 멋있다 ♡)

Q&A

그래프 모티프는 아직 구상 단계이고 구체적인 알고리즘같은게 나온 단계는 아니라고 하심

필기끝!