유한 상태 변환기

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다. (2014년 8월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인) 이 글은 인용 문체가 불분명하다 사용된 참조는 인용 및 각주를 달리하거나 일관된 스타일로 명확하게 할 수 있습니다. (2014년 8월) (이 템플릿메시지를 삭제하는 방법과 시기에 대해 알아보기) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

유한상태변환기(FST)는 튜링기계용 용어인 입력테이프와 출력테이프를 따르는 2개의 메모리테이프를 가진 유한상태 기계이다.이것은 하나의 테이프가 있는 일반적인 유한 상태 오토마톤과 대조됩니다.FST는 2개의 ^[1]심볼 세트 간에 매핑되는 Finite-State Automaton(FSA; 유한 상태 오토마톤)의 일종입니다.FST는 FSA보다 일반적입니다.FSA는 수신된 문자열 세트를 정의함으로써 정식 언어를 정의하고 FST는 문자열 세트 간의 관계를 정의합니다.

FST는 입력 테이프에서 문자열 세트를 읽고 출력 테이프에서 일련의 관계를 생성합니다.FST 는, 세트내의 문자열간의 변환기 또는 릴레이터로서 생각할 수 있습니다.

형태학적 해석에서는 예를 들어 FST에 문자열을 입력하고 FST는 형태소 문자열을 출력합니다.

개요

외부 비디오
유한 상태 변환기 // Karlsruhe 공과대학, YouTube 비디오

테이프 내용을 입력으로 보면 오토마톤은 문자열을 인식한다고 할 수 있습니다.즉, 자동화는 {0,1} 집합에 문자열을 매핑하는 함수를 계산합니다.또는 자동화가 문자열을 생성한다고 할 수 있습니다.즉, 테이프를 출력 테이프로 볼 수 있습니다.이 관점에서 자동화는 문자열 집합인 형식 언어를 생성합니다.오토마타의 두 가지 관점은 동일하다: 오토마톤이 계산하는 함수는 정확히 그것이 생성하는 문자열 집합의 지시 함수이다.유한 오토마타에 의해 생성된 언어의 클래스는 정규 언어의 클래스로 알려져 있습니다.

트랜스듀서의 2개의 테이프는 일반적으로 입력테이프와 출력테이프로 간주됩니다.이러한 관점에서 트랜스듀서는 입력테이프의 문자열을 받아들여 출력테이프에 다른 문자열을 생성함으로써 입력테이프의 내용을 출력테이프로 변환(즉 번역)한다고 한다.비결정적으로 그렇게 할 수 있으며 각 입력 문자열에 대해 여러 출력을 생성할 수 있습니다.변환기는 또한 주어진 입력 문자열에 대해 출력을 생성하지 않을 수 있으며, 이 경우 입력을 거부한다고 한다.일반적으로 변환기는 2개의 형식 언어 간의 관계를 계산한다.

각 문자열간 유한 상태 변환기는 입력 알파벳 δ와 출력 알파벳 δ를 관련짓는다.유한 상태 변환기로 구현될 수 있는 δ*×δ* 위의 관계 R을 유리 관계라고 한다.부분 함수인 유리 관계, 즉 δ*부터 최대 1개의 δ*까지의 모든 입력 문자열을 관련짓는 유리 함수라고 합니다.

유한 상태 변환기는 종종 자연 언어 처리 연구와 응용 분야에서 음운 및 형태학적 분석에 사용됩니다.이 분야의 선구자들은 로널드 카플란, 라우리 카트툰, 마틴 케이, 키모 코스케니에미 ^{[2][non-primary source needed]}등이다.변환기를 사용하는 일반적인 방법은 이른바 "캐스케이드(cascade)"입니다. 이 캐스케이드에서는 합성 연산자의 반복적인 적용에 의해 다양한 연산을 위한 변환기가 단일 변환기로 결합됩니다(아래 정의).

형식 구조

형식적으로 유한 변환기 T는 다음과 같은 6 태플(Q, δ, δ, I, F, δ)이다.

