전진 알고리즘

Forward algorithm

전진 알고리즘은 숨겨진 마르코프 모델(HM)의 맥락에서 '믿음 상태' 즉, 증거의 이력을 감안할 때 특정 시간에 상태가 발생할 확률을 계산하는 데 사용된다.이 과정은 필터링이라고도 한다.전방 알고리즘은 Viterbi 알고리즘과 밀접하게 관련되어 있지만 구별된다.

전방 및 후방 알고리즘은 단순히 몇 개의 분야 내에서 표준 수학 절차 집합에 주어진 이름인 것처럼 보이기 때문에 확률의 맥락 안에 배치되어야 한다.예를 들어 케임브리지 수학 백과사전에는 '전방 알고리즘'도 '비테비'도 등장하지 않는다.이러한 알고리즘에서 벗어나야 할 주요 관찰사항은 Bayesian 업데이트와 추론을 어떻게 구성하여 변수의 지시된 그래프(sum-product networks 참조)의 맥락에서 효율적일 수 있는가 하는 것이다.

이와 같은 HM의 경우:

Temporal evolution of a hidden Markov model

this probability is written as . Here is the hidden state which is abbreviated as and are the observations to 신념 상태는 각 단계마다 계산될 수 있지만, 이렇게 하는 것은 엄밀한 의미에서 가장 가능성이 높은 상태 순서가 아니라, 이전 역사를 감안할 때 각 단계마다 가장 가능성이 높은 상태를 산출한다.

역사

전방 알고리즘은 디코딩 문제를 해결하기 위해 사용되는 알고리즘 중 하나이다.음성 인식과[1] 패턴 인식, HMM을 사용하는 컴퓨터 생물학 등 관련 분야가 발달한 이후 포워드 알고리즘이 인기를 끌었다.

알고리즘.

The goal of the forward algorithm is to compute the joint probability , where for notational convenience we have abbreviated as and as . Computing directly would require marginalizing over all possible state sequences , the number of which grows exponentially with . Instead,전진 알고리즘은 숨겨진 마르코프 모델(HM)의 조건부 독립성 규칙을 이용하여 계산을 재귀적으로 수행한다.

재귀에 대해 설명하려면

.

체인 규칙을 사용하여 , - , : t) 그리고 나서 쓸 수 있다.

.

(는) 조건상 모든 것과 이지만x t {\ x_x t {\t-1}은(는) - 을 제외한 모든 것과 조건상 독립적이기 때문에 다음과 같이 단순화된다

.

Thus, since and are given by the model's emission distributions and transition probabilities, one can quickly calculate from ) (를) 표시하고 지수 계산 시간이 발생하지 않도록 하십시오.

전진 알고리즘은 마르코프 점프 선형 시스템과 같이 숨겨진 마르코프 모델의 변종으로부터 오는 관측을 설명하기 위해 쉽게 수정된다.

스무딩

미래의 역사(즉, 과거 추정을 개선하고자 하는 경우)를 고려하기 위해, 전진 알고리즘을 보완하는 후진 알고리즘을 실행할 수 있다.이것을 스무딩이라고 한다.[why?]전방/ 알고리즘< 대해 ( :t) 을 계산하므로 완전한 전방/후방 알고리즘은 모든 증거를 고려한다.

디코딩

가장 가능성이 높은 시퀀스를 달성하기 위해서는 비테르비 알고리즘이 필요하다.관측치의 이력, 즉 : : t 를 최대화하는 상태 를 고려하여 가장 가능성이 높은 상태 시퀀스를 계산한다

가성음

init = 전환 p x - ){\p( 방출 확률 y ) 관측된 시퀀스, : t)

for  .        until t=T

반환 (y (: )= (1

이 예는 로저 보일의 HMM 자습서에서 미역의 관측 가능한 날씨 상태를 관찰하는 것이다.우리는 3일 연속 김을 순서대로 건조하고, 축축하고, 눅눅한 것으로 관찰한다.가능한 날씨 상태는 화창하거나, 흐리거나, 비가 올 수 있다.= 날씨 시퀀스가 있을 수 있다.그러한 모든 가능한 상태 시퀀스를 탐구하는 것은 계산적으로 매우 비싸다.이러한 복잡성을 줄이기 위해 전방 알고리즘이 유용하다. 여기서 트릭은 부분 확률을 계산하기 위해 시퀀스 단계의 조건부 독립성을 사용하는 데 있다. ( x )= ( x :) = t ) t- ( t- ) - ( x - 1) . \y_})=pt-1따라서 적절한 관측치/배출 확률 ( 이전의 관측치에서 t)에 나타난 y {\t})의 곱으로 확률을 계산할 수 있으며, 이때 t, calcula.전환 확률을 이용한 테드.이는 전체 검색 공간을 검색하는 것에서 이전에 계산된 s및 전환 확률을 사용하는 것으로 문제의 복잡성을 줄인다.

