[SCFG]. ContextFreeGrammar의 확률버젼.

seqeunce들의 모델로 StochasticContextFreeGrammar를 쓸수 있다. Stochastic Grammar를 쓰는 것은 단지 BiologicalSequenceAnalysis를 위한 유용한 확률 모델링 시스템을 만드는데 있어서의 첫 번째 step 일 뿐이다. [HMM] 에서와 같이, 우리는 다음의 세가지 문제를 처리하는 algorithm이 있어야 한다.

1. Parameterised stochastic grammar 에 대한 sequence 의 optimal alignment 의 계산 (alignment problem)
2. 주어진 parameterised stochastic grammar 에 대한 sequence 의 probability 계산 (scoring problem)
3. sequence/structure 의 예제 set 이 주어졌을 때, unparameterised stochastic grammar 의 optimal probability parameter 들의 estimate (training problem)

Normal forms for stochastic context-free grammars

촘스키 normal form 은 모든 CFG production rule 이 의 형태일 것을 요구한다. 어떤 CGF 도 non-conforming rewriting rule을 추가적인 nonterminal 을 사용하여 normal form production 의 series 로 확장함으로써 촘스키 normal form 으로 고쳐 쓸 수 있다.

The inside algorithm

촘스키 normal form에서 SCFG 에 대한 InsideOutsideAlgorithm은 당연히 [HMM]에 대한 ForwardBackwardAlgorithm과 상대적이 된다.

InsideAlgorithm 의 best path variant 인 Cocke-Younger-Kasami (CYK) algorithm은 [HMM]에서의 ViterbiAlgorithm 과 같이, sequence 에 대한 SCFG 의 maximum probability alignment를 찾는다.

InsideAlgorithm 은 모든 (symbol에 대한 index) 와 (nonterminal 에 대한 index) 에 대해서 subsequence의 nonterminal 에서 root한 parse subtree 의 확률을 계산한다.

The OutsideAlgorithm

OutsideAlgorithm 은 모든 (symbol 에 대한 index) 와 (nonterminal 에 대한 index) 에 대해서 nonterminal에서 root한 subsequence 에 대한 모든 parse subtree 제외하고 start nonterminal 에서 root 한 complete ParseTree의 확률을 계산한다.

참고> state 가 사용된 경우를 두가지 경우로 생각해 볼 수 있다.

1. 이 안에서 alignment 가 이루어지는 경우 : inside
2. 이 안에서 alignment 가 이루어지지 않는 경우 : outside ( 왼쪽으로 벗어난 경우 / 오른쪽으로 벗어난 경우)

Parameter re-estimation by ExpectationMaximisation

Inside변수인 와 outside 변수인 는 EM 에 의한 [HMM]의 training 에 있어 forward, backward 변수를 사용한 것과 같이, ExpectationMaximisation 에 의해서 [SCFG]의 probability parameter를 re-estimate 하기 위해 사용되어질 수 있다.

The [CYK] alignment algorithm

남은 문제는 sequence 에 대한 optimal parse tree (alignment)를 찾는 것이다. 이것은 "+"을 "max" 연산으로 대신한 InsideAlgorithm 의 변형인 [CYK] algorithm으로 해결된다.

ViterbiAlgorithm이 [HMM]에 대한 [EM] training algorithm 의 근사치로 사용될 수 있는 것과 같이, [CYK] 는 inside-outside training 의 근사치로 사용될 수 있다.

Summary of SCFG algorithms

InsideOutsideAlgorithm과 [CYK] Algorithm을 사용해서, [SCFG]는 [HMM]과 같이 full probabilistic modelling system 으로 사용될 수 있다.