Logical view on fairness of a binary classification task
Authors: Serge Berger
Venue: Submitted to ICLR 2023 (2023)
Keywords: binary classification
fairness
first-order logic
decidability

Abstract: Ethical, Interpretable/Explainable, and Responsible AI are an active area of research and important social initiative. 

We prove that, with no regards to data, fairness and trustworthiness are algorithmically undecidable for a basic machine learning task, the binary classification. Therefore, even the approach based on not only improving but fully solving the three usually assumed issues -- the insufficient quality of measurements, the complex consequences of (mis)measurements, and the limits of existing social theories -- is only heuristics. We show that, effectively, the fairness of a classifier is not even a (version of bias-variance) trade-off since it is a logical phenomenon. 
Namely, we reveal a language $L$ and an $L-$theory $T$ for binary classification task such that the very notion of loss is not expressible in the first-order logic formula in $L$. 

Under review as a conference paper at ICLR 2023
LOGICAL VIEW ON FAIRNESS OF A BINARY CLASSIFICATION TASK
Anonymous authors Paper under double-blind review
ABSTRACT
Ethical, Interpreeable/Expliiaalele and Responsible AI are an active area of re- search and important social initiative. Vendors offer solutions. For instance, Microsoft compiled a platform, Responsible AI. Within the context, challenges of algorithmic faimess and trustworthiness of machine learning paramount. Furthermore, several authors argue that the emergence of algorithmically infused societies necessitates innovative approaches to measuring feasible information, e.g., collecting data shall follow a trustworthy social theory. In this paper, we show that this approach is heuristic at best.
We prove that, with no regards to data, fairness and trustworthiness are algorith- mically undecidable for basic machine learning task, the binary classification. Therefore, even the approach based on not only improving but fully solving the three usually assumed issues the insufficient quality of measurements, the com- plex consequences of (mis measuurnauss,,sss,,, and the limits of existing social theories is only heuristies. We show that, effectively, the fairness of a classifier not even (version of bias variance)) trade-off inasmuch as it is a logical phenomenon. Namely, we reveal language and an L L-theory for binary classification task such that the very notion of loss is not expressible in the first-order logic formula in I..
1 INTRODUCTION
Ethical, Interretable/Fxxlaainhee, and Responsible AI are an active area of research and important social initiative. Vendors offer solutions. For instance, Microsoft compiled a platform, Responsible AI. Within the context, challenges of algorithmic fairness and trustworthiness of machine learning are paramount. Furthermore, several authors argue that the emergence of algorithmically infused societies necessitates innovative approaches to measuring feasible information, e.g., collecting data shall follow a trustworthy social theory [3]. Difficulties, associated with such approach, can be found in [7]. Moreover, in this paper, show that this approach is heuristic at best.
We prove that, with no regards to data, faimess and trustworthiness are algorithmically undecidable for binary classification task (cf. [4], [5]). Therefore, even the approach based on only improving but fully solving the three usually assumed issues - the insufficient quality of measurements, the complex consequences of (mis) measuremnnts,,, and the limits of existing social theories only heuristic. We prove that, effectively, the fairness of a binary classifier is not even a trade-off (e.g., version of hlaa-varriane/coopleityy etc.) inasmuch is logical phenomenon. Namely, we reveal a language L and L-theory T for binary classification task such that the very notion of loss is not expressible in the first-order logic L-formula.
Note that the essence of "mass view" " approach is that unlike in a traditional machine learning context, we are not making any assumptions on nature of a classifier loss, other than it should provide a way to compare two (potentially different) classifiers. Under this very broad perspective, it turns out that, in natural model, the loss of classifier is inexpressible as first-order logic expression (cf. Appendix for the definitions). Without loss of generality, it follows that any feasible definition of faimess for machine learning classification task is undecidable. Indeed, one has to assume that two classifiers have to be comparable in their performance characteristics in the first place. If the latter is not expressible, then one cannot achieve sensible conclusion on fairness. By the same token, since all derived heuristics such as transparency, interpretability and trust, must include notion of faimess,

---

