필터링된 팝핑 재귀 전환 네트워크

Filtered-pping Recursive Transition Network(FPRTN;^[1] 필터포핑 재귀 전이 네트워크) 또는 Simply-pping Network(FPN; 단순 포핑 네트워크)는 서브루틴 점프에서 복귀할 때 수용자와 복귀 상태를 같은 키에 매핑해야 하는 키로의 상태 맵으로 확장되는 재귀 전이 네트워크(RTN)^[2]입니다.RTN은 리턴 스테이트 스택을 가진 유한 스테이트 오토마타로 간주할 수 있는 유한 스테이트 머신입니다 $.또한$ RTN은 트랜지션을 소비하고 있습니다 $.$ 또 $\varepsilon$ , $RTN$ 은 콜 트랜지션을 정의할 수도 있습니다.이러한 트랜지션은 트랜지션의 타겟 상태를 스택에 푸시하고 머신을 착신 상태로 함으로써 서브루틴 점프를 실행합니다.스택이 비어 있지 않은 경우, Acceptor 상태가 될 때마다 스택의 맨 위에 있는 반환 상태가 튀어나와 머신이 이 상태가 됩니다.

이 기사 전체에서 우리는 필터 포핑 재귀 전이 네트워크를 FPN이라고 부르지만, 이 약어는 애매하다(예: 퍼지 페트리 네트).필터링된 포핑네트워크와 FPRTN은 명확한 대체 수단입니다.

정식 정의

FPN은 $구조체$ $(Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)$ $(Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)$ ,, $(Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)$ $(Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)$ F )( $Q, K$ , \ $Sigma,$ \ $delta,$ \ $kappa, Q_{I$ })입니다 $.$

$(\displaystyle$ Q $)$ 는 $Q$ 유한한 상태의 집합입니다.
$(\displaystyle$ K $)$ 는 $K$ 한정된 키 세트입니다.
$σ$ \ $displaystyle$ \ $\Sigma$ Sigma $\Sigma$ }는 유한 입력 알파벳입니다.
$Q$ $Q\times(\Sigma \cup \{\varepsilon$ $\varepsilon$ $\}\cup$ Q $)\to$ Q $)$ 는 $\delta :Q\times (\Sigma \cup \{\varepsilon \}\cup Q)\to Q$ 부분 $\varepsilon$ 천이함수입니다 $.\$ $displaystyle \varepsilon$ 은 빈 기호입니다.
$\kappa :Q\to K$ $Q\to$ K는 상태를 $\kappa :Q\to K$ 키로 매핑한 것입니다.
$Q_{I}\subseteq Q$ $I}\subseteq$ Q $}$ 는 $Q_{I}\subseteq Q$ 초기 상태의 집합입니다.
$F\subseteq Q$ F $F\subseteq Q$ Q $F\subseteq Q$ $displaystyle$ F \ $subseteq$ ）는 $F\subseteq Q$ 승인 상태의 집합입니다.

이행

