Many tasks in statistical and causal inference can be construed as problems of entailment in a suitable formal language. We ask whether those problems are more difficult, from a computational perspective, for causal probabilistic languages than for pure probabilistic (or “associational”) languages. Despite several senses in which causal reasoning is indeed more complex—both expressively and inferentially—we show that causal entailment (or satisfiability) problems can be systematically and robustly reduced to purely probabilistic problems. Thus there is no jump in computational complexity. (...) Along the way we answer several open problems concerning the complexity of well-known probability logics, in particular demonstrating the ${\exists \mathbb {R}}$ -completeness of a polynomial probability calculus, as well as a seemingly much simpler system, the logic of comparative conditional probability. (shrink)

This paper revisits the bearing of underdetermination arguments on scientific realism. First it argues that underdetermination considerations provide good reason to doubt that science is objective in the strong sense that anyone following the its methods will be led closer and closer to the truth about any given question within the purview of those methods, as more relevant data are considered. Then it argues that scientific realism is difficult to maintain in the absence of this sort of objectivity.

The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. But how could this leave room for a learning theory, that shows that some algorithms are better than others? Drawing parallels to the philosophy of induction, we point out that the no-free-lunch results presuppose a conception of learning algorithms as purely data-driven. On this conception, every algorithm must have an inherent inductive bias, that wants justification. We argue that many standard learning algorithms should rather (...) be understood as model-dependent: in each application they also require for input a model, representing a bias. Generic algorithms themselves, they can be given a model-relative justification. (shrink)

Ravit Dotan argues that a No Free Lunch theorem from machine learning shows epistemic values are insufficient for deciding the truth of scientific hypotheses. She argues that NFL shows that the best case accuracy of scientific hypotheses is no more than chance. Since accuracy underpins every epistemic value, non-epistemic values are needed to assess the truth of scientific hypotheses. However, NFL cannot be coherently applied to the problem of theory choice. The NFL theorem Dotan’s argument relies upon is a member (...) of a family of theorems in search, optimization, and machine learning. They all claim to show that if no assumptions are made about a search or optimization problem or learning situation, then the best case performance of an algorithm is that of random search or random guessing. A closer inspection shows that these theorems all rely upon assigning uniform probabilities over problems or learning situations, which is just the Principle of Indifference. A counterexample can be crafted that shows that NFL cannot be coherently applied across different descriptions of the same learning situation. To avoid this counterexample, Dotan needs to privilege some description of the learning situation faced by scientists. However, this means that NFL cannot be applied since an important assumption about the problem is being made. So Dotan faces a dilemma: either NFL leads to incoherent best-case partial beliefs or it is inapplicable to the problem of theory choice. This negative result has implications for the larger debate over theory choice. (shrink)