Under review as a conference paper at ICLR 2023
the undecidability result immediately generalizes to these concepts (thus complementing results of [4]).
More specifically, present almost surely decidable model where the classifier loss is not expressible. Thus, undecidability of a classifier loss is not necessarily associated with undecidability of the model. However, if we utilize yet another view of binary classifiers over infinite domain, the class, viewed as a lower bounded lattice, is (first-order logic) undecidable.
Throughout the paper, we consider the natural generalization of the binary classifier for the infinite domain.
Our goal is to introduce purely logical view on loss for binary classifier achieved by introducing general notion of classifier loss based on an observation that any natural loss is a first-order formula in a suitable structure. The latter has a theory T represented by tuple (L, M) where L is a language and M is model for L.
infinite domain. It
Next, will show that the resulting first-order theory T admits an extension RG on random graph structure such that a notion that graph has an equal number of connected and unconnected nodes not expressible the -irsst-rrttrrr logic. The binary classifiers' structure is isomorphic (with probability 1 to T. Therefore, if a first-order sentence in one theory is deducible (i.e., can be proved) in that theory, the corresponding sentence deducible in another.
Then, for two given classifiers, assuming that the classifier loss is first-order logic formula, C1 (D, Lai) and C2 = L2), we can construct first-order expression Lel Lea which is equivalent to an expression that the two classifiers have the same number of connected and unconnected nodes which leads to contradiction. This effectively means that any loss function not expressible in the RG first-orrer logic. The rest of the paper is dealing with the proof of these statements. It is interesting to compare this with a general undecidability of identities for wide class of functions in [1].
We conclude with discussion of losses expressible in second and higher logic theory and immediate implications for adopting them fairness and interpretability (the extended version of the paper contains more information on each of these topics).
1.1 NOTATIONS AND DEFINITIONS
We will try to make this paper self-sufficient and provide all necessary references to the reader who would like to invest more time into the mathematical foundations of machine learning and interpretablity. We would need some information from model theory. We assume that the reader is familiar with the concepts of domain, classifier, and loss as well as the standard body of statistics and probability theory normally used a supervised machine learning. Notations are natural; N denotes the set of natural numbers, Z stands for integers, and R denotes reals. RR,, would be positive reals. I, or normally stands for a loss unless it is a space which is then defined explicitly. S ~ means a sample from a distribution D; contextually, D can stand for domain. In general, we assume an infinite countable domain.
Traditionally, given hypotheses space H and domain Z, loss / is non-negative real function H: R..
We denote (h) a standard expected loss of a binary classifier h E H over domain X where H is hypotheses space, with respect to probability distribution D; by definition: LD(h) Es-Dllo- (h, =)], and, since for 0-1 loss Z ranges over pairs,
{ if h(x)) = if h(x)) マリ
10 10
We also need some definitions from model theory and logic. A filter a on the set of natural numbers N is collection of sets of natural numbers obeying the following axioms:
1) If E FF CN and E Ea then F Ea;
2) If E Ea and F Ea then E nF Ea;
3) Empty set & a.
2

---