알고리즘의 적용

전방 알고리즘은 우리가 관찰의 순서에 대해 알 때 특정 상태에 있을 확률을 결정하기 위해 우리가 필요로 하는 어플리케이션에서 주로 사용된다.먼저 이전 관측치에 대해 계산된 상태에 대해 확률을 계산하여 현재 관측치에 사용하고, 전환 확률표를 사용하여 다음 단계까지 확률을 확장한다.접근방식은 기본적으로 모든 중간 상태 확률을 계산하므로 한 번만 계산한다.이것은 우리가 고정된 상태 경로를 계산하는데 도움을 준다.그 과정을 후부 디코딩이라고도 한다.이 알고리즘은 순진한 접근법보다 훨씬 더 효율적으로 확률을 계산하는데, 이것은 매우 빠르게 결합 폭발로 끝난다.그들은 함께 관찰 순서의 각 위치에서 주어진 방출/관찰의 확률을 제공할 수 있다.가장 가능성이 높은 상태 경로의 버전이 계산되는 것은 이 정보로부터이다("posterior det코딩").이 알고리즘은 우리가[2] Baum-Welch 또는 어떤 일반 전자파 알고리즘을 사용하여 데이터를 수신하기 때문에 우리가 모델을 훈련할 수 있는 곳이라면 어디든지 적용될 수 있다.그런 다음 Forward 알고리즘은 우리의 모델에서 예상되는 것과 관련된 데이터의 확률을 우리에게 알려줄 것이다.응용 프로그램 중 하나는 유형자산을 언제 매입하거나 매도할지를 결정하는 데 도움을 줄 수 있는 파이낸스 영역에 있을 수 있다.Hidden Markov Model을 적용하는 모든 분야에 응용할 수 있다.인기 있는 것들은 언어의 부분과 음성 인식 태그와 같은 자연 언어 처리 도메인을 포함한다.[1]최근에는 생물정보학 영역에서도 사용되고 있다.Forward 알고리즘은 Weather 억측에도 적용할 수 있다.우리는 연속적으로 며칠 동안 날씨와 관측 상태와의 관계를 설명하는 HMM을 가질 수 있다(일부 예로는 건조, 습기, 습기, 습기, 햇볕, 구름, 비 등).HMM이 주어진 관측치의 순서를 반복적으로 관찰할 확률을 계산하는 것을 고려할 수 있다. 그런 다음 중간 상태에 도달할 확률을 중간 상태에 대한 가능한 모든 경로의 합으로 계산할 수 있다.따라서 최종 관측에 대한 부분 확률은 가능한 모든 경로를 통과하는 상태에 도달할 확률을 유지할 것이다.

알고리즘의 변형

하이브리드 전방 알고리즘:[3] 하이브리드 전방 알고리즘(HFA)이라고 불리는 전방 알고리즘의 변형은 튜닝 가능한 노드를 가진 방사상 기준 함수(RBF) 신경 네트워크를 구성하는 데 사용될 수 있다.RBF 신경망은 기존의 서브셋 선택 알고리즘에 의해 구성된다.네트워크 구조는 단계적 전진 네트워크 구성과 연속적 RBF 매개변수 최적화를 모두 결합하여 결정한다.일반화가 잘되는 파시모닉 RBF 신경망을 효율적이고 효과적으로 생산하기 위해 사용한다.연속 파라미터 공간에 대한 네트워크 구조 결정과 파라미터 최적화를 동시에 통해 달성한다.HFA는 통합 분석 프레임워크를 사용하여 혼합 정수 하드 문제를 해결함으로써 네트워크 성능을 향상시키고 네트워크 구축을 위한 메모리 사용량을 감소시킨다.

