How can a finite number of observations justify confidence in complex theories

Question

First I'll tell you a bit about how (at least modern) software development works to clarify what I mean by a "test". I'll also narrow the scope to a very particular kind of test known as block box testing since its the simplest form of test and is often highly effective in practice. I try not to assume too much about the nature of programs or programming here but I don't think I entirely accomplish that. Please feel free to ask questions!

A program (for the purposes of this discussion) is something that can be given inputs such as numbers or text and produces outputs. This narrow definition of a program can be mathematically formalized as a function. Specific inputs produce specific outputs. Under this simplified definition if the same inputs are given on two separate occasions, the same output is produced. A program of this kind is just a mechanical realization of a mathematical function.

When creating programs, programmers make mistakes. Sometimes programmers get it right however. In order to build confidence that a program has been created to mimic the desired function, other programs are creates to "test" the program. These programs that "test" another program are called "tests" conveniently enough. A test will give various inputs, one at a time, to a program under test to see if the program outputs the desired values. If an input is found that causes a mistmatch between the output and the expected output, we have a bug. If no bugs are found by the tests, we say the tests are passed (but we don't say that the program is correct because we haven't checked all possible inputs).

It's hard to explain why this process should give confidence of correctness however. Certainly I should have more confidence in a program if I've run some tests on it than if I've run no tests since I at least know that the tested inputs are correct. I should also have a bit more confidence if I test a new input and it sill passes. The more inputs I test the more confidence I should have. But why?

In practice forms of black box testing that randomly check many thousands of inputs consistently find bugs in practice. Programs which pass these checks generate very high confidence in practice. Additionally when tests check all "small" inputs exhaustively this generates high confidence as well. There are cases where the programmer has some information which tells them that the such randomized testing is unlikely to catch the inputs of greatest concern and this can undermine these high levels of confidence but in general this sort of testing typically generates high levels of trust that the program is correct.

One incomplete explanation is parsimony. As more and more inputs are attempted, a program which is correct on all of those inputs and yet not on some other input becomes more and more complicated to write pending contrived cases like a correct program modified to output something incorrect on one highly specific input. Can we be more formal?

It's similar to "why does seeing another black raven increase my confidence that all ravens are black" but each observation can be distinguished in this case. Additionally, while I haven't elaborated on this, programs have specific structure. For instance we can talk about the "size" of a program or we can talk about the kinds of mistakes programmers are likely to make in practice. Does this difference in structure change the problem? Does it give us a way to talk more concretely about evidence in confidence based on tests?

Answer 1

Just warning you, this is a math heavy proof. Lets start by defining some terms:

N = number of tests preformed
P(S) = probability of a result happening if S was true

S1: The program does not have a bug.
S2: R = (number of inputs the give a correct result)/(number of all possible inputs) = 1 
S3: r = (number of inputs the give a correct result)/(number of all possible inputs) =/= 1

D1: Iff S1 then S2.
D2: Iff S3 then not S1.

I believe it is rather trivial to prove deductions 1, and 2. Moving on, all outcomes of testing can be divided into 2 cases. First case, one or more tests returned negative results. If this happens, then S3 is true, which proves S1 is false via D2.

Second case, all tests returned positive results. In this case, P(S2) = 1/R^N = 1 and P(S3) = 1/r^N < 1. Lets add one more new term

D = P(S2)-P(S3)

Now for some simple algebra with a limit:

lim [N->inf] (D) = lim [N->inf] (P(S2)-P(S3)) 
= lim [N->inf] (1/R^N)-(1/r^N) 
= lim [N->inf] (1-1/r^N)
= 1

The conclusion is that if every test gives a positive result, then as the number of tests increase the difference between S2 being true and S3 being true grows. By D1 and D2 the exact same thing happens with S1 and not S1. In other words, as the number of tested a programs passes grows, the more likely it becomes that the program does not have a bug than it does.

Here is were things get philosophically interesting though; is there a correlation between D and the amount of confidence someone has that a statement is true? In other words, do people place more confident in statements that are more likely to be true? You may be tempted to just shout 'Yes, of course!', but I am not so sure. You see, the problem is flat-earthers.

It is generally accepted that P("The Earth is flat") is incredibly small (possibly even 0). Yet, there is a significant amount of people who display a high level of confidence that the statement is true. Without some mechanism to explain this discrepancy, these people prove that the above question must be answered 'No'. Fortunately, I have such a mechanism at hand.

Belief that the probability of a statement being true is a factor in determining confidence does not imply that no other factors can exist. I believe that most psychologists refer to such factors as 'biases', but I am not 100% sure that probability of truth and biases are the only factors.

Answer 2

The more inputs I test the more confidence I should have. But why?

In the general all question, given a black box with infinite possible inputs and some output, and with unknown complexity, it is unclear what amount of testing will give what amount of confidence when predicting the next behavior of the black box.

However when the complexity of the interior of the box is known (white or grey box), then the actual behavior of the box is likely completely describable using a simple function, and thus only a few samples are required to check it matches the intended function.

As a concrete example, consider the problem of tracing electrical wiring inside a wall using a voltage detector. Without any other information, you'd need to test every point of the wall with the detector to determine whether there is wiring at this point. But when you can be sure that all wiring is done horizontally and vertically (from outlets and switches), you can test only a few points or lines of a wall and still be confident afterwards that you know all the invisible wiring.

Software testing follows the same principle, a software is generally assumed to follow certain principles such that only using a few data points, the structure can be confirmed with high confidence. This assumption is made viable by applying certain methods and conventions when creating and documenting software (similar to electrical wiring being laid out horizontally and vertically in drywalls).

Answer 3

It comes down to intelligible intelligence. Which I suggest is a specific case of mutual intelligibility. As an experiment, people tried reverse diagnosing the function of a microchip; it was basically impossibly difficult. You need insight into how something occured, and how it fits within systems, to make sense of it. Language is like this too. An machine learning program can undertake an opaque learning process, which can have completely unpredictable features - unless it is drawn into a web of intelligibility, into the web of understandings & abstractions we call language. This is like finding a bridge between languages. Really advanced AGI, or aliens, might have a web of abstractions which can encompass our set of abstractions (eg senses +all-mutually-intelligible-words +maths) but not be expressed in them. Then we would be like a dog being shown relativity.

You could take a defined volume, if it has maximum entropy it is completely chaotic, like say a section of the superfluid at the centre of a black hole, thought to occupy the maximum density of states. Every notch toward less entropy than that, involves some symmetry, some reduction of total possible complexity. And that is abstraction. For a given closed system of a certain complexity there are finite abstractions that can work, and through testing you can narrow down on the tree of possibilities at least to certain categories or limbs.

But, entropy can only be measured in relative terms, as change of state. If there is hidden information that you can't gauge from heuristics and knowledge of available states, that can always be a source of unpredictability. If you build the system, you should be able to put at least boundary conditions on the type & scope of errors. Systems capable of self-directed learning are an interesting case, if that was in the black box. Energy/entropy consumption would still impose boundary conditions. But given a tree of possible abstractions, an intelligence might find an extremely unlikely tip of a branch, which heuristics wouldn't be much use for constraining.