BioinformaticsTheMachineLearningApproach Chap 3.

• Probabilistic Modeling and Inference: Examples

The Simplest Sequence Models

single coin flip : single parameter p

• string data {H,T}

->DNA sequnce의 경우 : we shall move directly to more complex version with four letters

The Single-Die Model with Sequence Data

* 가정: the strings have been obrained by independednt tosses of the same four-sided die (fig 3.1)

* Likelihood

• length N을 가진 single observation seq 의 Data ={ O } with O = X^1...Xn and X^i ∈ A

  P(D|M) = ∏ pX^{nX (X∈A) = pA}(nA)pB^(nB)pC(nC)pD^(nD) nX : the number of times the letter X appears in the sequence O log P(M|D) = - ∑nX log pX (X∈A) - log P(M) + log P(D)

* MAP parameter estimation

• uniform prior distribution 을 가정한 경우 ML ParameterEstimation problem 과 동일. L= - ∑nX log pX(X∈A) -λ (1-∑pX) 이는 negative 값인데, normalizing constraints를 통해서 증가하게 된다. 이를 막기 위해서 partial derivate 인 ∂L/∂pX 값을 0으로 두어서 계산하면, pX = nX/ λ 이 되고, normalization constraints 를 사용하면 λ= N , 따라서 Px* = nX / N for all X∈A

* entropy 로의 확장

• the valure of the negative log-likelihood per letter을 구하는 이전 공식에서 Px* 를 nX / N 로 대체하면 RelativeEntropy H(P*)를 구하는 식과 동일해진다. (3.5) - pX : fixed die probability

  • nX / N : the observed frequencies

* not uniform prior인 경우

• DirichletPrior Dαq(P) 를 사용하면 (3.6)과 같은 식이 나온다. 이는 (2.13)식을 log 로 변형시켜 (3.2) 식에 대입하면 나온다. Z는 pX 에 독립적인 normalization constant이다.

  ParameterEstimation 과정을 동일하게 수행하면 (3.7)과 같은 식이 나온다. In particular, Dirichlet prior는 관찰된 count에 pseudocount를 더하는 것과 동일한 효과를 가진다. - uniform한 Q 인 경우, Dirichlet prior는 symmetric 하다고 할 수 있다.

  • 이 때 qX = 1 / α = 1/ |A| 인 경우 p(M|D) 는 DβR ( with β= N + α and rX = (nX + αqX)/(N+α) )

  -> rx로 인해 alternative estimate for pX 값인 the predictive distribution or MP (mean poterior) estimate 를 구할 수 있다. (3.8)

  • 이는 특별한 경우에 expected relative entropy distance를 최소화시키기도 한다.

* Evidence P(D)

• - single DirichletPrior 인 경우 (3.9) 식이 가능

  • 이것은 (2.13)식의 DirichletDistribution의 적분형과 비슷, 계산하면 (3.10)식이 나온다.

  • -> the ratio of the normalizing constants of the prior and posterior distributions

* mixture of DirichletDistributions (3.11)

• - Prior Distribution : a mixture of conjugate distributions - Posterior Distribution : a mixture of conjugate distributions

The Single-Die Model tiwh Counts Data

• with the same die model, assume that available data consists of the counts themselves, D = {nX}

* Likelihood (3.12)

• 이 때 count nX의 distribution을 MultinomialDistribution 에 속하며 이항정리를 일반화할 수 있다. With little abuse, die model 자체가 Multinomial model 이기도 하다..

* MAP and MP estimates

• Dirichlet Prior DαQ(P) on the parameter vector P, Dirichlet Posterior DβR 이 모두 [1.1]의 모델과 동일. 따라서 MAP and MP estimates 도 동일

* Distribution : that a fixed ventor P induced on the counts nX