Under review as a conference paper at ICLR 2023
An ultrafilter the natural numbers is filter which obeys additional axiom: If E CN then exactly one or N,E' Ea. A non-principal ultrafilter is ultrafilter that obeys one additional axiom yet: 4) No finite set belongs to a.
It easy to see that non-principal ultrafilters exist. We can start with the filter of cofinite (i.e., the complements of finite sets in N), and applying Zorn lemma [3] to embed the filter into an ultrafilter. We call an ultrafilter principal if it is not non-principal. One can prove that every non-principal ultrafilter of the form {E C N/n E E where a natural number.
One fundamental property of binary classifier μ 2 + {0. 1). if it maps o-large sets to 1, and a-small sets to O, is that is finitely additive probability measure. Moreover, every finitely additive probability measure has this form.
We also are going to an important tool from model theory that is called ultraproduct Ilirr L//U where L; are some algebraic structures indexed by i I, and U is an ultrafilter. Algebraic operations
the ultraproduct defined the same way in a Cartesian product of L; and the ultraproduct is a quotient set with respect to relation which is defined as follows: x o y iff / ar v1) E U.
{i E
Since we need some notions from lattice theory, remind the fundamentals of it. Lattice is partially ordered set in which any two elements have supremum and an infimum. Zı, I E N is lattice (Zz, <) if we set a a b in bj and a b sup(a, b}.
Then Zi is an algebra and a lattice. For a lattice L, we put 1 aa- = {b E Lib 2 a} and I a {b e Lib S a}.
If we fix the domain, then a multi-class classifier, as structure, defined (by the lattice isomorphism) by the ordered set of values in Z,. (A( denotes a standard 0-1 loss for binary classifier A.
Finally, we need to touch decidability. Intuitively, is the situation in first-order logic theory when we can find an effective algorithm that decides whether a well-defined formula for the theory is true (in particular, it does not loop indefinitely - the very reason why halting problem is undecidable). The first-order logic is natural setting for the context, because the second order (and, in general, higher order) logic only leads to difficulties in any formalization or contemporary understanding of interpretabilityy The celebrated Gödel incompleteness theorem, for instance, deals with the second order formulas.
These definitions are sufficient for our purposes. We need only point out that these funda- mental notions normally essential for non-standard analysis. However, we deal with standard context herein and just use them in some proofs.
1.2 RANDOM GRAPH CLASSIFIERS
There is one interesting class of classifiers. similar in nature to binary classifiers, such that its first- order theory is almost for sure decidable (in the sense of probability). This class associated with random graphs. We would call those the random (binary) classifiers. The class defined as follows. Assume that domain is enumerated (countable). Consider graph with vertex set N of all natural numbers. Pick "random" binary classifier A which is the one that decides on every scoring randomly, with probability 2 Let RG be the resulting structure.
To decide whether there is an edge between x and y (with æ Ayy) we check values A(x) and A(y). If they coincide, then, by definition, there an edge, otherwise there not. Being viewed as structure, the class of binary classifiers is bounded lattice in case of finite domain, and left bounded lattice in case infinite domain.
In fact, the very same proof works within the context, we assume a ratio 2 where p and y are integer numbers such that 0 < 2 1.
3

---

Under review as a conference paper at ICLR 2023
The class of all graphs built this way forms the class of random graphs. We show next that all these graphs are isomorphic (as graphs) with probability (i.e., almost for sure). Namely, consider two disjoint finite subsets of N, X and Y, with respected sizes and Consider that is joined to every element of X and no element in Y; we would call that property P. Given any vertex æ, the probability it does not have the property P above is p = 2 mm+m) So, for different vertices, the probability that none of them has the desired property is pm* Clearly, this would converge to zero if n is going to infinity. Thus, at least one z E N will have the property, with probability 1. Taking into account the fact that there are only countably many disjoint pairs (X,Y) Y) of finite sets in x N, with probability 1, for each pair (X, Y) we can find a vertex that x is joined every vertex in X and to vertex in Y. Let P be that property.
element E N
Denote the resulting structure by RGezt defined by the property P. Any binary classifier C'= (D may be viewed as an element in RG where each element the domain is represented by a pair of vertices in RGG. Loss of the classifier C' is defined accordingly and becomes a first-order expression in the theory = Logxt-theor where LoEzt is the extension of basic logical language Lo extended with the property P.
From that point, we can simply repeat the arguments from [2], Chapter IV.23, pp.645-646 and deduce that the first order theory of random graphs almost surely decidable, so the first order logic theory of binary classifiers, associated with random graphs, is almost surely decidable too.
In particular, we can consider the extension RG for RG with additional property that with probability 1, for every pair (A, B) of disjoint subsets in our domain, there is vertex such that joined to every vertex in A and no vertex in B.
Q.E.D.
Namely, we have the following
Proposition 1.1. The theory LoEan of random graph classifiers RGest is almost surely decidable.
For completeness, we provide the proof based on an extension in the appendix.
MAIN RESULT
2.1 INEXPRESSIBILTTE OF FAIRNESS
Let theory T be (as above) the LoEze-theoe of binary classifiers based structure RG Despite of the fact that the theory is almost surely decidable, once cannot use any first-order expression to compare two binary classifiers. Namely, the following theorem holds:
Theorem 2.1. Two binary classifiers cannot be compared using any first-order logic expression T.
Proof. Assume that the classifier loss is expressible in figst-first-odder logic of T. By Marker's theorem for almost sure theory of graphs (c.g., cf. [2], p. 646), the theory obeys a zero-one law tends as N - inf. On the other hand, can that the probability that random graph contains r( ( edges tends to 1/r as N tends to infinity for any integer r >
which states that for any Seneeneentence á the probability (Ø) tends
Translating this to classifiers in RG consider any non-trivial classifier. Its loss function then would tend to one or zero as we enumerate the elements domain. Thus, we witness a contradiction with the fact that the limit is between and one. Q.E.D.
4

---

Under review as a conference paper at ICLR 2023
(1)
b
{0}
Figure Finite Lattice Diagram representation
UNDECIDABILITY
Theorem 3.1. Given domain the class of binary classifiers over (viewed as lower bounded lattices) is (first-order logic) undecidable
Proof.
The main idea is to show that the class is not closed under ultraproducts (or Cartesian products). Then, the class is not axiomatizable. As a consequence, being viewed as a structure, it is not decidable.
We first consider the case of finite domain. Strictly speaking. not every binary classifier, viewed as structure, is a lattice. However, if it is, the immediate observation is that, up to lattice isomorphism, such binary classifier is bounded. Namely, for a lattice I., A lattice homomorphism h M - L is lower bounded if for any E L,, set 1 (a)) is either empty or has the least element. A lattice is lower bounded, any homomorphism from finitely generated free lattice is lower bounded. Dual definitions are established for the upper bounded lattices.
consider set t (a) = (b E L.bb 2 a).
If lattice is lower and upper bounded, then it called bounded. Any binary classifier is lower bounded as a lattice is representable as a lattice. obvious for finite classifiers, since we can view classifier as a lexicographically ordered sequence of pairs (Iz, y1), i N and thus it contains 0 (the lowest bound). Given a finite domain, it also contains 1; any homomorphism preserves Os and 1s. For an infinite domain D, assume it can be countably enumerated (thus, the order of the product D x D is lexicographical) Then, any classifier on such domain is lower bounded, since D, as lattice would contain 0.
Any finite lattice I, can be identified as a binary elassifier I: x I. - {0, 1} that is associated with the lattice diagram in the following manner. The lattice is represented, up to isomorphism, by its diagram which is directed graph G = G(V. E) such that for every E V C. L there is no such that a > x >> c for vertices a and with edge e(a, e) (covering property). The direction of the is pointing towards smaller element. Then we simply set classifier value to for the pair (a, c). If a the diagram, we set the value to zero. It is not difficult to check that the diagram can be restored from the classifier only one way (cf. I the process, I(a,c) ++1 and I(c.a) +0).
pair (Ir, y)
"(Informaly, there is no efficient algorithm that decides whether a well fell-formed formula in the first order logic theory of binary classifiers is true. Therefore, if we try to find an "interpretable" explanation for a phenomenon heing explained by model, then, in general, that explanation may not be possible to formulate in first order logic terms. One may argue that this reduces the very notion of interpretability heuristics).
5

