On the relative asymptotic expressivity of inference frameworks
We consider logics with truth values in the unit interval $[0,1]$. Such logics are used to define queries and to define probability distributions. In this context the notion of almost sure equivalence of formulas is generalized to the notion of asymptotic equivalence. We prove two new results about...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2024-11-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | http://lmcs.episciences.org/9560/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344758473818112 |
|---|---|
| author | Vera Koponen Felix Weitkämper |
| author_facet | Vera Koponen Felix Weitkämper |
| author_sort | Vera Koponen |
| collection | DOAJ |
| description | We consider logics with truth values in the unit interval $[0,1]$. Such logics are used to define queries and to define probability distributions. In this context the notion of almost sure equivalence of formulas is generalized to the notion of asymptotic equivalence. We prove two new results about the asymptotic equivalence of formulas where each result has a convergence law as a corollary. These results as well as several older results can be formulated as results about the relative asymptotic expressivity of inference frameworks. An inference framework $\mathbf{F}$ is a class of pairs $(\mathbb{P}, L)$, where $\mathbb{P} = (\mathbb{P}_n : n = 1, 2, 3, \ldots)$, $\mathbb{P}_n$ are probability distributions on the set $\mathbf{W}_n$ of all $\sigma$-structures with domain $\{1, \ldots, n\}$ (where $\sigma$ is a first-order signature) and $L$ is a logic with truth values in the unit interval $[0, 1]$. An inference framework $\mathbf{F}'$ is asymptotically at least as expressive as an inference framework $\mathbf{F}$ if for every $(\mathbb{P}, L) \in \mathbf{F}$ there is $(\mathbb{P}', L') \in \mathbf{F}'$ such that $\mathbb{P}$ is asymptotically total variation equivalent to $\mathbb{P}'$ and for every $\varphi(\bar{x}) \in L$ there is $\varphi'(\bar{x}) \in L'$ such that $\varphi'(\bar{x})$ is asymptotically equivalent to $\varphi(\bar{x})$ with respect to $\mathbb{P}$. This relation is a preorder. If, in addition, $\mathbf{F}$ is at least as expressive as $\mathbf{F}'$ then we say that $\mathbf{F}$ and $\mathbf{F}'$ are asymptotically equally expressive. Our third contribution is to systematize the new results of this paper and several previous results in order to get a preorder on a number of inference systems that are of relevance in the context of machine learning and artificial intelligence. |
| format | Article |
| id | doaj-art-c9fe520d110f4dfeac746cc79b53f330 |
| institution | Kabale University |
| issn | 1860-5974 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj-art-c9fe520d110f4dfeac746cc79b53f3302025-08-20T03:42:35ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742024-11-01Volume 20, Issue 410.46298/lmcs-20(4:13)20249560On the relative asymptotic expressivity of inference frameworksVera KoponenFelix WeitkämperWe consider logics with truth values in the unit interval $[0,1]$. Such logics are used to define queries and to define probability distributions. In this context the notion of almost sure equivalence of formulas is generalized to the notion of asymptotic equivalence. We prove two new results about the asymptotic equivalence of formulas where each result has a convergence law as a corollary. These results as well as several older results can be formulated as results about the relative asymptotic expressivity of inference frameworks. An inference framework $\mathbf{F}$ is a class of pairs $(\mathbb{P}, L)$, where $\mathbb{P} = (\mathbb{P}_n : n = 1, 2, 3, \ldots)$, $\mathbb{P}_n$ are probability distributions on the set $\mathbf{W}_n$ of all $\sigma$-structures with domain $\{1, \ldots, n\}$ (where $\sigma$ is a first-order signature) and $L$ is a logic with truth values in the unit interval $[0, 1]$. An inference framework $\mathbf{F}'$ is asymptotically at least as expressive as an inference framework $\mathbf{F}$ if for every $(\mathbb{P}, L) \in \mathbf{F}$ there is $(\mathbb{P}', L') \in \mathbf{F}'$ such that $\mathbb{P}$ is asymptotically total variation equivalent to $\mathbb{P}'$ and for every $\varphi(\bar{x}) \in L$ there is $\varphi'(\bar{x}) \in L'$ such that $\varphi'(\bar{x})$ is asymptotically equivalent to $\varphi(\bar{x})$ with respect to $\mathbb{P}$. This relation is a preorder. If, in addition, $\mathbf{F}$ is at least as expressive as $\mathbf{F}'$ then we say that $\mathbf{F}$ and $\mathbf{F}'$ are asymptotically equally expressive. Our third contribution is to systematize the new results of this paper and several previous results in order to get a preorder on a number of inference systems that are of relevance in the context of machine learning and artificial intelligence.http://lmcs.episciences.org/9560/pdfcomputer science - logic in computer science03c13, 68t27, 68q87f.4.1 |
| spellingShingle | Vera Koponen Felix Weitkämper On the relative asymptotic expressivity of inference frameworks Logical Methods in Computer Science computer science - logic in computer science 03c13, 68t27, 68q87 f.4.1 |
| title | On the relative asymptotic expressivity of inference frameworks |
| title_full | On the relative asymptotic expressivity of inference frameworks |
| title_fullStr | On the relative asymptotic expressivity of inference frameworks |
| title_full_unstemmed | On the relative asymptotic expressivity of inference frameworks |
| title_short | On the relative asymptotic expressivity of inference frameworks |
| title_sort | on the relative asymptotic expressivity of inference frameworks |
| topic | computer science - logic in computer science 03c13, 68t27, 68q87 f.4.1 |
| url | http://lmcs.episciences.org/9560/pdf |
| work_keys_str_mv | AT verakoponen ontherelativeasymptoticexpressivityofinferenceframeworks AT felixweitkamper ontherelativeasymptoticexpressivityofinferenceframeworks |