• - taking the logarithm of Likelihood(3.12) and using Stirling's approxmation formula for factorials (3.13)
  • n! = (n/e)^n √2πn
  - log ( P(D|P)= C- H(nX!N, pX)
  • C : nX에 독립적인 constant

    H : 경험적으로 얻은 entropy 와 P 사이의 the Relative Entropy

  - Entropic distribution

  • P가 uniform 경우(constant term 제외), nX(가능한 histogram의 모든 space)에 대한 Entropic Distribution을 유도. Entropic Prior를 이용하여 나오는 MaxEnt principle에 대한 standard justification의 하나이기도 .

* exercise

• - P is entropic prior

  • - nX에 대한 the posterior is not entropic, nor Dirichlet - entropic distribution is not the conjugate of a multinomial - MAP estimate is still of the form pX* = nX / N

* simple die model의 활용

• - This can be viewed as a first step in an iterative modeling process, and therefore the performance of subsequent models must be evaluated with respect to the first-order model. - can be extended by having strings of letters on each face.

The Multiple-Die Model with Sequence Data

조건: gap을 가지고 있는 N length를 가진 K 개의 sequence

• 정해진 순서로 N개(or N times )의 dice를 던져서 각 position의 letter를 만들어낸다. pXi : probability of producing the letter X with die number i nXi : the number of times the letter X appears in position i dice와 sequence는 독립

* Likelihood (3.17)

* ParameterEstimation

• - with uniform prior, single-die case 와 동일 (3.18)

* n-gram model

• - language modeling에 사용됨. - |A|^(n-1)개의 dice 필요, each die 는 |A| faces를 가진 simple die dlau, prefix (n-1)을 가짐. length n 의 window 로 scanning하고, current prefix에 맞는 die를 골라 random하게 던져서 sequence를 만들어낸다.

  • Thus the choice of the die to be flipped is not independent of the previous flips.

  -> prefix의 갯수만큼의 order 를 가진 Markov model 이라는 관점으로 보는 것도 가능하다.

Statistical Mechanics

*MachineLearning과 ComputationalBiology 와 연관된 Statistical mechanics의 원리를 이해하기 위한 5가지 원리

• Statistial Mechanics는

• Bayesian reasoning의 가장 오래되고 최선의 방법으로 생각할 수 있다.
• 전통적으로 단순한 극히 미세하게 상호작용하는 단위 전체들의 통계학적인 macroscopic properties 를 유도하는 것에 관심을 두어 오고 있다.
• techniq 과 결과들이 Machine Learning에서 사용되는 graphical models의 properties와 learning evolution을 이해하는데 유용하다
• biological macromolecule에 직접적으로 적용되어 오고 있다.
• Machine Learning의 fundamental 한 몇가지 알고리즘을 이해하는데 유용하다.

* Baysian derivation of statistical mechanics and the basic concept

• [조건] microscopic states : S = {s1, ... , s|S|} , the probability of being in state s for a distribution P = (ps)
  • f(s) : function of states, data : the expectation or average of f
  • we write D = E(f) = ∑s ps f(s)

* Interaction Parameter

• [조건] states가 microscopic structure 를 가지는 경우 : s = (x1, ..., xn) , xi are local variables we write f = typically the energy of the system , f(s) = f(x1, ... , xn) = ∑(i,j) wij xi xj + ∑(i) wi xi wi (interaction parameters) = local 이 될수도 있으며, 기초적인 graphical model과도 연관이 있다.

* 이러한 가정들이 특정한 시스템의 모델링과 세부적인 이론의 전개에 중요함에도 불구하고, 다음 장에서는 불필요하게 된다.

The Boltzmann-GibbsDistrubution

Standard Derivation

Most standard treatments at this point are based on the maximum entropy principle.

다른 부가적인 정보 없이, 선택할 때 distribution P 의 조건 : constraints 인 f(s)ps = D를 만족시키며, 가장 높은 entropy를 가져야 . -> 이유 : 이 방법이 가장 널리 퍼져 있고, 부가적인 가정의 수를 최소화 하기 때문이다.

이 문제를 relevant 한 constraints로 optimize 된 함수들의 linear combination 으로 이루어진 Lagrangian L 로 만들면 쉬워진다. (3.19)

이를 Ps 로 편미분 하여 그 값을 0으로 두면 solution distribution을 얻게 된다. 3.20

Z(λ) = ∑e^(-λf(s)) : partition function

Lagrangian multiplier는 λ= 1/kT (k는 볼츠만 상수)라는 정의해 의해서 계의 온도인 T에 연관이 있다. 그러나 그것을 고려할 필요는 없고 λ을 생각하자. 그러나 λ는 3.21 식을 보면 obsevation D에 의해 결정된다. 종종 λ=1이라는 가정만으로 충분하기도 하다.

*Boltzmann-GibbsDistribution

1. optimal distribution P* 는 Boltzmann-GibbsDistribution 이라고 부른다.

2. -lpg P에 비례하는 에너지 함수를 사용하면, 적어도 일정한 온도에서는 어떤 distribution도 Boltzmann-GibbsDistribution으로 나타낼 수 있다. 따라서 ps 에 대한 multiple linear constraints가 있을 때 비슷한 방정식이 유도될 수 있다.

*Baysiean standard derivation 의 한계 (Boltzmann-Gibbs distribution의 관점에서 볼때.)

1. The prior distribution is not explicit. 따라서 ps에 대한 다른 정보를 결합한다는 것이 어렵다.
2. The probablistic model is not explicit. likelihood P(D|ps) 계산이 어렵다.

3. The justification for the use of MaxEnt is weak. 공평하게 말하면, MaxEnt의 사용은 앞서 말한 combinatorial arguement 에 의해 부분적으로 정당화되어지지만, 그것은 entropy의 최대화시키는 것이 가능한 현실화 의 수를 최대화 시키는 것과 근본적으로 같다는 것을 보여준다. 이런 관점에서 MaxEnt solution은 가장 많은 방법으로 현실화 될 수 있는 것이며, 그런 논쟁은 realizations의 수에 근거하고 있고, 스들의 상대적인 확률을 고려하지 않은 것이다.

Baysial Derivation

*대안

특히 likelihood function P(D|ps)는 분명하게 정의되지 못하며, 이런 방향으론 그 계의 실질적인 전개가 고려되지 않고선 진전이 거의 없게 된다. 따라서 초기 설정을 더 확대하여, 매우 큰 N을 고정시키고, system이 그 period 에 걸쳐 관찰되도록 가정한다. Accordingly, we dicide to paramerterize the model using the counts ns.

*가능한 prior

1. Dirichlet prior - natural
2. entropic prior - the distribution on ns, when P is uniform
   • such a prior is best justified when the runs are independent, the underlying probabilistic model is a simple die with |S| faces

* 계산

1. likelihood function is trivial and has value 1 or 0.
2. proceed with the first step of Bayesian inference and estimate the parameters ns by MAP estimation. (3.22)

   the entropy act as a regularizer. this is of course virtually identical to (3.19) -> MAP Boltzmann-Gibbs distribution for ns/N. 이때 ns 대신 ps를 써도 비슷한 결과가 나온다.

*결론

the Boltzmann-Gibbs distribution corresponds to a first step of Bayesian inference by MAP with an entropic prior. 따라서 MaxEnt 는 일반적인 원리일 뿐만 아니라, entropic prior와 관계있는 multinomial setting에서는 Bayesian inference의 첫 번째 단계의 간단한 지름길로 볼수도 있는 것이다.

Thermodynamic Limit and Phase Transitions

* ThemodynamicLimit : as the size of the system goes to infinity, a limiting value that the value of an extensive quantity per unit of volume tends to

* Main Goals of StaticalMechanics

(1) To estimate the ThermodydamicLimit of macroscopic quantites : to approximate expectations with respect to the Boltzmann-Gibbs distribution

- 특히 partition function 인 Z(λ) 에 가까워 지는 것!

• Z(λ)의 특징 : this function constains most of the relevant information aout the system,
  • easy to show that all the moments of the function f can be computed from Z(λ), and more precisely from its logarithm. for instance (3.23), (3.24), (3.25)

(2) The study of phase transitions, that is abrupt changes in the behavior of the system as some of the parameters are varied

- first-order phase transition, second-order phase transition

The Free Energy

* definition : the logarithm of the partition function

• (1) F= F(f,λ) = f(λ) --> F(λ) =1/λlog Z(λ) (3.26) (2) F(λ) = E(f) - 1/λ H(P*) : (3.26)를 다시 (3.25)에 대입하여 정리

  • : the free energy depends on the function f, the parameter λ, the distibution P* over states.
  (3) consider any Other Distribution Q(s) : (3.29) - free energy를 Lagrangian 과 비교해 보면, Boltzmann-Gibbs Distribution이 free energy를 최소화하는 distribution으로서의 특징을 가진다. (4) consider any Two Distributions Q(s) and R(s) : Comparing their free energies - 3.30

  - free energy의 차이는 RelativeEntropy와 같다. (3.31)

The Hidden Variables Case

*notation

• H : hidden/unobserved/latent variables or causes D : the data state : the vales assumed by the hidden variables

* the posterior P(H|Q,P*) 와 그에 대응하는 기대값들을 계산하기 어려울 때 DataLikelihood를 최대화 하기 위해서는 때때로 차선의 전략-based on a different family of distributions Q -을 사용할 수도 있다.