---

Under review as a conference paper at ICLR 2023
We need the following result from [6].
Theorem 3.2. There are finite lower bounded lattices L,, i E I for Cauchy filter D such that Iler Li/ is not lower bounded.
The theorem is stated there for just bounded lattices; however, is valid for lower bounded lattices as well for completeness, we present the proof in the appendix. To prove our result, theorem 3.1 we only need notice that, according to the theorem 3.2 the product is lattice, but it no longer binary classifier, that is, there are finite (lower bounded) binary classifiers such that their ultraproduct not a binary classifier.
Q.E.D.
4 CONCLUSION
An elementary class (or axiomatizable class) consists all structures satisfying a fixed first-order theory. There to be a reason to move to the second-order logic; however, with higher expressiveness, and some inheritance of the first-order logic properties, there important negative effects, associated with completeness and compactness theorems. More practical approach is to use the first-order logic.
few limitations of expressiveness of elementary classes. Theorem 3.1 seems
Discussion One may ask natural question whether the second-order and higher order logic is more suitable for the modeling the machine learning tasks for formalization of fairness, because the first-order logic has quantifiers' scope "reduced" to elements, rather than sets. Clearly, binary classification task is only useful tool if we verify the model the individual level (e.g., the target wawiggaann/oonmmlliinnnnn
tumor in medicine). Moreover, we would like our formalism be as simple possible, that our expression of boolean target shall refer to individual prediction rather than subset of those, because the problem of defining and selecting the subsets is likely (and, logically, will be) more complex than task in the first place, least, for majority of practical problems. By the same token, interpretability requires its scope to be at the individual elements.
Once more point is permissible here for computer science settings. The mass view approach is fundamentally different from adopted (un)decidability patterns of computability theory (e.g., Rice theorem about semantic properties of a program). It is viewpoint inspired by model theory.
In addition, one important consideration is due to formal verification. Many modern verifiers and theorem provers use higher order logic since they employ type theory. However, the verification and automatic proving are yet other research domains that are not being discussed in this paper.
ACKNOWLEDGMENTS
The author thanks Prof. V. Pestov for his extremely useful comments. In particular, he pointed out that the phenomenon of inexpressibility can be associated with nonmeasurability of the classifier (the standard model just assumes Borel measurability). That prompts an additional question about the classifier such as what its Bayes loss is which we not address this paper since it is out of scope for the mass view approach on classification that does not make any assumption measurability.
REFERENCES
[1] Richardson, D. (1968) Some unsolvable problems involving elementary functions of real variable. Journal Symbolic Logic 33:514-520.
[2] Gowers, T. & Barrow-Green, & Leader, (2008) Princeton Companion Mathematics. Princeton and Oxford.
[3] Wagner, C. & Strohmaier, M. & Olteanu, A. & Kiciman, I. & Contractor, N. & Eliassi-Rad, T. (2021) Measuring algorithmically infused societies. Nature 595:197-204
[4] Ben-David, S. & Hrubes, P. & Moran, S. & Shpilka, A. & Ychudayoff, A. (2019) Learnailityy Can Be Undecidable. Nature Machine Intelligence 1(1):44.