트랜지션은 추가 액션을 수행함으로써 FPN을 소스 $q_{s}$ (\ $displaystyle q_{s})$ 에서 $q_{s}$ 타깃 $(\$ 로 $q_t$ 이행할 가능성을 나타냅니다.이 액션에 따라 다음 유형의 명시적으로 정의된 천이를 구분합니다.

$\displaystyle$ \ $varepsilon$ } - transitions는 $\varepsilon$ $\delta (q_{s},\varepsilon )\to q_{t}$ s, $t$ \ $displaystyle \displaysilon (q_$ {s $},\varepsilon$ )\ $to$ q_{t $\delta (q_{s},\varepsilon )\to q_{t}$ } $형식$ 으로 변환되며 추가 액션은 수행되지 $\varepsilon$ .
소비전이는 $\delta (q_{s},\sigma )\to q_{t}$ s $\delta (q_{s},\sigma )\to q_{t}$ " $\delta (q_{s},\sigma )\to q_{t}$ $\delta (q_{s},\sigma )\to q_{t}$ $\delta (q_{s},\sigma )\to q_{t}$ t $\delta (q_{s},\sigma )\to q_{t}$ t \ $displaystyle$ \ $display$ ( $q _$ { s , \ $display )\ to q$ _ { $t$ }형식의 $\delta (q_{s},\sigma )\to q_{t}$ 천이이며 $\sigma$ "\ $displaystyle$ \ displays $\sigma$ 를 소비합니다.
콜의 천이는 $\delta (q_{s},q_{c})\to q_{t}$ , $\delta (q_{s},q_{c})\to q_{t}$ c $\delta (q_{s},q_{c})\to q_{t}$ $\delta (q_{s},q_{c})\to q_{t}$ t $\delta (q_{s},q_{c})\to q_{t}$ \ $displaystyle$ \ displaystyle ( $q_{s,q_{c})\ to q_{t$ $}$ 형식의 $\delta (q_{s},q_{c})\to q_{t}$ 천이로, $\$ $displaystyle$ $q_{c}$ $q_{c$ 에 $q_{c}$ $q_{t}$ 하기 전에 서브루틴 점프를 실행합니다.

콜 천이의 동작은, 다음의 2 종류의 암묵적으로 정의된 천이에 의해서 제어됩니다.

$\delta (q_{s},q_{c})\to q_{t}$ 콜 천이 $\delta (q_{s},q_{c})\to q_{t}$ ( ( $\delta (q_{s},q_{c})\to q_{t}$ s , $\delta (q_{s},q_{c})\to q_{t}$ c ) $\delta (q_{s},q_{c})\to q_{t}$ t { $displaystyle$ \ display ( $q$ _ { $s$ , $q$ _ { $c$ } )\ $to q_$ { t $}$ 에 $\delta (q_{s},q_{c})\to q_{t}$ 대해서 $q_{s}$ , FPN은 $q_{t}$ t { $display$ style q _ { $s$ }에서 $q_{c}$ c { $displaystyle$ $q$ _ { $c$ } 로의 $q_t$ 푸시 천이를 암묵적으로 정의합니다.
$(q_{f},q_{r})\in F\times Q$ 상태 쌍( q $(q_{f},q_{r})\in F\times Q$ , $(q_{f},q_{r})\in F\times Q$ r ) $(q_{f},q_{r})\in F\times Q$ F × $Q$ ({displaystyle $(q_{f},q_{r})\in$ F $\times$ Q)에 $(q_{f},q_{r})\in F\times Q$ 대해 FPN은 $q_{r}$ r { $displaystyle$ $q_{r}$ ${f}$ 스택에서 $q$ $q_{r}$ r {displaystyle $q_r}$ 을 $q_f$ $q_{r}$ $q_{r}$ $q_{r}$ 으로써 머신을 $q_{f}$ q_ ${$ $q_{r}$ }로 이행하는 팝 트랜지션을 암묵적으로 정의합니다. $yle q_{r}$ 은 $q_{r}$ 스택의 맨 위에 있는 $\kappa (q_{f})=\kappa (q_{r})$ 이며 $\kappa (q_{f})=\kappa (q_{r})$ " $\kappa (q_{f})=\kappa (q_{r})$ f" $\kappa (q_{f})=\kappa (q_{r})$ " $\kappa (q_{f})=\kappa (q_{r})$ r $")$ { $displaystyle \kappa (q_{f$ ) = \ $kappa (q_{r$ 입니다.

푸시 전환은 서브루틴 점프를 초기화하며 팝 전환은 리턴 문과 동일합니다.

목적

출력 RTN을 적용함으로써 (자연어) 텍스트는 메타 정보로 풍부해질 수 있다.예를 들어 RTN 삽입 XML 태그를 사용하여 플레인 텍스트를 구조화 XML 문서로 변환할 수 있다.자연어 문법을 나타내는 출력을 가진 RTN은 각 텍스트 문장의 구문 구조를 구분하여 추가합니다(파싱 참조).출력이 있는 다른 RTN은 단순히 관련 정보를 포함하는 텍스트 세그먼트를 표시할 수 있다(정보 추출 참조).애매한 문법을 나타내는 출력에 RTN을 적용하면 입력의 번역 또는 해석이 가능합니다.이 세트 추가하십시오. 예를 들어 입력 길이라는 자연 언어 문장의 해석의 수가 증가하면서 기하 급수적으로 w.r.t. RTNs에 대한 Earley 파서도 output,[3]과 지수 최악의 경우 비용에 번역의 수가 증가하면서 기하 급수적으로 w.r.t 사건으로 인해 해결되지 않은 전치사의 p.의 수가 많았습니다시간ase ^[4]^[5]첨부 파일:

문장상 소녀는 망원경으로 원숭이를 보았다.소녀가 망원경을 사용했는지 원숭이가 그것을 들고 있었는지 알 수 없다(2개의¹ 해석).
문장상 소녀는 정원에서 망원경으로 원숭이를 보았다.또한 원숭이가 정원에 있었는지, 아니면 정원에서 행해진 행동인지는 알 수 없다(2개의² 해석).
문장상 소녀는 나무 아래 정원에서 망원경으로 원숭이를 보았다.또한 원숭이가 나무 아래에 있었는지 나무 아래에 있었는지도 알 수 없다(2개의³ 해석).
기타.

FPN은 이 변환 세트를 콤팩트하게 표현하기 때문에 Earley와 같은 ^[1]파서를 사용하여 큐빅 타임으로 계산할 수 있습니다.FPN 상태는 출력 없는 RTN용 얼리 파서의 실행 상태(명령 스텝 참조)에 대응하고, FPN 천이는 입력 심볼의 가능한 변환에 대응합니다. $\kappa$ FPN의 $\kappa$ {\ $displaystyle$ \ $kappa$ } $\kappa$ 맵은 표시된 출력 세그먼트와 인식된 입력 세그먼트 간의 대응 관계를 제공합니다.인식된 $\sigma _{1}\ldots \sigma _{l}$ 시퀀스 $\sigma _{1}\ldots \sigma _{l}$ 1 ... $\sigma _{1}\ldots \sigma _{l}$ l \ $displaystyle$ \ $sigma$ _ ${1}\ldots$ \ $sigma$ _{ $l$ $}$ 및 $\sigma _{1}\ldots \sigma _{l}$ display $\sigma _{1}\ldots \sigma _{l}$ $p$ display display display display display display display displaydisplaydisplay displaydisplaydisplaydisplaydisplaydisplay $displaydisplaydisplaydisplaydisplaydisplaydisplaydisplay$ $displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay$ displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay $style q}$ and ending at a state $q^{\prime }$ , $p$ represents a possible translation of input segment $\sigma _{\kappa (q)+1}\ldots \sigma _{\kappa (q^{\prime })}$ .FPN 패스가 절단 또는 오버랩된 입력 세그먼트의 변환을 나타내지 않도록 하기 위해 필터 처리 기능이 필요합니다.FPN 콜에는 착신 상태에서 Acceptor 상태로의 변환 패스가 여러 개 포함될 수 있습니다.이 변환 패스는 같은 시작점을 공유하기 위해 대응하는 입력 세그먼트의 길이가 같을 필요는 없습니다.콜을 종료한 수신자 상태와 같은 입력 포인트에 대응하는 리턴 스테이트만이 유효한 리턴 스테이트입니다.

레퍼런스

^ ^a ^b 하비에르 M. Sastre, "필터링된 팝핑 재귀 전이 네트워크를 사용한 효율적인 해석", 인공지능 강의 노트, 5642:241-244, 2009
^ 윌리엄 A.Woods, "자연어 분석을 위한 전환 네트워크 문법", Communications of the ACM, ACM Press, 13:10:591-606, 1970
^ 하비에르 M. Sastre & Mikel L. Forcada, "출력을 가진 재귀 전이 네트워크를 사용한 효율적인 해석", 컴퓨터 과학 강의 노트, 5603:192-204, 2009
^ Adwait Ratnaparkhi, "감독되지 않은 전치사 어구 첨부의 통계적 모델", ACL-36: 제36회 컴퓨터 언어학 협회 및 제17회 컴퓨터 언어학 국제 회의의 속행, 1079-1085, 1998년 페이지
^ 미리암 버트, "Chunk/Shallow 구문 분석", 강의 노트, 2002

[sastre09jb-1] 하비에르 M. Sastre, "필터링된 팝핑 재귀 전이 네트워크를 사용한 효율적인 해석", 인공지능 강의 노트, 5642:241-244, 2009

[woods70jb-2] 윌리엄 A.Woods, "자연어 분석을 위한 전환 네트워크 문법", Communications of the ACM, ACM Press, 13:10:591-606, 1970

[sastre09ja-3] 하비에르 M. Sastre & Mikel L. Forcada, "출력을 가진 재귀 전이 네트워크를 사용한 효율적인 해석", 컴퓨터 과학 강의 노트, 5603:192-204, 2009

[ratnaparkhi98ip-4] Adwait Ratnaparkhi, "감독되지 않은 전치사 어구 첨부의 통계적 모델", ACL-36: 제36회 컴퓨터 언어학 협회 및 제17회 컴퓨터 언어학 국제 회의의 속행, 1079-1085, 1998년 페이지

[5] 미리암 버트, "Chunk/Shallow 구문 분석", 강의 노트, 2002

[1]

[2]

[4]

[5]

Search

필터링된 팝핑 재귀 전환 네트워크

네임스페이스

더

목차

정식 정의

이행

목적

레퍼런스