하이브리드 시스템의 최적 제어를 위한 전방 알고리즘:[4]이러한 Forward 알고리즘의 변형은 공정과 운영 제어를 통합하는 제조 환경의 구조에 의해 동기 부여된다.우리는 비용 함수의 수정된 조건 하에서 유지되는 최적의 상태 궤적 구조의 새로운 속성을 도출한다.이를 통해 우리는 최적의 제어장치를 명시적으로 결정하기 위한 저복잡성, 확장 가능한 알고리즘을 개발할 수 있는데, 이것은 전방 알고리즘보다 더 효율적일 수 있다.

연속 전진 알고리즘:[5]연속 전방 알고리즘(CFA)은 방사상 기준 함수(RBF) 신경 네트워크를 이용한 비선형 모델링 및 식별에 사용할 수 있다.제안된 알고리즘은 통합 분석 프레임워크 내에서 네트워크 구축과 매개변수 최적화라는 두 가지 과제를 수행하며, 두 가지 중요한 이점을 제공한다.첫째, 연속 파라미터 최적화를 통해 모델 성능을 크게 개선할 수 있다.둘째로, 신경 표현은 모든 후보 퇴행기를 생성하고 저장하지 않고도 구축될 수 있어 메모리 사용량과 계산 복잡성이 현저히 감소한다.

복잡성

전방 알고리즘의 복잡성은 2) 이며 여기서 (는) 위의 예에서 날씨와 같은 숨겨진 변수 또는 잠재 변수의 수입니다. 관측된 변수의 시퀀스 길이입니다.이는 ( m 의 복잡성으로 가능한 모든 상태를 탐색하는 adhoc 방법에서 분명히 줄어든 것이다

참고 항목

추가 읽기

  • 러셀과 노르빅의 인공지능은 2010년판 570페이지에서 시작되는 모던 어프로치(Modern Access)로, 이 주제와 관련 주제에 대해 간결한 설명을 제공한다.
  • 스미스, 파드레이크, 데이비드 헤커만, 그리고 마이클 조던."숨겨진 마르코프 확률 모델을 위한 확률론적 독립 네트워크."신경 계산 9.2 (1997): 227-269.[1]
  • 읽어, 조나톤."히든 마르코프 모델과 동적 프로그래밍."오슬로 대학교(2011년).[2]
  • 콜쉐인, 크리스티안, 히든 마르코프 모델 소개 [3]
  • 망가니엘로, 파비오, 미르코 마르체티, 미슐레 콜라야니.침입 탐지 시스템의 다단계 공격 탐지 및 경보 상관 관계정보 보안 및 보증.스프링거 베를린 하이델베르크, 2011년 101-110[4]

참조

  1. ^ a b Lawrence R. Rabiner, "Hidden Markov Models and Selected Applications in Speech Incognition".IEEE 절차, 77(2), 페이지 257–286, 1989년 2월. 10.1109/5.18626
  2. ^ 장, 옌쉐, 동메이 자오, 징크스 류."다단계 공격에 바움-웰치 알고리즘의 적용"2014년 사이언티픽 월드 저널.
  3. ^ 펑, 지안순, 강리, 드샹황."RBF 신경망 구축을 위한 하이브리드 전방 알고리즘."신경망, IEEE 17.6(2006년): 1439-1451.
  4. ^ 장, 핑, 크리스토스 G. 카산드라스."하이브리드 시스템 클래스의 최적 제어를 위한 개선된 전방 알고리즘."47.10(2002년)의 자동 제어, IEEE 거래: 1735-1739.
  5. ^ 펑, 지안순, 강리, 조지 W.어윈 "RBF 신경 모델링에 대한 새로운 연속 전진 알고리즘"자동 제어, IEEE 52.1(2007) 거래: 117-122.
  • 스트라토노비치, R. L. "조건부 마르코프 과정"확률과 그것의 응용에 관한 이론 5, 2호(1960): 156178.
  • Lawrence R. Rabiner, B. H. Juang (January 1986). "An introduction to hidden Markov models". IEEE ASSP Magazine: 4–15.
  • Roger Boyle, Hidden Markov Models. 2016년 4월 24일.[5]
  • 장, 핑, 크리스토스 G. 카산드라스."하이브리드 시스템 클래스의 최적 제어를 위한 개선된 전방 알고리즘."47.10(2002년)의 자동 제어, IEEE 거래: 1735-1739.

외부 링크

소프트웨어