---

Under review as a conference paper at ICLR 2023
[5] Sehra, S. & Flores, & Montanez, G.D. (2021) Undecidability of Underfiting in Learning Algorithms. In The 2nd International Conference on Computing and Data Science (CONF-CDS 2021).
[6] Schwidefsky, M.V. (2016) The class of bounded lattices is not axiomatizable. Algebra and Logic, 55(4)3327 330.
17] Dai, J. & Fazelpour, S. & Lipton, Z. (2021) Fair machine learning under partial compliance. In Proceedings of the 2021 AAAI/ACM Conference AI, Ethics, and Society 33:55-65.
[8] Freese, R. et (1995) Math. Surv, Monogr, Amer: Math. Soc. 42 Providence, RI

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.I PROOF OF PROPOSITION I.1
Theorem A.1. RGext almost surely decidable.
Proof. This is completion of the proof sketched in the main text. We aim to construct extension for the first-order theory such that it is almost for sure decidable. In the main text, we proved that, with probability 1, there a countably many disjoint pairs (X, Y) of finite sets, for every such pair one can find x E X that is joined to every vertex in X and to no vertex in B. That extension property formalization as follows:
(i) Va I ~ y
(ii) Vz (x J);; (iii) nn for n,, m 2
where & m is the formula:
Vor...tn Vyi...um A A x, # Ui
3=((N ~ x) (M -yi ~ z)).
Consider the theory for graph with the extension property (i)-iiii holds for any pair of disjoint finite set of vertices. By the argumentation above in the main text, with probability I, random classifiers are models T.
are isomorphic. The isomorphism can be con- structed as follows. Induction. Given model M, and M2, and enumerations ag, ai, of vertices in Mj and bo, bi.... of vertices in M2, let set f(o)) = by. For a1, a1 is joined to dg. find a vertex that is joined to bp. and in similar way, if not. These are property 11,0 and o correspondingly, Selecting alternatively an image for the first a that does not yet have an image, and preimage for the first by that does not yet have preimage, and regular case 2..j. continue by induction.
Moreover, any two countable models
The theory T is complete. Furthermore, there is algorithm that decides whether any formula or its negation are true in very model of T. That is simple corollary from the previous considerations. To prove completeness, assume that the opposite is true. Then, by compactness theorem, there are two countable models MI, M2 such that formula is true in M,, but its negation is true M2. This would mean that there are two non-isomorphic models of T which is not the case. Similarly, to prove that there a deciding algorithm for T, for any formula, one would search the proofs for it or its negation. By completeness theorem (Gödel, Henkin), syntactic and semantic consequence equivalent for first-order logic, so we will find eventually proof for the formula or its negation.
To prove almost for sure decidability for random graphs, we only need to notice that T provides the proof for formula & or its negation. The proofs finite, so the proof can only finitely many statements Pn,m- Thus, there exists m E N such that M } pm then M -= Φ. As we saw before, the probability of M - 2m.m tends when m - so is the probability of M F ó. This means that the first order theory of random graphs is almost surely decidable. Q.E.D.
A.2 PROOF OF THEOREM 3.2
Proof.
That statement is the main result of [6]. Following the very construction of [6], we need only to build ascending chain of elements in the free lattice that its image under natural embedding saves the order of elements.
Next, given domain, bounded lattices. More specifically. let X will be a finite set with at least free elements (that is not a real restriction for binary classifier case, because logically multinomial classifier can be split into
identify classifier with embedding into inverse limit of finite
8

---

Under review as a conference paper at ICLR 2023
sequence of binary ones), and let (XX) be free lattice generated by X. is known [8] that F(X) embeds into an inverse limit of finite bounded lattices.
Specifically, there are finite bounded lattices, L, w, and surjective lattice homomorphisms Tij Lj + Li, i I j < w such that Tis = Idz, and Ti = T for all S j S < w. and embedding Φ F(X) - I I for which ne = T with any i S j where TT : I.w L; + Lx is the canonical projection for any < w.
Fix a filter over w, e.g.. the filter of all cofinite subsets of w. Then the map o(a)/$ is lattice homomorphism, by definition. In fact, it is a lattice embedding. Namely, suppose a & b in F(X). then we have n,,(() # x;b(b) for some < w. For the inverse limit, it means that T. (a) + T. T(b( for all n 2 i. Immediately, E(a)/ + /bb)
F(X)
IIw 5 :
Next, consider t E F(X) and an ascending chain faz, < w} in F(X). Then (Tn w// S E(t) if and only if a, S for all < w. We will prove now that homomorphism & is not lower bounded. It is known (ef. [8], Example 1.24, Whitman) that F(X) contains an infinite ascending chain {a, |m < w] which does not have least upper bound.
Consider (Tn,(an)) In < w)/2. Since 1 E E (t x), follows that the last set is non-empty, Therefore, if we choose arbitrary element from the set, have {(t) 21 a. As saw before, it means we have t 2 an for all n S w. Since l is not a least upper bound for the sequence {an In < w). there exists L such that
w. As usual, means that E(4,) 21 and thus t E E- (f a). Hence the set 5 (t a) does not have least element, i.e., & is not lower bounded.
an for all
Q.E.D.
One variation of the proof for binary classifiers is based on the following consideration. For finite and countably infinite domains, binary classifier is distributive lattice over N we fa V b, A b} = {a. b} Ya, b. As is known, for very partial set (poset) C' there exists unique, up to isomorphism, free completed distributed lattice I. over C with embedding á C L. such that for every distributed lattice M, and a monotone function f' C M there exists unique homomorphism So that the following diagram is commutative:
C
L
f0
M
id
M
This allows us to uniquely identify a classifier (as a distributive lattice) with a free distributed lattice embedding; more precisely, with its image under the embedding Since L is free lattice generated by C, it, in turn, embeds into inverse limit of free finite bounded lattices [6].
Next, it is sufficient to prove that there are finite lower bounded lattices the embedding above, that are identified as binary classifiers, that for non non-principal ultrafilter D (c.g., w), the ultraproduct IhEE L,/ is not lower bounded.
Then, we can find an infinite chain in the embedding directly, and the rest of the proof is as above.
A.3 FORMAL DEFINITION FOR LANGUAGE L
Let be a language (an extension of basic formal logical language, Lo).
Definition The set of L Lerms is the smallest set L, such that contains all constant symbols of L, all variables, and if f1, 122 ..., in are in L, then for any n-ary function symbol f. f(11, t2, .2., tx) is also in L, Set La of atomic formulas (1) t, and to are terms then t = t2 is in L,,, and (2) the corresponding n-ary function symbols also in Taa-
represented by the properties:

---

Under review as a conference paper at ICLR 2023
In other words, the set of all formulas in L (expressions, sentences herein, use these interchange- ably) is the smallest set containing all atomic formulas and closed under logical connectives V, A, 7 ++, quantifiers 3, V, equality symbol parenthesis " (" and ")", and variables.
10


Reviews:
[{"review_id": "wDQIlMDSuc", "reviewer": "Reviewer_ExFJ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "I am unable to review this paper.", "summary_of_the_review": "NA", "strength_and_weaknesses": "NA", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Xfdc0q0jw9T", "reviewer": "Reviewer_ZpSj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In the development of social sciences to investigate human societies, measurement models in the social sciences did not keep in mind the deep societal reach of  algorithms. This calls for new methods to measure feasible information. However, this paper shows that innovative approaches to obtaining such fair and trustworthy information are heuristic at best. \n\nThe ineffectiveness of fairness in a machine learning task is proven by a purely logical view on fairness of a binary classification task. Namely, it is shown that first-order logic language 𝐿 and 𝐿- theory 𝑇 for binary classification is not expressible in the first-order logic 𝐿-formula. This means in first-order logic that fairness and trustworthiness is algorithmically undecidable for binary classification. And so we are unable to find an effective algorithm that decides whether a well-defined formula in logic theory is true. To prove this undecidability, the paper looks at a special class of classifiers that, in logic, are similar to binary classifiers. These classifiers are called random binary classifiers, and they are based on a random graph structure. It is shown that random graphs are isomorphic, which results in the theory of random graphs to be almost surely decidable. However, in a considerable proof it is shown that despite random binary classifiers to be almost surely decidable, one cannot use any first-order logic expression to compare two binary classifiers fairly. Hence, we arrive to the conclusion of the paper, that fairness in binary classification remains to be heuristic at best. The paper suggests further research on higher-order logic.", "summary_of_the_review": "Overall, I think this is an interesting and possibly, a novel paper. It took me some effort to understand everything, which will probably have to do with me, but maybe also with the way the paper is written.", "strength_and_weaknesses": "Strengths: \n\nUse of first-order logic in machine learning\nPaper with profound mathematics with mainly known-results\n\nWeaknesses: \n\nFields of mathematics are mentioned, but I doubt that they are immediately obvious to regular machine learning researcher. It seems to be model theory at first, next I’m thinking it’s more real analysis. This may be due to the order of the paper. However, many definitions are introduced in Section 1.1. \n\nThroughout the paper and its proofs, I am missing the connection to a more intuitive definition of fairness in a classification task.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-y-UiqaBeyE", "reviewer": "Reviewer_isj2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper claims that it proves that fairness and trustworthy are undecidable for binary classification. The authors frame this as a first-order logic problem to guide their proof.", "summary_of_the_review": "See above. Paper's contributions are not clear, both in a big picture sense and in terms of how it relates to the field on algorithmic fairness. It is also not clear what is novel here, even if it were relevant (e.g., see footnote 2 in the paper).", "strength_and_weaknesses": "I am not entirely sure what the point of this paper is, unfortunately. The introduction makes claims about fairness and trustworthiness not being decidable, but the preliminaries (which claim to be self-contained) do not provide a formal mathematical definition of either concept that would be necessary to make claims about decidability. This is not made clearer in section 2.1, where the first result concerning inexpressiveness of fairness is claimed. Some translation here between any common fairness metric and the claim here would be helpful. Moreover, I do not understand how the claim in section 3 around undecidability is novel (even if it is valid), which also seems acknowledged in footnote 2. I also do not understand how these claims relate to trust, as the concept does not come up again in the paper. Overall, I am not sure what the contribution of the paper is, or what I should take from it.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject