Between Markov and restriction. Two more monads on categories for relations

당신이 다양한 유형의 "관계"들을 담은 거대한 도서관을 정리하려고 한다고 상상해 보십시오. 수학과 컴퓨터 과학에서 이러한 관계들은 **범주(categories)**라고 불리는 구조를 사용하여 모델링됩니다. 어떤 범주들은 확실하고 완전한 것들(예: 완벽한 지도)을 설명하는 반면, 다른 범주들은 부분적이거나, 확률적이거나, 혹은 불완전한 것들(예: 대략적인 지도나 추측)을 설명합니다.

**"Between Markov and restriction"**이라는 제목의 이 논문은, 마치 두 개의 새로운, 매우 구체적인 선반을 발견하여 그곳에 '관계' 책들을 배치하려는 사서와 같습니다. 이 새로운 선반들은 기존에 잘 알려진 두 영역인 마르코프(Markov) 섹션(확률과 우연을 다룸)과 제한(Restriction) 섹션(부분적 또는 불완전한 정보를 다룸)의 바로 중간에 위치합니다.

이 논문의 주요 아이디어를 쉬운 비유를 사용하여 다음과 같이 정리했습니다.

1. 거시적 관점: "관계"의 도서관

**대칭 단항 콤모노이달 범주(Symmetric Monoidal Category)**를 물건을 결합하거나(재료를 섞는 것처럼) 복제할 수 있는(문서를 복사하는 것처럼) 거대한 창고라고 생각해 보십시오.

• **마르코프 범주(Markov Categories)**는 창고에서 꺼낸 모든 물건이 "온전하고" "완전함"이 보장되는 창고와 같습니다. 빠진 것이 없습니다. 이는 확률론에 적합합니다.
• **카테시안 제한 범주(Cartesian Restriction Categories)**는 물건이 "부서졌거나" "불완전할" 수 있는 창고와 같습니다. 모든 입력에 대해 작동하는 것이 아니라 일부에 대해서만 작동하는 함수를 가질 수 있습니다. 이는 부분 함수에 적합합니다.

저자들은 이전에 이러한 창고들이 서로 어떻게 연관되는지에 대한 지도(분류 체계)를 만들었습니다. 이번 새 논문에서, 그들은 이 "완벽한" 것들과 "부서진" 것들 사이에 존재하는 두 가지 새로운 유형의 창고를 발견했습니다.

2. 두 가지 새로운 개념: "질량(Mass)"과 "도메인(Domain)"

저자들은 이 범주들에서 화살표(관계 또는 과정)를 측정하는 두 가지 새로운 방법을 도입합니다.

• 질량 (화살표의 "무게"):
  당신이 패키지를 배송한다고 상상해 보십시오. 화살표의 질량은 창고를 통과해 나가는 패키지의 총 무게를 확인하는 것과 같습니다.

  • 질량 범주에서의 규칙은 다음과 같습니다: "만약 과정을 거친 후에 패키지의 무게를 확인한다면, 목적지의 세부 사항을 무시할 경우 과정을 거치기 전의 무게와 같다."
  • 이것은 과정이 특정 방식으로 (추상적인 의미에서) "물질"(확률 질량)을 마법처럼 생성하거나 파괴하지 않는다는 것을 의미합니다.

• 도메인 (화살표의 "유효 영역"):
  어떤 종이의 특정 부분에만 찍히는 도장을 상상해 보십시오. 도메인은 스탬프가 실제로 자국을 남기는 특정 영역입니다.

  • 도메인 범주에서의 규칙은 다음과 같습니다: "만약 스탬프가 작동하는 영역을 살펴보고, 그 후 과정을 통해 스탬프를 실행한다면, 그것은 단순히 스탬프를 실행하는 것과 정확히 같은 결과를 얻는다."
  • 이는 부분 함수의 개념을 일반화한 것입니다. 이는 프로세스가 특정 입력에 대해 정의되어 있다면 일관되게 동작함을 보장합니다.

3. 발견: 새로운 중간 지대

저자들은 반드시 완전히 "마르코프"(완전하게 전체적인)이거나 완전히 "제한적"(완전히 부분적인)일 필요는 없다는 것을 깨달았습니다.

• 우리는 질량을 존중하지만 반드시 완전히 마르코프일 필요는 없는 시스템을 가질 수 있습니다.
• 우리는 도메인을 존중하지만 반드시 완전히 제한적일 필요는 없는 시스템을 가질 수 있습니다.

그들은 유명한 마르코프 범주가 사실 이 두 가지 새로운 유형의 교집합이라는 것을 증명했습니다. 즉, 어떤 범주가 마르코프라는 것은 그것이 질량 범주이면서 동시에 "약한 마르코프(Weakly Markov)" 범주(특정한 종류의 질량 범주)라는 것과 같습니다. 이는 마치 "정사각형"이 "정사각형 직사각형"이자 "정사각형 마름모"인 것과 같다고 말하는 것과 같습니다.

4. "리프트(Lift)" 메커니즘: 클레이슬리 범주(Kleisli Categories)

컴퓨터 과학에서 **모나드(Monad)**라고 불리는 도구가 있습니다(데이터를 특수한 컨테이너, 예를 들어 상자에 담아 감싸는 기계라고 생각하십시오). 당신이 어떤 범주를 가져와서 모나드를 적용하면, 당신은 클레이슬리 범주라고 불리는 새로운 범주를 얻게 됩니다.

논문은 질문합니다: 만약 내가 "도메인" 또는 "질량" 범주로 시작해서 이 기계를 통과시킨다면, 새로운 범주는 그 속성들을 유지할 것인가?

• 답변: 그렇습니다, 하지만 그 기계(모나드)가 올바르게 구축되었을 때만 그렇습니다.
• 그들은 **"도메인 보존적(Domain-preserving)"**이고 **"질량 보존적(Mass-preserving)"**인 기계들을 정의했습니다. 만약 기계가 "도메인" 또는 "질량" 규칙을 존중하도록 만들어졌다면, 그 기계를 통과해 나오는 새로운 범주 역시 그 규칙들을 존중할 것입니다.
• 이것은 매우 중요한데, 왜냐하면 연구자들이 확률적 또는 부분적 시스템을 구축할 때 어떤 규칙(공리)이 여전히 유효할지 정확히 알 수 있게 해주기 때문입니다.

5. 실제 사례 (사례 연구)

이론이 작동함을 증명하기 위해 저자들은 두 가지 구체적인 사례를 살펴보았습니다.

1. 세미링 가중 관계(Semiring-Weighted Relations): 관계가 단순히 "예/아니오"(표준적인 지도와 같은)가 아니라 "가중치"를 가진 시스템(도로에 교통 점수가 있는 지도와 같은)을 상상해 보십시오. 그들은 이 가중치(세미링이라 불림)의 수학적 성질(예를 들어 $x + x = x$인 "멱등성")이 특정 속성을 가진다면, 결과적인 시스템이 자동으로 도메인 범주가 된다는 것을 보여주었습니다. 이는 왜 특정 퍼지 논리나 확률 시스템이 특정한 방식으로 행동하는지를 설명해 줍니다.

2. 부분 마르코프 범주(Partial Markov Categories): 그들은 존재하지 않을 수도 있는 확률 분포를 다루는 *Partial(FinStoch)*라는 시스템을 조사했습니다. 그들은 자신들의 새로운 "도메인 보존적" 도구를 사용하여, 이 시스템이 실제로 도메인 범주임을 증명함으로써, 이전에는 증명하기 더 어려웠던 사실에 대해 새롭고 더 간단한 증명을 제공했습니다.

요약

단순하게 말하자면, 이 논문은 수학적 논리의 지도를 정교화하는 것에 관한 것입니다.

• 저자들은 "확률"과 "부분성"의 이웃들 사이에 위치하는 두 가지 새로운 "동네"(질량 및 도메인 범주)를 발견했습니다.
• 그들은 데이터를 이 동네들 사이로 이동시키면서도 동네의 규칙을 깨뜨리지 않는 기계(모나드)를 만드는 방법을 보여주었습니다.
• 그들은 유명한 "마르코프" 동네가 사실 이 두 새로운 동네의 겹치는 부분임을 증명했습니다.

이는 컴퓨터 과학자와 수학자들이 코드와 논리 속에서 불확실성, 부분적 정보, 그리고 관계를 모델링하는 것을 지배하는 구조적 규칙들을 더 잘 이해할 수 있도록 도와줍니다.