[2023-03-17] 오늘의 자연어처리

Milner's Proof System for Regular Expressions Modulo Bisimilarity is Complete (Crystallization: Near-Collapsing Process Graph Interpretations of Regular Expressions)

 

Milner (1984) defined a process semantics for regular expressions. He formulated a sound proof system for bisimilarity of process interpretations of regular expressions, and asked whether this system is complete. We report conceptually on a proof that shows that Milner's system is complete, by motivating, illustrating, and describing all of its main steps. We substantially refine the completeness proof by Grabmayer and Fokkink (2020) for the restriction of Milner's system to `1-free' regular expressions. As a crucial complication we recognize that process graphs with empty-step transitions that satisfy the layered loop-existence/elimination property LLEE are not closed under bisimulation collapse (unlike process graphs with LLEE that only have proper-step transitions). We circumnavigate this obstacle by defining a LLEE-preserving `crystallization procedure' for such process graphs. By that we obtain `near-collapsed' process graphs with LLEE whose strongly connected components are either collapsed or of `twin-crystal' shape. Such near-collapsed process graphs guarantee provable solutions for bisimulation collapses of process interpretations of regular expressions.

 

밀너(1984)는 정규 표현식에 대한 프로세스 의미론을 정의했다. 그 프로세스 해석의 이중 유사성을 위한 방음 시스템을 공식화했다 정규 표현식, 그리고 이 시스템이 완벽한지 물었다. 우리는 Milner의 시스템이 모든 주요 단계를 동기 부여, 설명 및 설명함으로써 완료합니다. 우리가 Gravmayer와 Fokkink(2020)에 의한 완전성 증명을 실질적으로 개선한다 밀너의 체계가 '1-free' 정규 표현으로 제한되는 것. 로서 빈 단계로 그래프를 처리하는 중요한 복잡성을 인식합니다 레이어드 루프 존재/제거 속성 LLEE를 만족하는 전환 이중 시뮬레이션 붕괴 시 닫히지 않음(LLEE가 있는 프로세스 그래프와 달리) 적절한 단계 전환만 가능). 우리는 다음과 같이 이 장애물을 우회한다 이러한 프로세스 그래프에 대한 LLEE 보존 '결정 절차'를 정의한다. 그것에 의해 우리는 LLEE를 강하게 가진 '거의 붕괴된' 프로세스 그래프를 얻는다 연결된 구성 요소가 접히거나 '접힌' 모양입니다. 그런 근적외선 프로세스 그래프는 이중 시뮬레이션을 위한 입증 가능한 솔루션을 보장합니다 정규식의 공정 해석 축소. 

 

 

The Image of the Process Interpretation of Regular Expressions is Not Closed under Bisimulation Collapse

 

Axiomatization and expressibility problems for Milner's process semantics (1984) of regular expressions modulo bisimilarity have turned out to be difficult for the full class of expressions with deadlock 0 and empty step~1. We report on a phenomenon that arises from the added presence of 1 when 0 is available, and that brings a crucial reason for this difficulty into focus. To wit, while interpretations of 1-free regular expressions are closed under bisimulation collapse, this is not the case for the interpretations of arbitrary regular expressions. Process graph interpretations of 1-free regular expressions satisfy the loop existence and elimination property LEE, which is preserved under bisimulation collapse. These features of LEE were applied for showing that an equational proof system for 1-free regular expressions modulo bisimilarity is complete, and that it is decidable in polynomial time whether a process graph is bisimilar to the interpretation of a 1-free regular expression. While interpretations of regular expressions do not satisfy the property LEE in general, we show that LEE can be recovered by refined interpretations as graphs with 1-transitions refined interpretations with 1-transitions (which are similar to silent steps for automata). This suggests that LEE can be expedient also for the general axiomatization and expressibility problems. But a new phenomenon emerges that needs to be addressed: the property of a process graph `to can be refined into a process graph with 1-transitions and with LEE' is not preserved under bisimulation collapse. We provide a 10-vertex graph with two 1-transitions that satisfies LEE, and in which a pair of bisimilar vertices cannot be collapsed on to each other while preserving the refinement property. This implies that the image of the process interpretation of regular expressions is not closed under bisimulation collapse.

 

밀너 프로세스 시맨틱에 대한 공리화 및 표현성 문제 (비공식) 모듈로 비 유사성은 다음과 같이 밝혀졌다 교착 상태가 0이고 단계가 비어 있는 전체 표현식 클래스에 대해 어렵습니다~1. 우리는 0일 때 1의 추가된 존재로 인해 발생하는 현상에 대해 보고한다 이용 가능하며, 그것은 이 어려움에 대한 중요한 이유를 집중시킨다. 로. 위트, 1-자유 정규 표현의 해석은 아래에서 닫힌다 이중 시뮬레이션 붕괴, 이것은 해석의 경우가 아니다 임의의 정규 표현. 1-자유 정규식의 공정 그래프 해석이 루프를 만족시킵니다 이중 시뮬레이션으로 보존되는 존재 및 제거 속성 LEE 무너지다. LEE의 이러한 특징은 등식을 보여주기 위해 적용되었다 1 자유 정규 표현 모듈로비 유사성에 대한 증명 시스템이 완성되었습니다, 그리고 프로세스 그래프가 다음과 같은지 여부는 다항식 시간에 결정할 수 있다 1-자유 정규식의 해석과 유사하다. 정규 표현식의 해석은 LEE 속성을 만족시키지 못한다 일반적으로, 우리는 LEE가 다음과 같은 정제된 해석에 의해 회복될 수 있음을 보여준다 1-전이가 있는 그래프는 1-전이가 있는 정제된 해석입니다(이는 다음과 같다) 자동화를 위한 무음 단계와 유사). 이것은 LEE가 편법일 수 있음을 시사한다 또한 일반 공리화 및 표현성 문제에 대해서도. 하지만 새로운 해결해야 할 현상: 프로세스 그래프의 속성 "1-전이와 LEE를 사용하여 공정 그래프로 정제할 수 있다"는 것은 아니다 이중 시뮬레이션 붕괴 하에서 보존됩니다. 우리는 두 개가 있는 10- 꼭짓점 그래프를 제공한다 LEE를 만족시키는 1-전이, 그리고 쌍이 유사한 꼭짓점 쌍이 있는 경우 정제 속성을 보존하는 동안 서로 접을 수 없습니다. 이것은 정규적인 프로세스 해석의 이미지를 의미한다 표현식은 이중 시뮬레이션 붕괴 시 닫히지 않습니다. 

 

 

On the Calibration and Uncertainty with Pólya-Gamma Augmentation for Dialog Retrieval Models

 

Deep neural retrieval models have amply demonstrated their power but estimating the reliability of their predictions remains challenging. Most dialog response retrieval models output a single score for a response on how relevant it is to a given question. However, the bad calibration of deep neural network results in various uncertainty for the single score such that the unreliable predictions always misinform user decisions. To investigate these issues, we present an efficient calibration and uncertainty estimation framework PG-DRR for dialog response retrieval models which adds a Gaussian Process layer to a deterministic deep neural network and recovers conjugacy for tractable posterior inference by Pólya-Gamma augmentation. Finally, PG-DRR achieves the lowest empirical calibration error (ECE) in the in-domain datasets and the distributional shift task while keeping $R_{10}@1$ and MAP performance.

 

심층 신경 검색 모델은 그들의 힘을 충분히 입증했지만 예측의 신뢰성을 추정하는 것은 여전히 어렵다. 대부분의. 대화 상자 응답 검색 모델은 방법에 대한 응답에 대한 단일 점수를 출력합니다 그것은 주어진 질문과 관련이 있다. 그러나, 심층 신경의 나쁜 교정은 네트워크는 단일 점수에 대한 다양한 불확실성을 초래한다 신뢰할 수 없는 예측은 항상 사용자의 결정을 오보한다. 이들을 조사하기 문제, 우리는 효율적인 교정과 불확실성 추정을 제시한다 가우스를 추가하는 대화 응답 검색 모델을 위한 프레임워크 PG-DRR 프로세스 계층을 결정론적 심층 신경망에 연결하고 다음에 대한 활용성을 복구합니다 Polya-Gamma 확대에 의한 다루기 쉬운 후방 추론. 마지막으로, PG-DRR 도메인 내 데이터 세트에서 가장 낮은 경험적 교정 오류(ECE)를 달성한다 $R_{10}@1$ 및 MAP 성능을 유지하면서 분산 이동 작업을 수행한다.