• Q는 유한 집합, 즉 상태 집합이다.
• δ는 입력 알파벳이라고 불리는 유한 집합입니다.
• δ는 출력 알파벳이라고 불리는 유한 집합입니다.
• I는 초기 상태 집합인 Q의 하위 집합입니다.
• F는 최종 상태 집합인 Q의 하위 집합이다.
• ${\displaystyle (}$ ${\displaystyle Q}$ × (${\displaystyle \mathrm{\sigma }}${ {${\displaystyle ϵ}$) × (${\displaystyle \mathrm{\gamma \gamma }}${${\displaystyle }$} ${\displaystyle \}}$ ) × $Q$( \$displaystyle$ \ delta \ $subseteq Q \$ times ) \$times$ ( \$Sigma$ \ cup \ { \ { \ $epsilon$\ $$} ) \ times ( \ $Gamma$ \ cup \ { \ { \ \ } ) string) \ \ \ \ \ \ \ \ \ \ \ $times$ ) string ) string) string) ) 。

(Q, ))는 라벨이 붙은 유향 그래프로서 T의 트랜지션 그래프라고 불립니다.정점 집합은 Q입니다.${\displaystyle 또}$,${\displaystyle }$(${\displaystyle q,}$ ${\displaystyle a,}$ ${\displaystyle b,}$ r ) $∈$ { $display$ style $(q, a, b, r)\in \delta }$는, 정점 q에서 정점 r로 이어지는 라벨이 붙은 에지가 있음을 의미합니다.또한 a는 해당 에지의 입력 라벨이고 b는 해당 에지의 출력 라벨이라고 합니다.

참고: 유한 변환기의 정의는 문자 변환기(Roche 및 Schabes 1997)라고도 합니다. 대체 정의는 가능하지만, 모두 변환기로 변환될 수 있습니다.

확장 전이 관계 $「」(\$^{*})를 다음과 같이 최소 세트로 정의합니다.

• $\displaystyle \displayeq$ \displayeq$^\{*\}$ ;
• ${\displaystyle (q}$ ,${\displaystyle }$" , "${\displaystyle }$, " ,${\displaystyle }$" q )${\displaystyle }$" " " " ($$q , \ $epsilon$, \ $epsilon , q$ ) \ $in$\$delta ^$ { * }" (${\displaystyle \mathrm{모든}}$ Q$)$에 대해 "\ $displaystyle$$q$$\ in$ Q" 입니다$.$
• $({\displaystyle q}$ ,${\displaystyle }$x ,${\displaystyle y}$ ,${\displaystyle }$r ) ${\displaystyle \in }$ $、$ \ $display$style ($q$ , x ,$y$ , $r$) \$$$in$ \ display $^$ { * ${\displaystyle \}}$$($ ( (${\displaystyle }$${\displaystyle {}^{}}$${\displaystyle }$( $r$ ,$a$, ${\displaystyle b}$ , ${\displaystyle s}$ )\${\displaystyle \mathrm{in<img\; alt="(q,x,y,r)\; \backslash in\; \backslash delta^*"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/ed0e573ab63414177f1330fa532111375715a56f"\; style="vertical-align:\; -0.838ex;\; width:14.463ex;\; height:2.843ex;">}}$\ $display$style ($r$ ,$$${\displaystyle a}$ , ${\displaystyle b}$, s )\ ${\displaystyle {}^{}}$ \ ${\displaystyle \mathrm{display}}$ $style$ ( r ,$a$, ${\displaystyle b}$, s ) $、$ )${\displaystyle 。}$

확장된 전이 관계는 기본적으로 가장자리 레이블을 고려하기 위해 증가된 전이 그래프의 반사적 전이 폐쇄입니다.「$$」의 요소$(\displaystyle$ \delta$$^{*})는$$ 패스로 알려져 있습니다.경로의 에지 레이블은 구성 전환의 에지 레이블을 순서대로 연결하여 가져옵니다.

트랜스듀서 T의 동작은 다음과 같이 정의되는 유리관계 [T$$$]$입니다${\displaystyle .}$$i I$ \ ${\displaystyle \mathrm{display}}$ i \ $in$ ${\displaystyle {}^{}}$$$$f$ f f f$$ f$$$f$ f （ $i$,$x$,$y$ ,$） 。$입력라벨이 x이고 출력라벨이 y인 초기상태에서 최종상태로의 경로가 존재하는 경우 ${\displaystyle {\mathrm{}}^{}}$ x " $"\$x$\$$in \Sigma$$$$^{*}"$ 를$$$$ ${\displaystyle {\mathrm{}}^{}}$ y 로${\displaystyle }$변환합니다.

가중 오토마타

유한 상태 변환기는 가중치를 부여할 수 있으며, 여기서 각 전환에는 입력 및 출력 라벨 외에 가중치로 라벨이 지정됩니다.가중치 K에 대한 가중치 유한 상태 변환기(WFST)는 가중치되지 않은 것과 유사하게 8-태플 T=(Q, δ, δ, I, F, E, δ, δ, δ)로 정의할 수 있다. 여기서, 다음과 같다.

• Q, δ, δ, I, F는 위와 같이 정의된다.
• $E$Q${\displaystyle }$× ( ${\displaystyle \mathrm{\sigma }}${ { ${\displaystyle ϵ}$ ${\displaystyle \}}$)${\displaystyle }$× ( ${\displaystyle \mathrm{\gamma }}${ { }${\displaystyle \}}$ )${\displaystyle }$× $Q$× K × \ $display$E \ $subseteq$\ times ( \$Sigma$ \ cup \ { \ $epsilon$ \ }$$ ) \ times ( \$Gamma$ \ cup \ { \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $times$ \$times$ \ times \ times \ times \ times ) $）$ ） ε \ $times$ 。
• $K$$$$I\right 화살표$K는$$ 초기 상태를 가중치에 매핑합니다.
• ${\displaystyle :}$ : ${\displaystyle F}$→ $K${$style$ \$rho$ : F \$right 화살표$ K$$$$}는 최종 상태를 가중치에 매핑합니다.

WFST에서 특정 동작을 명확하게 정의하기 위해서는 가중치 세트를 요구하여 ^[3]세미링을 구성하는 것이 편리합니다.실제로 사용되는 두 가지 일반적인 반설정은 로그 반설과 열대 반설이다. 비결정론적 자동설정은 부울 ^[4]반설정에 가중치가 있는 것으로 간주될 수 있다.

확률적 FST

확률론적 FST(확률론적 FST 또는 통계적 FST라고도 함)는 아마도 가중 ^{[citation needed]}FST의 한 형태이다.

유한 상태 변환기의 동작

유한 오토마타에 정의된 다음 연산은 유한 변환기에도 적용됩니다.

• Union. 변환기 T와 S가 주어지면 $변환기{\displaystyle }$ T${\$ ${\displaystyle S}$ {\$displaystyle T\cup$S }가$$ $존재$하며 x${\displaystyle }$[ ${\displaystyle T}$$$S ${\displaystyle ]}$ { $displaystyle$$$x [ T \ $cup$ S $]y$는 x${\displaystyle }$[ T${\displaystyle }$]$$ \ $displaystyle$$$x [ $T$$]y$$x$ [${\displaystyle }$T$]$$y x$ Y [ ${\displaystyle S}$ $]$ y 입니다.
• 연결.${\displaystyle {변환기\mathrm{}}_{}}$ T와 S에 따라 $변환기{\displaystyle }$ T ${\displaystyle s}$ S ${\displaystyle$ T$\$$cdot$ S$$가 존재합니다$$.$x{\displaystyle {}_{}}$ [ ${\displaystyle T}$S $]$y [ T \ $displaystyle$ x $]y$$${$1$、${\displaystyle {}_{}{}_{}}$ 2,${\displaystyle {}_{}{y\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, y$$2 { $displaystyle x { 1$ } { $y }$ $}$ 。$playstyle$ x$=x_{$1}$x_{2},y=y_{$1}$y_{2},x_$${1}[T]y_{1$} $및{\displaystyle {}_{}}$ ${\displaystyle {x2\mathrm{}}_{}}$[$.$ {$displaystyle x_{2}[S]y_{2}.$$}$
• 클린 클로징.트랜스듀서 T가 주어지면 다음과 ^[5]같은 특성을 가진 $트랜스듀서$ T ${\$ {\$displaystyle$ T$^{*}}$가 존재할 수 있습니다.

${\displaystyle [}$ [ ${\displaystyle T{}^{}}$ ] ${\$ {$displaystyle$ \$epsilon$ [ T^ { * } \ $epsilon$ ;

(k1)

$w{\displaystyle }$[ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle y}$ \$display w$[ $T^$ { * ] $y$} $및$ x [${\displaystyle T}$ ]$$ \ $displaystyle$x [$T$]$z$일$$경우 ${\displaystyle w}$x [ ${\displaystyle {}^{}}$ ]${\displaystyle {}^{}}$] ${\displaystyle \mathrm{yz}}$ \$displaystyle wx$[$T^$ { * } $yz$} ;

(k2)

($k1{\displaystyle )}$ ${\displaystyle {}^{}}$ (k2)에 의해 지시되지 않는 한 x [ T ${\displaystyle {}^{}}$ $]y$ 및 x [ $tyle$x [ $T^$ { * ]y는$$ 유지되지 않습니다.

• 구성.알파벳 δ와 δ의 변환기 T와 알파벳 δ와 δ의 변환기 S가 주어졌을 때${\displaystyle ,}$ δ와 δ의 $변환기{\displaystyle }$ T${\displaystyle \delta }$S(\$displaystyle$ T$\circ$ S$)$는 $x{\displaystyle }$ [T$δ$ ${\displaystyle S]}$ ${\displaystyle z}$ $[\displaystyle X\circ$]이다.$e$x [ $T ]y$$y$ y y${\displaystyle }$[ S $]$ \ $displaystyle y$ [ S $]z$ 이 연산은 가중치 ^[6]대소문자로 확장됩니다.

이 정의는 수학에서 관계 구성에 사용되는 것과 동일한 표기법을 사용합니다.${\displaystyle 단}$, (x, $S$ \ ${\displaystyle \mathrm{display}}$ style$(x$${\displaystyle ,}$ y$)\in$S$$${\displaystyle }$、 Y style$$ (x$, y$${\displaystyle )\backslash }$$circ$S 등2개의 관계 T와 S($x$, z) ${\displaystyle )}$ T$\circ$ S(${\displaystyle x}$${\displaystyle ,}$$$${\displaystyle z)}$${\displaystyle \mathrm{two}}$ T$\$circ ${\displaystyle 。}$

• 오토마톤에 투영.투사기능은 ${\displaystyle {1\mathrm{}}_{}}$ 1$$\ $displaystyle$\$pi$_ {$1$} ${\displaystyle 2_{}}$ 2$$\ $displaystyle$\ $pi$_ {2} 2 tape2 \ display style \ pi _ {$$}로$$ 출력테이프를 유지합니다.$첫{\displaystyle {}_{}}$ 번째 투영 § $(\$ _${1})$은 다음과 같이 정의됩니다.

변환기 T가 주어지면, 유한 ${\displaystyle {}_{}}$ ${\displaystyle {\theta \mathrm{}}_{}}$ 1 $(\displaystyle \pi$ _${1$}$T)$가 존재하기 때문에${\displaystyle ,}$ x [$T$y .$$\$displaystyle$x [ T ]$y$가 $존재$하는 문자열 y 가 존재하는 경우에만, ${\displaystyle {1\mathrm{}}_{}}$T(\$displaystyle \pi$ _{1}$T)$ T)가$$ x 를 받아들인다.$}$

두 번째 $투영법{\displaystyle {}_{}}$ § $(\style$ \$pi _{$2})도$$ 마찬가지로 정의되어 있습니다.

• 결정.변환기 T가 주어진 경우, 우리는 고유한 초기 상태를 가지며 어떤 상태를 남기는 두 개의 전환이 동일한 입력 라벨을 공유하지 않도록 동등한 변환기를 구축하고 싶다.파워셋 구조는 변환기 또는 가중 변환기로 확장할 수 있지만 때때로 정지하지 못한다. 실제로 일부 비결정론적 변환기는 동등한 결정론적 ^[7]변환기를 허용하지 않는다.결정 가능한 변환기의 특성화는 이를 ^[9]테스트하기 위해 효율적인 알고리즘과 함께 제안되었다^[8]. 변환기의 구조에 대한 일반 특성뿐만 아니라 가중 사례에 사용된 세미링에 의존한다(쌍둥이 특성).
• 가중치 케이스에 ^[10]대한 가중치 밀어내기.
• 가중치 ^[11]부여 케이스의 최소화.
• 엡실론 천이 제거

유한 상태 변환기의 추가 특성

• 변환기 T의 관계[T]가 비어 있는지 아닌지는 판정할 수 있다.
• 특정 문자열 x에 대해 x[T]y가 되는 문자열 y가 존재하는지 여부를 판단할 수 있습니다.
• 두 개의 변환기가 ^[12]동일한지 아닌지는 판단할 수 없다.단, 변환기 T의 관계[T]가 (부분) 함수인 특수한 경우에는 등가성이 결정 가능하다.
• $라벨{\displaystyle }$ L ${\displaystyle =}$ ( ${\displaystyle \mathrm{display}}$display { ${\displaystyle \mathrm{display}}$ ${\displaystyle \}}$ )${\displaystyle }$× ( ${\displaystyle \mathrm{display}}${ ${\displaystyle \mathrm{display}}$ ${\displaystyle \}}$ )$${ $displaystyle$ L = ( \ $Sigma$\$cup$ \ { \ $explilon$ \$$$}$ ) \ $times$ ( \$Gamma$ \ $cup$ \ { \ scapilon \ $}$ )의 유한 상태 변환기는$L$의 알파벳 위에 NDFA $형식$입니다.${\displaystyle L}$ ${\displaystyle =}$[ ( $σ$ { ϵ${\displaystyle \}}$ × ${\displaystyle \mathrm{\gamma }}$ ${\displaystyle ]}$ ${\displaystyle [}$ [${\displaystyle \mathrm{\gamma }\cup }$ { ${\displaystyle ϵ\}}$)$$\ $displaystyle$ L = [ ( ( \$Sigma$ \ cup \ { \ $explilon$ \ } ) \$times$ \ Gamma ] \ cup [ \$Sigma$ \ times ( \ $Gam \$ cup \ $times$ \ } ) } }$$} $}$

적용들

FST는 컴파일러의 사전 분석 단계에서 의미 값을 검색된 ^[13]토큰과 관련짓기 위해 사용됩니다.

언어학에서 음운학적 규칙과 소리 변화를 모델링하기 위해 사용되는 a → b / c _ d 형식의 문맥에 민감한 재작성 규칙은 애플리케이션이 반복적이지 않을 경우, 즉 규칙이 동일한 하위 문자열을 두 ^[14]번 재작성하는 것이 허용되지 않을 경우, 계산상 유한 상태 변환기와 동일하다.

가중 FST는 기계번역을 포함한 자연어 처리 및 ^[15][16]기계학습에서 응용 프로그램을 발견했습니다.Part-of-Speech 태깅 구현은 OpenGrm^[17] 라이브러리의 한 구성 요소로 찾을 수 있습니다.

「 」를 참조해 주세요.

• 밀리머신
• 무어 기계
• 형태학 사전
• foma(소프트웨어)
• 트리 변환기

메모들

레퍼런스

외부 링크

• OpenFst, FST 작업을 위한 오픈 소스 라이브러리입니다.
• 유한 상태 형태학—제록스(XFST/LEXC)는 언어 애플리케이션을 위한 유한 상태 변환기의 구현에 대한 설명입니다.
• 헬싱키 오픈 소스 구현 및 Xerox fst 확장
• FOMA는 Xerox XFST/LEXC 구현의 대부분의 기능을 오픈 소스로 구현한 것입니다.
• 또 다른 오픈 소스 FST 툴킷인 Stuttgart Finite State Transducer Tools
• Java FST Framework는 OpenFst 텍스트 형식을 처리할 수 있는 오픈 소스 Java FST Framework입니다.
• Vcsn은 가중치 자동 데이터 및 합리적인 표현을 위한 오픈 소스 플랫폼(C++ 및 IPython) 플랫폼입니다.

추가 정보

• Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Prentice Hall. pp. 71–83. ISBN 0-13-095069-6.
• Kornai, Andras (1999). Extended Finite State Models of Language. Cambridge University Press. ISBN 0-521-63198-X.
• Roche, Emmanuel; Yves Schabes (1997). Finite-state language processing. MIT Press. pp. 1–65. ISBN 0-262-18182-7.
• Beesley, Kenneth R.; Lauri Karttunen (2003). Finite State Morphology. Center for the Study of Language and Information. ISBN 1-57586-434-7.
• Roark, Brian; Richard Sproat (2007). Computational Approaches to Morphology and Syntax. Oxford University Press. ISBN 978-0-19-927478-9.
• Berstel, Jean (1979). Transductions and Context-free Languages. Teubner Verlag.. PDF판 무료