This handbook takes you on a journey from fundamental logical principles to their practical applications in software development, scientific reasoning, and critical thinking.

Whether you're a high school student learning to think more clearly, a professional debugging complex systems, or simply someone curious about how sound reasoning works, this handbook provides tools for sharper, more reliable thinking.

What We’ll Cover:

Part I: Foundational Theory

We start with the bedrock of formal logic – understanding implications, truth tables, and the core rules of reasoning.

You'll learn the scaffolding for everything that follows:

• How "if-then" statements actually work (spoiler: it's not always intuitive!)

• The power of truth tables to map all possible scenarios

• Why some arguments are valid while others are logical fallacies

• The elegant relationship between Modus Ponens, Modus Tollens, and Contrapositives

Part II: Practical Applications

Here's where logic comes alive in tangible ways:

In Software Development:

• How debugging mirrors logical reasoning, and why your tests might be lying to you

• The logic behind Test-Driven Development and Mutation Testing

In Scientific Thinking:

• Karl Popper's falsification principle and why it matters beyond academia

• How Hypothesis Testing is just statistics meets Modus Tollens

In Everyday Reasoning:

• Spotting logical fallacies in arguments, media, and your thinking

• The art of considering multiple causal paths instead of jumping to conclusions

Part III: Philosophical Depths

The final section confronts the beautiful complexity of applying pure logic to an impure world:

• Why perfect "if-and-only-if" relationships are the goal but rarely achievable

• How modern software systems hide their complexity

• The butterfly effect of bugs and why root cause analysis is often harder than it seems

• Formal verification tools: from Prolog to Coq to TLA+

What You'll Gain

For Students:

• Critical thinking superpowers: Learn to spot flawed reasoning in arguments, social media, and news

• Academic advantage: These concepts appear in debates, philosophy, computer science, mathematics, and statistics

For Software Engineers:

• Debugging mastery: Modus Tollens for debugging: "If the output is wrong, what could cause it?"

• Testing philosophy: Move beyond "make the tests pass" to "prove the code is correct"

• Problem analysis: Avoid jumping to solutions before understanding the real problem

• System design: Think more rigorously about failure modes and edge cases, evaluate cause-and-effect relationships in complex systems

• Communication and career growth: Present arguments more clearly and persuasively, gain logical thinking skills that separate senior engineers from juniors

For Scientists:

• Experimental design: Strengthen your understanding of hypothesis testing and falsifiability

• Peer review: Better evaluate the logical soundness of research claims

• Grant writing: Structure arguments more persuasively using solid logical foundations

Pre-requisites

I’ll introduce code samples starting in the second half of the article, so knowing a programming language would be helpful. The concepts in this article are programming language-agnostic, but I’ve used Python throughout for readability.

No prior formal logic or philosophy background is strictly necessary, but the following will let you reap the most benefits from this article:

• Experience in testing and debugging during software development.

• Know what REPL (Read-Evaluate-Print-Loop) is if you want to try the Proof Assistants.

• Knowledge of logical operators (NOT, AND, OR), and the fact that they take 1 or 2 boolean values as input and return a single boolean value as output.

• Basic Algebraic Thinking: representing statements as variables (P, Q), the concept of NOT (¬) as an inversion of statements, and the concept that different input combinations can reach the same output.

• Exposure to deductive reasoning, where inferences are made based on some facts, and fallacies, which are some ways arguments can be flawed.

• Willingness to engage in conceptual back-and-forth between concrete English examples and abstract logical symbols.

• Holding possibly conflicting ideas between the ideal logic world and the impure real world.

• Openness to challenging intuition and following logical rules before applying your real-world experience.

Table of Contents

1. An Introduction to Logic

2. Truth Tables: Mapping All Possibilities

3. Contrapositives, Modus Ponens, Modus Tollens

4. The Origin of P⟹Q: Science and Reality

5. Revisiting Argument Forms: Valid Inferences and Common Fallacies

6. Denying the Antecedent: A Database Example

7. Assigning Real-World Meanings to Logic

8. Applying Logic to Software Testing

9. A Closer Look at Testing

10. Revisiting the Four Statements for Coding

11. The Missing Ingredient - If and Only If

12. Mutation Testing: Testing the Tests

13. Toward If-and-Only-If Confidence

14. Real-World Challenges

15. Glimmers of Hope: Tools and Practices for Clarity

16. The Power of Falsification in Testing

17. Proof Assistants

18. Food for Thought

19. Q.E.D.: The Enduring Power of Logic in an Uncertain World

20. Resources

21. Glossary

An Introduction to Logic

Imagine that the following statement is True:

If you are a coding instructor, then you have a job.

Now, do these make sense?

1. You have no job, so you are not a coding instructor

2. You have a job, so you are a coding instructor

3. You are not a coding instructor, so you have no job

Interpretations

Based on logic:

• Statement 1 is correct.

• Statement 2 is wrong because you may have other jobs without being a coding instructor.

• Statement 3 is wrong because you may or may not have a job, and as before, you may have other jobs without being a coding instructor.

Growing complexity

These statements grow increasingly complex due to:

• Changing from 2 valid statements to 2 invalid conclusions

• Moving from a clear job status (1, 2) to uncertainty about job existence or type (3).

Let’s get familiar with some notation before seeing how Truth tables help manage this complexity.

Notations

Truth Tables: Mapping All Possibilities

What is a Truth Table?

A truth table is a powerful tool in logic that helps us determine the overall truth or falsity of a compound logical statement. It does this by systematically listing all possible combinations of truth values (True or False) for its individual component propositions.

For every way the "inputs" (our propositions like P and Q) can be true or false, the truth table shows you the precise "output" (the truth value of the entire logical statement, such as P⟹Q).

Why are Truth Tables Helpful?

Truth tables offer critical benefits for clear thinking:

• Clarity and precision: They eliminate ambiguity by explicitly showing the outcome for every single scenario.

• Systematic analysis: They ensure no possible combination is missed, which is vital for sound reasoning.

• Foundation for understanding: They define how logical rules work, forming the bedrock for analyzing more complex arguments in any domain.

How to Read Our First Truth Table:

Let's examine the truth table for the implication P⟹Q ("If P then Q").

Each row represents a unique scenario, combining the truth values of P and Q to show the resulting truth value of P⟹Q.

Let's break down each row:

• P and Q Columns: These show the input truth values (True or False) for our two propositions. Since each can be one of two values, we have 2×2 = 4 unique combinations, filling all four rows.

• P ⟹ Q Column: This is the output truth value of the "If P then Q" statement for each combination of inputs P and Q.

  • Row 1: P is True, Q is True.

    • If P is true (you are a coding instructor) and Q is also true (you have a job), then the implication P⟹Q is True. (The "If...then..." statement holds).

    • This row is key for Modus Ponens.

  • Row 2: P is True, Q is False

    • If P is true (you are a coding instructor) but Q is false (you have a job), then the implication P⟹Q is False. This is the only scenario that disproves an "if-then" statement.

    • This row is key for Falsifiability.

  • Row 3: P is False, Q is True.

    • If P is False (you are not a coding instructor) but Q is True (you have a job), then the implication P⟹Q is still considered True. This can seem counter-intuitive.

    • The reason is that the implication statement only makes a claim about what happens when P is true. If P is false, the implication's claim isn't tested, so it is considered vacuously true.

  • Row 4: P is False, Q is False.

    • If P is False (you are not a coding instructor) and Q is False (you have no job), then the implication P⟹Q is also considered True.

    • Similar to Row 3, since the initial condition (P) was false, the implication's truth value remains True, as it hasn't been disproven.

    • This row is key for Modus Tollens.

The "Used In" column serves as a preview of the specific logical arguments or concepts that rely on each row's behavior, which we will explore in detail later.

Understanding the Implication (P⟹Q) Deeper

Most programmers are familiar with truth tables from logical operators like AND (∧), OR (∨), and NOT (¬), where they define the output based on combinations of inputs.

The implication (P⟹Q) works similarly, its output is defined by the rules of propositional logic, not by any real-world causal relationship or your “common sense”. For any given pair of inputs for P and Q, the result of P⟹Q is fixed.

If this feels counter-intuitive, consider that mathematical logic, like any formal system, is built upon agreed-upon axioms. These basic accepted truths allow us to construct complex systems of ideas. If later found ineffective or contradictory, these axioms can be redefined, or a new system can be developed.

In formal logic, this implication is also defined as being logically equivalent to "NOT P OR Q" (¬P∨Q).

This is the fundamental logical rule that dictates why, if P is False, P⟹Q is always True, regardless of Q's truth value. You can also understand this using the NOT P OR Q form.

• If P is False, that means NOT P is True.

• Using the rules of Logical operation:

  • True (Not P) OR True (Q) is True (NOT P OR Q)

  • True (Not P) OR False (Q) is True (NOT P OR Q)

  • NOT P OR Q is True regardless of what Q is.

The above explains rows 3 and 4 of the truth table from the NOT P OR Q form. As an exercise, you can apply the inputs (P, Q) from the first two rows of the truth table to NOT P OR Q to arrive at the same results defined in the P⟹Q column.

This formal definition allows us to use implication to reason in powerful ways, not just in the "forward" direction (P⟹Q, leading to Modus Ponens), but also in a crucial "backward" direction.

This backward form (Contrapositive) involves swapping and negating the propositions (¬Q⟹¬P).

For example, if "If you are a coding instructor, then you have a job" is true, then it must also be true that "If you have no job (¬Q), then you are not a coding instructor (¬P). ".

This "backward" way of reasoning, which underpins Modus Tollens, is a powerful tool for inferring conclusions from observed outcomes.

We'll explore the Contrapositive and two argument forms (Modus Ponens, Modus Tollens) in detail next.

Contrapositives, Modus Ponens, Modus Tollens

We've explored the fundamental implication (P⟹Q) and how truth tables reveal its behavior.

Now, we explore reasoning tools that build upon this foundation: Modus Ponens, Modus Tollens, and the concept of Contrapositives. These are bedrock principles of valid argument and efficient logical thought.

What is Logical Equivalence?

Before we dive into these specific concepts, let's clarify what logical equivalence means. Two statements are logically equivalent if they always have the same truth value under all possible circumstances. In simpler terms, if one statement is true, the other is always true. If one is false, the other is always false. They are, in essence, different ways of saying the same logical thing.

Understanding logical equivalence is incredibly useful. It:

• Simplifies logic: It allows us to substitute one statement for another without changing the truth of an argument, which simplifies complex proofs and reasoning.

• Reduces complexity: In fields like circuit design, it can lead to fewer physical gates.

• Maintains software correctness: In programming, it helps maintain code's correctness during refactoring and debugging, especially when simplifying conditional statements, by ensuring the transformed code still behaves identically to the original under all conditions.

The Contrapositive: An Equivalent Implication

One of the most important logical equivalences involves the Contrapositive of an implication. The contrapositive of an "If P then Q" (P⟹Q) statement is "If not Q, then not P" (¬Q⟹¬P).

You might intuitively question how "If P then Q" could be logically the same as "If not Q then not P." Let's demonstrate this using a truth table.

We'll start with our familiar P and Q columns and the P⟹Q implication. Then, we'll add columns for ¬P (Not P) and ¬Q (Not Q), and finally, the implication for the contrapositive, ¬Q⟹¬P.

Let's look at how the truth table explicitly shows this equivalence:

Explanation of the table

1. P, Q, P ⟹ Q (Columns 1-3): These are our standard propositions and the implication we've already defined.

2. ¬P (Column 4): This column simply shows the negation (opposite truth value) of the P column. If P is True, ¬P is False, and vice-versa.

3. ¬Q (Column 5): Similarly, this column shows the negation of the Q column.

4. ¬Q ⟹ ¬P (Column 6): This is the contrapositive. We apply the same rules for implication that we learned earlier, but now using ¬Q as our "if" part and ¬P as our "then" part. For example, in Row 2, ¬Q is True and ¬P is False. According to the implication rule (True ⟹ False yields False), the result for ¬Q⟹¬P is False.

5. The Proof of Equivalence: Now, compare Column 3 (P⟹Q) with Column 6 (¬Q⟹¬P). You'll notice that for every single row, their truth values are identical! When P⟹Q is True, ¬Q⟹¬P is also True. When P⟹Q is False, ¬Q⟹¬P is also False. This perfectly illustrates why they are logically equivalent.

So, "If you are a coding instructor, then you have a job" (P⟹Q) is logically the same as saying "If you have no job, then you are not a coding instructor" (¬Q⟹¬P). They convey the same information about the relationship between being a coding instructor and having a job.

How Modus Ponens and Modus Tollens Relate to Implication

Having defined logical equivalence and the contrapositive, we can now precisely understand two of the most fundamental and valid forms of deductive argument: Modus Ponens and Modus Tollens. Both of these argument forms rely on a core premise that an implication (P⟹Q) is true, and then use additional information to draw a valid conclusion.

1. Modus Ponens (Affirming the Antecedent): This is often considered the most intuitive and direct form of logical inference. It works in the "forward" direction of the implication.

   • Premise 1: We are given that the implication is true: If P, then Q (P⟹Q).

   • Premise 2: We are also given that the "if" part, the antecedent, is true: P is true.

   • Conclusion: Therefore, we can validly infer that the "then" part, the consequent, must also be true: Q is true.

Example:

• Premise 1: If it is raining (P), then the ground is wet (Q).

• Premise 2: It is raining (P).

• Conclusion: Therefore, the ground is wet (Q).

This directly corresponds to Row 1 (True, True) of our truth table for P⟹Q.

2. Modus Tollens (Denying the Consequent): This argument form works in the "backward" direction and relies directly on the logical equivalence of an implication and its contrapositive.

   • Premise 1: We are given that the implication is true: If P, then Q (P⟹Q).

   • Premise 2: We are also given that the "then" part, the consequent, is false: Not Q (¬Q).

   • Conclusion: Therefore, we can validly infer that the "if" part, the antecedent, must also be false: Not P (¬P).

Example:

• Premise 1: If it is raining (P), then the ground is wet (Q).

• Premise 2: The ground is not wet (¬Q).

• Conclusion: Therefore, it is not raining (¬P).

Modus Tollens is valid because if P⟹Q is true, its contrapositive (¬Q⟹¬P) must also be true. Applying Modus Ponens to this contrapositive (with ¬Q as our second premise) directly leads to the conclusion ¬P. This corresponds to Row 4 (False, False) of our original truth table for P⟹Q, where P and Q are both false but the implication is still true.

These two argument forms are central to rigorous deductive reasoning, allowing us to draw certain conclusions based on the truth of implications and related facts.

The Origin of P⟹Q: Science and Reality

In science, hypotheses often take the form "If P, then Q" where P is a cause and Q is its predicted effect –for example, "If a drug is given (P), then symptoms improve (Q)."

Ideally, P is controllable, as in experimental studies, but even in observational studies, P must be clearly defined and measurable.

Each experiment yields one observation, reflecting one of four possible truth-value combinations of P and Q.

The Falsifying Case in Science and Logic

Each experiment produces a single observation – one of the four possible combinations of P and Q.

• If P=True, Q=False is observed (row 2 of the truth table), the hypothesis is falsified

• In all other cases, the hypothesis is not falsified (yet)

Thus:

• If all observations fall in the 3 truth-preserving rows, the hypothesis remains viable.

• If at least one experiment yields P=True, Q=False, we either:

  • Conclude falsification, or

  • Re-examine the experiment and attempt replication before accepting falsification.

The Power of the Falsifying Case

In the Logical World

The falsifying case is not useful for inference with Modus Ponens or Modus Tollens because these two argument forms require starting with P⟹Q = True. I’ll explain both arguments in detail later.

But the falsifying case is useful for showing counterexamples to disprove the implication, or proof by contradiction.

In the Real Scientific world

The falsifying case embodies Falsifiability – a crucial concept in Science.

In so far as a scientific statement speaks about reality, it must be falsifiable: and in so far as it is not falsifiable, it does not speak about reality.

— Karl R. Popper, The Logic of Scientifc Discovery

Scientific theories come about through hypotheses that are continually tested and survive attempts at falsification.

Popperian Falsification and Hypothesis Testing

These two approaches, one philosophical and one statistical, are distinct but complementary in the scientific method.

• Popperian Falsification starts with a scientific hypothesis (for example, "P has an effect on Q"). Its core aim is to actively seek evidence that would disprove this hypothesis. If such disproving evidence is found, the hypothesis is falsified.

• Statistical Hypothesis Testing begins with a null hypothesis (H0​) (for example, "P has no effect on Q"). Its goal is to determine if the collected data provides sufficiently extreme evidence to reject this null hypothesis.

If the null hypothesis is rejected, it provides statistical support for the alternative hypothesis (that P does have an effect on Q). This statistically supported hypothesis then becomes a stronger candidate, continually subjected to further Popperian attempts at falsification through new experiments and observations.

The Nuance: Implication is Not Causality

P⟹Q does not inherently imply that P causes Q.

Consider these examples:

• "If the fire alarm is sounding, then there is smoke." The alarm doesn't cause the smoke.

• "If a colleague screams during code review, then the code is bad." Does the screaming cause the bad code, or merely reveal it? (Perhaps sometimes both! 😰)

Causality is a real-world concept crucial for making informed decisions, predicting outcomes, and inferring the underlying reasons for events.

It's often central to predictive modeling and supervised learning in data science, where the target variable is the effect and the predictors are proposed causes. A common pitfall here is data leakage, where predictors are inadvertently influenced by (or are themselves effects of) the target, violating the causal assumption.

Logic, however, doesn't model time, mechanisms, or interventions. It only cares about truth values and formal structure. Logic defines what is true based on premises, not what makes something true in a causal sense.

Revisiting Argument Forms: Valid Inferences and Common Fallacies

We've now established the rules of implication, understood logical equivalence, and learned about two powerful, valid argument forms: Modus Ponens and Modus Tollens. But when we try to reason using "if-then" statements, it's easy to fall into common logical traps.

In this section, we'll systematically revisit the four common ways we might try to draw conclusions from an implication P⟹Q (If you are a coding instructor, then you have a job) introduced at the start of the handbook.

Two are valid arguments (Modus Ponens and Modus Tollens), and two are common logical fallacies. Understanding the differences is crucial for sound reasoning.

First, let's quickly define the parts of an "if-then" condition:

• Antecedent: The "if" part of the condition (P).

• Consequent: The "then" part of the condition (Q).

Now, let's examine these four argument forms, using our knowledge of truth tables and the coding instructor example.

Affirming the Antecedent (Modus Ponens)

This is the first valid argument form we discussed. It's called "affirming the antecedent" because it asserts the truth of the "if" part (the antecedent, P) to conclude the "then" part (the consequent, Q).

• Argument Form:

  1. If P, then Q (P⟹Q)

  2. P is true.

  3. Therefore, Q is true.

• Examples:

  • You are a coding instructor (P), so you have a job (Q).

  • You provided invalid input data (P), so the code will show an error (Q).

• Interpretation: This argument directly aligns with Row 1 (P=True, Q=True) of our truth table, where the implication holds true. It's often the most intuitive form of logical deduction. In programming, it's natural to expect bad input to lead to error messages if the code is designed correctly.

Denying the Consequent (Modus Tollens)

This is the second valid argument form. It's called "denying the consequent" because it asserts the falsity of the "then" part (the consequent, ¬Q) to conclude the falsity of the "if" part (the antecedent, ¬P). As we learned, Modus Tollens derives its validity from the logical equivalence of P⟹Q and its contrapositive (¬Q⟹¬P).

• Argument Form:

  1. If P, then Q (P⟹Q)

  2. Not Q is true (¬Q).

  3. Therefore, Not P is true (¬P).

• Examples:

  • You have no job (¬Q), so you are not a coding instructor (¬P).

  • There are no error messages (¬Q), so the input data is valid (¬P)

• Interpretation: This argument corresponds to Row 4 (P=False, Q=False) of our truth table, where P⟹Q is true, and both P and Q are false. This form of reasoning is critical for skillful debugging, allowing you to infer reasonably true conclusions about the cause (P) from observations of the outcome (Q), assuming your program logic (P⟹Q) holds true.

Affirming the Consequent (Fallacy)

Now we move to the common pitfalls. This is an invalid argument form where we attempt to conclude that the antecedent (P) is true simply because the consequent (Q) is true. It's a fallacy because the truth of Q does not guarantee the truth of P, as Q could have been caused by something other than P.

• Argument Form (Invalid):

  1. If P, then Q (P⟹Q)

  2. Q is true.

  3. Therefore, P is true. (**Incorrect inference!**🚨)

• Examples:

  • You have a job (Q), so you are a coding instructor (P).

    • Incorrect: You could have many other jobs.

  • The code showed an error (Q), so you provided invalid data (P).

    • Incorrect: Other things besides invalid data can cause errors.

• Interpretation: This fallacy highlights the difference between a one-to-one and a one-to-many relationship. Looking at our truth table, when P⟹Q is True and Q is True, P could be True (Row 1) or False (Row 3). The argument mistakenly concludes that P must always be True. The uncertainty arises because observing Q as True doesn't uniquely point to P as the cause – there could be many other reasons or paths that lead to Q.

  • Think of walking down a forest path, unaware that another trail has merged into yours from behind you. When retracing your steps in reverse, you encounter a split (Q) at that merge and feel disoriented, unsure which path leads back to your start point (P). Just as multiple paths can converge on the same point, multiple causes can produce the same outcome.

Denying the Antecedent (Fallacy)

This is another invalid argument form. Here, we attempt to conclude that the consequent (Q) is false simply because the antecedent (P) is false. It's a fallacy because P being false does not guarantee that Q will also be false. Q could still be true for other reasons, or the implication might not cover all scenarios where Q occurs.

• Argument Form (Invalid):

  1. If P, then Q (P⟹Q)

  2. Not P is true (¬P).

  3. Therefore, Not Q is true (¬Q). (**Incorrect inference!**🚨)

• Examples:

  • You are not a coding instructor (¬P), so you have no job (¬Q).

    • Incorrect: You could have a different job.

  • You provided valid data (¬P), so you have no error (¬Q).

    • Incorrect: Valid data doesn't guarantee no error. Other factors like network issues, memory leaks, or non-idempotent operations can still cause errors.

• Interpretation: Similar to Affirming the Consequent, this fallacy stems from incorrectly assuming a unique relationship. From our truth table, when P⟹Q is True and P is False, Q could be True (Row 3) or False (Row 4). The argument mistakenly concludes Q must always be False.

Both of these fallacies (Affirming the Consequent and Denying the Antecedent) creep into our thinking when we prematurely assume a single cause for an effect. In complex real-world systems, many factors can lead to an outcome, and narrowing your thinking too soon can lead to missed bugs or incorrect conclusions.

Fallacies and Implication: A Prerequisite

Both the fallacy of affirming the consequent and denying the antecedent assume the underlying implication (P⟹Q) is true.

If this implication is false from the start, there's no logical argument to be made, and thus, no fallacy to speak of.

Exercise: Identifying an Argument Form

Which of the 4 forms of argument is this?

• Penguins can’t fly. I can’t fly. Therefore, I’m a penguin.

Hint: Rephrase the first statement into an if-then form.

Denying the Antecedent: A Database Example

We just saw that Denying the Antecedent is a logical fallacy, meaning that even if the initial implication (P⟹Q) is true, concluding ¬Q from ¬P is not a valid inference. To make this abstract concept concrete, and to illustrate why this fallacy can be particularly dangerous in real-world systems like software, let's explore a practical example involving a database.

The implication: If the database is down (P), we’ll see a connection timeout error (Q).

Now, applying the fallacy of Denying the Antecedent, we might incorrectly conclude: If the database is not down (¬P), we will not see a connection timeout error (¬Q). ❌

But even if the database itself is perfectly operational and "not down," you might still encounter a connection timeout error. This could happen due to a variety of other, independent reasons, such as:

• Network problems

• Firewall rules

• The database is up but extremely slow

• The query engine is stuck

This specific example of multiple potential causes for a "timeout" highlights a broader, critical skill in software development: thorough case analysis.

This is precisely why technical assessments, especially in areas like algorithms and system design, frequently demand that you consider exhaustive possibilities. For instance, you are often asked to handle base and recursive cases in dynamic programming, or to ensure mutually exclusive and collectively exhaustive coverage when grouping multiple scenarios in problems like interval merging.

Such strong case analysis is vital for minimizing bugs and cultivating an open-minded approach to considering multiple causal paths, driven by experience, curiosity, and a dedication to craftsmanship.

But even perfect case analysis doesn't guarantee a correct implementation. Weak language mastery or mistaken assumptions can still lead to errors, making tests a crucial last line of defense.

Before jumping into applying logic to software testing, let’s practice our agility in conceptually switching between real-world concepts in English and symbols in logic.

Assigning Real-World Meanings to Logic

We must define what P, Q, and P⟹Q refer to when applying logical theory to real-world concepts.

How we define these variables affects our truth tables.

For example:

• If P means "valid input," then ¬P means "invalid input."

• If P means "invalid input," then ¬P means "valid input."

Imagine we define P = "Good input" and Q = "No Error."

• When testing the happy path, we are verifying that the implication P⟹Q (If input is good, then no error) holds true.

• When testing the unhappy path (mutation testing, more details later), we are verifying that ¬P⟹¬Q (If input is not good, then an error occurs) holds true.

In any test, a failure indicates that the tested implication is false. This warrants investigation into whether the issue lies with the specification's interpretation, the implementation, or even the test itself.

Applying Logic to Software Testing

Software development relies on constructing systems that behave predictably. Software testing is our primary tool for validating these behaviors. At its core, testing is a process deeply rooted in logical implications, where we propose a hypothesis about our code and then run an experiment (the test) to check its truth.

A test case is carefully designed to evaluate a specific piece of code. This involves:

1. Setting up Preconditions and Inputs: Before executing the code under test, we meticulously establish a specific environment and provide particular inputs. This includes:

   • Function/Method Arguments: The precise values passed into the code being tested.

   • System State: Setting up relevant data in a database, preparing the content of a file system, configuring an object's instance variables, or dictating the responses of external services (often through "mocks" or "stubs").

   • Environmental Factors: Controlling elements like the current time, specific network conditions, or user permissions relevant to the code's execution. This precise setup ensures that the code runs under defined conditions, allowing us to evaluate its behavior consistently.

Once the setup is complete, the code under test is executed, and its output or behavior is observed. This observation is then compared against an expected result.

To precisely analyze test outcomes, let's establish our specific logical mapping:

• P: The code under test is correct for the specific scenario defined by the test. This refers to the actual, objective state of the code's internal logic and implementation when presented with the test's preconditions and inputs. If P is True, the code is without defect for this case. If P is False, there is a bug or deviation.

• Q: The test passes. This means the actual output or behavior observed from the code precisely matches the expected outcome defined in our test case. If they do not match, the test fails.

• P⟹Q: If the code under test is correct for this specific scenario, then the test will pass. In pure propositional logic, the truth value of P⟹Q is indeed defined by the truth values of P and Q. But in the context of software testing, P⟹Q represents our hypothesis or desired specification for how the code should behave. We don't directly "know" P's truth value beforehand. Instead, the test's execution provides empirical data (the actual Q) that allows us to evaluate whether this hypothesis holds true in practice, and thereby infer the actual state of P.

Understanding this mapping is vital for interpreting test results. Let's examine the different outcomes of a test run, referencing the truth table for P⟹Q:

• Row 1: P is True (Code is correct), Q is True (Test passes)

  • Interpretation in Testing: Ideal State/Validation

    • This is the desired outcome and strengthens our confidence that the code adheres to its specification.

    • This scenario directly confirms the truth of our hypothesis (P⟹Q).

• Row 2: P is True (Code is correct), Q is False (Test fails)

  • Interpretation in Testing: Logical Contradiction / Falsification of Hypothesis

    • This row means our overall hypothesis P⟹Q is false for this specific instance.

    • This demands investigation: either our initial assumption that P was True (meaning the code was correct) is wrong (i.e., there's an actual bug, so P is actually False), or the test itself is flawed (its inputs/expectations are incorrect), or the specification is wrong.

    • This is where rethinking of the P⟹Q hypothesis itself happens.

• Row 3: P is False (Code is incorrect), Q is True (Test passes)

  • Interpretation in Testing: False Positive / Inadequate Test

    • This is a problematic scenario. It implies the test is not robust enough to detect the defect in the code, or the test's expectation is flawed.

    • While P⟹Q remains true vacuously, this outcome is misleading and means the test is not effectively verifying code correctness.

• Row 4: P is False (Code is incorrect), Q is False (Test fails)

  • Interpretation in Testing: Bug Found / Confirmation of Incorrectness

    • This is a beneficial outcome, as the test has successfully identified a defect.

    • When P is truly False, P⟹Q is vacuously true.

    • This row can represent either a known, intended 'P is False' state (e.g., TDD Red phase) or the actual state discovered via deduction (explained below in Scenario 1).

Note on this Contextualized Truth Table and Probabilistic Nature

This truth table differs from a purely abstract logical truth table by being explicitly contextualized for software testing.

• Specific Definitions: Unlike a generic P and Q, here they have precise meanings within the domain of code correctness and test outcomes.

• "Interpretation in Testing" Column: This is the key distinguishing feature. It translates the raw logical outcomes of (P, Q, and P⟹Q) into actionable insights and common debugging/development scenarios for software engineers. It explains what it means when a particular row is observed in the context of testing.

• Probabilistic Confidence: While formal logic operates in binary (True/False), real-world software testing often involves probabilistic confidence. A test doesn't provide absolute logical proof of correctness (for example, a passing test doesn't guarantee P is 100% True due to the possibility of undiscovered bugs or false positives). Instead, test results increase our confidence that the code is correct, or provide strong evidence that it is incorrect. Testing is fundamentally about reducing uncertainty and increasing the probability that our code functions as intended.

Let's now explore how these logical outcomes are interpreted in two common testing scenarios:

Scenario 1: Debugging an Unexpected Defect (Applying Modus Tollens)

This scenario occurs when a test that was previously passing, or a newly written test that we strongly trust as a precise and correct specification, unexpectedly fails. In this context, we assume the validity of the implication P⟹Q for this specific test case, treating it as an unbreakable rule for how correct code should behave.

1. Our Core Premise (Trusted Specification): We operate under the assumption that the implication "P⟹Q" ("If the code is correct for this scenario, then the test passes") is True for this specific test. Our confidence stems from the test's meticulous design, its history of passing, or its role in a well-established regression suite.

2. Test Execution and Observation: We run the test, which has its preconditions and inputs set.

   • If the Test Fails (Q is False): This is the key observation. Since we trust our premise that P⟹Q is True, and we observe ¬Q (the test fails), we are logically compelled to deduce that our initial belief about P (the code being correct for this scenario) must be false.

     • Application of Modus Tollens:

       • Premise 1: If the code is correct for this scenario (P), then the test passes (Q). (P⟹Q, assumed true as a trusted specification).

       • Premise 2: The test did not pass (¬Q).

       • Conclusion: Therefore, the code is not correct for this scenario (¬P).

     • Outcome: This inference directly points us to a defect in the code. The test's failure, given its trusted nature, reveals that the actual state of the code for this scenario is P is False. This effectively places the scenario in Row 4 (P False, Q False) of our truth table, confirming the presence of a bug that needs fixing. This is typical in regression testing, where a previously correct feature suddenly breaks.

Scenario 2: Validating/Refining the Specification (Falsifying P⟹Q or Confirming Known Incorrectness)

This scenario arises when a test fails, and our primary focus is not immediately on debugging the code as if it's a regression. Instead, it's on understanding why the P⟹Q relationship (our hypothesis for this specific behavior) isn't holding, or simply confirming an expected failure. This can involve questioning the test itself, the underlying requirements, or confirming a deliberately incorrect state of the code.

1. Our Hypothesis (Being Challenged or Confirmed): We are either actively evaluating the validity of the implication "P⟹Q" for a specific behavior, or we are running a test against code we know is incomplete or incorrect.

2. Test Execution and Observation: We run the test with its defined preconditions and inputs.

3. If the Test Fails (Q is False): The interpretation here depends on our prior knowledge or intent about the code's state (P):

   • Sub-scenario 2A: Falsifying P⟹Q and Rethinking Specification (Corresponds to Row 2: P True, Q False):

     • We observe Q is False (the test fails).

     • If we then examine the code and the requirements, and we conclude that the code should have been correct for this scenario (meaning, our expectation/belief was P is True), then the test result means the specific instance of our hypothesis "P⟹Q" is FALSE.

     • This direct falsification reveals a contradiction. We must then investigate:

       • Is our initial belief that P was True mistaken (that is, is there a genuine bug in the code that makes P actually False, moving this to a Row 4 scenario)?

       • Or, is the test itself incorrect (its inputs or expected output are wrong), meaning our P⟹Q premise needs to be re-evaluated and corrected?

       • Or, have the underlying requirements changed or been misunderstood?

     • Outcome: This critical outcome prompts us to "rethink" – either the code needs fixing, or the test needs adjusting, or the specification needs clarification. This is common in exploratory testing or when working with new/evolving features where the exact behavior is still being defined.

   • Sub-scenario 2B: Confirming Known Incorrectness (Corresponds to Row 4: P False, Q False):

     • We observe Q is False (the test fails).

     • We already know or intentionally designed the code to be incorrect for this scenario (that is, we are actively developing a feature and haven't written the full code yet, or we're running a test against a known, un-fixed bug, so our expectation is P is False).

     • The test result simply confirms our prior knowledge that P is False. The test correctly highlights the missing or incorrect behavior. In this case, the P⟹Q implication is vacuously true, and the test effectively served its purpose of showing the existing defect.

     • Outcome: This is typical in Test-Driven Development (TDD) in the Red phase, where a failing test for a not-yet-implemented feature confirms the "P is False" state, guiding development to make P True. It also applies when verifying that a bug fix indeed works: the test initially fails (confirming the bug), and then passes after the fix (confirming P is now True).

A Closer Look at Testing

The Illusion of Correctness: Affirming the Consequent

Consider a common scenario where a test passes, seemingly validating our code:

def get_user_role(user_id):
    if user_id == 42:
        return "admin"
    return "guest"

# test
assert get_user_role(42) == "admin"

Here, our implicit claim (the specification) is: If the code is correct (P), then the output will match the expectation (Q).

In this example, the test passes – the output is "admin" (Q), but can we definitively conclude that the function is correct (P)? Not necessarily.

This scenario often exemplifies the logical fallacy of affirming the consequent. We see the desired outcome (Q) and mistakenly assume that our specific intended cause (P, the correctness of our specific implementation path) was the reason.

The Problem: What if the real condition for an "admin" role should be checking a database, but we have temporarily hardcoded the value for testing? The test would pass, but the correctness is illusory. If we see P as false because the code did not implement the behaviour from the full specification, this corresponds to Row 3 (P False, Q True: False Positive) in our truth table.

As I mentioned before, deliberately implementing ¬P works well if ¬Q is observed, but is not useful, or even erroneous, if Q is observed.

Even without hardcoding, the output might match by coincidence, or because of factors outside the direct logic we intended to test. This can happen due to:

• Default behavior: A broader system default might produce the expected output.

• Caching: A previous successful operation might have cached the result, bypassing the actual logic.

• Fallback logic: An unintended fallback mechanism produces the correct output despite an error in the primary path.

• Test harness bugs: Flaws in the testing setup itself might obscure real issues.

The Role and Risks of Test Doubles

The challenges highlighted above are particularly relevant when using test doubles, such as Stubs and Mocks. These are artificial components that replace real dependencies (for example, databases, external APIs, time-sensitive operations) during testing.

• Stubs focus on state: they provide pre-programmed fake data or return values to get the rest of the code under test working predictably, like the get_user_role example

• Mocks focus on behavior: they allow you to verify interactions, such as the number of calls made to a certain API, or how control flow flows through specific parts of the system.

Both remove external dependencies, allowing you to isolate and focus on the internal logic of the code without noise or side effects. But using them without understanding their limitations can lead to false confidence.

If a test double simulates a "correct" response, but the real dependency it replaces has a bug, or the way the main code interacts with that dependency is flawed, the test will pass (Q is True) – yet P (the code's overall correctness in a real environment) might be False, leading to a dangerous false positive.

Whether you encounter such logical fallacies in your testing depends on precisely what behavior or state you are attempting to verify, and whether you are over-interpreting the test results.

Test Scope and Interpretation

The choice of testing scope – from narrowly focused unit tests to broader integration tests, system tests, user acceptance tests (UAT), and even testing in production – represents a continuum. On this spectrum, various trade-offs are involved, especially concerning the effort-reward ratio. This effort is influenced by factors like individual developer skill, company engineering practices (for example, responsibility split between feature developer and dedicated tester roles), and industry regulations.

Generally:

• Smaller-scoped tests (for example, unit tests) have fewer assumptions baked in and a shorter chain of logical implications. This translates to less risk of committing fallacies in both test implementation and test result interpretation. They are excellent for quickly verifying isolated units of code.

• Larger-scoped tests (for example, end-to-end integration tests) incorporate more real-world complexities and dependencies. While providing higher confidence in the system's overall behavior, they inherently increase the potential for confounding factors that can lead to false positives or make debugging more challenging.

Being acutely aware of the assumptions implicit in each test, at every scope level, is paramount. Passing tests for the wrong reasons will inevitably cause problems down the road.

Debugging, Observability, and Mental Models

Failing tests are not failures of the testing process but are, in fact, incredibly valuable learning moments. They represent opportunities to:

• Run focused debugging experiments to pinpoint the exact cause of the failure.

• Refine your mental model of the code-to-outcome (P⟹Q) link. A failing test (where Q is False) tells you that your current understanding of P, or of the P⟹Q relationship, is flawed. Use this feedback to update your understanding of the code's actual behavior.

• Improve both the code and the tests themselves.

Enhance system observability to better detect and confirm outcomes (Q). The more clearly, from multiple angles, and through diverse methods we can observe Q (for example, logs, metrics, tracing, output inspection), the more confident we can be in its causes and, by extension, the actual state of P.

Crucially, avoid blindly fixing tests just to make them pass. Always ensure you thoroughly understand why a test failed and update your P⟹Q model accordingly. The ultimate goal is not just to fix current bugs, but to prevent them in the future by continually strengthening both the correctness of the code and the verifiability of its behavior.

Falsifiable Tests Reveal Regressions

Beyond avoiding false positives (where the code is incorrect but the test passes), a good test must also be falsifiable. This means the test must be genuinely capable of failing under certain (incorrect) conditions. An unfalsifiable test is a broken test – it cannot serve its purpose of revealing regressions or confirming the presence of bugs.

While we strive for the implication P⟹Q to hold true for all the scenarios we care about, it may not be true for all cases due to unforeseen or mistaken assumptions, or simply because the code is incorrect. The test's ability to demonstrate this incorrectness by failing under specific, well-defined conditions makes it profoundly valuable.

Some common culprits for unfalsifiable or "bad" tests include:

• Vague or Untestable Specifications: Statements like "The system should behave well under most conditions," "It shouldn't crash randomly," or "The algorithm is robust" lack clear, measurable criteria. It's impossible to design a test that definitively passes or fails against such statements, thus rendering them effectively unfalsifiable.

• Broken Implementations of the Test Suite: The test code itself might be flawed, perhaps due to logical errors or control flow issues that prevent assertions from ever being reached or correctly evaluated, inadvertently taking the same passing path regardless of the code under test.

• Insufficient Test Data or Edge Cases: If tests only cover "happy path" scenarios and fail to include challenging inputs or boundary conditions, they might pass for incorrect code that only breaks under specific, untested circumstances.

A robust specification clearly defines what constitutes success and failure. Correspondingly, a good test suite correctly implements that specification, making its tests both accurate and truly falsifiable.

Take a step back

Critical thinkers might observe that the application of the four fundamental logical argument forms to coding scenarios, as initially presented, could be misleading in the complexities of real-world software.

The next section shows some nuances that arise when we transition from the clear-cut rules of formal logic to the often messy reality of software development.

Specifically:

• The first two points below show why the seemingly valid arguments of Modus Ponens and Modus Tollens may not always lead to reliable conclusions when applied to coding scenarios.

• The last two points below show why the two common logical fallacies, Affirming the Consequent and Denying the Antecedent, may actually provide correct insights under specific real-world coding conditions.

Revisiting the Four Statements for Coding

Here are the four arguments and their associated coding examples:

1. Modus Ponens: If you provide invalid input data (P), the code will show an error (Q).

2. Modus Tollens: There are no error messages (¬Q), so the input data is valid (¬P).

3. Affirming the Consequent (Fallacy): The code showed an error (Q), so you provided invalid data (P).

4. Denying the Antecedent (Fallacy): You provided valid data (¬P), so you have no error (¬Q).

Now, let's dive into the nuances of each:

Modus Ponens

• Our coding example: If you provide invalid input data (P), then the code will show an error (Q).

• Why it may not always hold: This application of Modus Ponens assumes that either your code or any third-party code it relies upon will always properly detect and explicitly raise exceptions or show errors on bad data. In reality, systems might automatically fix or sanitize bad input, silence errors, or simply proceed with unexpected behavior without explicitly signaling an error, leading to a passing (or non-failing) state (¬Q) even when P (invalid input) was true.

Modus Tollens

• Our coding example: There are no error messages (¬Q), so the input data is valid (¬P).

• Why it may not always hold: This application of Modus Tollens assumes there are no automatic mechanisms within the system to fix or silence bad input before errors are typically displayed. If such "silent correction" or "error suppression" occurs, you might observe no error messages (¬Q), but the input data could still be invalid (P), rendering the conclusion (¬P) false despite the premise (¬Q) being true. This highlights the dangers of incomplete observability.

Affirming the Consequent (Fallacy)

• Our coding example: The code showed an error (Q), so you provided invalid data (P).

• Why it may actually be correct: While logically a fallacy, in specific, highly constrained real-world conditions, this inference can gain practical validity. If the error message is so uniquely and specifically defined that it can only be caused by invalid input data (P) and no other known factor, then this statement can become reliable. This is rare and typically requires meticulous error handling design where each error message maps unambiguously to a single root cause.

Denying the Antecedent (Fallacy)

• Our coding example: You provided valid data (¬P), so you have no error (¬Q).

• Why it may actually be correct: Although a fallacy in general logic, this inference can hold a high degree of practical confidence under certain programming paradigms (Functional Programming). If the code is sufficiently simple, purely functional (meaning outputs depend only on inputs and have no side effects), and has no external dependencies (like network or database interactions), then the absence of invalid data (¬P) can indeed make us reasonably confident that there will be no errors (¬Q). The lack of external variables and internal state makes the code's behavior highly predictable and directly tied to its inputs.

You may now be thinking: what’s the point of studying logic if it has so many loopholes and edge cases when applied to coding?

The Missing Ingredient – If and Only If

In our exploration of logical implications, we've focused primarily on the unidirectional relationship P⟹Q ("If P, then Q"). This statement tells us what happens if P is true, but it remains silent on whether Q only happens when P is true. It's like saying, "If it rains, the ground gets wet." This is true, but the ground can also get wet if a sprinkler is on, even if it's not raining.

But in many critical contexts, especially in rigorous scientific theories and robust software systems, we often seek a much stronger relationship: one where the truth of Q absolutely depends on the truth of P, and vice versa. This powerful bidirectional relationship is captured by the phrase "If and Only If" (P⟺Q).

What "If and Only If" Means: A Stronger Statement

When we assert "P⟺Q", we're making two distinct claims simultaneously:

1. If P, then Q (P⟹Q): P is a sufficient condition for Q. Whenever P is true, Q must also be true.

2. If Q, then P (Q⟹P): P is also a necessary condition for Q. Whenever Q is true, P must also be true. In other words, Q cannot be true without P being true.

Notice the significant increase in the strength of the statement. "If P, then Q" merely states a consequence. "P⟺Q" declares a definitive equivalence, where P and Q are inextricably linked. They rise and fall together – one cannot be true without the other being true, and one cannot be false without the other being false.

Bidirectional Truth Table: Unambiguous Relationships

Let's construct the truth table for P⟺Q to clearly see this strong relationship.

P⟺Q is logically equivalent to (P⟹Q)∧(Q⟹P).

Creating the Table (columns 4 and 5 are new):

• Q⟹P (Column 4): We apply the standard implication rules, but with Q as our "if" and P as our "then." For instance, in Row 3, Q is True and P is False, so Q⟹P is False.

• P⟺Q (Column 5): This is the logical AND of the P⟹Q and Q⟹P columns. For P⟺Q to be True, both component implications must be True, which explains why you see less Trues in the bidirectional implication compared to any of the unidirectional implications.

Implications for the Two Common Fallacies

The clarity provided by "If and Only If" is particularly powerful in preventing the very logical fallacies we discussed earlier: Affirming the Consequent and Denying the Antecedent. These fallacies arise from the incorrect assumption that an "if-then" statement implies an "if and only if" relationship.

Let's revisit them with the lens of P⟺Q If and Only If you provided invalid data (P), then the code will show an error (Q):

Affirming the Consequent: No More Ambiguity

• The Fallacy (assuming unidirectional P⟹Q):

  • If the code showed an error (Q), then you provided invalid data (P).

  • Previously, when P⟹Q was True and Q was True, P could be True (Row 1) or False (Row 3). This ambiguity led to the fallacy.

• With P⟺Q:

  • Now, look at the P⟺Q column in the table. When P⟺Q is True and Q is True (Row 1), P is unambiguously True. The confusion from Row 3 is gone because if Q were True while P was False, P⟺Q would be False (as Q⟹P would be False), thus making that row irrelevant for valid modus ponens inference under the P⟺Q premise.

  • In a system designed with P⟺Q in mind, knowing that Q is True (observing an error) would force the conclusion that P is True (invalid data is the cause), assuming the "if and only if" relationship holds true for that specific system design.

Denying the Antecedent: Unmistakable Consequences

• The Fallacy (assuming unidirectional P⟹Q):

  • You provided valid data (¬P), so you have no error (¬Q).

  • Previously, when P⟹Q was True and P was False, Q could be True (Row 3) or False (Row 4). This ambiguity led to the fallacy.

• With P⟺Q:

  • Now, when P⟺Q is True and P is False (Row 4), Q is unambiguously False. The problematic scenario from Row 3 (where P was False but Q was True) is irrelevant here because P⟺Q would be False in that case (specifically, Q⟹P would be False).

  • If your system genuinely adheres to "P⟺Q", then knowing that P is False (valid data provided) guarantees that Q is False (no error messages).

Practical Mitigation in Coding

The insights from "If and Only If" are more than just theoretical. Practically, both fallacies (Affirming the Consequent and Denying the Antecedent) can be mitigated by striving for conditions that approximate an "if and only if" relationship in your code and tests.

Focused Unit Tests

Design unit tests that are so granular and isolated that they effectively aim to establish an "if and only if" scenario for a tiny piece of logic. By thoroughly mocking or controlling all external dependencies and environmental factors, you reduce the impact of "other causes."

If your test for a specific input passes, you want to be as confident as possible that it passed only because the code handled that specific input correctly, and not due to some irrelevant side effect. Similarly, if it fails, you want to be sure that the failure points directly to the intended logical path.

Exception Handling and Specificity

Instead of catching broad Exception types, catch and handle specific exceptions. This helps differentiate between various "causes" (P1​,P2​,…) that might lead to a generic "error" (Q). The more precise your error handling, the closer you get to a scenario where "If X error, then Y specific cause," moving towards a bidirectional understanding of error conditions.

Test-Driven Development (TDD) and Mutation Testing

These methodologies inherently push towards P⟺Q thinking. TDD encourages writing a failing test first (¬Q), which then necessitates a specific code change (P) to make it pass.

Mutation testing, which we'll explore further, takes this a step further by ensuring that your tests are robust enough to fail when code is subtly altered (that is, proving that ¬P leads to ¬Q, and thus, that the original P was indeed necessary for Q).

By consciously aiming for "if and only if" relationships in your code's design and your testing strategies, you can build systems that are not only predictable but also much easier to debug and reason about, moving beyond mere correlation to a deeper understanding of cause and effect.

Callback to Mutation Testing

In the earlier section on Assigning Real-World Meanings to Logic, we discussed:

When testing the happy path, we are verifying that the implication P⟹Q (If input is good, then no error) holds true.

When testing the unhappy path (mutation testing), we are verifying that ¬P⟹¬Q (If input is not good, then an error occurs) holds true.

This dual view is key to understanding how mutation testing contributes to software correctness.

Mutation Testing: Testing the Tests

Mutation testing deliberately introduces small faults (mutations) in the code and checks whether the test suite detects them by failing. This process assesses not the code, but the tests themselves.

In a robust test suite, we strive for two ideal conditions:

• All correct implementations should pass the tests.

• All incorrect implementations should fail the tests.

If a mutated (wrong) version of the code is introduced and causes no test failures, that defeats the fundamental purpose of testing. It means your tests aren't sensitive enough to catch a deviation from correctness. Mutations reveal hidden assumptions or gaps in your test coverage, acting as a sensitivity probe for your test suite.

Example code mutations:

• Changing an arithmetic operator (+ to -, > to >=).

• Flipping a boolean condition (true to false).

• Deleting or duplicating a statement.

• Modifying a constant value.

Common Python mutation testing tools:

• mutmut uses Python’s built-in ast module.

• cosmic-ray uses parso, which provides a more complete AST.

These tools rely on abstract syntax trees to surgically mutate code.

You can even swap out underlying AST libraries for different precision or completeness: https://github.com/boxed/mutmut/issues/281

Logic Behind Mutation Testing

Let's formalize the logical mapping of mutation testing, recalling our definitions:

• Let P: Code is correct.

• Let Q: Tests pass.

Standard happy path testing primarily checks that P⟹Q – "if the code is correct, then tests pass."

Mutation testing focuses on the other side of the coin: we intentionally make ¬P true (by introducing a fault), and then we expect ¬Q (the tests should fail). This process rigorously checks whether the implication ¬P⟹¬Q ("if the code is not correct, then the tests fail") holds true for your test suite.

But there's a deeper, more powerful logical implication here:

As we learned earlier, the statement ¬P⟹¬Q is logically equivalent to its contrapositive, Q⟹P.

So, by successfully verifying that introducing a fault (¬P) leads to a test failure (¬Q), we are simultaneously validating the contrapositive: if tests pass (Q), then the code must be correct (P).

This is incredibly significant! It moves us much closer to establishing a bidirectional guarantee between our code and our tests: P⟺Q (code correctness is tightly coupled with test success). Mutation testing helps us confidently eliminate false positives in the test suite – situations where Q is true (the test passes) but P is false (the code is actually incorrect).

In a world where LLMs help us write and refactor code quickly, having this "if and only if" confidence in our test suite is invaluable for ensuring the generated or refactored code truly meets expectations.

Clarifying the Kinds of Failures

In software, we typically categorize errors into three main types:

• Syntax errors: Violations of the language's grammatical rules (for example, missing colon, invalid keyword). These prevent the code from running at all.

• Runtime errors: Errors that occur during program execution, often due to unexpected conditions (for example, TypeError, AttributeError, ZeroDivisionError).

• Logic errors: The program runs without crashing, but it produces an incorrect result or behaves in a way that doesn't match the intended specification (for example, wrong algorithm, wrong return value).

Mutation testing focuses on logic errors – failures where the program runs, but produces incorrect results. These are usually caught via AssertionError in the "Assert" phase of the Arrange–Act–Assert (AAA) testing pattern.

You could argue pedantically that AssertionError is a runtime error, but in testing, we treat it as a signal for logical failure:

"The function ran, but the output didn’t match the expected behavior."

Mutation testing assumes that syntax and runtime errors are already handled. Its purpose is to validate whether the test suite reliably catches logical misbehavior.

A Deeper Falsification Perspective

Now, let's connect mutation testing back to Karl Popper's principle of falsification, which we introduced earlier in the context of scientific reasoning. Recall that Popper argued scientific theories gain strength not by being "proven," but by surviving rigorous attempts to disprove them. The core idea of falsification logic is that to disprove an implication like P⟹Q, you only need to find one instance where P is True and Q is False.

Mutation testing applies this same powerful principle, but to our test suite's effectiveness:

Instead of trying to prove directly that our tests are perfect, mutation testing takes a falsification approach to the implication ¬P⟹¬Q ("If the code is incorrect, then the tests fail"). It actively tries to falsify this crucial relationship.

If we introduce a mutation (making ¬P true, that is, the code is now incorrect) but the existing test suite still passes (meaning Q is true), then we have found an instance where:

1. ¬P is True (the code is incorrect due to the mutation).

2. Q is True (the test still passes).

In this scenario, the implication ¬P⟹¬Q is falsified because we have a True antecedent (¬P) leading to a False consequent (¬Q is false, because Q is true).

And, critically, if ¬P⟹¬Q is falsified, then its logically equivalent contrapositive, Q⟹P ("If the tests pass, then the code is correct"), is also falsified. This means we can no longer trust that a passing test suite reliably indicates correct code. Our desired P⟺Q relationship is broken – the test suite is no longer fully effective at guaranteeing correctness.

By pushing for zero surviving mutants, mutation testing forces us to minimize the surface area of these "hidden assumptions" in our test suite. It demands highly sensitive and specific tests that can pinpoint even subtle logical flaws, thereby moving us closer to building truly resilient systems.

Comparing TDD (Red Phase) and Mutation Testing

Both methodologies, albeit through different means and at different stages of the development cycle, aim to establish confidence in the ¬P ⟹ ¬Q relationship.

Key Differences Summarized:

Toward If-and-Only-If Confidence

Ultimately, the goal in software development is to establish if-and-only-if relationships whenever possible, both in the code implementation and especially in the sensitivity of the test suite to the code under test.

This means if a certain condition (P) is true, then a specific outcome (Q) must occur, and if Q occurs, then P must have been the cause. Achieving this level of clarity comes from:

• A deep understanding of the problem.

• Aligned expectations during requirements gathering.

• Logical analysis and interpretation of well-designed experiments.

• Adherence to Single Responsibility Principle in SOLID

• Rigorous tests with meaningful coverage.

This allows us to understand how control flow and data flow work with greater depth and confidence, leading to better inferences throughout the entire software development lifecycle.

Real-World Challenges

While striving for perfect "if-and-only-if" relationships provides a powerful logical ideal, the messy reality of modern software development presents significant hurdles. The very characteristics that make large systems powerful and scalable – their intricate interconnections and inherent dynamism – simultaneously obscure clear cause-and-effect relationships, making precise logical reasoning and debugging an ongoing battle.

A Web of Complexity

Fan-In, Fan-Out: The Nature of Modern Systems

Any reasonably large software system rarely operates through purely linear control and data flows. Fan-out and fan-in patterns – where many components are called and then their results merged – are inevitable.

For example:

• In ETL pipelines, data may be ingested from multiple sources (external APIs, CSVs) and logged to multiple destinations (files, databases).

• In concurrent programming, Python’s ProcessPoolExecutor splits data into chunks processed in parallel, then recombines the results.

SRP Meets Real-World Boundaries

Just as functional programming must eventually perform I/O, the Single Responsibility Principle (SRP) runs into real-world boundaries, whether conceptual or infrastructural. At some point, something must glue these isolated units together.

Orchestration logic might live in a single function, span multiple files, or even distribute across microservices and machines communicating over networks. While this decomposition enhances modularity, it also increases surface area for bugs involving:

• Side effects: Unintended changes to system state outside a component's explicit outputs.

• Circular dependencies: Components relying on each other in a loop, leading to difficult-to-trace behavior.

• Interface drift: Changes in one component's input/output expectations not being correctly reflected elsewhere.

• Race conditions: Timing-dependent bugs in concurrent operations.

• Serialization issues: Problems translating data between different formats or systems.

• Network unreliability: Unpredictable latency, packet loss, or disconnections in distributed systems.

The Double-Edged Sword of Abstraction

This web of dependencies is the price of progress, made manageable only through better tooling and abstractions.

• If boundaries are well-designed, observable, and testable, they enable asynchronous collaboration, improve long-term maintainability, and increase developer confidence. (See GitHub Playbook in References)

• If systems lack architectural coherence or fall behind evolving needs, they calcify into technical debt that demoralizes even the most motivated teams.

Clean Code Is Contextual

While abstractions and orchestration help manage complexity, overusing design patterns or creating unnecessary class layers can introduce needless indirection. This is a common counterargument to architectural purism.

Ultimately, what counts as "clean code" is context-dependent. It varies with programmer skill, the tooling at hand (linters, tests, Copilot), and whether the project is a throwaway script or a multi-year infrastructure investment. Architectural practices like SRP should evolve alongside those constraints.

The Butterfly Effect of Bugs

From SRP to Reasoning Chains

Previously, we focused on simple, direct cause-effect logic (P ⟹ Q), but real-world systems are messier.

The more we adhere to SRP through small, focused functions, the more we create longer chains of logic. This improves separation of concerns but also extends the reasoning required to debug behavior.

Debugging in a Causal Fog

A seemingly minor trigger (O) can cascade through a chain like O⟹P⟹Q⟹R, which we may not fully understand due to knowledge silos, evolving requirements, or runtime dynamism.

Even when we understand the components, precisely identifying “P” is hard, much like how redefining a research question shifts the statistical population being studied. In complex systems with feedback loops (recommender engines), there might not be a single "root cause" at all.

Short-Term Triage vs. Long-Term Insight

Finding the true origin of a bug often demands experimentation, telemetry, and broad system insight. These investigations produce robust, future-proof fixes but take time.

In on-call scenarios, however, urgency reshapes priorities. Fast mitigations and clear communication often take precedence over deep diagnosis.

Masked by Design and Debt

As systems scale, failure stops looking like a crash. Instead, it shows up as a retry spike, a slow metric drift, or silent fallback behavior.

Modern fault-tolerant systems, built with retries, failovers, circuit breakers, and autoscaling, are designed to recover quickly. This resilience often masks deeper problems, delaying detection for weeks and making root cause analysis harder.

Operating in non-deterministic environments with flaky networks, race conditions, or dynamic routing adds further ambiguity. Small symptoms become harder to link back to specific causes.

Compounding this, technical debt driven by weak technical leadership, shifting priorities or time pressure weakens the system’s observability and test coverage. Teams inherit brittle, poorly understood code, making it hard to draw clean lines between cause and effect.

Even the best engineers struggle in such conditions. When a system resists clarity, it doesn’t just block debugging. It erodes trust, slows learning, and fuels long-term burnout.

Glimmers of Hope: Tools and Practices for Clarity

Despite these challenges, several strategies and practices offer a path toward more robust and understandable software.

Leveraging Design Patterns

Design patterns offer a shared vocabulary and time-tested strategies for structuring systems. When applied well, they tame complexity, reduce technical debt, and make behavior more predictable.

They also tend to concentrate similar failure modes. The same bug might appear across companies or industries, creating a wealth of prior art and solution playbooks. Familiarity with patterns can accelerate debugging and deepen shared understanding across teams.

Nurturing Expert Mentorship

Promoting mentors based on real technical impact instead of tenure builds stronger teams and avoids the Peter Principle (people in a hierarchy tend to rise to a level of respective incompetence).

Great mentors teach more than skills – they model falsifiability, independent thinking, and an ability to reason under uncertainty.

They help others challenge assumptions, navigate tradeoffs, and grow both technically and interpersonally. In systems where root causes are murky, this kind of leadership is essential.

One of the most powerful techniques that scales from mentorship to code is falsification: the disciplined search for counterexamples. Whether applied in design reviews, debugging sessions, or automated tests, this mindset anchors reasoning in reality.

The Power of Falsification in Testing

The deliberate search for counterexamples is core to building reliable systems.

• In algorithm design, testing edge cases is just falsification in disguise: finding where your logic breaks.

• In code, fuzz testing (Atheris) throws diverse inputs at functions to expose falsifying examples.

• Property-based testing (Hypothesis) goes further by generating inputs that satisfy certain rules, then shrinks failures to their minimal form. This greatly improves reproducibility and helps stress-test concurrency issues.

The more rigorously we attempt to falsify our assumptions, the more confidently we can reason about behavior using tools like Modus Ponens and Modus Tollens.

Assumptions are always present in software to simplify complexity. The question is whether they're explicitly codified in tests or left hidden and fragile.

Of course, no test is ever bulletproof: our assumptions could be mistaken, or the world could change. That’s why critical thinking, discerning "what should be" versus "what is", remains essential as newer generations increasingly rely on AI tools like Large Language Models.

This deliberate, falsification-driven approach is paramount for building reliable software. It underpins sophisticated testing techniques designed to expose hidden assumptions and break our logical chains.

While testing helps us uncover where our reasoning might falter, some domains demand an even higher degree of certainty. For those critical systems, we turn to the ultimate tools for logical rigor: Proof Assistants.

Proof Assistants

While traditional testing and fuzzing are powerful for finding bugs, they fundamentally cannot guarantee correctness for all possible inputs or scenarios. They can only prove the presence of bugs, not their absence.

To achieve formal, mathematically verified proofs of program behavior – providing the strongest possible guarantees – we turn to proof assistants. These tools allow us to build step-by-step logical proofs, ensuring that a program or system design adheres to its specification with absolute rigor.

Prolog

Prolog offers a relatively straightforward entry point into the world of logic programming and theorem proving. SWI-Prolog is a common interpreter (a REPL, or Read-Eval-Print Loop) for Prolog.

You interact with Prolog by providing it with a knowledge base composed of facts and rules (which are a type of logical clause called Horn clauses). You then pose queries.

Installing SWI-Prolog

You can download SWI-Prolog from its official website: https://www.swi-prolog.org/download/stable
Follow the instructions for your operating system (Windows, macOS, or Linux).

On Ubuntu/Debian, you can usually install it via:

sudo apt update
sudo apt install swi-prolog

Using Prolog: REPL vs. File

• REPL (swipl) is best for: Quick, interactive tests of single facts or rules, and posing queries to an already loaded knowledge base.

• A File (.pl extension) is best for: Defining your entire knowledge base (multiple facts and rules) and storing your program for reusability. This is the standard way to work with Prolog for anything beyond a few lines.

Example: A Simple Knowledge Base

Let's define a knowledge base to represent who has a job and who is a coding instructor.

1. Create a file named knowledge.pl with the following content:

% knowledge.pl
% This file defines a small knowledge base in Prolog.
% In Prolog, all statements (facts and rules) about the same predicate
% (identified by its name AND number of arguments, e.g., 'has_job' with 1 argument is 'has_job/1')
% must be written consecutively without other predicate definitions in between.

% --- Definitions for the 'has_job' predicate (takes 1 argument) ---

% Fact: Alice has a job.
has_job(alice).

% Fact: Bob has a job.
has_job(bob).

% Rule: Anyone (represented by variable X) has a job IF they are a coding instructor.
% ':-' means 'if'. 'X' is a variable (starts with uppercase).
has_job(X) :- is_coding_instructor(X).

% --- Definitions for the 'is_coding_instructor' predicate (takes 1 argument) ---

% Fact: Alice is a coding instructor.
is_coding_instructor(alice).

What each line does:

• Lines starting with %: These are comments for human readability, ignored by Prolog. They explain the file's purpose and key rules like predicate grouping.

• has_job(alice). / has_job(bob).: These are facts. They assert simple truths, like "Alice has a job." The . at the end is mandatory for every statement.

• has_job(X) :- is_coding_instructor(X).: This is a rule. It states a conditional truth: "For any X, X has a job if X is a coding instructor." X is a variable (always starts with an uppercase letter), and :- means "if." This rule allows Prolog to deduce new information.

• is_coding_instructor(alice).: Another fact, asserting "Alice is a coding instructor." It's placed after all has_job/1 clauses to satisfy Prolog's grouping rule.

2. Load and Query in the REPL:

Open your terminal and type swipl. Once at the ?- prompt, load the file and then pose your queries:

$ swipl
?- [knowledge].   % Load the 'knowledge.pl' file (omit .pl, use square brackets and a period)
% Press Enter. Prolog will confirm it loaded the file, e.g., '% knowledge.pl compiled...'
True.

?- has_job(alice). % Query: Does Alice have a job?
% Press Enter. Prolog gives you a solution, then waits.
True.              % Output: Yes, because it's a fact.
% After 'True.', you'll see the '?- ' prompt again, indicating Prolog is ready for your next query.
% If there were multiple ways to prove 'True.', Prolog would present the first 'True.' then wait for you to press ';' for alternatives, then Enter to confirm the final 'True.' or 'False.'.

?- has_job(carol). % Query: Does Carol have a job?
% Press Enter.
False.             % Output: No, Prolog cannot prove it from its knowledge.

?- has_job(X).     % Query: Who has a job? (Find values for X)
% Press Enter
X = alice ;        % Prolog finds Alice as the first solution. Type ';' and press Enter to ask for the next solution.
X = bob ;          % It finds Bob. Type ';' and press Enter for the next solution.
X = alice          % It finds Alice again (this time deduced via the rule and is_coding_instructor(alice)).
% Press Enter. This accepts the current set of solutions and stops searching for more.
False.             % Output: Indicates no more solutions found after the last 'Enter' (or if you explicitly chose not to search further).

?- halt.           % Type 'halt.' to exit the Prolog REPL cleanly.
% Alternatively, you can often use Ctrl+D (press and hold Ctrl, then D) to exit most REPLs.

The Prolog example clearly demonstrates:

• "Is P(X) true for a specific X?": Shown by ?- has_job(alice). (returns True.) and ?- has_job(carol). (returns False.).

• "Is there an X for which P(X) is true?": Shown by ?- has_job(X). (provides solutions like X = alice, X = bob).

Prolog Limitations

Prolog's limitations become evident when attempting to reason about falsity or non-existence. You cannot directly ask "Is there any X for which P(X) is false?"

Instead, Prolog operates on the principle of negation as failure. This means that if Prolog cannot prove a statement, it considers that statement false.

For example, if you ask ?- \+ has_job(carol). (meaning "Is it not true that Carol has a job?"), Prolog will say True, because it simply cannot find any proof that Carol has a job in its knowledge base.

This is a significant distinction: it doesn't mean Carol definitely doesn't have a job, nor does Prolog provide a formal counterexample. It merely reflects a lack of provable information.

This fundamental constraint means Prolog, while powerful for logic programming, falls short of being a full-fledged proof assistant for comprehensive formal verification.

Coq

After experimenting with Prolog and seeing its limitations, you can move on to a more powerful proof assistant like Coq. Coq is employed in safety-critical domains where absolute mathematical certainty is paramount. coqtop is the standard REPL for Coq.

A fundamental difference from Prolog is Coq's lack of a Closed World Assumption. In Coq, anything not explicitly proven is simply unknown, not automatically false.

Unlike Prolog, Coq's primary purpose isn't solving computational problems by searching a knowledge base. Its true power lies in its ability to construct and verify formal mathematical proofs and programs with absolute rigor. Its interaction involves managing a proof state (your remaining goals) and applying tactics (logical inference steps) until the proof is complete.

Installing Coq

Coq can be installed in several ways, often via package managers or a tool called opam (the OCaml package manager, as Coq is written in OCaml).

• Official Downloads: Visit the Coq website for detailed instructions for your OS: https://coq.inria.fr/download

• Using a system package manager (for example, Ubuntu/Debian): Bash

    sudo apt update
    sudo apt install coq
  

Using Coq: REPL vs. File

• REPL (coqtop) is best for: Trying out single tactics, inspecting the current proof state, or learning basic syntax for very short commands.

• A File (.v extension) is best for: Almost all Coq development and proof construction. This is how complex proofs and verified programs are structured and managed.

Coq's Comprehensive Question Answering

Unlike Prolog, Coq can directly address all three types of logical questions we've discussed, providing robust answers backed by formal proof:

• "Is P(X) true for a specific X?": Coq allows you to define a precise statement (a theorem) like "Alice has a job." You then build a step-by-step logical proof that formally confirms whether this statement is true based on your definitions. If the proof succeeds, Coq formally verifies it: if it fails, Coq clearly shows where your logic breaks down.

• "Is there an X for which P(X) is true?": Coq handles questions of existence. If you ask, "Does someone have a job?", you can construct a proof by explicitly providing an example (like "Alice") and then proving that your chosen example indeed satisfies the condition ("Alice has a job").

• "Is there any X for which P(X) is false?": This is a key capability where Coq excels over Prolog. Coq allows you to formally prove that a statement is false, or that a counterexample exists. For instance, you could prove "Carol does not have a job" by showing it contradicts the definition, or prove "there exists someone who doesn't have a job" by explicitly identifying such a person and proving that they indeed lack a job. This direct ability to reason about negation and provide formal counterexamples (or prove their non-existence) is what makes Coq a full-fledged proof assistant.

While Coq's core doesn't automatically generate counterexamples when a proof fails, plugins like QuickChick can be integrated for property-based testing to find falsifying examples.

It's a Coq library that allows you to specify properties about your Coq definitions and then randomly generate inputs to try and find a counterexample that falsifies your property.

This is a powerful way to find bugs early in your formalization before you invest a lot of time trying to prove a false theorem.

TLA+, Isabelle, and Lean: A Spectrum of Formal Verification

Beyond Prolog and Coq, other powerful proof assistants and formal specification languages cater to different needs and paradigms:

• TLA+: This is a formal specification language developed by Leslie Lamport. It focuses on modeling and verifying system designs (especially concurrent and distributed ones) using temporal logic, rather than proving low-level code. It helps ensure critical properties like safety (nothing bad ever happens) and liveness (something good eventually happens). Its practicality and accessibility make it popular in industry, notably at Amazon and Microsoft for robust system design.

• Isabelle and Lean: These are modern, highly advanced proof assistants.

  • Isabelle, grounded in higher-order logic, is widely used by researchers and institutions (for example, in projects like the seL4 verified microkernel) for formal theorem proving and software verification in academic and safety-critical domains demanding extreme rigor.

  • Lean, based on dependent type theory, is favored by mathematicians for formalizing proofs in pure mathematics (for example, number theory, algebra). It's known for its powerful automation and active community.

These tools represent the pinnacle of applying formal logic to ensure the correctness and reliability of both mathematical theories and complex software systems.

Now that you have a good lay of the land in both theory and practice, here are some thought experiments to enrich your education.

Food for Thought

The journey into formal logic and its intersection with practical domains like software and science offers many avenues for deeper exploration.

Hypothesis Testing in Science and the Implication Truth Table

Statistical hypothesis testing uses a probabilistic form of Modus Tollens. We start with a null hypothesis (H0​): "If H0​ is true, then observing this data (or more extreme data) is likely." We then observe data that is highly unlikely/unexpected if H0​ were true (that is, a small p-value). This serves as our probabilistic "not Q." Therefore, we conclude that H0​ is likely not true (we reject H0​). This is our probabilistic "∴¬P."

Here, the "truthiness" of P⟹Q is being tested, rather than simply assumed to be true for developing arguments, as in Modus Ponens or Modus Tollens. There's no absolute truth or anything to "prove" definitively.

Inferences are drawn from prior experiments (which inform the test data distribution) and context-specific experiment setups (which determine the significance level α), together defining the threshold (critical value) for what is considered an unlikely observation of Q.

The experiment's result is a rejection (or lack thereof) of H0​, not a definitive proof that H0​ is true.

Inductive Reasoning's Relationship to Deductive Arguments

• Induction generates general rules (for example, "P is always followed by Q") from specific observations or cases.

• Deduction then tests or applies those general rules in new situations.

If deduction leads to wrong predictions (that is, a rule is falsified), induction may need to revise the original rule, which forms a continuous feedback loop that refines our understanding.

Necessity and Sufficiency in Implication

The implication P⟹Q ("If you crossed the border, you must have had a passport") unpacks into two fundamental logical concepts:

• P is sufficient for Q: Crossing the border guarantees you had a passport. (P alone is enough for Q.)

• Q is necessary for P: If you didn't have a passport (¬Q), you couldn't have crossed (¬P). (Q is required for P to happen.)

Q.E.D.: The Enduring Power of Logic in an Uncertain World

Throughout this handbook, we’ve journeyed from the foundational concepts of propositional logic and truth tables to the powerful argument forms of Modus Ponens and Modus Tollens. We explored how these tools enable valid deductions and identified common logical fallacies like Affirming the Consequent and Denying the Antecedent, understanding why they lead to incorrect inferences when an "if-then" relationship isn't a strict "if and only if." We learned the profound importance of falsifiability – the ability for a statement or hypothesis to be disproven – a cornerstone of both scientific inquiry and robust software testing.

We then delved into the practical application of these logical principles in software development, mapping code correctness to test outcomes. We discovered how a failing test, when trusted, becomes a powerful application of Modus Tollens, pinpointing defects. We also confronted the "illusion of correctness" that arises from the affirming the consequent fallacy when tests pass for the wrong reasons, especially when using test doubles.

Crucially, we introduced the "If and Only If" (P⟺Q) relationship, highlighting its unparalleled power in establishing unambiguous connections between cause and effect. This bidirectional guarantee is the ideal we strive for in test suite quality, moving beyond mere correlation to a deeper understanding of causality. We saw how mutation testing rigorously pushes us towards this "if and only if" confidence by actively trying to falsify the assumption that "incorrect code leads to failing tests," thereby strengthening the inverse: "passing tests guarantee correct code."

We also acknowledged the "messy reality" of modern software. Large systems are webs of complexity, with fan-in/fan-out patterns, side effects, and unforeseen interactions that can obscure clear logical chains. Technical debt and the double-edged sword of abstraction often mask the true origins of bugs, turning debugging into a "causal fog."

Logic as Your Compass

Despite these formidable challenges, the logical principles we've explored remain your most vital tools. They provide the mental framework to navigate uncertainty.

When confronted with a bug, your ability to reason logically allows you to formulate hypotheses, design focused experiments (your tests), and interpret their outcomes with precision. Whether you're debugging a complex microservice or reasoning about a simple function, applying Modus Tollens to a failing test or designing tests that aim for P⟺Q clarity helps you cut through the noise.

We also touched upon advanced tools like Proof Assistants (Prolog, Coq, TLA+, Isabelle, Lean), which represent the pinnacle of applying formal logic to guarantee system correctness – a testament to the enduring power of logical rigor in critical domains.

In the intricate dance between theory and practice, the principles of logic stand as an unshakeable foundation. They are the "rocks" upon which you can meticulously build your understanding and your systems. The more consistently you apply this critical thinking, driven by curiosity and a commitment to rigorous validation, the clearer your path becomes.

This clarity is not just about fixing today’s bugs, it’s about continually refining your mental models, fostering trust in your codebase, and equipping yourself to build increasingly robust and predictable systems in an ever-evolving technological landscape.

If you love problem solving, critical thinking, or have experiences on how you fixed an issue that looked different from how it initially seemed, feel free to connect with me at https://linkedin.com/in/hanqi91.

Resources

1. Article that motivated this handbook: Classical Reasoning and Debugging

2. 3 Formal proofs of modus tollens: https://en.wikipedia.org/wiki/Modus_tollens

3. Table of 24 syllogisms: https://en.wikipedia.org/wiki/Syllogism

4. Challenging Assumptions: Falsehoods software teams believe about user feedback

5. How assumptions and software evolve beyond your control: https://www.tdda.info/why-code-rusts

6. Relationship to Hypothesis Testing: https://sites.google.com/view/reasonedwriting/home/FRAMEWORK_FOR_SCIENTIFIC_PAPERS/HYPOTHESES/HOW_TO_TEST_HYPOTHESES/MODUS_TOLLENS

7. The Troubleshooting Mindset: https://www.autodidacts.io/troubleshooting/

8. Causal Diagrams from The Effect Book: https://theeffectbook.net/ch-CausalDiagrams.html

9. A systematic guide to the mindsets and practices of debugging: https://www.amazon.sg/Debug-Find-Repair-Prevent-Bugs/dp/193435628X

10. Constructing P in a way to ensure software correctness: https://www.hillelwayne.com/post/constructive/

11. Fail Fast by explicitly representing assumptions as assertions: https://www.martinfowler.com/ieeeSoftware/failFast.pdf

12. Deterministic Simulation Testing to tackle complex systems: https://pierrezemb.fr/posts/learn-about-dst/

13. GitHub’s Engineering System Success Playbook (ESSP) - Quality, Velocity, Developer Happiness on Business Outcomes: https://assets.ctfassets.net/wfutmusr1t3h/us6AUuwawrtNGTlwlT9Ac/f0fce86712054fc87f10db28b20f303b/GitHub-ESSP.pdf

14. Closed-world assumption: https://en.wikipedia.org/wiki/Closed-world_assumption

Glossary

• Axiom: A fundamental truth or rule accepted as a starting point for a logical or mathematical system, without requiring proof.

• Contrapositive: A logically equivalent form of an "if-then" statement (P⟹Q), which is ¬Q⟹¬P ("If not Q, then not P").

• Deductive Reasoning: A type of logical reasoning where a conclusion is necessarily true if its premises are true.

• Falsification: The principle, especially in science (from Karl Popper), that a hypothesis or theory must be capable of being proven false by empirical observation or experiment.

• Formal Logic: The study of abstract systems of reasoning and arguments based on their structure, independent of content.

• Hypothesis Testing: A statistical method for making inferences about a population based on sample data, typically by testing a null hypothesis (e.g., "P has no effect on Q") against an alternative hypothesis.

• Logical Fallacy: A flaw in the structure or content of an argument that makes it unsound or invalid, even if its conclusion might seem plausible.

  • Affirming the Consequent (Fallacy): An invalid argument form that mistakenly assumes if P⟹Q is true, and Q is true, then P must be true.

  • Denying the Antecedent (Fallacy): An invalid argument form that mistakenly assumes if P⟹Q is true, and P is false, then Q must be false.

• Modus Ponens: A valid argument form: If P⟹Q is true and P is true, then Q must be true.

• Modus Tollens: A valid argument form: If P⟹Q is true and ¬Q is true, then ¬P must be true.

• Mutation Testing: A software testing technique that involves deliberately introducing small, single-point faults (mutations) into code to assess the effectiveness and coverage of a test suite.

• Propositional Logic: A branch of logic that deals with propositions and their relationships using logical operators.

• Test-Driven Development (TDD): A software development methodology where tests are written before the code, guiding the development process and ensuring correctness.

• Truth Table: A table that systematically lists all possible truth values for a set of propositions and shows the resulting truth value of a complex logical statement.

• Vacuously True: Describes an implication (P⟹Q) that is considered true simply because its antecedent (P) is false.

Here is a list of 460 free textbooks, arranged by topic. Once you find a topic that interests you, click that link and it will jump you down to a list of related textbooks.

High School Textbook Categories

• Math
• Natural Sciences
• Classical Novels

College Textbook Categories

• Computer Science
• Engineering
• Education
• Math
• Natural Sciences
• Medicine
• Social Sciences
• Humanities
• Business
• Law
• Journalism and Communication

High school Textbooks (90)

Math

1. Statistics
2. Advanced High School Statistics - 2nd Edition
3. Advanced High School Mathematics

Natural Sciences

1. AP Physics Collection
2. Biology for AP courses
3. Physics
4. Principles of Macroeconomics for AP courses 2e
5. Principles of Microeconomics for AP courses 2e

Classical Novels

1. Adventures of Huckleberry Finn, The
2. Adventures of Tom Sawyer, The
3. Aesop’s Fables
4. Agnes Grey
5. Alice’s Adventures in Wonderland
6. Andersen’s Fairy Tales
7. Anna Karenina
8. Anne of Green Gables
9. Around the World in 80 Days
10. Beyond Good and Evil
11. Bleak House
12. Brothers Karamazov, The
13. Christmas Carol, A
14. Crime and Punishment
15. David Copperfield
16. Down and Out in Paris and London
17. Dracula
18. Dubliners
19. Emma
20. Erewhon
21. For the Term of His Natural Life
22. Frankenstein
23. Great Expectations
24. Great Gatsby, The
25. Grimms Fairy Tales
26. Gulliver’s Travels
27. Heart of Darkness
28. Hound of the Baskervilles, The
29. Idiot, The
30. Iliad, The
31. Island of Doctor Moreau, The
32. Jane Eyre
33. Jungle Book, The
34. Kidnapped
35. Lady Chatterly’s Lover
36. Last of the Mohicans, The
37. Legend of Sleepy Hollow, The
38. Les Miserables
39. Little Women
40. Madame Bovary
41. Merry Adventures of Robin Hood, The
42. Metamorphosis, The
43. Middlemarch
44. Moby Dick
45. 1984
46. Northanger Abbey
47. Nostromo: A Tale of the Seaboard
48. Notes from the Underground
49. Odyssey, The
50. Of Human Bondage
51. Oliver Twist
52. Paradise Lost
53. Persuasion
54. Picture of Dorian Gray, The
55. Pollyanna
56. Portrait of a Lady, The
57. Portrait of the Artist as a Young Man, A
58. Pride and Prejudice
59. Prince, The
60. Robinson Crusoe
61. Scarlet Pimpernel, The
62. Sense and Sensibility
63. Sons and Lovers
64. Strange Case of Dr Jekyll and Mr Hyde, The
65. Swanns Way
66. Tale of Two Cities, A
67. Tales of Mother Goose, The
68. Tarzan of the Apes
69. Tender is the Night
70. Tess of the d’Urbervilles
71. Thirty Nine Steps, The
72. Three Musketeers, The
73. Time Machine, The
74. Treasure Island
75. Trial, The
76. Ulysses
77. Utopia
78. Vanity Fair
79. War and Peace
80. Within A Budding Grove
81. Women In Love
82. Wuthering Heights

College TextBooks (370)

Computer Science

1. Python for Everybody: Exploring Data Using Python 3
2. Web Accessibility for Developers
3. The Missing Link: An Introduction to Web Development and Programming
4. Foundations of Computation
5. Algorithms and Data Structures With Applications to Graphics and Geometry
6. Think Data Structures: Algorithms and Information Retrieval in Java
7. Open Data Structures: An Introduction
8. Java with BlueJ
9. Introduction to Programming Using Java - Eighth Edition
10. A Byte of Python
11. Eloquent JavaScript: A Modern Introduction to Programming
12. High Performance Computing
13. Database Design - 2nd Edition
14. Relational Databases and Microsoft Access
15. A First Course in Electrical and Computer Engineering
16. How to Think Like a Computer Scientist: Learning with Python
17. How to Think Like a Computer Scientist: C Version
18. How to Think Like a Computer Scientist: C++ Version
19. Programming Fundamentals - A Modular Structured Approach using C++
20. Think Java: How To Think Like a Computer Scientist - 2e
21. Java, Java, Java: Object-Oriented Problem Solving
22. Think Stats: Probability and Statistics for Programmers - 2e
23. Think Bayes: Bayesian Statistics Made Simple
24. Think Complexity: Exploring Complexity Science with Python - 2e
25. Digital Circuit Projects: An Overview of Digital Circuits Through Implementing Integrated Circuits
26. Introduction to the Modeling and Analysis of Complex Systems
27. Physical Modeling in MATLAB
28. Spatial Thinking in Planning Practice: An Introduction to GIS
29. Introduction to Computer Graphics
30. Computer Networks: A Systems Approach
31. An Introduction to Computer Networks - Second Edition
32. Computer Networking : Principles, Protocols and Practice
33. Signal Computing: Digital Signals in the Software Domain
34. x86-64 Assembly Language Programming with Ubuntu
35. Professional Web Accessibility Auditing Made Easy
36. First Semester in Numerical Analysis with Python
37. The Crystal Ball Instruction Manual - version 1.1 Volume One: Introduction to Data Science
38. An Introduction to Matlab and Mathcad
39. Yet Another Introductory Number Theory Textbook (Cryptology Emphasis Version)
40. Delftse Foundations of Computation
41. The Unicode cookbook for linguists: Managing writing systems using orthography profiles
42. Implementing a One Address CPU in Logisim
43. Embedded Controllers Using C and Arduino - 2e
44. Introduction to MIPS Assembly Language Programming
45. Think DSP: Digital Signal Processing in Python
46. Information Systems for Business and Beyond
47. Information Systems: A Manager's Guide to Harnessing Technology
48. The Little Book of Semaphores
49. Essentials of Geographic Information Systems
50. Programming Languages: Application and Interpretation - Version Second Edition

Engineering

1. A Brief Introduction to Engineering Computation with MATLAB
2. Introduction to Industrial Engineering
3. Fundamentals of Electrical Engineering I
4. A First Course in Electrical and Computer Engineering
5. Sustainability: A Comprehensive Foundation
6. Notes on Diffy Qs: Differential Equations for Engineers
7. Elementary Differential Equations with Boundary Value Problems
8. Developing New Products and Services
9. Introduction to Aerospace Structures and Materials
10. Building Maintenance & Construction: Tools and Maintenance Tasks
11. Direct Energy
12. Operational Amplifiers & Linear Integrated Circuits: Theory and Application - 3e
13. Manufacturing Processes 4-5
14. Electromagnetics Vol 1
15. DC Electrical Circuit Analysis: A Practical Approach
16. AC Electrical Circuit Analysis: A Practical Approach
17. Applied Fluid Mechanics Lab Manual
18. Fundamentals of Microwave and RF Design
19. Introduction to Probability
20. Introduction to Linear, Time-Invariant, Dynamic Systems for Students of Engineering

Education

1. Hybrid-Flexible Course Design
2. Creating Online Learning Experiences
3. Education for a Digital World: Advice, Guidelines and Effective Practice from Around Globe
4. Educational Psychology
5. Learning to Learn Online
6. Sharing Our Knowledge: Best Practices for Supporting English Language Learners in Schools
7. Introduction to Curriculum for Early Childhood Education
8. Bad Ideas About Writing
9. Write Here, Right Now: An Interactive Introduction to Academic Writing and Research
10. Elementary Earth and Space Science Methods
11. Mathematics for Elementary Teachers
12. Trauma Informed Behaviour Support: A Practical Guide to Developing Resilient Learners
13. Trauma-Informed School Practices: Building Expertise To Transform Schools
14. Wellbeing in Educational Contexts
15. Parenting and Family Diversity Issues
16. Safety, Health, and Nutrition in Early Childhood Education
17. The ELC: An Early Childhood Learning Community at Work
18. Building Democracy for All: Interactive Explorations of Government and Civic Life
19. Foundations of Learning and Instructional Design Technology
20. Ethical Use of Technology in Digital Learning Environments: Graduate Student Perspectives
21. Writing Instruction Tips For Automated Essay Graders: How To Design an Essay for a Non-human Reader
22. Conventions 101: A Functional Approach to Teaching (And Assessing!) Grammar and Punctuation
23. Choosing & Using Sources: A Guide to Academic Research
24. WAC and Second-Language Writers: Research Towards Linguistically and Culturally Inclusive Programs and Practices
25. WAC Partnerships Between Secondary and Postsecondary Institutions
26. Working With Academic Literacies: Case Studies Towards Transformative Practice
27. Antiracist Writing Assessment Ecologies: Teaching and Assessing Writing for a Socially Just Future
28. Critical Expressivism: Theory and Practice in the Composition Classroom
29. Copy(write): Intellectual Property in the Writing Classroom
30. Teaching Autoethnography: Personal Writing in the Classroom

Math

1. Algebra and Trigonometry
2. Calculus Volume 1
3. Calculus Volume 2
4. Calculus Volume 3
5. Multivariable Calculus
6. College Algebra
7. Open Resources for Community College Algebra
8. Elementary Algebra 2e
9. Intermediate Algebra 2e
10. Fundamentals of Matrix Algebra
11. Introduction to GNU Octave: A brief tutorial for linear algebra and calculus students
12. A Cool Brisk Walk Through Discrete Mathematics
13. Mathematical Analysis I
14. Introductory Statistics with Randomization and Simulation - First Edition
15. Introductory Business Statistics
16. Introductory Statistics
17. Statistical Thinking for the 21st Century
18. Lies, Damned Lies, or Statistics: How to Tell the Truth with Statistics
19. Prealgebra 2e
20. Precalculus
21. Geometry with an Introduction to Cosmic Topology
22. Technical Mathematics
23. Introduction to Game Theory: a Discovery Approach
24. Quantitative Problem Solving in Natural Resources
25. Euclidean plane and its relatives
26. Proofs and Concepts: The Fundamentals of Abstract Mathematics
27. Applied Finite Mathematics
28. Linear Regression Using R: An Introduction to Data Modeling
29. Applied Combinatorics
30. Math in Society - Edition 2.5

Natural Sciences

1. Anatomy and Physiology
2. Human Anatomy Lab Manual
3. A Mixed Course-Based Research Approach to Human Physiology
4. Fundamentals of Anatomy and Physiology - Australian Edition
5. Astronomy
6. Biochemistry: Free For All
7. Biology 2e
8. Concepts of Biology
9. Principles of Biology: Biology 211, 212, and 213
10. Microbiology
11. General Microbiology - 1st Edition
12. A Primer for Computational Biology
13. From Growing to Biology: Plants 1e
14. A Student's Guide to Tropical Marine Biology
15. Chemistry 2e
16. Chemistry: Atoms first 2e
17. College Physics
18. Foundations of Neuroscience
19. Foundations of Epidemiology
20. Radiation Safety
21. Environmental Toxicology
22. Geological Structures: a Practical Introduction
23. Physical Geology - First University of Saskatchewan Edition
24. Climate Toolkit: A Resource Manual for Science and Action
25. Introduction to Climate Science - 1st Edition
26. Bending the Curve: Climate Change Solutions
27. Chemical Biology & Biochemistry Laboratory Using Genetic Code Expansion Manual
28. Biotechnology Foundations - 2nd Edition
29. An EKG Interpretation Primer
30. Introduction to Oceanography

Medicine

1. Nutrition: Science and Everyday Application - beta v 0.1
2. Human Nutrition - 2020 Edition
3. Concepts of Fitness and Wellness
4. Histology and Embryology for Dental Hygiene
5. Nursing Pharmacology
6. Nursing Care at the End of Life: What Every Clinician Should Know
7. Transitions to Professional Nursing Practice - 2nd Edition
8. Safety, Health, and Nutrition in Early Childhood Education
9. The Complete Subjective Health Assessment
10. Evidence-Based Massage Therapy
11. A Laboratory Guide to Clinical Hematology
12. Undergraduate Diagnostic Imaging Fundamentals
13. Public Health Ethics: Global Cases, Practice, and Context
14. Literature Reviews for Education and Nursing Graduate Students
15. Health Case Studies
16. Supporting Individuals with Intellectual Disabilities & Mental Illness
17. Field Trials of Health Interventions: A Toolbox
18. Clinical Procedures for Safer Patient Care
19. Creative Clinical Teaching In The Health Professions
20. Veterinary Epidemiology: Principles and Methods

Social Sciences

1. American Government 2e
2. American Government 3e
3. Introduction to Sociology 2e
4. Introduction to Sociology 3e
5. Principles of Economics 2e
6. Principles of Macroeconomics 2e
7. Principles of Microeconomics 2e
8. Psychology 2e
9. Psychology: The Science of Human Potential
10. Abnormal Psychology - 2nd Edition
11. Introduction to Community Psychology
12. An Introduction to Psychological Statistics
13. Human Behavior and the Social Environment I
14. Human Behavior and the Social Environment II
15. Language and Culture in Context - A Primer on Intercultural Communication
16. Intercultural Communication
17. Contemporary Families: An Equity Lens
18. Child Growth and Development
19. Child, Family, and Community
20. Parenting and Family Diversity Issues
21. Interpersonal Communication: A Mindful Approach to Relationships
22. Attenuated Democracy: A Critical Introduction to U.S. Government and Politics
23. Foundations of Social Work Research
24. Introduction to Human Geography - 2nd Edition
25. Beyond Race: Cultural Influences on Human Social Life
26. Classical Sociological Theory and Foundations of American Sociology
27. Speak Out, Call In: Public Speaking as Advocacy
28. A Quick Guide to Quantitative Research in the Social Sciences
29. The Balance of Personality
30. The Art of Being Human: A Textbook for Cultural Anthropology

Humanities

1. Stand up, Speak out: The Practice and Ethics of Public Speaking
2. U.S. History
3. World History: Cultures, States, and Societies to 1500
4. Modern World History
5. International Relations
6. Becoming America: An Exploration of American Literature from Precolonial to Post-Revolution
7. American Literature I: An Anthology of Texts From Early America Through the Civil War
8. Spanish I: Beginning Spanish Language and Culture
9. Linguistics for Teachers of English
10. The Changing Story: digital stories that participate in transforming teaching & learning
11. Essentials of Linguistics
12. Technical Writing
13. Let's Get Writing!
14. You, Writing! A Guide to College Composition
15. Writing for Success
16. College ESL Writers: Applied Grammar and Composing Strategies for Success
17. Introduction to Sociology - 2e
18. Introduction to Philosophy: Philosophy of Religion
19. Introduction to Philosophy: Philosophy of Mind
20. English Composition: Connect, Collaborate, Communicate
21. Studying the Bible: The Tanakh and Early Christian Writings
22. Philosophical Ethics
23. Ethics for A-Level
24. Steps to Success: Crossing the Bridge Between Literacy Research and Practice
25. Exploring Public Speaking - 4th Edition
26. Plato's 'Republic': An Introduction
27. Decoding the 1920s: A Reader for Advanced Learners of Russian
28. An Introduction to Technical Theatre
29. Theatrical Worlds
30. Understanding Basic Music Theory
31. Music Theory for the 21st-Century Classroom
32. Music on the Move
33. Introduction to Art: Design, Context, and Meaning
34. Guide to Ancient Egyptian Art
35. Guide to Ancient Roman art
36. Guide to Ancient Greek Art
37. Moving Pictures: An Introduction to Cinema
38. Naming the Unnameable: An Approach to Poetry for New Generations
39. Prose Fiction: An Introduction to the Semiotics of Narrative
40. Mindful Technical Writing: An Introduction to the Fundamentals
41. Explorations 1: Grammar for the Experienced Beginner
42. Introduction to Logic and Critical Thinking
43. Writing and Literature: Composition as Inquiry, Learning, Thinking, and Communication
44. British Literature I Anthology: From the Middle Ages to Neoclassicism and the Eighteenth Century
45. British Literature II: Romantic Era to the Twentieth Century and Beyond
46. Perspectives: An Open Invitation to Cultural Anthropology
47. A Guide to Good Reasoning: Cultivating Intellectual Virtues - Second edition, revised and updated
48. Inferring and Explaining
49. Exploring Perspectives: A Concise Guide to Analysis
50. EmpoWord: A Student-Centered Anthology & Handbook for College Writers

Business

1. Introduction to Business
2. Business Ethics
3. Business Law 1 Essentials
4. Entrepreneurship
5. Introduction to Intellectual Property
6. Organizational Behavior
7. Principles of Financial Accounting
8. Principles of Managerial Accounting
9. Principles of Management
10. Business Writing Style Guide
11. Financial Management for Small Businesses: Financial Statements & Present Value Models
12. Intermediate Microeconomics with Microsoft Excel - 2nd Edition
13. Business Computers 365
14. Problem Solving in Teams and Groups
15. Digital Accessibility as a Business Practice
16. Management Communication
17. Introduction to Financial Accounting: U.S. GAAP Adaptation
18. eMarketing - The Essential Guide to Online Marketing
19. Fundamentals of Infrastructure Management
20. An Introduction to Cooperation and Mutualism
21. Financial Strategy for Public Managers
22. Entrepreneurship and Innovation Toolkit
23. Business Plan Development Guide
24. Project Management
25. Introducing Marketing
26. Fundamentals of Business - 3rd Edition
27. Business Law and the Legal Environment
28. Good Corporation, Bad Corporation: Corporate Social Responsibility in the Global Economy
29. Guidelines for Improving the Effectiveness of Boards of Directors of Nonprofit Organizations
30. Small Business Management in the 21st Century
31. The Sustainable Business Case Book
32. Advanced Business Law and the Legal Environment
33. Electronic Commerce: The Strategic Perspective
34. Developing New Products and Services
35. Focusing on Organizational Change
36. Human Relations
37. Leading with Cultural Intelligence
38. Managerial Accounting
39. Business English for Success
40. Human Resource Management
41. International Business
42. Strategic Management
43. Sustainability, Innovation, and Entrepreneurship
44. The Power of Selling
45. Principles of Marketing
46. The Legal and Ethical Environment of Business
47. Money and Banking
48. Risk Management for Enterprises and Individuals
49. Exploring Business
50. International Finance: Theory and Policy

Law

1. Law School Materials for Success
2. Introduction to Criminal Investigation: Processes, Practices and Thinking
3. Ethics in Law Enforcement
4. Criminal Law
5. Intellectual Property: Law & the Information Society—Cases and Materials
6. Wetlands Law: A Course Source
7. First Amendment: Cases, Controversies, and Contexts - Second Edition
8. The Indigo Book: A Manual of Legal Citation
9. Fundamentals of Business Law
10. Business Law I Essentials
11. Law 101: Fundamentals of the Law
12. Liberty, Equality and Due Process: Cases, Controversies, and Contexts in Constitutional Law
13. Business Law and the Legal Environment
14. Introduction to the American Criminal Justice System
15. The Law of Trusts
16. Sources of American Law: An Introduction to Legal Research - 4th Edition
17. Basic Income Tax - 8th Edition
18. What Color is Your C.F.R.?
19. U.S. Federal Income Taxation of Individuals 2020
20. Introduction to Contracts, Sales and Product Liability
21. Law for Entrepreneurs
22. Legal Aspects of Corporate Management and Finance
23. Legal Aspects of Marketing and Sales
24. Introduction to Basic Legal Citation
25. Contract Doctrine, Theory & Practice Volume 1
26. United States Copyright Law
27. Land Use
28. Introduction to the Law of Property, Estate Planning and Insurance
29. Law of Commercial Transactions
30. United States Securities Law

Journalism and Communication

1. Exploring Public Speaking - 4th Edition
2. Stand up, Speak out: The Practice and Ethics of Public Speaking
3. Communication in the Real World: An Introduction to Communication Studies
4. Launch! Advertising and Promotion in Real Time
5. Business Communication for Success
6. Understanding Media and Culture: An Introduction to Mass Communication
7. Information Strategies for Communicators
8. Tools for Podcasting
9. Digital Foundations: Introduction to Media Design with the Adobe Creative Cloud - Revised Edition
10. Humans R Social Media - Open Textbook Edition
11. Writing for Strategic Communication Industries
12. Open Technical Writing: An Open-Access Text for Instruction in Technical and Professional Writing
13. Writing for Electronic Media
14. Be Credible
15. Language and Culture in Context - A Primer on Intercultural Communication
16. Intercultural Communication
17. Arguing Using Critical Thinking
18. Writing Unleashed: Content and Structure - 3.0
19. Management Communication
20. OER: A Field Guide for Academic Librarians
21. The Data Journalism Handbook
22. Media, Society, Culture and You
23. Message Processing: The Science of Creating Understanding
24. Media Innovation and Entrepreneurship
25. A Guide to Technical Communications: Strategies & Applications
26. Graphic Design and Print Production Fundamentals
27. Media Studies 101
28. Small Group Communication: Forming & Sustaining Teams
29. New Media Futures
30. Communication, Affect, & Learning in the Classroom - 4th Edition

For the longest time, the evolution of cooperative social behaviour has fascinated evolutionary biologists.

The mathematical field of game theory helps shed light on how it emerges. Game theory is “the study of mathematical models of strategic interaction among rational decision-makers” (according to Wikipedia).

Game theory applies to “games” as varied as economics, politics, chess and tic-tac-toe. In each case, there are some rules, some “players” or “agents”, and a set of strategies available to them.

Each player has a concept of “utility” – a “currency” they seek to individually maximise through the strategies they play.

The currency of evolution is the concept of fitness.

That is, the chance of being represented in the next generation. Genes and traits which increase the odds of survival to reproductive age are more likely to be passed on to future generations. Therefore, they confer a greater fitness to the individual which "hosts” them.

Evolutionary game theory takes the concepts from game theory and applies them in an evolutionary context.

For a given model, it lets you ask questions about which strategy prevails, and whether certain strategies can coexist. And if so – at what frequencies?

Replicator dynamics

Evolutionary game theory plays “games” over many generations.

Each game will alter the utility (that is, fitness) of the players. The next generation is produced, with players being represented proportionally to their overall fitness.

This set up is called “replicator dynamics”. It is easy to simulate and explore different models of evolutionary games.

The classic model of evolutionary game theory is the “Hawk-Dove” game, popularised by John Maynard Smith in the 1970s.

In this game, there exists a population of animals which compete for a finite resource (for example, food). The more resources an individual wins, the greater its fitness.

Each animal can play one of two strategies:

• Hawks are aggressive, and will fight for a resource at all costs.
• Doves are passive, and will share instead of fight for a resource.

The animals are all the same kind – “hawk” and “dove” refer to their behaviour.

There are three pairwise competitions that can exist:

Hawk vs Hawk

• If two hawks compete, they will engage in a 50:50 battle to win the resource. This is a winner-takes-all scenario – the winner obtains the full value of the resource. The injured loser pays a price, and loses a certain amount of fitness.

Hawk vs Dove

• If a hawk meets a dove, the dove will back down immediately. The hawk wins the full value of the resource, and the dove walks (or, rather flies) away with nothing. But they do not pay any cost.

Dove vs Dove

• When two doves meet, they agree to share the resource evenly. No one gets hurt.

This can be modelled mathematically. Doing so allows us to understand whether these strategies can coexist (or if one of them prevails).

The math of replicator dynamics

Let V be the value of winning a contest, and C be the cost of injury in a contest.

Represent the frequency of hawks in the population as p, and the frequency of doves as 1-p.

Now, define two functions F(H) and F(D) which define the expected fitness of playing the hawk and dove strategies, respectively.

Playing as a hawk will mean engaging in a hawk-vs-hawk contest with frequency p. The expected utility of doing so is understood as the average outcome. Half the time the hawk wins V, half the time it loses C.

The rest of a hawk’s contests will be against doves. This guarantees an easy win V.

Playing as a dove will win nothing against hawks. But a dove will encounter another dove with frequency 1-p. Under this scenario, the expected utility is the shared resource, worth V/2.

Now, set F(H) equal to F(D) and solve for p.

This reveals the frequency p at which the hawk strategy confers no more or less fitness than the dove strategy.

At this frequency, there is no advantage to either strategy, so this is the equilibrium at which both strategies may coexist.

Some algebraic rearrangement gives:

Which provides the ratio of hawks-to-doves that exists at equilibrium.

Just a little more rearranging gives the equilibrium in terms of p:

Considering the properties of this expression reveals two things:

• Whenever the cost C of losing a contest is less than or equal to the value V of winning, the hawk strategy will dominate. Neither strategy can coexist.
• If the cost C is greater than the value V, the strategies will coexist in equilibrium.

Plugging in the values V=4 and C=6 shows the equilibrium occurs when 2/3 of the population play the hawk strategy.

You can test this by simulating the model in Python.

The code

In the file called bird.py:

import random

class Bird:
    def __init__(self, strategy):
        """
        Each bird has a strategy type (hawk or dove)
        And a small starting fitness
        """
        self.strategy = strategy
        self.fitness = 10

    def contest(self, opponent, v, c):
       """
       Simulate the outcomes depending on the strategies
       """

        # both hawks --> 50:50 battle

        if self.strategy == opponent.strategy == "hawk":
            if random.randint(0, 1) == 1:
                self.fitness = self.fitness + v
                opponent.fitness = opponent.fitness - c
            else:
                self.fitness = self.fitness - c
                opponent.fitness = opponent.fitness + v

        # hawk meets dove

        elif self.strategy == "hawk" != opponent.strategy:
            self.fitness = self.fitness + v
            opponent.fitness = opponent.fitness
        elif self.strategy == "dove" != opponent.strategy:
            self.fitness = self.fitness
            opponent.fitness = opponent.fitness + v

        # both doves --> share the resource

        else:
            self.fitness = self.fitness + v/2
            opponent.fitness = opponent.fitness + v/2

    def spawn(self):
        """
        Allow a small chance of mutation to flip strategy
        Otherwise, return offspring of the same type
        """

        mutation = random.randint(0, 1000) > 999
        if mutation:
            if self.strategy == "dove":
                return Bird("hawk")
            else:
                return Bird("dove")
        else:
            return Bird(self.strategy)

The next file is called simulation.py.

1. Initialise a population of all doves.
2. Define a timestep function to simulate randomised contests.
3. Draw the next generation weighted by their relative fitnesses.
4. Rinse and repeat a thousand times over, then save the output as a graph.

from bird import Bird
import random
import numpy as np
import pandas as pd
import matplotlib


def initialise():
    """
    Create a population of birds - all dove to begin
    """

    birds = []

    for _ in range(1000):
        birds.append(Bird("dove"))

    return (birds)


def timestep(birds, value, cost):
    """
    Pair up the birds, make them compete
    Then produce next generation, weighted by fitness
    """

    next_generation = []

    random.shuffle(birds)

    for _ in range(1000):

        # pair up random birds to contest
        a, b = random.sample(birds, 2)
        a.contest(b, value, cost)

    # generate next generation
    fitnesses = [bird.fitness for bird in birds]

    draw = random.choices(birds, k=1000, weights=fitnesses)
    next_generation = [bird.spawn() for bird in draw]

    return next_generation


def main():

    birds = initialise()

    rows = []

    V = 4 ; C = 6

    for _ in range(1000):

        # add the counts to a new row
        strategy = [bird.strategy for bird in birds]
        n_hawks = strategy.count("hawk")
        n_doves =  strategy.count("dove")
        row = {'n_hawks': n_hawks, 'n_doves': n_doves}
        rows.append(row)

        # run the timestep function
        birds = timestep(birds, V, C)


    # create dataframe and save output

    df = pd.DataFrame(rows)
    df.to_csv('simulation.csv')
    fig = df.plot(y=["n_hawks", "n_doves"]).get_figure()
    fig.savefig('simulation.pdf')

if __name__ == "__main__":
    main()

And voilà - here’s an example of the output for V=4 and C=6:

Exactly as the theory predicts.

Outro

The evolution of complex systems is a fascinating field of study. Understanding how natural forces and competitive pressures can shape individual-level traits to give rise to complex social behaviours has been one of the major areas of research in biological sciences in the last few decades.

The ability of relatively simple mathematical models to accurately predict outcomes of dynamic systems is also a key point to take away.

In this case, it is the existence of a feedback loop that results in the two strategies reaching an equilibrium. The advantage conferred by either strategy varies depending on how many others in the population are playing that strategy.

In other words, when more individuals play "dove", there is an advantage to playing "hawk". However, as more individuals play "hawk", the expected value of playing "dove" increases.

Finally, the availability of programming and software tools makes it possible to test theoretical predictions through simulation.

If you found this article interesting, you may also find How to Model an Epidemic With R worth checking out, too.

You can follow more of my writing at gleeson.substack.com

A research paper is often the culmination of a wide range of deep and authentic practices surrounding a topic. When writing a research paper, the author thinks critically about the problem, performs rigorous research, evaluates their processes and sources, organizes their thoughts, and then writes. These genuinely-executed practices make for a good research paper.

If you’re struggling to build a habit of reading papers (like I am) on a regular basis, I’ve tried to break down the whole process. I've talked to researchers in the field, read a bunch of papers and blogs from distinguished researchers, and jotted down some techniques that you can follow.

Let’s start off by understanding what a research paper is and what it is NOT!

What is a Research Paper?

A research paper is a dense and detailed manuscript that compiles a thorough understanding of a problem or topic. It offers a proposed solution and further research along with the conditions under which it was deduced and carried out, the efficacy of the solution and the research performed, and potential loopholes in the study.

A research paper is written not only to provide an exceptional learning opportunity but also to pave the way for further advancements in the field. These papers help other scholars germinate the thought seed that can either lead to a new world of ideas or an innovative method of solving a longstanding problem.

What Research Papers are NOT

There is a common notion that a research paper is a well-informed summary of a problem or topic written by means of other sources.

But you shouldn't mistake it for a book or an opinionated account of an individual’s interpretation of a particular topic.

Why Should You Read Research Papers?

What I find fascinating about reading a good research paper is that you can draw on a profound study of a topic and engage with the community on a new perspective to understand what can be achieved in and around that topic.

I work at the intersection of instructional design and data science. Learning is part of my day-to-day responsibilities. If the source of my education is flawed or inefficient, I’d fail at my job in the long term. This applies to many other jobs in Science with a special focus on research.

There are three important reasons to read a research paper:

1. Knowledge — Understanding the problem from the eyes of someone who has probably spent years solving it and has taken care of all the edge cases that you might not think of at the beginning.

2. Exploration — Whether you have a pinpointed agenda or not, there is a very high chance that you will stumble upon an edge case or a shortcoming that is worth following up. With persistent efforts over a considerable amount of time, you can learn to use that knowledge to make a living.

3. Research and review — One of the main reasons for writing a research paper is to further the development in the field. Researchers read papers to review them for conferences or to do a literature survey of a new field. For example, Yann LeCun’s paper on integrating domain constraints into backpropagation set the foundation of modern computer vision back in 1989. After decades of research and development work, we have come so far that we're now perfecting problems like object detection and optimizing autonomous vehicles.

Not only that, with the help of the internet, you can extrapolate all of these reasons or benefits onto multiple business models. It can be an innovative state-of-the-art product, an efficient service model, a content creator, or a dream job where you are solving problems that matter to you.

Goals for Reading a Research Paper — What Should You Read About?

The first thing to do is to figure out your motivation for reading the paper. There are two main scenarios that might lead you to read a paper:

1. Scenario 1 — You have a well-defined agenda/goal and you are deeply invested in a particular field. For example, you’re an NLP practitioner and you want to learn how GPT-4 has given us a breakthrough in NLP. This is always a nice scenario to be in as it offers clarity.

2. Scenario 2 — You want to keep abreast of the developments in a host of areas, say how a new deep learning architecture has helped us solve a 50-year old biological problem of understanding protein structures. This is often the case for beginners or for people who consume their daily dose of news from research papers (yes, they exist!).

If you’re an inquisitive beginner with no starting point in mind, start with scenario 2. Shortlist a few topics you want to read about until you find an area that you find intriguing. This will eventually lead you to scenario 1.

ML Reproducibility Challenge

In addition to these generic goals, if you need an end goal for your habit-building exercise of reading research papers, you should check out the ML reproducibility challenge.

[https://openreview.net/group?id=ML_Reproducibility_Challenge/2020](https://openreview.net/group?id=ML_Reproducibility_Challenge/2020" rel="nofollow noopener)

You’ll find top-class papers from world-class conferences that are worth diving deep into and reproducing the results.

They conduct this challenge twice a year and they have one coming up in Spring 2021. You should study the past three versions of the challenge, and I’ll write a detailed post on what to expect, how to prepare, and so on.

Now you must be wondering – how can you find the right paper to read?

How to Find the Right Paper to Read

In order to get some ideas around this, I reached out to my friend, Anurag Ghosh who is a researcher at Microsoft. Anurag has been working at the crossover of computer vision, machine learning, and systems engineering.

https://anuragxel.github.io/

Here are a few of his tips for getting started:

• Always pick an area you're interested in.

• Read a few good books or detailed blog posts on that topic and start diving deep by reading the papers referenced in those resources.

• Look for seminal papers around that topic. These are papers that report a major breakthrough in the field and offer a new method perspective with a huge potential for subsequent research in that field. Check out papers from the morning paper or CVF - test of time award/Helmholtz prize (if you're interested in computer vision).

• Check out books like Computer Vision: Algorithms and Applications by Richard Szeliski and look for the papers referenced there.

• Have and build a sense of community. Find people who share similar interests, and join groups/subreddits/discord channels where such activities are promoted.

In addition to these invaluable tips, there are a number of web applications that I’ve shortlisted that help me narrow my search for the right papers to read:

• r/MachineLearning — there are many researchers, practitioners, and engineers who share their work along with the papers they've found useful in achieving those results.

[https://www.reddit.com/r/MachineLearning/](https://www.reddit.com/r/MachineLearning/" rel="nofollow noopener)

• Arxiv Sanity Preserver — built by Andrej Karpathy to accelerate research. It is a repository of 142,846 papers from computer science, machine learning, systems, AI, Stats, CV, and so on. It also offers a bunch of filters, powerful search functionality, and a discussion forum to make for a super useful research platform.

• Google Research — the research teams at Google are working on problems that have an impact on our everyday lives. They share their publications for individuals and teams to learn from, contribute to, and expedite research. They also have a Google AI blog that you can check out.

How to Read a Research Paper

After you have stocked your to-read list, then comes the process of reading these papers. Remember that NOT every paper is useful to read and we need a mechanism that can help us quickly screen papers that are worth reading.

To tackle this challenge, you can use this Three-Pass Approach by S. Keshav. This approach proposes that you read the paper in three passes instead of starting from the beginning and diving in deep until the end.

The three pass approach

1. The first pass — is a quick scan to capture a high-level view of the paper. Read the title, abstract, and introduction carefully followed by the headings of the sections and subsections and lastly the conclusion. It should take you no more than 5–10 mins to figure out if you want to move to the second pass.

2. The second pass — is a more focused read without checking for the technical proofs. You take down all the crucial notes, underline the key points in the margins. Carefully study the figures, diagrams, and illustrations. Review the graphs, mark relevant unread references for further reading. This helps you understand the background of the paper.

3. The third pass — reaching this pass denotes that you’ve found a paper that you want to deeply understand or review. The key to the third pass is to reproduce the results of the paper. Check it for all the assumptions and jot down all the variations in your re-implementation and the original results. Make a note of all the ideas for future analysis. It should take 5–6 hours for beginners and 1–2 hours for experienced readers.

Tools and Software to Keep Track of Your Pipeline of Papers

If you’re sincere about reading research papers, your list of papers will soon grow into an overwhelming stack that is hard to keep track of. Fortunately, we have software that can help us set up a mechanism to manage our research.

Here are a bunch of them that you can use:

• Mendeley [not free] — you can add papers directly to your library from your browser, import documents, generate references and citations, collaborate with fellow researchers, and access your library from anywhere. This is mostly used by experienced researchers.

https://www.mendeley.com/?interaction_required=true

• Zotero [free & open source] — Along the same lines as Mendeley but free of cost. You can make use of all the features but with limited storage space.

https://www.zotero.org/

• Notion — this is great if you are just starting out and want to use something lightweight with the option to organize your papers, jot down notes, and manage everything in one workspace. It might not stand anywhere in comparison with the above tools but I personally feel comfortable using Notion and I have created this board to keep track of my progress for now that you can duplicate:

⚠️ Symptoms of Reading a Research Paper

Reading a research paper can turn out to be frustrating, challenging, and time-consuming especially when you’re a beginner. You might face the following common symptoms:

• You might start feeling dumb for not understanding a thing a paper says.

• Finding yourself pushing too hard to understand the math behind those proofs.

• Beating your head against the wall to wrap it around the number of acronyms used in the paper. Just kidding, you’ll have to look up those acronyms every now and then.

• Being stuck on one paragraph for more than an hour.

Here’s a complete list of emotions that you might undergo as explained by Adam Ruben in this article.

Key Takeaways

We should be all set to dive right in. Here’s a quick summary of what we have covered here:

• A research paper is an in-depth study that offers an detailed explanation of a topic or problem along with the research process, proofs, explained results, and ideas for future work.

• Read research papers to develop a deep understanding of a topic/problem. Then you can either review papers as part of being a researcher, explore the domain and the kind of problems to build a solution or startup around it, or you can simply read them to keep abreast of the developments in your domain of interest.

• If you’re a beginner, start with exploration to soon find your path to goal-oriented research.

• In order to find good papers to read, you can use websites like arxiv-sanity, google research, and subreddits like r/MachineLearning.

• Reading approach — Use the 3-pass method to find a paper.

• Keep track of your research, notes, developments by using tools like Zotero/Notion.

• This can get overwhelming in no time. Make sure you start off easy and increment your load progressively.

Remember: Art is not a single method or step done over a weekend but a process of accomplishing remarkable results over time.

You can also watch the video on this topic on my YouTube channel:

Feel free to respond to this blog or comment on the video if you have some tips, questions, or thoughts!

If this tutorial was helpful, you should check out my data science and machine learning courses on Wiplane Academy. They are comprehensive yet compact and helps you build a solid foundation of work to showcase.

Being a computer scientist with an interest in evolution and biological processes, the topic of genetic algorithms, and more broadly, evolutionary computation is to me what a candy shop is to a 5-year-old: Heaven. The mere possibility of being able to merge two of my interests in such a seamless manner has been extremely exhilarating, and it would be wrong for me to keep this knowledge and excitement all to myself.

So in an attempt to test out some of my learnings thus far, and share my findings with the rest of the world, I have decided to put together a series of articles on this topic.

In this post, I will provide a brief introduction to genetic algorithms and explain how they imitate the same natural processes that have been taking place on Earth for billions of years.

Life on Earth

Over the past 3.5 billion years, mother nature, father time, evolution and natural selection have collaborated together to produce all of the specialized forms of life that we see on earth today: like the carnivorous Venus Flytrap plant; the ocean-dwelling Atlantic Flying Fish; echolocation-using bats; long-necked giraffes; super-quick cheetahs, dancing Honeybees; and of course, yours truly, the street smart Homo sapiens.

The Venus Flytrap is a carnivorous plant that primarily feasts on insects and arachnids.

Some bats use echolocation to navigate and hunt prey and contrary to popular belief, bats are actually not blind; a species of bats known as The Flying Foxes actually have better eyesight than humans.

Flying Fish cannot fly in the same way that birds do, however, these fish can make powerful, self-propelled leaps out of the water where their long wing-like fins enable them to glide for considerable distances above the water’s surface.

Needless to say, life on Earth is one of, if not the most successful experiments ever run in our universe; and judging from the impressive outcomes of this experiment, it is clear that evolution is clearly onto something.

Recently, we humans — just one of the many end products of this process — realized that we could also take advantage of this ingenious approach to progressive problem solving, and since the 1950s, computer scientist, geneticists, mathematicians, and biologist, have attempted to mimic these biological processes through the implementation of computer simulations. With the aim of producing optimal solutions for difficult, non-trivial problems, in an efficient manner.

The blind watchmaker

One of the first books I came across that sparked my interest in the field of evolutionary biology was The Blind Watchmaker, by Richard Dawkins. In this book, Richard Dawkins explains how complex mechanisms like echolocation (a process that bats use to navigate, hunt and forage, also known as bio-sonar), complex structures like spiderwebs (which spiders use to attract and catch their prey), and complex instruments like the human eye (those two spherical objects that you are currently using to read this article) are simply the result of thousands, if not millions of years of evolution and adaptation.

_The progressive evolution of the human eye. What started off as simple photosensitive cells, evolved into a complex instrument that we often take completely for granted. The first animals with anything resembling an eye lived about 550 million years ago. And, according to one [scientist’s](https://www.pbs.org/wgbh/evolution/library/01/1/l_011_01.html" rel="noopener" target="blank" title=") calculations, it would only take 364,000 years for a camera-like eye to evolve from a light-sensitive patch.

Even though these marvels of nature give the impression that they were built with a purpose from the get-go (i.e by a conscious ‘maker’), they are actually just a result of iterations upon iterations of trial and error, bundled up with ever-changing selection pressure (i.e a change in climate, habitat, or the behaviour and capabilities of predators or prey). So while they may look and behave like the outcome of precise, forward-thinking engineering, they are actually the result of a completely blind process, a process that does not know beforehand what the perfect ‘solution’ would be.

What are genetic algorithms and why do we need them?

Genetic algorithms are a technique used to generate high-quality solutions to optimization and search problems, which are based on fundamental biological processes. These algorithms are used in situations where the possible range of solutions is very large, and where the more basic approaches to problem-solving like exhaustive search/brute force would consume too much time and effort.

The traveling salesman problem asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization.

We can use genetic algorithms to provide high-quality solutions to this problem, at a much lower cost than the more primitive problem-solving techniques, like exhaustive search, which would require you to permute through all possible solutions.

How do genetic algorithms work?

An algorithm works by iterating through a number of steps, up until it reaches a predefined termination point. Each iteration of the genetic algorithm produces a new generation of possible solutions, which, in theory, should be an improvement on the previous generation.

The steps are as follows:

1. Create an initial population of N possible solutions (the primordial soup)

The first step of the algorithm is to create an initial group of solutions that serve as the base solutions in generation 0. Each solution in this initial population will carry a set of chromosomes, which are made up of a collection of genes, where each gene is assigned to one of the possible variables of the problem. It is important that the solutions in the initial population are created with randomly assigned genes, in order to have a high degree of genetic variation.

2. Rank the solutions of the population by fitness (survival of the fittest, part 1).

In this step, the algorithm needs to be able to determine what makes one solution more ‘fit’ than another solution. This is determined by the fitness function. The aim of the fitness function is to evaluate the genetic viability of the solutions within the population, placing those with the most viable, favorable & superior genetic traits at the top of the list.

In the traveling salesman problem, the fitness function could be a calculation of the total distance traveled by the solution. Where a shorter distance equates to higher fitness.

3. Cull the weaker solutions (survival of the fittest, part 2)

In this step, the algorithm removes the less fit solutions from the population. The ‘fittest’ does not necessarily mean the strongest, the fastest or the fiercest, as humans usually tend to assume. Survival of the fittest simply means that the better equipped an organism is to survive in its environment, the more likely it is to live long enough to reproduce and spread its genes onto the next generation.

Steps 3 and 4 are collectively known as selection.

4. Breed the stronger solutions (survival of the fittest, part 3)

The remaining solutions are then paired with each other in order to mate and reproduce offspring. During this process, in its most basic form, each parent will contribute a % of their genes (in nature it is a 50/50 split) to each of their offspring, where P1(G)% +P2(G)% = 100%. The process of determining which of the parents’ genes will be inherited by the offspring is known as crossover.

5. Mutate the genes of the offspring (mutation)

The offspring will contain a percentage of the ‘mother’s’ genes, and a percentage of the ‘fathers’ genes and occasionally there will be a ‘mutation’ of one or more of these genes. A mutation is essentially a genetic abnormality, a copying error which causes one or more of the offspring’s genes to differ from the genes it inherited from its parents. In genetic algorithms, in some cases a mutation will increase the fitness of the offspring, in other cases, it will reduce it.

It is important to note that there does not need to be a mutation with each offspring, the required mutation frequency can also be a parameter of the algorithm.

In genetic algorithms, selection, crossover, and mutation are known as genetic operators.

6. Termination

Steps 2 to 5 will be repeated up until a predefined termination point. This termination point can be one of the following:

1. Maximum time/resource allocation reached.
2. Fixed number of generations have passed.
3. The fitness of the dominant solution cannot be surpassed by any future generations.

Solution convergence

1. Global optimum

In the ideal situation, the fittest solution will have the highest fitness value possible, i.e it will be the optimal solution, meaning that there will be no need to continue with the algorithm and produce further generations.

2. Local optimum

In some cases, if the parameters of the algorithm are not reasonable, the population may tend towards a premature convergence upon a less optimal solution, which is not the global optimum that we are after, but rather a local one. Once here, continuing the algorithm and producing further generations may be futile.

Global optimum vs local optimum

What would happen if there were no mutations?

On first glance, mutations may seem like an unnecessary, irrelevant part of the process. But without this fundamental aspect of randomness, evolution by natural selection would be completely restricted to the genetic variety set by the initial population, and there would be no new traits introduced into the population after that. This would severely hinder nature’s problem-solving capabilities, and life on earth would not be able to ‘adapt’ to its environment, at least not physically.

If this was the case in our genetic algorithm, at some point in our simulation, the future generations of the population would not be able to explore part of the solution space that their predecessors did not explore. A simulation without any mutations would severely restrict the genetic variation within the population, and in most cases — depending on the initial population — prevent us from ever reaching a global optimum.

Without mutations, we wouldn’t have mutants, and without mutants, we wouldn’t have the X-men franchise.

What would happen if the population size was not large enough?

I was recently at the Jukani Wildlife Sanctuary in Plettenberg, where I had the privilege of meeting a white tiger. He was a truly majestic animal. He was large, he looked ferocious, and, he was also 80% blind and getting progressively worse as the years went by.

Why was he blind? Because he is a product of generations of inbreeding. These white tigers are only produced when two tigers that carry a recessive gene controlling coat color are bred together. Thus, in order to ensure the continuation of these tigers in captivity, people have been breeding these tigers within a very limited population in order to either show them off at circuses, parade them at zoos, or keep them as household pets.

But one of the negative effects of inbreeding is that you severely limit the genetic variation within the species, which progressively increases the chances that harmful recessive traits will be passed onto the offspring.

The white tiger that I met at the Jukani Wildlife Sanctuary in April 2019. He looks majestic, but he is suffering.

Even in the wild, inbreeding can still be a massive problem. Over the past few decades, the rhino population in Southern Africa has been significantly impacted due to poaching, and if the population size reaches a low enough number it would mean that maintaining the genetic diversity of these threatened rhino species would be extremely difficult. So even if poaching doesn’t completely lead them to extinction, inbreeding could.

_Photo by [Unsplash](https://unsplash.com/photos/xtvo0ffGKlI?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText" rel="noopener" target="_blank" title="">redcharlie on <a href="https://unsplash.com/search/photos/black-rhino?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText" rel="noopener" target="blank" title=").

Of course, humans are no strangers to inbreeding. One famous result of continuous inbreeding within our own species is Charles (Carlos) the II of Spain.

“The Habsburg King Carlos II of Spain was sadly degenerated with an enormous misshapen head. His Habsburg jaw stood so much out that his two rows of teeth could not meet; he was unable to chew. His tongue was so large that he was barely able to speak. His intellect was similarly disabled.”

The Habsburg King Charles II of Spain. His father was his mother’s uncle, making Charles their son, great-nephew and first-cousin respectively.

‘Inbreeding’ in our genetic algorithm, essentially means the breeding of solutions that have a very similar genetic makeup, which, thankfully, in this case, would not result in offspring with a predisposition to any physical abnormalities. But if the population is very small and if all of the solutions share a very similar genetic makeup then the fitness of the future generations of the population will be severely restricted. Meaning that it could take much longer to converge upon a globally optimal solution if we even get there at all.

Inbreeding is not always a bad thing, it just depends on which stage of the simulation you are in. In very advanced stages of the simulation, as the population converges towards a global/local optima, it is obviously very hard to avoid inbreeding, because, in some cases, many of the dominant solutions will be very similar to each other, and thus, will share a lot of the same genetic traits.

Wrapping up

Alright, that should cover the basics. If you have any questions, requests, or genetic mutations to contribute, please leave a comment below.

In the next post, we will delve into some code as we look at how each of the genetic operators outlined above plays out in the world of programming. I used the Ruby programming language for the software simulation that I worked on, and in it, I show how in only a few generations, a genetic algorithm can produce a predefined word or phrase from an initial collection of complete and utter gibberish. All of the code will be hosted on Github.

Getting that rejection call or email is not pleasant. You feel disappointed, sad, confused, or teary-eyed. It is especially hard after getting so many no’s, or when you know that you are objectively an excellent candidate for the job. You start doubting yourself and wondering what you are missing.

While there is always room for improvement from your end, there is always room for mistakes from the other end. Those mistakes could be the worst ones of their careers and the biggest opportunities of yours. Treat each rejection as what it is — possibly the best thing that ever happened to you.

When doubt starts getting to your head because you received many rejections, remember that some of the greatest scientists and entrepreneurs were rejected many times, too. Those rejections have led to much better outcomes. Here are some of the rejection stories that inspire me to keep going in the face of rejections.

Albert Einstein

After graduating with a degree in mathematics and physics in 1900, Albert Einstein could not find anybody to hire him. He got rejected from all the schools and colleges to which he applied for a teaching or a research post.

He was struggling so much to find a job that he thought about switching fields and selling insurance! His father wrote letters to his friends, without telling Einstein, asking if they could get a job for his son, with no success.

After almost two years of unemployment, the desperate Einstein moved to Bern — the Swiss capital — where the father of one of his friends got him a job as a junior patent examiner. He worked there until 1909.

Einstein used to finish his tasks quickly and use the rest of his time to work on scientific research that interested him. During that time — specifically 1905 — he published four of the most important scientific papers ever published. These papers laid the foundation of modern physics in space, time, mass and, energy.

Srinivasa Ramanujan

Despite living in poverty for most of his life, receiving little formal education, and passing away at the age of 32, Srinivasa Ramanujan contributed substantially to the field of mathematics.

Ramanujan was able to get a scholarship to attend college. However, his strong interest in mathematics distracted him, thus he failed other subjects and was dropped from the scholarship. He enrolled in another college later and failed other subjects again.

With no college degree, he pursued his mathematical research independently. He lived in poverty and was going door-to-door looking for a clerical job. He would show prospective employers his work and send letters to mathematicians and colleges, detailing advanced theorems that he came up with.

Some didn’t respond to him, some thought he was a fraud, and some were impressed by the work he presented but doubted it was his. There were others, however, who gave him letters of introduction to other notable mathematicians.

His break came as a reply and a sponsorship from G. Hardy — a mathematician at Cambridge University — who recognized the work of a genius. Ramanujan traveled to the UK to work with Hardy, and become one of the youngest Fellows of the Royal Society in history, at the age of 31.

Jack Ma

Jack Ma, the founder of Alibaba and a global business leader, had his fair share of rejections. After graduating college from his home city of Hangzhou, China, he applied for 30 jobs and got rejected from all of them. He applied to be a police officer. Out of five applicants, he was the only one rejected.

He was even rejected by KFC. When they came to his home city, he tried to get a job with them. Out of 24 applicants, he was the only one rejected, he stated.

Later on, the rejections did not stop! Ma tried to get into Harvard Business School ten times, and got rejected every time. When he came to the USA in 2001 to raise $5 million investment, he got rejected. “…we [will] come back raising a little bit more,” he said.

Ma attributes his resilience and success as entrepreneur in part to the rejections he encountered all the way.

Brian Acton

Brian Acton, co-founder of WhatsApp, got his “best thing happened to me” rejections as well. In 2009, Acton —a software engineer with years of experience at Yahoo and Apple —got rejected by Twitter, then Facebook.

As no other company he aspired to join would hire him, he took the entrepreneurship route and started WhatsApp with Jan Koum — another Yahoo alum.

Five years later, the cloud-based messaging company co-founded by Acton changed how people text around the world. The company who rejected him earlier — Facebook — wanted him. This time, they had to pay $19 billion to acquire his company and hire him back.

Brian Chesky

In 2008, Brian Chesky, co-founder and CEO of Airbnb, was a “nobody” entrepreneur looking for someone to believe in him, his small team, and their idea.

Chesky and his team were looking for $150,000 investment for 10% of Airbnb. One of his friends introduced him to seven potential investors. Five of them rejected him, and the other two didn’t bother to even reply to him.

Ten years later, in 2018, Airbnb is the largest hotel company in the world. Rejecting Chesky’s 10% offer turned to be a $3 billion mistake for those investors now that Airbnb is valued at $30 billion.

Kevin Systrom

Systrom, the co-founder of Instagram, joined Google right after graduating Stanford.

He worked with Salar Kamangar — a senior Google executive— who was impressed by Systrom, and wanted to transfer him to Googles’s Associate Product Manager (APM) program.

The APM program is an elite rotational program at Google where a select few are chosen and given vital roles in real-impact projects.

Systrom was rejected because the program only accepted candidates with a computer science degree. This occurred despite Salar Kamangar’s efforts to convince his fellow executives to accept Systrom who “is a brilliant self-taught programmer with a history of working closely with engineers to ship products”.

Frustrated by the rejection, Kevin left Google to later co-found Instagram in 2010 and sell it to Facebook for $1 billion two years later.

The lesson

While rejection is a setback in the short term, it is a necessary step to potential significant outcomes in the long term that are unlikely to happen without it.

We have a choice. We can choose to get depressed over the rejections we receive because “we are not good”. Or we can choose to have faith that our future days want the superiority for us by getting in the way of inferiority. I choose the latter and I trust you do too!

Sources

[1] Einstein: Wikipedia, The Extraordinary Genius of Albert Einstein.

[2]Srinivasa Ramanujan: Wikipedia, Who Was Ramanujan?

[3] Jack Ma: Wikipedia, Rejection — Jack Ma.

[4] Brian Acton: Wikipedia, Forbes.

[5] Brain Chesky: Wikipedia , Brian Chesky’s Medium

[6] Kevin Systrom: Wikipedia, How Google Works

How an esoteric theorem gives important clues about the power of Artificial Neural Networks

Nowadays, artificial intelligence is present in almost every part of our lives. Smartphones, social media feeds, recommendation engines, online ad networks, and navigation tools are examples of AI-based applications that affect us on a daily basis.

Deep learning has been systematically improving the state of the art in areas such as speech recognition, autonomous driving, machine translation, and visual object recognition. However, the reasons why deep learning works so spectacularly well are not yet fully understood.

Hints from Mathematics

Paul Dirac, one of the fathers of quantum mechanics and arguably the greatest English physicist since Sir Isaac Newton, once remarked that progress in physics using the “method of mathematical reason” would

“…enable[s] one to infer results about experiments that have not been performed. There is no logical reason why the […] method should be possible at all, but one has found in practice that it does work and meets with reasonable success. This must be ascribed to some mathematical quality in Nature, a quality which the casual observer of Nature would not suspect, but which nevertheless plays an important role in Nature’s scheme.”

— Paul Dirac, 1939

Portrait of Paul Dirac is at the peak of his powers (Wikimedia Commons).

There are many examples in history where purely abstract mathematical concepts eventually led to powerful applications way beyond the context in which they were developed. This article is about one of those examples.

Though I’ve been working with machine learning for a few years now, I’m a theoretical physicist by training, and I have a soft spot for pure mathematics. Lately, I have been particularly interested in the connections between deep learning, pure mathematics, and physics.

This article provides examples of powerful techniques from a branch of mathematics called mathematical analysis. My goal is to use rigorous mathematical results to try to “justify”, at least in some respects, why deep learning methods work so surprisingly well.

_Abstract representation of a neural network ([source](https://www.shutterstock.com/g/ktsdesign" rel="noopener" target="blank" title=")).

A Beautiful Theorem

In this section, I will argue that one of the reasons why artificial neural networks are so powerful is intimately related to the mathematical form of the output of its neurons.

_A manuscript by Albert Einstein ([source](http://www.alberteinstein.info/manuscripts.html" rel="noopener" target="blank" title=")).

I will justify this bold claim using a celebrated theorem originally proved by two Russian mathematicians in the late 50s, the so-called Kolmogorov-Arnold representation theorem.

The mathematicians Andrei Kolmogorov (left) and Vladimir Arnold (right).

Hilbert’s 13th problem

In 1900, David Hilbert, one of the most influential mathematicians of the 20th century, presented a famous collection of problems that effectively set the course of the 20th-century mathematics research.

The Kolmogorov–Arnold representation theorem is related to one of the celebrated Hilbert problems, all of which hugely influenced 20th-century mathematics.

Closing in on the connection with neural networks

A generalization of one of these problems, the 13th problem specifically, considers the possibility that a function of n variables can be expressed as a combination of sums and compositions of just two functions of a single variable which are denoted by Φ and ϕ.

More concretely:

Kolmogorov-Arnold representation theorem

Here, η and the λs are real numbers. It should be noted that these two univariate functions are Φ and ϕ can have a highly complicated (fractal) structure.

Three articles, by Kolmogorov (1957), Arnold (1958) and Sprecher (1965) provided a proof that there must exist such representation. This result is rather unexpected since according to it, the bewildering complexity of multivariate functions can be “translated” into trivial operations of univariate functions, such as additions and function compositions.

Now what?

If you got this far (and I would be thrilled if you did), you are probably wondering: how could an esoteric theorem from the 50s and 60s be even remotely related to cutting-edge algorithms such as artificial neural networks?

A Quick Reminder of Neural Networks Activations

The expressions computed at each node of a neural network are compositions of other functions, in this case, the so-called activation functions. The degree of complexity of such compositions depends on the depth of the hidden layer containing the node. For example, a node in the second hidden layer performs the following computation:

Computation performed by the k-th hidden unit in the second hidden layer.

Where the _w_s are the weights, and the _b_s are the biases. The similarity with the multivariate function f shown a few paragraphs above is evident!

Let us quickly write down a function in Python only for forward-propagation which outputs the calculations performed by the neurons. The code for the function below has the following steps:

• First line: the first activation function ϕ acts on the first linear step given by:

x0.dot(w1) + b1

where x0 is the input vector.

• Second line: the second activation function acts on the second linear step

y1.dot(w2) + b2

• Third line: a softmax function is used in the final layer of the neural network, acting on the third linear step

y2.dot(w3) + b3

The full function is:

def forward_propagation(w1, b1, w2, b2, w3, b3, x0):        y1 = phi(x0.dot(w1) + b1)    y2 = phi(y1.dot(w2) + b2)    y3 = softmax(y2.dot(w3) + b3)        return y1, y2, y3

To compare this with our expression above we write:

y2 = phi(phi(x0.dot(w1) + b1).dot(w2) + b2)

The correspondence can be made more clear:

A Connection Between Two Worlds

We, therefore, conclude that the result proved by Kolmogorov, Arnold, and Sprecher implies that neural networks, whose output is nothing but the repeated composition of functions, are extremely powerful objects, which can represent any multivariate function or equivalently almost any process in nature. This partly explains why neural networks work so well in so many fields. In other words, the generalization power of neural networks is, at least in part, a consequence of the Kolmogorov-Arnold representation theorem.

As pointed out by Giuseppe Carleo, the generalization power of forming functions of functions of functions ad nauseam was, in a way, “discovered independently also by nature” since neural networks, which work as shown above doing precisely that, are a simplified way to describe how our brains work.

Thanks a lot for reading! Constructive criticism and feedback are always welcome!

My Github and my website www.marcotavora.me have some other interesting stuff both about data science and physics.

There is a lot more to come, stay tuned!

Laplace, Bayes, and machine learning today

It may not be a question that you were worrying much about. After all, it appears to happen every day without fail.

But what is the probability the sun will rise tomorrow?

Believe it or not, this question was given consideration by one of mathematics’ all-time greats Pierre-Simon Laplace in his pioneering work of 1814, “Essai philosophique sur les probabilités”.

Fundamentally, Laplace’s treatment of the question was intended to illustrate a more general concept. It was not a serious attempt to estimate whether the sun will, in fact, rise.

In his essay, Laplace describes a framework for probabilistic reasoning that today we recognise as Bayesian.

The Bayesian approach forms a keystone in many modern machine learning algorithms. But the computational power required to make use of these methods has only been available since the latter half of the 20th Century.

(So far, it appears current state-of-the-art AI is keeping quiet on the issue of tomorrow’s sunrise.)

Laplace’s ideas are still relevant today, despite being developed more than two centuries ago. This article will review some of these ideas, and show how they are used in modern applications, perhaps envisaged by Laplace’s contemporaries.

Pierre-Simon Laplace

Born in the small Normandy commune of Beaumont-en-Auge in 1749, Pierre-Simon Laplace was initially marked out to become a theologian.

However, while studying at the University of Caen, he discovered a brilliant aptitude for mathematics. He transferred to Paris, where he impressed the great mathematician and physicist Jean le Rond d’Alembert.

At the age of 24, Laplace was elected to the prestigious Académie des Sciences.

Laplace was an astonishingly prolific scientist and mathematician. Amongst his many contributions, his work on probability, planetary motion, and mathematical physics stand out. He counted figures such as Antoine Lavoisier, Jean d’Alembert, Siméon Poisson, and even Napoleon Bonaparte, as his collaborators, advisers, and students.

Laplace’s “Essai philosophique sur les probabilités” was based upon a lecture he delivered in 1795. It provided a general overview of ideas contained within his work “Théorie analytique des probabilités”, published two years earlier in 1812.

In “Essai philosophique”, Laplace provides ten principles of probability. The first few cover basic definitions, and how to calculate probabilities relating to independent and dependent events.

Principles eight, nine, and ten concern the application of probability to what we might describe today as cost-benefit analysis.

The sixth is an important generalization of Thomas Bayes’ eponymous theorem of 1763.

It states that, for a given event, the likelihood of each possible cause is found by multiplying the prior probability of that cause by a fraction.

This fraction is the probability of the event arising from that particular cause, divided by the probability of the event occurring by any cause.

Probability of A-given-B equals probability of A times probability of B-given-A, divided by probability of B

This theorem’s influence within machine learning cannot be overstated.

The seventh principle is the one that has caused the most controversy since its publication. However, the actual wording is innocuous enough.

Rather, it is Laplace’s choice of discussing the probability of the sun rising the next day by way of illustrative example that has in turn drawn derision and objection over the following two centuries.

The rule of succession is still used today under various guises, and sometimes in the form Laplace originally described.

In fact, the rule of succession represents an important early step in applying Bayesian thinking to systems for which we have very limited data and little or no prior knowledge. This is a starting point often faced in modern machine learning problems.

Laplace’s rule of succession

The seventh principle of probability given in Laplace’s “Essai philosophique” is, in essence, straightforward.

It states that the probability of a given event occurring is found by summing the probability of each of its potential causes multiplied by the probability of that cause giving rise to the event in question.

Laplace then proceeds to outline an example based upon drawing balls from urns. So far, so good. Nothing contentious yet.

However, he then describes how to proceed with estimating the probability of an event occurring in situations where we have limited (or indeed no) prior knowledge about what that probability might be.

“On trouve ainsi qu’un événement étant arrivé de suite un nombre quelconque de fois , la probabilité qu’il arrivera encore la fois suivante est égale à ce nombre augmenté de l’unité, divisé par le même nombre augmenté de deux unités.”

Which translates in English: “So, one finds for a event which has occurred any number of times until now, the probability it will occur again the next time is equal to this number increased by one, divided by the same number increased by two”.

Or, in math notation:

That is, given s successes out of n trials, the probability of success on the next trial is approximately (s+1)/(n+2).

To make his point, Laplace doesn’t hold back:

“… par exemple, remonter la plus ancienne époque de l’histoire à cinq mille ans, ou à 1,826,213 jours, et le soleil s’étant levé constamment dans cet intervalle, à chaque révolution de vingtquatre heures, il y a 1,826,214 à parier contre un qu’il se lèvera encore demain”

Which translates as: “…for example, given the sun has risen every day for the last 5000 years — or 1,826,213 days — the probability it will rise tomorrow is 1,826,214 / 1,826,215”.

At 99.9%, that’s a pretty certain bet. And it only becomes more certain each day the sun continues to rise.

Yet Laplace acknowledges that, for someone who understands the mechanism by which the sun rises and sees no reason why it should cease to function, even this probability is unreasonably low.

And it turns out that this qualification is perhaps just as important as the actual rule itself. After all, it hints at the fact that our prior knowledge of a system is encoded in the assumptions we make when assigning probabilities to each of its potential outcomes.

This is true in machine learning today, especially when we try learning from limited or incomplete training data.

But what is the rationale behind Laplace’s rule of succession, and how does it live on in some of today’s most popular machine learning algorithms?

Nothing is impossible?

To better understand the significance of Laplace’s rule, we need to consider what it means to have very little prior knowledge about a system.

Say you have one of Laplace’s urns, which you know to contain at least one red ball. You know nothing else about the contents of the urn “system”. Perhaps it contains many different colors, perhaps it only contains that one red ball.

Draw one ball from the urn. You know the probability that it will be red is greater than zero, and either less than or equal to one.

But, as you don’t know whether the urn contains other colors, you cannot say the probability of drawing red certainly equals one. You simply cannot rule out any other possibility.

So, how do you estimate the probability of drawing a red ball from the urn?

Well, according to Laplace’s rule of succession, you can model drawing a ball from the urn as a Bernoulli trial with two possible outcomes: “red” and “not-red”.

Before we’ve drawn anything from the urn, we’ve already allowed for two potential outcomes to exist. In so doing, we’ve effectively “pseudo-counted” two imaginary draws from the urn, observing each outcome once.

This gives each outcome (“red” and “not-red”) a probability of 1/2.

As the number of draws from the urn increases, the effect of these pseudo-counts becomes less and less important. If the first ball drawn is red, you update the probability of the next one being red to (1+1)/(1+2) = 2/3.

If the next ball is red, the probability updates to 3/4. If you keep drawing red, the probability reaches ever closer to 1.

In today’s language, probability concerns a sample space. This is a mathematical set of all possible outcomes for a given “experiment” (a process that selects one of the outcomes).

Probability was put on a formal axiomatic basis by Andrey Kolmogorov in the 1930s. Kolmogorov’s axioms make it easy to prove that a sample space must contain at least one element.

Kolmogorov also defines probability as a measure that returns a real valued number between zero and one for all elements of the sample space.

Naturally, probability makes a useful way to model real world systems, especially when you assume complete knowledge about the contents of the sample space.

But when we don’t understand the system at hand, we don’t know the sample space — apart from that it must contain at least one element. This is a common starting point in many machine learning contexts. We have to learn the contents of the sample space as we go.

Therefore, we ought to allow the sample space to contain at least one extra, catch-all element — or, if you like, the “unknown unknown”. Laplace’s rule of succession tells us to assign the “unknown unknown” a probability of 1/n_+_2, after n repeated observations of known events.

Although in many cases it is convenient to ignore the possibility of unknown unknowns, there are epistemological grounds for always allowing such eventualities to exist.

One such argument is known as Cromwell’s Rule, coined by the late Dennis Lindley. Quoting the 17th century’s Oliver Cromwell:

“I beseech you, in the bowels of Christ, think it possible that you may be mistaken”

This rather dramatic statement asks us to allow a remote possibility for the unexpected to occur. In the language of Bayesian probability, this amounts to requiring us to always consider a non-zero prior.

Because if your prior probability is set to zero, no amount of evidence will ever convince you otherwise. After all, even the strongest evidence to the contrary will still yield a posterior probability of zero, when multiplied by zero.

Objections, and a defence of Laplace

It may come as little surprise to learn that Laplace’s sunrise example attracted much criticism from his contemporaries.

People objected to the perceived simplicity — naivety, even — of Laplace’s assumptions. The idea that there was a 1/1,826,215 probability the sun would not rise the following day seemed absurd.

It is tempting to believe that, given a large number of trials, a non-zero probability event must happen. And therefore, observing so many consecutive sunrises without a single failure surely implies Laplace’s estimate is an overestimate?

For example, you might expect that after a million trials, you’d have observed a one-in-a-million event — almost guaranteed by definition! What’s the probability of doing otherwise?

Well, you wouldn’t be astonished if you tossed a fair coin twice without landing heads. Nor would it be cause for concern if you rolled a die six times, and never saw the number six. These are events with probability 1/2 and 1/6 respectively, but that absolutely does not guarantee their occurrence in the first two and six trials.

A result attributed to Bernoulli back in the 17th Century finds the limit as the probability 1/n and number of trials n grow very large:

Although on average you will have observed at least one occurrence of an event with probability 1/n after n trials, there is still a greater than 1/3 chance you will not.

Likewise, if the true probability of the sun failing to rise were indeed 1/1,826,215, then we perhaps shouldn’t be so surprised such an occurrence has never been recorded in history.

And, arguably, Laplace’s qualification is too generous.

It is true that, for a person who claims to understand the mechanism by which the sun rises every day, the probability of it failing to do so must be much closer to zero.

Yet to assume an understanding of such a mechanism requires us to possess prior knowledge of the system, beyond that which we have observed. This is because such a mechanism is implicitly assumed constant — in other words, true for all time.

This assumption lets us, in a sense, “conjure up” an unlimited number of observations — on top of those we have actually observed. It’s an assumption called for by none other than Isaac Newton, at the beginning of the third book in his famous “Philosophiae Naturalis Principia Mathematica”.

Newton outlines four “Rules of Reasoning in Philosophy”. The fourth rule claims we can regard propositions derived from previous observations as “very nearly true”, until contradicted by future observations.

“In experimental philosophy we are to look upon propositions collected by general induction from phenomena as accurately or very nearly true”

Such an assumption was crucial for the scientific revolution, despite being a kick in the teeth for philosophers such as David Hume, who famously argued for the problem of induction.

It is this epistemological compromise that lets us do useful science and, in turn, invent technology. Somewhere along the line, as we see the estimated probability of the sun failing to rise diminish ever closer to zero, we allow ourselves to “round down” and claim a fully fledged scientific truth.

But all of this presumably lies beyond the scope of the point Laplace originally sought to make.

Indeed, his choice of a sunrise example is unfortunate. The rule of succession really comes into its own when applied to completely unknown “black-box” systems for which we have zero (or very few) observations.

This is because the rule of succession offers an early example of a non-informative prior.

How to assume as little as possible

Bayesian probability is a keystone concept in modern machine learning. Algorithms such as Naive Bayes classification, Expectation Maximisation, Variational Inference and Markov Chain Monte Carlo are amongst the most popular in use today.

Bayesian probability generally refers to an interpretation of probability where you update your (often subjective) belief in the light of new evidence.

Two key concepts are prior and posterior probabilities.

Posterior probabilities are those we ascribe to after updating our beliefs in the face of new evidence.

Prior probabilities (or ‘priors’) are those we hold to be true before seeing new evidence.

Data scientists are interested in how we assign prior probabilities to events in the absence of any previous knowledge at all. This is a typical starting point for many problems in machine learning and predictive analytics.

Priors can be informative, in the sense they come with “opinions” about the probability of different events. These “opinions” can be strong or weak, and are usually based on past observations or otherwise reasonable assumptions. These are invaluable in situations where we want to train our machine learning model quickly.

However, priors can also be non-informative. This means they assume as little as possible about the respective probabilities of an event. These are useful in situations where we want our machine learning model to learn from a blank state.

So we must ask: how do you measure how “informative” a prior probability distribution is?

Information theory provides an answer. This is a branch of mathematics that concerns how information is measured and communicated.

Information can be thought of in terms of certainty, or a lack thereof.

After all, in an everyday sense, the more information you have about some event, the more certain you are about its outcome. Less information equates to less certainty. This means that information theory and probability theory are inextricably linked.

Information entropy is a fundamental concept in information theory. It serves as a measure of the uncertainty inherent to a given probability distribution. A probability distribution with high entropy is one for which the outcome is more uncertain.

Perhaps intuitively, you can reason that a uniform probability distribution — a distribution for which each event is equally likely — has the highest possible entropy. For example, if you flipped a fair coin and a biased coin, which outcome would you be least certain about?

Information entropy provides a formal means of quantifying this, and if you know some calculus, you can check out the proof here.

So the uniform distribution is, in a very real sense, the least informative distribution possible. And for that reason, it makes an obvious choice for an uninformative prior.

Perhaps you’ve spotted how Laplace’s rule of succession effectively amounts to using a uniform prior? By adding one success and one failure before we’ve even observed any outcomes, we’re using a uniform probability distribution to represent our “prior” belief about the system.

Then, as we observe more and more outcomes, the weight of the evidence increasingly overpowers the prior.

Case study: Naive Bayes classification

Today, Laplace’s rule of succession is generalised to additive smoothing and pseudo-counting.

These are techniques which allow us to use non-zero probabilities for events not observed in training data. This is an essential part of how machine learning algorithms are able to generalize when faced with inputs not seen previously.

For instance, take Naive Bayes classification.

This is a simple yet effective algorithm that can classify textual and other suitably tokenized data, using Bayes’ theorem.

The algorithm is trained on a corpus of pre-classified data, in which each document consists of a set of words or “features”. The algorithm begins by estimating the probability of each feature, given a certain class.

Using Bayes’ theorem (and some very naive assumptions about feature independence), the algorithm can then approximate the relative probabilities of each class, given the features observed in a previously unseen document.

The best estimate is the class, k, which maximizes the likelihood of observing the individual features, x, within a given document

An important step in Naive Bayes classification is estimating the probability of a feature being observed within a given class. This can be done by calculating the frequency at which the feature is observed in each of that class’s records in the training data.

For instance, the word “Python” might appear in 12% of all documents classed as “programming”, compared to 1% of all documents classed as “start-up”. The word “learn” might appear in 10% of programming documents and 20% of all start-up documents.

Take the sentence “learn Python”.

Using these frequencies, we find the probability of the sentence being classed as “programming” equals 0.12 ×0.10 = 0.012, and the probability of it being classed as “start-up” is 0.01×0.20 = 0.002.

Therefore, “programming” is the more likely of these two classes.

But this frequency-based approach runs into trouble whenever we consider a feature which never occurs in a given class. This would mean it has a frequency of zero.

Naive Bayes classification requires us to multiply probabilities, but multiplying anything by zero will, of course, always yield zero.

So, what happens if a previously unseen document does contain a word never observed in a given class in the training data? That class will be deemed impossible — no matter how frequently every other word in the document occurs in that class.

Additive smoothing

An approach called additive smoothing offers a solution. Instead of allowing for zero frequencies, we add a small constant to the numerator. This prevents unseen class/feature combinations from derailing the classifier.

When this constant equals one, additive smoothing is the same as applying Laplace’s rule of succession.

As well as Naive Bayes classification, additive smoothing is used in other probabilistic machine learning contexts. Examples include problems in language modelling, neural networks, and hidden Markov models.

In mathematical terms, additive smoothing amounts to using a beta distribution as a conjugate prior for carrying out Bayesian inference with binomial and geometric distributions.

The beta distribution is a family of probability distributions defined over the interval [0,1]. It takes two shape parameters, α and β. Laplace’s rule of succession corresponds to setting α = 1 and β = 1.

As discussed above, the beta(1,1) distribution is the one for which information entropy is maximised. However, there are alternative priors for cases in which the assumption of one success and one failure are not valid.

For instance, Haldane’s prior is defined as a beta(0,0) distribution. It applies in cases when we are not even sure if we can allow for a binary outcome. Haldane’s prior places an infinite amount of “weight” on zero and one.

Jeffrey’s prior, the beta(0.5, 0.5) distribution, is another non-informative prior. It has the helpful property that it remains invariant under reparameterization. Its derivation is beyond the scope of this article, but if you are interested, check out this thread.

The legacy of ideas

Personally, I find it fascinating how some of the earliest ideas in probability and statistics have survived years of contention, and still find widespread use in modern machine learning.

It is extraordinary to realise that the influence of ideas developed more than two centuries ago is still being felt today. Machine learning and data science have gained real mainstream momentum in the last decade or so. But the foundations upon which they are built were laid long before the first computers were even close to realization.

It’s no coincidence that such ideas border on the philosophy of knowledge. This becomes especially relevant as machines become more and more intelligent. At what point might the focus shift onto our philosophy of consciousness?

Finally, what would Laplace and his contemporaries make of machine learning today? It’s tempting to suggest they’d be astounded by the progress that’s been made.

But that would probably be a disservice to their foresight. After all, the French philosopher René Descartes had written of a mechanistic philosophy back in the 17th Century. Describing a hypothetical machine:

“Je désire que vous considériez … toutes les fonctions que j’ai attribuées à cette machine, comme … la réception de la lumière, des sons, des odeurs, des goûts … l’empreinte de ces idées dans la mémoire … et enfin les mouvements extérieurs … qu’ils imitent le plus parfaitement possible ceux d’un vrai homme … considériez que ces fonctions … de la seule disposition de ses organes, ni plus ni moins que font les mouvements d’une horloge … de celle de ses contrepoids et de ses roues”

Which translates as: “I desire that you consider that all the functions I’ve attributed to this machine such as… the reception of light, sound, smell and taste… the imprint of these ideas in the memory… and finally the external movements which imitate as perfectly as possible those of a true human…Consider that these functions are only under the control of the organs, no more or less than the movements of a clock are to its counterweights and wheels”

The passage above describes a hypothetical machine capable of responding to stimuli and behaving like a “true human”. It was published in Descartes’ 1664 work “Traité de l’homme” — a full 150 years before Laplace’s “Essai philosophique sur les probabilités”.

Indeed, the 18th and early 19th Centuries saw the construction of incredibly sophisticated automata by inventors such as Pierre Jaquet-Droz and Henri Maillardet. These clockwork androids could be “programmed” to write, draw, and play music.

_Drawing produced by one of Henri Maillardet’s early 19th Century automata ([video](https://www.youtube.com/watch?v=LCNQvm61_78" rel="noopener" target="blank" title="))

So there is no doubting that Laplace and his contemporaries could conceive of the notion of an intelligent machine. And it surely would not have escaped their notice how progress made in the field of probability might be applied to machine intelligence.

Right at the beginning of “Essai philosophique”, Laplace writes of a hypothetical super-intelligence, retrospectively named “Laplace’s Demon”:

“Une intelligence qui, pour un instant donné, connaîtrait toutes les forces dont la nature est animée, et la situation respective des êtres qui la composent, si d’ailleurs elle était assez vaste pour sou- mettre ces données à l’analyse … rien ne serait incertain pour elle, et l’avenir comme le passé, serait présent à ses yeux”

Which translates as: “An intelligence, which in a given moment, knows all the forces by which nature is animated, and the respective situation of the beings which compose it, and if it were large enough to submit these data to analysis … nothing would be uncertain to it, and the future as the past, would be present in its eyes”.

Could Laplace’s Demon be realized as one of Descartes’ intelligent machines? Modern sensibilities overwhelmingly suggest no.

Yet Laplace’s premise envisaged on a smaller scale may soon become a reality, thanks in no small part to his own pioneering work in the field of probability.

Meanwhile, the sun will (probably) continue to rise.

Most kids absolutely LOVE Legos. My son has been playing with the Duplo ones, but we have since recently “upgraded” him to the normal ones. Since we didn’t have a collection of regular legos yet, we opted to just inherit someone else’s. We finally got our break when we found someone selling off their kids’ Lego collection since they were too old for them.

This is just half of the collection. Half was already sorted by colours, but these weren’t.

Since we had just gotten a payload of more than a thousand pieces, we now had to sort them by colour just to organise them. I sure wasn’t going to sort them by part or catalogue them, since that would have taken forever.

So given the insurmountable task, we then decided to get into it. We started sorting by picking up all the green bricks and collecting them in a basin for washing. Yep, this was a very old collection, so it was very dusty.

The initial plan of attack was this:

• I sort the bricks and my wife cleans them and the shelves included. Yes the deal included 3 shelves, 9 boxes, 1 Lego bag (in the photo) and 1 Lego head in addition to probably five to ten thousand pieces
• We then pack them away — easy, right?

This sounded like a good plan, until I realised that sorting by colour the way I was doing it was too slow. I was only picking up one colour at a time. I’d probably only sorted about 30 bricks and it had taken me five minutes. Imagine how long it would have taken for me to finish with the other colours like black, grey, red and blue!

So I had to rethink my plan. I was joking around with a couple of friends who then mentioned I was probably doing bubble sort, which was one of the slowest sorting algorithms our there (yes there are some other slower algorithms!). I laughed at the joke, then realised I might be able to use my computer science knowledge here — at least what’s left of it! Uni was ages ago, so I knew I’d have to improvise.

Enter horizontal scaling

I told everyone to stop what they were doing and help me sort out the bag. This meant that now there were more people sorting, so I basically scaled horizontally by adding more resources to finish the job.

As a web developer, I have seen this as a common solution to a problem with server load.

When your server is overloaded by a lot of incoming traffic, you usually have two options: vertical or horizontal scaling.

Vertical scaling means you basically add more power to your server. For example, if you’re using AWS, instead of having a t2.micro which only has 1 CPU and 1GB of RAM, you upgrade it to a t2.xlarge which has 4 CPUs and 16GB of RAM.

_[The Amazon EC2 instance types](https://aws.amazon.com/ec2/instance-types/" rel="noopener" target="blank" title=")

Horizontal scaling means you just add more resources. So, instead of upgrading your singlet2.micro instance, you add 5 more to accommodate the load.

Both have their use cases, but for this specific instance, horizontal scaling was the solution.

I mean, I wouldn’t have been able to vertically scale myself by adding more brain power, so the only choice was to horizontally scale by adding more people.

After five minutes of sorting, I noticed that we did make some sort of progress. It wasn’t enough for me though. Time was passing and I was getting tired. We needed to make it faster!

Divide and conquer algorithm

I had a think. There were three of us with a large bag full of bricks in front of us. I estimated it to be about two thousand pieces at this point. And while we had made some progress in the last five minutes, we were still looking at hours of sorting.

I have since then changed my initial technique of just looking for green blocks. Instead, I was having a quick look at which colour looked like the majority, and getting as many as I could with my hand. After putting the bricks in their appropriate colour basket, I looked at the pile again and picked the “majority” again. It usually changed, since after getting a bunch of say, reds, it would have fewer reds. The next majority would be blue or green, for example.

This was looking good. But after analysing it, I was basically looking at two thousand pieces, getting the maximum count of a colour, getting that colour and subtracting it from the pile. My processing was slow, because how do you actually get the majority without counting or estimating?

Since I was taking too much cognitive load, I was slowing down. So I stopped looking at the colour with the most bricks and just picked a random colour every time I dumped the handful of bricks I had just collected. This sped up my processing a little, but I thought we could still improve.

So, divide and conquer it was. In CS terms, this meant an algorithm that broke down a huge problem into smaller bits so they were simple enough to solve in a faster time.

Let’s say your site accepts user uploaded zip files with photos and processes them. If your server accepted the zip file, unzipped it, and processed it the minute you uploaded it, everyone else would be waiting for it to finish. Sure you can horizontally or vertically scale your server, but the wait time is unnecessary. Also, what happens when a user uploads a zip file with 100 photos in it?

You can solve this by using a divide and conquer technique instead. First off, you delegate the processing to a delayed job infrastructure like Rails’ ActiveJob. Or if you’re not using Rails, Sidekiq. Still, that job would take a long time if it was a 100 photos, and there would be the possibility of your worker dying from the workload.

One solution would be to have a job that unzips it, and then enqueues each of the photos to be processed as a separate job. Now instead of your worker having to process 100 photos by itself, it then puts 100 tiny jobs of processing single photos in the queue, which can then be picked up by other workers.

With that in mind, I made a factory line deal with my son: he had to get a handful (or two) of bricks from the bag and dump them into my corner. That meant I only had about 50 bricks to sort which was easier and faster — mainly because by this point, I knew the colour with the most bricks: grey.

The most common block colour was grey.

So what if I knew it was grey? Well, that meant that I only had to pick all the red, green, yellow, blue, black and white bricks. When I was left with grey, I dumped the remaining bricks into the grey box — that saved me one less colour to sort that I would not have been able to do on a larger scale.

An hour later …

All done! Now we just had to clean them. The initial plan was:

• Dump a box of colours into a basin.
• Wash with water and soap
• Dry

What was the problem here? I’ll give you a guess.

Still there? Okay. If we washed with water and soap, that meant we had to rinse the soap off — which meant we had to wash it twice! No way! So I decided not to add soap but just thoroughly wash with warm water.

The modified plan was:

• Dump a box of colours into a basin
• Wash with water thoroughly
• Dry

On to the next problem: drying the Legos.

Centrifugal force to the rescue!

Initially, we tried drying the pieces with a towel. It wasn’t very effective. Next was to use a hairdryer and blow hot air into the pieces. It was okay, but it still didn’t dry the pieces — we were getting hopeless and almost decided to just lay them all on the floor and let all the water evaporate.

Only, it was autumn so it wouldn’t have been hot enough. So while pondering about how to dry thousands of Lego pieces, I suddenly remembered how I dry salad leaves using a salad spinner. “I wish I could use the salad spinner,” I thought. Then it dawned on me: a salad spinner works by using centrifugal force to separate the water from the leaves. I could do the same!

I wrapped the lego pieces into a towel and secured them by turning the towel into a giant candy wrapper. I stepped on one end of the towel, pulled the other end as tight as I could and started spinning the towel.

What do you know — it actually worked! I could see the towel suddenly become wet as the water from the pieces flew out of them and into the towel. SCIENCE!

SCIENCE!

The Legos weren’t completely dry, of course, so I still had to use the hairdryer to help the remaining droplets evaporate. But that was all right — the hard part was over.

I never thought I’d use my stock CS knowledge for something like sorting Legos. In any case, it was a good and fun experience scaling horizontally, using a divide and conquer strategy, and even bringing out centrifugal force to organise my son’s newly inherited Lego collection. I don’t look forward to the day he jumbles them all up and we have to sort them again, though!

This is about AlphaGo, Google DeepMind’s Go playing AI that shook the technology world in 2016 by defeating one of the best players in the world, Lee Sedol.

Go is an ancient board game which has so many possible moves at each step that future positions are hard to predict — and therefore it requires strong intuition and abstract thinking to play. Because of this reason, it was believed that only humans could be good at playing Go. Most researchers thought that it would still take decades to build an AI which could think like that. In fact, I’m releasing this essay today because this week (March 8–15) marks the two-year anniversary of the AlphaGo vs Sedol match!

But AlphaGo didn’t stop there. 8 months later, it played 60 professional games on a Go website under disguise as a player named “Master”, and won every single game, against dozens of world champions, of course without resting between games.

Naturally this was a HUGE achievement in the field of AI and sparked worldwide discussions about whether we should be excited or worried about artificial intelligence.

Today we are going to take the original research paper published by DeepMind in the Nature journal, and break it down paragraph-by-paragraph using simple English.

After this essay, you’ll know very clearly what AlphaGo is, and how it works. I also hope that after reading this you will not believe all the news headlines made by journalists to scare you about AI, and instead feel excited about it.

Worrying about the growing achievements of AI is like worrying about the growing abilities of Microsoft Powerpoint. Yes, it will get better with time with new features being added to it, but it can’t just uncontrollably grow into some kind of Hollywood monster.

You DON’T need to know how to play Go to understand this paper. In fact, I myself have only read the first 3–4 lines in Wikipedia’s opening paragraph about it. Instead, surprisingly, I use some examples from basic Chess to explain the algorithms. You just have to know what a 2-player board game is, in which each player takes turns and there is one winner at the end. Beyond that you don’t need to know any physics or advanced math or anything.

This will make it more approachable for people who only just now started learning about machine learning or neural networks. And especially for those who don’t use English as their first language (which can make it very difficult to read such papers).

If you have NO prior knowledge of AI and neural networks, you can read the “Deep Learning” section of one of my previous essays here. After reading that, you’ll be able to get through this essay.

If you want to get a shallow understanding of Reinforcement Learning too (optional reading), you can find it here.

Here’s the original paper if you want to try reading it:

As for me: Hi I’m Aman, an AI and autonomous robots engineer. I hope that my work will save you a lot of time and effort if you were to study this on your own.

Do you speak Japanese? Ryohji Ikebe has kindly written a brief memo about this essay in Japanese, in a series of Tweets.

Let’s get started!

Abstract

As you know, the goal of this research was to train an AI program to play Go at the level of world-class professional human players.

To understand this challenge, let me first talk about something similar done for Chess. In the early 1990s, IBM came out with the Deep Blue computer which defeated the great champion Garry Kasparov in Chess. (He’s also a very cool guy, make sure to read more about him later!) How did Deep Blue play?

Well, it used a very brute force method. At each step of the game, it took a look at all the possible legal moves that could be played, and went ahead to explore each and every move to see what would happen. And it would keep exploring move after move for a while, forming a kind of HUGE decision tree of thousands of moves. And then it would come back along that tree, observing which moves seemed most likely to bring a good result. But, what do we mean by “good result”? Well, Deep Blue had many carefully designed chess strategies built into it by expert chess players to help it make better decisions — for example, how to decide whether to protect the king or get advantage somewhere else? They made a specific “evaluation algorithm” for this purpose, to compare how advantageous or disadvantageous different board positions are (IBM hard-coded expert chess strategies into this evaluation function). And finally it chooses a carefully calculated move. On the next turn, it basically goes through the whole thing again.

As you can see, this means Deep Blue thought about millions of theoretical positions before playing each move. This was not so impressive in terms of the AI software of Deep Blue, but rather in the hardware — IBM claimed it to be one of the most powerful computers available in the market at that time. It could look at 200 million board positions per second.

Now we come to Go. Just believe me that this game is much more open-ended, and if you tried the Deep Blue strategy on Go, you wouldn’t be able to play well. There would be SO MANY positions to look at at each step that it would simply be impractical for a computer to go through that hell. For example, at the opening move in Chess there are 20 possible moves. In Go the first player has 361 possible moves, and this scope of choices stays wide throughout the game.

This is what they mean by “enormous search space.” Moreover, in Go, it’s not so easy to judge how advantageous or disadvantageous a particular board position is at any specific point in the game — you kinda have to play the whole game for a while before you can determine who is winning. But let’s say you magically had a way to do both of these. And that’s where deep learning comes in!

So in this research, DeepMind used neural networks to do both of these tasks (if you have never read about neural networks yet, here’s the link again). They trained a “policy neural network” to decide which are the most sensible moves in a particular board position (so it’s like following an intuitive strategy to pick moves from any position). And they trained a “value neural network” to estimate how advantageous a particular board arrangement is for the player (or in other words, how likely you are to win the game from this position). They trained these neural networks first with human game examples (your good old ordinary supervised learning). After this the AI was able to mimic human playing to a certain degree, so it acted like a weak human player. And then to train the networks even further, they made the AI play against itself millions of times (this is the “reinforcement learning” part). With this, the AI got better because it had more practice.

With these two networks alone, DeepMind’s AI was able to play well against state-of-the-art Go playing programs that other researchers had built before. These other programs had used an already popular pre-existing game playing algorithm, called the “Monte Carlo Tree Search” (MCTS). More about this later.

But guess what, we still haven’t talked about the real deal. DeepMind’s AI isn’t just about the policy and value networks. It doesn’t use these two networks as a replacement of the Monte Carlo Tree Search. Instead, it uses the neural networks to make the MCTS algorithm work better… and it got so much better that it reached superhuman levels. THIS improved variation of MCTS is “AlphaGo”, the AI that beat Lee Sedol and went down in AI history as one of the greatest breakthroughs ever. So essentially, AlphaGo is simply an improved implementation of a very ordinary computer science algorithm. Do you understand now why AI in its current form is absolutely nothing to be scared of?

Wow, we’ve spent a lot of time on the Abstract alone.

Alright — to understand the paper from this point on, first we’ll talk about a gaming strategy called the Monte Carlo Tree Search algorithm. For now, I’ll just explain this algorithm at enough depth to make sense of this essay. But if you want to learn about it in depth, some smart people have also made excellent videos and blog posts on this:

1. A short video series from Udacity
2. Jeff Bradberry’s explanation of MCTS
3. An MCTS tutorial by Fullstack Academy

The following section is long, but easy to understand (I’ll try my best) and VERY important, so stay with me! The rest of the essay will go much quicker.

Let’s talk about the first paragraph of the essay above. Remember what I said about Deep Blue making a huge tree of millions of board positions and moves at each step of the game? You had to do simulations and look at and compare each and every possible move. As I said before, that was a simple approach and very straightforward approach — if the average software engineer had to design a game playing AI, and had all the strongest computers of the world, he or she would probably design a similar solution.

But let’s think about how do humans themselves play chess? Let’s say you’re at a particular board position in the middle of the game. By game rules, you can do a dozen different things — move this pawn here, move the queen two squares here or three squares there, and so on. But do you really make a list of all the possible moves you can make with all your pieces, and then select one move from this long list? No — you “intuitively” narrow down to a few key moves (let’s say you come up with 3 sensible moves) that you think make sense, and then you wonder what will happen in the game if you chose one of these 3 moves. You might spend 15–20 seconds considering each of these 3 moves and their future — and note that during these 15 seconds you don’t have to carefully plan out the future of each move; you can just “roll out” a few mental moves guided by your intuition without TOO much careful thought (well, a good player would think farther and more deeply than an average player). This is because you have limited time, and you can’t accurately predict what your opponent will do at each step in that lovely future you’re cooking up in your brain. So you’ll just have to let your gut feeling guide you. I’ll refer to this part of the thinking process as “rollout”, so take note of it!
So after “rolling out” your few sensible moves, you finally say screw it and just play the move you find best.

Then the opponent makes a move. It might be a move you had already well anticipated, which means you are now pretty confident about what you need to do next. You don’t have to spend too much time on the rollouts again. OR, it could be that your opponent hits you with a pretty cool move that you had not expected, so you have to be even more careful with your next move.
This is how the game carries on, and as it gets closer and closer to the finishing point, it would get easier for you to predict the outcome of your moves — so your rollouts don’t take as much time.

The purpose of this long story is to describe what the MCTS algorithm does on a superficial level — it mimics the above thinking process by building a “search tree” of moves and positions every time. Again, for more details you should check out the links I mentioned earlier. The innovation here is that instead of going through all the possible moves at each position (which Deep Blue did), it instead intelligently selects a small set of sensible moves and explores those instead. To explore them, it “rolls out” the future of each of these moves and compares them based on their imagined outcomes.
(Seriously — this is all I think you need to understand this essay)

Now — coming back to the screenshot from the paper. Go is a “perfect information game” (please read the definition in the link, don’t worry it’s not scary). And theoretically, for such games, no matter which particular position you are at in the game (even if you have just played 1–2 moves), it is possible that you can correctly guess who will win or lose (assuming that both players play “perfectly” from that point on). I have no idea who came up with this theory, but it is a fundamental assumption in this research project and it works.

So that means, given a state of the game s, there is a function v*(s) which can predict the outcome, let’s say probability of you winning this game, from 0 to 1. They call it the “optimal value function”. Because some board positions are more likely to result in you winning than other board positions, they can be considered more “valuable” than the others. Let me say it again: Value = Probability between 0 and 1 of you winning the game.

But wait — say there was a girl named Foma sitting next to you while you play Chess, and she keeps telling you at each step if you’re winning or losing. “You’re winning… You’re losing… Nope, still losing…” I think it wouldn’t help you much in choosing which move you need to make. She would also be quite annoying. What would instead help you is if you drew the whole tree of all the possible moves you can make, and the states that those moves would lead to — and then Foma would tell you for the entire tree which states are winning states and which states are losing states. Then you can choose moves which will keep leading you to winning states. All of a sudden Foma is your partner in crime, not an annoying friend. Here, Foma behaves as your optimal value function v*(s). Earlier, it was believed that it’s not possible to have an accurate value function like Foma for the game of Go, because the games had so much uncertainty.

BUT — even if you had the wonderful Foma, this wonderland strategy of drawing out all the possible positions for Foma to evaluate will not work very well in the real world. In a game like Chess or Go, as we said before, if you try to imagine even 7–8 moves into the future, there can be so many possible positions that you don’t have enough time to check all of them with Foma.

So Foma is not enough. You need to narrow down the list of moves to a few sensible moves that you can roll out into the future. How will your program do that? Enter Lusha. Lusha is a skilled Chess player and enthusiast who has spent decades watching grand masters play Chess against each other. She can look at your board position, look quickly at all the available moves you can make, and tell you how likely it would be that a Chess expert would make any of those moves if they were sitting at your table. So if you have 50 possible moves at a point, Lusha will tell you the probability that each move would be picked by an expert. Of course, a few sensible moves will have a much higher probability and other pointless moves will have very little probability. For example: if in Chess, let’s say your Queen is in danger in one corner of the game, you might still have the option to move a little pawn in another corner of the game She is your policy function, p(a\s). For a given state s, she can give you probabilities for all the possible moves that an expert would make.

Wow — you can take Lusha’s help to guide you in how to select a few sensible moves, and Foma will tell you the likelihood of winning from each of those moves. You can choose the move that both Foma and Lusha approve. Or, if you want to be extra careful, you can roll out the moves selected by Lusha, have Foma evaluate them, pick a few of them to roll out further into the future, and keep letting Foma and Lusha help you predict VERY far into the game’s future — much quicker and more efficient than to go through all the moves at each step into the future. THIS is what they mean by “reducing the search space”. Use a value function (Foma) to predict outcomes, and use a policy function (Lusha) to give you grand-master probabilities to help narrow down the moves you roll out. These are called “Monte Carlo rollouts”. Then while you backtrack from future to present, you can take average values of all the different moves you rolled out, and pick the most suitable action. So far, this has only worked on a weak amateur level in Go, because the policy functions and value functions that they used to guide these rollouts weren’t that great.

Phew.

The first line is self explanatory. In MCTS, you can start with an unskilled Foma and unskilled Lusha. The more you play, the better they get at predicting solid outcomes and moves. “Narrowing the search to a beam of high probability actions” is just a sophisticated way of saying, “Lusha helps you narrow down the moves you need to roll out by assigning them probabilities that an expert would play them”. Prior work has used this technique to achieve strong amateur level AI players, even with simple (or “shallow” as they call it) policy functions.

Yeah, convolutional neural networks are great for image processing. And since a neural network takes a particular input and gives an output, it is essentially a function, right? So you can use a neural network to become a complex function. So you can just pass in an image of the board position and let the neural network figure out by itself what’s going on. This means it’s possible to create neural networks which will behave like VERY accurate policy and value functions. The rest is pretty self explanatory.

Here we discuss how Foma and Lusha were trained. To train the policy network (predicting for a given position which moves experts would pick), you simply use examples of human games and use them as data for good old supervised learning.

And you want to train another slightly different version of this policy network to use for rollouts; this one will be smaller and faster. Let’s just say that since Lusha is so experienced, she takes some time to process each position. She’s good to start the narrowing-down process with, but if you try to make her repeat the process , she’ll still take a little too much time. So you train a faster policy network for the rollout process (I’ll call it… Lusha’s younger brother Jerry? I know I know, enough with these names). After that, once you’ve trained both of the slow and fast policy networks enough using human player data, you can try letting Lusha play against herself on a Go board for a few days, and get more practice. This is the reinforcement learning part — making a better version of the policy network.

Then, you train Foma for value prediction: determining the probability of you winning. You let the AI practice through playing itself again and again in a simulated environment, observe the end result each time, and learn from its mistakes to get better and better.

I won’t go into details of how these networks are trained. You can read more technical details in the later section of the paper (‘Methods’) which I haven’t covered here. In fact, the real purpose of this particular paper is not to show how they used reinforcement learning on these neural networks. One of DeepMind’s previous papers, in which they taught AI to play ATARI games, has already discussed some reinforcement learning techniques in depth (And I’ve already written an explanation of that paper here). For this paper, as I lightly mentioned in the Abstract and also underlined in the screenshot above, the biggest innovation was the fact that they used RL with neural networks for improving an already popular game-playing algorithm, MCTS. RL is a cool tool in a toolbox that they used to fine-tune the policy and value function neural networks after the regular supervised training. This research paper is about proving how versatile and excellent this tool it is, not about teaching you how to use it. In television lingo, the Atari paper was a RL infomercial and this AlphaGo paper is a commercial.

Alright we’re finally done with the “introduction” parts. By now you already have a very good feel for what AlphaGo was all about.

Next, we’ll go slightly deeper into each thing we discussed above. You might see some ugly and dangerous looking mathematical equations and expressions, but they’re simple (I explain them all). Relax.

A quick note before you move on. Would you like to help me write more such essays explaining cool research papers? If you’re serious, I’d be glad to work with you. Please leave a comment and I’ll get in touch with you.

A photo of two Japanese women playing Go, placed here in case you’re already sick of looking at long slabs of text.

So, the first step is in training our policy NN (Lusha), to predict which moves are likely to be played by an expert. This NN’s goal is to allow the AI to play similar to an expert human. This is a convolutional neural network (as I mentioned before, it’s a special kind of NN that is very useful in image processing) that takes in a simplified image of a board arrangement. “Rectifier nonlinearities” are layers that can be added to the network’s architecture. They give it the ability to learn more complex things. If you’ve ever trained NNs before, you might have used the “ReLU” layer. That’s what these are.

The training data here was in the form of random pairs of board positions, and the labels were the actions chosen by humans when they were in those positions. Just regular supervised learning.

Here they use “stochastic gradient ASCENT”. Well, this is an algorithm for backpropagation. Here, you’re trying to maximise a reward function. And the reward function is just the probability of the action predicted by a human expert; you want to increase this probability. But hey — you don’t really need to think too much about this. Normally you train the network so that it minimises a loss function, which is essentially the error/difference between predicted outcome and actual label. That is called gradient DESCENT. In the actual implementation of this research paper, they have indeed used the regular gradient descent. You can easily find a loss function that behaves opposite to the reward function such that minimising this loss will maximise the reward.

The policy network has 13 layers, and is called “SL policy” network (SL = supervised learning). The data came from a… I’ll just say it’s a popular website on which millions of people play Go. How good did this SL policy network perform?

It was more accurate than what other researchers had done earlier. The rest of the paragraph is quite self-explanatory. As for the “rollout policy”, you do remember from a few paragraphs ago, how Lusha the SL policy network is slow so it can’t integrate well with the MCTS algorithm? And we trained another faster version of Lusha called Jerry who was her younger brother? Well, this refers to Jerry right here. As you can see, Jerry is just half as accurate as Lusha BUT it’s thousands of times faster! It will really help get through rolled out simulations of the future faster, when we apply the MCTS.

For this next section, you don’t have to know about Reinforcement Learning already, but then you’ll have to assume that whatever I say works. If you really want to dig into details and make sure of everything, you might want to read a little about RL first.

Once you have the SL network, trained in a supervised manner using human player moves with the human moves data, as I said before you have to let her practice by itself and get better. That’s what we’re doing here. So you just take the SL policy network, save it in a file, and make another copy of it.

Then you use reinforcement learning to fine-tune it. Here, you make the network play against itself and learn from the outcomes.

But there’s a problem in this training style.

If you only forever practice against ONE opponent, and that opponent is also only practicing with you exclusively, there’s not much of new learning you can do. You’ll just be training to practice how to beat THAT ONE player. This is, you guessed it, overfitting: your techniques play well against one opponent, but don’t generalize well to other opponents. So how do you fix this?

Well, every time you fine-tune a neural network, it becomes a slightly different kind of player. So you can save this version of the neural network in a list of “players”, who all behave slightly differently right? Great — now while training the neural network, you can randomly make it play against many different older and newer versions of the opponent, chosen from that list. They are versions of the same player, but they all play slightly differently. And the more you train, the MORE players you get to train even more with! Bingo!

In this training, the only thing guiding the training process is the ultimate goal, i.e winning or losing. You don’t need to specially train the network to do things like capture more area on the board etc. You just give it all the possible legal moves it can choose from, and say, “you have to win”. And this is why RL is so versatile; it can be used to train policy or value networks for any game, not just Go.

Here, they tested how accurate this RL policy network was, just by itself without any MCTS algorithm. As you would remember, this network can directly take a board position and decide how an expert would play it — so you can use it to single-handedly play games.
Well, the result was that the RL fine-tuned network won against the SL network that was only trained on human moves. It also won against other strong Go playing programs.

Must note here that even before training this RL policy network, the SL policy network was already better than the state of the art — and now, it has further improved! And we haven’t even come to the other parts of the process like the value network.

Did you know that baby penguins can sneeze louder than a dog can bark? Actually that’s not true, but I thought you’d like a little joke here to distract from the scary-looking equations above. Coming to the essay again: we’re done training Lusha here. Now back to Foma — remember the “optimal value function”: v(s) -> that only tells you how likely you are to win in your current board position if both players play perfectly from that point on?
So obviously, to train an NN to become our value function, we would need a perfect player… which we don’t have. So we just u*se our strongest player, which happens to be our RL policy network.

It takes the current state board state s, and outputs the probability that you will win the game. You play a game and get to know the outcome (win or loss). Each of the game states act as a data sample, and the outcome of that game acts as the label. So by playing a 50-move game, you have 50 data samples for value prediction.

Lol, no. This approach is naive. You can’t use all 50 moves from the game and add them to the dataset.

The training data set had to be chosen carefully to avoid overfitting. Each move in the game is very similar to the next one, because you only move once and that gives you a new position, right? If you take the states at all 50 of those moves and add them to the training data with the same label, you basically have lots of “kinda duplicate” data, and that causes overfitting. To prevent this, you choose only very distinct-looking game states. So for example, instead of all 50 moves of a game, you only choose 5 of them and add them to the training set. DeepMind took 30 million positions from 30 million different games, to reduce any chances of there being duplicate data. And it worked!

Now, something conceptual here: there are two ways to evaluate the value of a board position. One option is a magical optimal value function (like the one you trained above). The other option is to simply roll out into the future using your current policy (Lusha) and look at the final outcome in this roll out. Obviously, the real game would rarely go by your plans. But DeepMind compared how both of these options do. You can also do a mixture of both these options. We will learn about this “mixing parameter” a little bit later, so make a mental note of this concept!

Well, your single neural network trying to approximate the optimal value function is EVEN BETTER than doing thousands of mental simulations using a rollout policy! Foma really kicked ass here. When they replaced the fast rollout policy with the twice-as-accurate (but slow) RL policy Lusha, and did thousands of simulations with that, it did better than Foma. But only slightly better, and too slowly. So Foma is the winner of this competition, she has proved that she can’t be replaced.

Now that we have trained the policy and value functions, we can combine them with MCTS and give birth to our former world champion, destroyer of grand masters, the breakthrough of a generation, weighing two hundred and sixty eight pounds, one and only Alphaaaaa GO!

In this section, ideally you should have a slightly deeper understanding of the inner workings of the MCTS algorithm, but what you have learned so far should be enough to give you a good feel for what’s going on here. The only thing you should note is how we’re using the policy probabilities and value estimations. We combine them during roll outs, to narrow down the number of moves we want to roll out at each step. Q(s,a) represents the value function, and u(s,a) is a stored probability for that position. I’ll explain.

Remember that the policy network uses supervised learning to predict expert moves? And it doesn’t just give you most likely move, but rather gives you probabilities for each possible move that tell how likely it is to be an expert move. This probability can be stored for each of those actions. Here they call it “prior probability”, and they obviously use it while selecting which actions to explore. So basically, to decide whether or not to explore a particular move, you consider two things: First, by playing this move, how likely are you to win? Yes, we already have our “value network” to answer this first question. And the second question is, how likely is it that an expert would choose this move? (If a move is super unlikely to be chosen by an expert, why even waste time considering it. This we get from the policy network)

Then let’s talk about the “mixing parameter” (see came back to it!). As discussed earlier, to evaluate positions, you have two options: one, simply use the value network you have been using to evaluate states all along. And two, you can try to quickly play a rollout game with your current strategy (assuming the other player will play similarly), and see if you win or lose. We saw how the value function was better than doing rollouts in general. Here they combine both. You try giving each prediction 50–50 importance, or 40–60, or 0–100, and so on. If you attach a % of X to the first, you’ll have to attach 100-X to the second. That’s what this mixing parameter means. You’ll see these hit and trial results later in the paper.

After each roll out, you update your search tree with whatever information you gained during the simulation, so that your next simulation is more intelligent. And at the end of all simulations, you just pick the best move.

Interesting insight here!

Remember how the RL fine-tuned policy NN was better than just the SL human-trained policy NN? But when you put them within the MCTS algorithm of AlphaGo, using the human trained NN proved to be a better choice than the fine-tuned NN. But in the case of the value function (which you would remember uses a strong player to approximate a perfect player), training Foma using the RL policy works better than training her with the SL policy.

“Doing all this evaluation takes a lot of computing power. We really had to bring out the big guns to be able to run these damn programs.”

Another photo, from the first AlphaGo vs Lee Sedol game.

Self explanatory.

“LOL, our program literally blew the pants off of every other program that came before us”

This goes back to that “mixing parameter” again. While evaluating positions, giving equal importance to both the value function and the rollouts performed better than just using one of them. The rest is self explanatory, and reveals an interesting insight!

Self explanatory.

Self explanatory. But read that red underlined sentence again. I hope you can see clearly now that this line right here is pretty much the summary of what this whole research project was all about.

Concluding paragraph. “Let us brag a little more here because we deserve it!” :)

Oh and if you’re a scientist or tech company, and need some help in explaining your science to non-technical people for marketing, PR or training etc, I can help you. Drop me a message on Twitter: @mngrwl

How scientists edit genomes with the help of computers

CRISPR (pronounced “crisper”) is part of a bacterial immune system evolved to ‘remember’ and remove invading viral DNA.

Its name is short for ‘Clustered Regularly Interspaced Short Palindromic Repeats’. But despite its mouthful of an acronym and complex biological origins, its engineering application is straightforward. To get started, there is only one protein you need to understand — Cas9.

Cas9 searches for a specified DNA sequence and cuts it by breaking both strands of the DNA molecule. This protein is useful to researchers because they can ‘program’ it to target any DNA sequence. A sgRNA (‘single guide’ RNA) molecule determines the sequence that Cas9 binds to. RNA is a biological molecule similar to DNA, that can bind to proteins and DNA.

sgRNAs are short sequences with a constant region and variable region. The constant region attaches the sgRNA to the Cas9 protein. The variable region causes Cas9 to bind to the DNA sequence that complements it (see the diagram below).

The Cas9 protein bound to the DNA when the PAM sequence is on the forward (top) strand. The bold sequence is the target sequence, the green sequence is the sgRNA, and the three blue characters are the PAM. The triangles show where Cas9 will cut the DNA.

Making sgRNA is cheap and fast. This allows researchers to quickly set up a Cas9 experiment that cuts any DNA sequence. Well, not actually any sequence. There is a small constraint: the target sequence must be flanked by the correct PAM (protospacer adjacent motif) — a short sequence of DNA.

Streptococcus pyogenes is an infectious species of bacteria. In the version of Cas9 it produces, the PAM motif is ‘NGG’, where N is any nucleotide (the ‘letters’ that make up DNA).

Luckily, the motif ‘NGG’ occurs roughly once every 42 basepairs in the human genome. This mean that researchers can find a target site near almost every sequence of interest.

Depending on the experimental set up, these cuts in the DNA can either cause a random change or a precise change to the DNA sequence (more on this later).

Before jumping into writing this program, I recommend studying the Cas9 diagram below.

The Cas9 protein bound to a DNA sequence when the PAM sequence is on the reverse (bottom) strand.

Note that DNA and RNA have a directionality based on their chemical structure. One end of the molecule is referred to as the 5(‘five-prime’) end, and the other is referred to as the 3 (‘three-prime’) end. This is important, because the sequences 5— AGG — 3 is not the same as 3— AGG — 5.

By convention, DNA and RNA sequences are assumed to be written 5to 3 unless otherwise marked. Sequences read in the 5— 3 direction are called ‘forward’ sequences. Sequences read the other way (3— 5) are called ‘reverse’ sequences. This is an arbitrary convention.

The diagram above shows an example of Cas9 bound when the PAM is on the reverse (bottom) strand.

Your first CRISPR program

The scenario

A scientist has a DNA sequence of interest and wants a list of all CRISPR targets contained in the sequence. Finding every target by hand is tedious and error prone.

The scientist wants a simple program where they can input a DNA sequence and have all possible Cas9 target sites returned. The scientist would also like the cut position and PAM sequence for each target site.

EXAMPLE INPUT (from Figure 1): 'CCACGGTTTCTGTAGCCCCATACTTTGGATG'

EXAMPLE OUTPUT: [{    'cut_pos': 6,    'pam_seq': 'TGG',    'target_seq': 'GTATGGGGCTACAGAAACCG',    'strand': 'reverse'  }, {    'cut_pos': 22,    'pam_seq': 'TGG',    'target_seq': 'GTTTCTGTAGCCCCATACTT',    'strand': 'forward'  }]

First, how do we find CRISPR targets in the sequence? Remember that the Cas9 protein can bind anywhere there is a ‘NGG’ motif.

The first step is to loop through the sequence looking for matches. When the program finds a ‘NGG’ match, we want to subtract three positions from the start of the PAM site, since that is where Cas9 cuts the DNA.

Then, we want to record the twenty basepairs before the PAM as the target sequence. Sounds good?

Well, the algorithm described above would actually miss about half of all CRISPR sites — because DNA is double stranded. This means if a ‘CCN’ is the sequence on the forward strand, then ‘NGG’ is the sequence on the reverse strand.

The program must also search for ‘CCN’ using similar logic for the reverse strand.

Example program

Not all CRISPR targets are equal

When CRISPR was first catching on, researchers would often pull up a sequence on their computer and pick targets by hand. Designing the optimal sgRNA has now become much more complex. Below are brief introductions to this complexity.

Off-targets

Researchers soon realized that Cas9 would sometimes bind and cut at loci that did not exactly match the target sequence. These off-target cuts would cause unintended changes in a researcher’s experiment (or potentially a patient’s genome in the case of a therapy!)

To design a good guide, a program must look at the entire genome (which is approximately 3 billion nucleotides for humans) to calculate an off-target score. Researchers have also recently engineered the Cas9 protein to have less off-target activity.

Knockout

When Cas9 binds, it creates a cut by making a double strand break to the DNA molecule. Most of the time, a cell can repair this break through a biochemcial pathway (called non-homologous end joining, or NHEJ).

This pathway is not always perfect, and sometimes when Cas9 cuts, the repair process makes a small insertion or deletion in the DNA sequence. In a protein-coding region of DNA, these small insertions and deletions cause a frameshift mutation — which will often disrupt the protein’s function.

Researchers will often knockout a gene to figure out how a protein affects a specific cell function or phenotype. Creating a knockout edit adds extra constraints to the sgRNA design, because now the guide must land in the coding region of the gene.

Editing

Instead of knocking out a gene, there are many times a scientist wants to make a precision edit. This is especially useful when trying to correct a disease causing a mutation. The best way to do this is still being researched. Most methods involve adding an extra donor piece of DNA.

On-target score

Some sgRNA sequences will cause Cas9 to cut better than others. Researchers have compared cutting efficiency across thousands of Cas9 targets to create predictive models of a sgRNA’s cutting efficiency.

Microsoft even supports an open source repository for ‘Machine Learning-Based Predictive Modeling of CRISPR/Cas9 guide efficiency’.

Other CRISPR-Cas systems

Researchers have discovered CRISPR-Cas systems in other bacteria. These other systems have different PAMs.

Final notes

Hope you learned something new! If you want to learn more about the biology, medical applications, commercial applications, or ethical implications of CRISPR-Cas genome engineering, then I recommend reading A Crack in Creation by Jennifer Doudna and Samuel Sternberg. Jennifer Doudna is one of the original discovers of CRISPR’s underpinnings.

About the Author

I was previously an undergraduate researcher in the Gersbach Lab at Duke University, and I am currently a Software Engineer at a Synthego.

Artificial Intelligence is moving fast. The vibe is all around. Facts are beginning to sound like science fiction movies and science fiction movies like a version of reality (with better graphics). It may be that AI has finally achieved the level of maturity it has been pursuing for decades and was stubbornly denied, making parts of its community, and the whole world, suspicious against its feasibility.

Frankenstein may contain parallels relevant to the present day. Mary Shelley’s Gothic novel contains a discussion on the consequences of creating and introducing an artificial being into society. The Creature puzzles us with its inhuman atrocity and yet human manifestations of weakness, need for companionship and existential crisis.

One could say that we should focus on the future and the consequences of our discoveries. But how can one focus on the chaos created by injecting an army of Creatures into a system so complicated as contemporary society? One could also focus on the achievements, the success-stories that made these ideas sound veracious. But how can one ex post discriminate between correct intuition and luck?

It takes self-restraint, and wisdom, to set aside for a while the branches of your work and evaluate the firmness of its roots. A blooming tree can be distracting.

Whether you are tracing the rules of logical thinking in the ancient Greek philosophers, the formulation of reasoning in Arabic mathematicians or the power of mathematical knowledge in 19th century intellectuals — one unsettling notion becomes clear: the questions are deeper than the networks you can design (even taking Moore’s law into account).

“I believe that what we become depends on what our fathers teach us at odd moments, when they aren’t trying to teach us. We are formed by little scraps of wisdom.”

Umberto Eco

The rest of the discussion will emerge from the history of AI. Not the history of achievements, but the history of questions, arguments and beliefs of some significant individuals. Most of the events revolve around the ‘60s, the era AI acquired its official definition, its purpose, its scientific community and its opponents.

Can machines think?

In 1950 Alan Turing attempts to answer this purposely simplistically-expressed, question in his seminal paper Computing Machinery and Intelligence. Acknowledging its ambiguity and the limits it imposes on understanding AI, he proceeds by formulating a thought-experiment, also known as the Turing test:

Player A is a man, player B is a woman and player C is of either sex. C plays the role of the interrogator and is unable to see either player, but can communicate with them by means of impersonal notes. By asking questions to A and B, C tries to determine which of the two is the man and which is the woman. A’s role is to trick the interrogator into making the wrong decision, while B attempts to assist the interrogator in making the right one.

The reformulated question is then:

What will happen when a machine takes the part of A in this game? Will the interrogator decide wrongly as often as he does when the game is played between two humans?

Turing’s approach seems to follow the doctrine of the duck test: If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck.

His attitude when it comes to “human” aspects of intelligence, such as consciousness, is that you can’t blame someone (or something) for not possessing a characteristic that you have yet to define. Thus, consciousness is irrelevant in our quest for AI.

Gödel’s incompleteness theorems were an obstacle in one’s attempt to talk about AI. According to them mathematical logic cannot be both complete and consistent, thus, machines equipped with mathematical logic to learn, as is the case of AI, are expected to fail in learning some truths. Turing’s answer to this is fairly disarming: how do you know that human-intellect does not also come with its limitations?

Turing’s paper is lavish both in terms of arguments and a clear, dialectical structure, nevertheless constrained in speculations about technologies that had yet to be discovered.

Steps towards artificial intelligence

Marvin Minsky was one of the fathers of AI as a research field. In the dusty album of AI family photos, Minsky would be this old man that brings some uneasiness to a family dinner: “Old uncle Minsky. He was charmingly peculiar and always had something interesting to say”.

Minsky was one of the organisers of the Dartmouth Conference in 1956, where Artificial Intelligence was first defined as a term and a field. He is mostly remembered for his vigour of believing that AI is feasible and his depreciation in pursuing it with wrong means.

Let’s see what Minsky had to say in 1961, when he was asked about the so far progress in AI.

Should we ask what intelligence “really is”? My own view is that this is more of an aesthetic question, or one of sense of dignity, than a technical matter! To me “intelligence” seems to denote little more than the complex of performances which we happen to respect, but do not understand. So it is, usually, with the question of “depth” in mathematics. Once the proof of a theorem is really understood, its content seems to become trivial.

Acknowledging the inherent difficulties in defining AI, and thus pursuing it, Minsky begins by setting the building pillars of it. According to him, these are search, pattern-recognition, learning, planning, and induction.

If the ultimate purpose of the program is to search and find solutions of its own, then pattern-recognition can help it recognise the appropriate tools, learning can help it improve through experience, and planning can lead to more efficient exploration. As regards the possibility of making a machine with inductive abilities and thus reasoning, Minsky has to say:

Now [according to Gödel’s incompleteness theorem], there can be no system for inductive inference that will work well in all possible universes. But given a universe [our world], or an ensemble of universes, and a criterion of success, this (epistemological) problem for machines becomes technical rather than philosophical.

The rest of the text contains a recurrent urge to clarify that the pursuit of AI should be conducted through complex, hierarchical architectures. For this reason he questions the perceptron approach, as it will fail for moderately difficult problems. And frankly, we can’t expect reality to be simplistic.

Minsky can be attributed the responsibility of discouraging research in perceptrons, which probably delayed the bloom of deep learning. The realisation that, even using simple building blocks, one can solve complicated problems by going into deep architectures seems to have escaped his, nevertheless, ingenious insight.

Yet his remarks can be seen as ultimately constructive criticism, as they helped the community explore the weaknesses of the original approaches. Also, deep learning may be the best we have so far (and how marvellous the applications), but should not be regarded unconditionally as the Holy Grail of AI.

Minds, brains, and programs

In 1980 John Searle got angry. Although he probably got angry earlier, this is the moment he decided to publicise his disagreement with strong AI. Indeed, even the title sounds sarcastic. I feel like Searle is grabbing me by the collar and, vigorously waving his finger, saying: “Let me help you make some fundamental distinctions young lad”.

“One gets the impression that people in AI who write this sort of thing think they can get away with it because they don’t really take it seriously, and they don’t think anyone else will either. I propose for a moment at least, to take it seriously.”

Searle is solely attacking the notion of strong AI, which he identifies as the capability of a computer to practice any human-like behaviour. He translates this to the ability of a machine to demonstrate consciousness which he disproves by analogy. His famous thought-experiment, the Chinese room, goes like this:

You are a monolingual English speaker locked in a room with the following things: a large batch of Chinese writing (called a script), another large batch of Chinese writing (called a story) and a set of English rules instructing you how to match Chinese symbols of the second batch to the first (called a program). Then, you are given another batch of Chinese writing (this time called questions) and another set of English instructions with rules that match the questions to the other two batches. Congratulations, you just learned Chinese!

This is the Chinese Room experiment, introduced by Searle in 1980 . A thought experiment is not an experiment per se, as its goal is not be conducted, but to explore the potential consequences of an idea. The oldest and most famous is, probably, Galileo’s Leaning Tower of Pisa experiment (did you also think Galileo was actually dropping apples from the tower?).

Searle’s point is that the fact that you can produce Chinese answers by accepting Chinese questions does not mean that you understand Chinese, if this ability was created by following rules in another language. As a consequence, a machine that gives the expected output after it has been given the appropriate algorithm should not be considered a ‘thinking’ entity.

What Searle does not dispute is the ability of a program to think, as in terms of some functional reasoning. He accuses current AI researchers of being behaviouristic and operationalistic, as they attempt to equate a program with a mind (which is true), letting aside however the importance of the brain.

According to him consciousness comes only from biological operations and since a program is totally independent from its implementation (as it can run on any hardware) it cannot exhibit consciousness.

Reading the original text, one gets the feeling that he is attacking an immature community of computer scientists that has not bothered to reach a consensus on what intelligence is, nevertheless attempts to simulate it guided by teleological approaches and speculations.

Minsky’s response to Searle, and philosophical approaches in general, is as nihilistic as it gets: “they misunderstand, and should be ignored”.

Elephants don’t play chess.

And you should not make them feel bad about it. This paper, written by Rodney A. Brooks in 1990, is an attempt of a Nouvelle AI evangelist to persuade, employing both arguments and his robotic fleet, that the classical approach to AI should leave some space for his.

To get the feeling of that era, AI was experiencing its second winter. Funding was cut as companies and governments realised that the community had set the expectations too high.

So, time for introspection. When something fundamentally fails, there are two ways to go at it: either it’s impossible to achieve or your approach is flawed.

Brooks suggested that AI’s stagnation is due to its dogma of functional representations. The symbol system hypothesis is a long-standing view on how intelligence operates. According to it, the world involves entities, like people, cars and cosmic love, so it is natural to match them to symbols and feed machines with them. If this hypothesis is correct, then you have provided the machine with all the necessary information for it to “come up” with intelligence.

Although this assumption does not seem problematic, it has some far-reaching consequences that might account for the bad performance of AI:

• The symbol system is not adequate to describe the world. According to the frame problem it is a logical fallacy to assume anything that is not explicitly stated. To this point, Brooks charmingly suggests: why not take the world as its own model?
• Intelligence cannot emerge from simple calculations. The immense use of heuristics, that are necessary to train intelligent algorithms is a contradiction to our attempt to create knowledge. (Your grid-search is insulting to human intellect.)
• AI’s obsession with ensuring generality of a learned model has lead to a phenomenon Brooks calls puzzlitis: excessive effort given on proving that the algorithm works in obscure cases. It ιs certainly an attractive ability, but it does not seem to be a fundamental consequence of knowledge and our world is rather consistent.

Brook’s counterproposal is the physical grounding hypothesis. That is, allow Artificial Intelligence to directly interact with the world and use it as its own representation. This certainly changes the standard practise of AI: from learning requiring immense computational resources, guidance from experts and a never-satisfied need for training data, Brook suggests equipping physical entities with cheap hardware and unleashing them in the world. But does this underestimate the problem?

Brooks sees intelligence rising from collective behaviour, not sophisticated parts. Perhaps the most profound observation of his experiments regards how “goal-directed behaviour emerges from the interactions of simpler non goal-directed behaviours”. There does not need to exist a predetermined coordination pattern, as an intelligent machine should draw its own strategies to optimally interact with the world.

Brook’s argument of evolution draws a long way along persuading us of the importance of the physical ground hypothesis: humans are the most common and closest example we have to intelligence. Thus, in our attempt to re-create this characteristic, isn’t it natural to observe the evolution, a slow, adaptive process that gradually led to the formulation of human civilisation? Now, if one considers the time it took us to evolve skills such as interacting, reproducing and surviving, in contrast to our still young abilities of using a language or playing chess, then one may reach the conclusion that these are the hardest skills to develop. So, why not focus on that?

Although ecstatic about the practicality of his approach, Brook acknowledges its theoretical limitations, which can be attributed to the fact that we have yet to develop a complete understanding of the dynamics of interacting populations. Once more, the disregard of an engineer towards philosophical objections is evident:

“At least if our strategy does not convince the arm chair philosophers, our engineering approach will have radically changed the world we live in.”

AI manifests progress

Despite floating in a sea of questions, AI manifests something we cannot dispute: progress. Nevertheless, stripping current applications from the effect of technological advancements and heuristic advantages to acquire an accurate perception of the quality of the current research is a tedious task.

Will deep learning prove a worthy tool towards pleasing our ever-demanding criteria of intelligence? Or is this another interglacial period before AI reaches winter again?

What’s more, the concerns and questions have shifted from pure philosophical to social, as the consequences of AI in everyday life are becoming more obvious and pressing than the need for understanding consciousness, God and intelligence. Yet, this may be an even more difficult question to answer and urge us to dig even deeper.

When Wittgenstein wrote the Tractactus, he was confronted with the danger of a fundamental fallacy: his arguments fell victims to the doctrine of his work. That is, if one accepted his doctrine as true, his arguments were illogical and thus his doctrine should be false. But Wittgenstein thought differently:

“My propositions are elucidatory in this way: he who understands me finally recognises them as senseless, when he has climbed out through them, on them, over them.”

To understand the truth behind a complicated idea, we need to evolve. We must stand firm on our previous step and be willing to abandon it. Not every step has to be correct, but it has to be understood. When later confronted with this argument, Wittgenstein said that he does not need a ladder, as he is capable of directly approaching the truth.

We may still need it.

We have all experienced our awkward moments. Something unexpected happens, there is some social tense and a personal uneasiness and you would really like to get over it or forget that it ever happened. But what if you are a rigorous mathematician and you just got your world disproven?

Math has always been about the pursuit of understanding the world through logic and expressing it in a strictly defined, mathematical language. It is really indicative, educative, and fun, to observe mathematics when it stopped (momentarily) making sense.

1. The discovery of irrational numbers

The School of Athens, depicting, among almost every possible ancient Greek philosopher, Pythagoras in the left corner

As the origins of mathematical rigor lie in ancient Greece, mathematical thought started close to religious beliefs, thus numbers were attributed divine characteristics.

The School of Pythagoras, an occult team of early mathematicians that pushed mathematical knowledge forward, like all cults, was based on some fundamentalistic beliefs. Astonished by the applicability of ratios to every practical problem, they believed that ratios (yes, simple divided numbers) are divine, as they can explain anything that is happening in the world.

Accordingly, everything that is happening in the world should be able to be expressed as a ratio, right?

Now, imagine their surprise when they discovered the number square root of 2, while applying the newly formulated Pythagorean Theorem. This irrational number (irrational meaning that it cannot be expressed as the ratio of two numbers) defied world order as expressed by divinity of ratios and questioned their whole philosophy.

Terrified by the consequences of this revolutionary discovery, they decided not to tell anyone about it. It is also said, that they even drowned the man who did the discovery, Hippasus. Quiet scientific, don’t you think?

2. Infinity

The discovery of irrational numbers, being already bad as it was, brought the Greeks in front of a more terrifying discovery: infinity. As irrational numbers are characterized by having an infinite number of decimal digits, Greeks had to come up with an explanation for how a never-ending series of numbers can be created. The notion of infinity is difficult to understand today, let alone an age when religion was connected with science and a mathematical belief should not challenge our understanding of God. So, what did the Greeks do? Philosophers, like Aristotle and Plato, rejected the notion of an absolut infinity and mathematicians came up with inventive ways to circumvent the need for infinity in geometry, like Eudoxus of Cnidus who developed the method of exhaustion to calculate the area of shapes. It was not until the late 17th century that Newton and Leibniz encouraged taking infinity into account through their use of infinitesimals and John Wallis introduced the well-known symbol of infinity in 1655.

3. Zeno’s paradoxes

The Greeks certainly went to extremes when it came to philosophical reasoning.

After his predecessor Heraclitus claimed that everything in the world is constantly changing, Parmenides claimed that nothing changes. As a result, motion is a mere illusion and therefore, using mathematics, the language of truth according to the Greeks, to describe it should be impossible.

Zeno, one of Parmenides’ students, devised a series of paradoxes aimed to prove the irrationality of motion. The most famous one, Achilles and his tortoise, goes like this: Achilles is racing against a tortoise, which being significantly slower is given the advantage of starting the race 100 meters ahead of him.

If we assume, for the shake of simplicity, that the speeds of the two contestants are constant and Achilles is 10 times faster than the tortoise then we can say that when Achilles reaches the starting point of the tortoise, this will have run 10 meters. So, Achilles will try to catch up and by the time he reaches this next point, the tortoise will have moved an extra one meter.

This high-school math problem, being as simple and clear as it is, leads us to the following paradoxical conclusion: Achilles will never reach the tortoise no matter how much faster he is. Congratulations Zeno, you made motion sound illogical.

Zeno’s paradoxes were believed to exist in the realm of metaphysics and troubled philosophers and mathematicians for ages, but today they can be explained with calculus, a mathematical tool the Greeks did not possess. Let’s “move” on then.

4. Möbius strip

A make-it-yourself Möbius strip

The funny looking Möbius strip, which was also independently discovered in 1858 by the unlucky Listing whose name left the history of mathematics untouched, is a surface with only one side and only one boundary, often used to puzzle young math students.

You can easily create it by taking a strip of paper, twisting it and then joining the ends of the strip.

Being the first example of a surface without orientation it did not shake the grounds of mathematics as much as the other discoveries of this list did, yet it provided a lot of practical applications, such as a resistant belt, and inspired mathematicians to come up with unorientable surfaces, like the Klein bottle. (The name of this surface possibly comes from a double coincidence: Klein, its conceptor, originally named it Fläche, which means surface in German and sounds similar to Flasche, which means bottle. The fact that it also looked like a bottle seems to have sealed the renaming).

5. Cantor’s uncountability of real numbers

Dealing with infinity already being a drag, Cantor proved in 1874 that there are in fact different kinds of infinity. In particular, proving the uncountability of real numbers, Cantor proved that this set is bigger to the already infinite set of natural numbers.

In 1891, he also provided the diagonal argument, one proof so elegant that it was later adopted as a tool to prove through the use of a paradox. His remark gave birth to the theory of cardinal numbers, as well as paradoxes dealing with the question: how many infinities can you handle?

6. Russell’s paradox

_Bertrand Russell was a mathematician, philosopher, [social critic](https://en.wikipedia.org/wiki/Mathematical_logic" rel="noopener" target="_blank" title="Mathematical logic">logician, mathematician, historian, writer, <a href="https://en.wikipedia.org/wiki/Social_critic" rel="noopener" target="blank" title="Social critic), political activist and, to my opinion, a personality worth studying and inspiring oneself from.

In 1901 Russell discovered a weak spot in Cantor’s so-far well-established set theory, which led him to a contradiction the mathematical world could not oversee. According to this theory, any collection of things can be a set.

Russell’s contradictory example, also called the Barber’s paradox, goes as follows: imagine a town that has a special rule; every man that is not shaved by himself must be shaved by the barber of the town. The awkward question, which you can try to answer yourselves, is: who shaves the barber?

This discovery led him to questioning the mere foundations of the previous set theory and creating a new one, which being more complicated than the later proposed Zermelo-Fraenkel set theory, did not catch up.

7. Gödel’s incompleteness theorems

Kurt Gödel the logician, mathematician and philosopher that shook the grounds of mathematics and logic in the 19th century.

If the previous events seemed to create slightly uncomfortable moments, wait for the following awkward turtle (and this is worse than the one of Achilles).

We are talking about the 20th century. People did not just want to know. They wanted to know if it is possible to know, and prove it. Unluckily for them, and the human need for understanding the universe, Gödel published in 1931 two theorems, known as the incompleteness theorems.

Explaining the technicalities of them is as difficult as coming in terms with their conclusions, as what Gödel proved was that, considering a consistent and complete system, such as the language of arithmetic, there are statements that are both true and cannot be proven. He illustrated the truth of his theorem with this simple statement, inspired by the liar’s paradox: “This statement cannot be proven”. If this is true, then this statement is true and cannot be proven. If this is false, then this statement can be proven, which contradicts to the original argument that it cannot be proven.

These were very bad news for mathematics, depriving them of their original glare of explaining the absolute truth. It was also a terrible comeback to Hilbert’s quest for knowledge, expressed in his statement “We must know, we will know”.

8. Tarski’s undefinability theorem

It seems that Tarski was inspired by the despair created by Gödel. In 1936 he provided proof for the undefinability problem.

Although the observations made by Tarski are also included in Gödel’s work, it is argued that Tarski’s work has a more profound philosophical impact. Tarski managed to reach the general conclusion that a language cannot define truth in itself. Although this is an important limitation, he suggests that using a more powerful meta-language is sufficient to define truth in the simpler language.

Now, an ordinary person may think that this solves the problem, but for a mathematician looking for the “one language to rule them all” this is not that consoling.

9. The halting problem

Alan Turing attempted to tackle the decision problem, which, in simple words, dealt with finding an algorithm that can answer whether a statement is true or not. In order to tackle this conceptually simple, but hard-to-solve problem, he rephrased it to the halting problem: is there a machine that can tell you whether a program will halt on a given problem?

Halting means that it will not loop forever. But how do you prove the infeasibility of a machine you know so little about? This is where paradoxes come handy.

Alan Turing began by assuming the existence of a machine which given an input program and a problem answers the question of whether it will halt or not. He then augmented this machine by looping its output back to itself if the answer was yes and halting if the answer was no.

So, will the augmented machine halt on the halting problem? Alan’s answer is: if yes then no, if no then yes. Sounds like bad news for logic.

10. The No Free Lunch Theorem

The passage to the 21st century signified a transfer from pure, almost philosophical mathematics, to applied areas, such as statistics and optimization.

If you consider yourself being fond of optimization, don’t you think this will make you a perfectionist? And wouldn’t a perfectionist want to find the optimal way to optimize things?

It seems that David Wolpert and William Macready sensed this need and came up with an answer, which, of course, was not encouraging at all (otherwise it would not be in our list). According to their No free lunch theorem for Optimization, published in 1997, “any two optimization algorithms are equivalent when their performance is averaged across all possible problems.”

Heart-breaking this may be, it does not mean optimization is futile. We’ll just never find a generally optimal way to do it.

These moments made the world of mathematics feel awkward, which is a light term for the feelings of despair and chaos that scientists tend to experience when the universe stops making sense. But shock is the way to move science forward.

Mathematical fields were created, we got the Turing Machine, fancy looking surfaces and, most importantly, the ability to re-examine our perceptions and adapt our tools accordingly.

These questioning moments helped us evolve intellectually.

Except for the incompleteness theorems. These were just devastating.

Disclaimer: This is a hypothetical think piece. It is a personal opinion and doesn’t represent the opinion of any of the companies (or secret societies) I may (..or may not) be involved with. If you tear a hole through space-time after reading this article… that’s your own fault.

If you haven’t heard, a research team out of China just made a huge leap with respect to realization of using Quantum Entanglement as a valid communication vessel. Their process was to use a low-earth satellite to create a pair of entangled photons and then send them to locations very far apart from each other. Even at never-before-done distances, the photons retained their entanglement, which has set the internet a buzz about the future of communication, and when the new quantum internet will happen.

Now, looking at the math, I’m still a bit dubious that quantum entanglement could be viably used for communication. This math person explains it a bit better than I ever could. However, there’s lots of people hypothesizing that this is the first steps in a new quantum internet where things like Entanglement Swapping and Twisted Light could bridge those gaps.

Then let’s propose a thought experiment: let’s assume there’s future where an internet exists, whose technology is based on quantum entanglement. This means that data can be transmitted between two locations, at close to speed-of-light without a physical connecting medium between the locations.

In such a world, does data compression matter any more?

A small idea on how a QE internet would work

We have to assume that due to current technology, the first realization of a QE Internet (QEI) would be very similar to the telegraph systems of the past. The cost to maintain and run these early QEI sites would limit their availability, meaning that communication could only occur between a handful of sites.

These sites would require two primary features:

1. A non-centralized system which can distribute entangled photon pairs to the sites (a low-orbit satellite, for example).
2. A recording system which logs the results of the entanglement tests and can store / retrieve them.

#2 would be most likely built on today’s modern technology. So you can expect a situation where a billion photon pairs are sent to a site, and sampled in unison, and stored as binary data at the location.

From that point, the data would be most likely distributed to it’s final destination using more conventional methods (e.g. fiber connection).

Limitations of a first generation QEI

Obviously, we still end up with some data-based bottlenecks here:

1. There is a physical limit to how many entangled pairs can be stored at a site, thus limiting it’s total bandwidth.
2. There is a physical limit to the speed in which entangled pairs can be sent from the distributor to the sites on a regular basis, thus limiting total system bandwidth.
3. Environmental factors will cause loss of data in the transfer of photons to the sites from the distributor system. Thus, there will be a need for redundancy in the process, limiting total system bandwidth.

When observing the above, you can quickly seen that the overall bandwidth of a QEI would be limited by the above systems, regardless of the ability for information to travel between sites through quantum means. So obviously, reducing the size of the data being sent through the sites will be important, but will today’s data compression algorithms make sense?

Data compression for a QEI

There’s a few definitions of “data” which represents it as a physical entity, and as the (potential) realization of a Quantum Internet is realized, the need for photon transferal makes this concept even more real.

In fact, that may be the largest ramification of a quantum entangled internet: your data now has a very physical manifestation and cost involved with it.

So it’s obvious that data compression, as a science, will still be needed in a QEI future, but the real question we should be asking ourselves is: Are today’s compression algorithms good enough to support a quantum internet?

My opinion? Not even close.

As explained in “Understanding Compression” today’s systems are still grounded around Shannon’s basic architecture of ‘the most frequent symbol gets the smallest bits.’ There’s a lot of power in this process, but until we move out of symbol space, and start gaining the computational power to handle compression entirely in bit-vector space, we’re going to be leaving a lot of information on the table. (But that’s my own unpopular opinion...)

Let’s look beyond that. Are there potential systems where, rather than applying Brotli to a data set, we instead can apply in to entangled photons directly? Will we start talking about algorithms to do diff’s against the photons on a site, and the data being transmitted, so we can reduce the number of updated pairs? What happens when we start thinking in terms of qubits, rather than just bits? Do we have to start thinking about LZ encoding in 8 dimensional space?

Obviously, the realization and standardization of Quantum Computing will create a massive technological shift in how our world works. And I’ve got every reason to believe that Data Compression will be right there, too.

Within 10¹ years your favorite pet is gonna die.

Within 1o² years you are gonna die.

Within 1o³ years your great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-great-grandkids are gonna die.

Within 1o⁹ years Earth is gonna die. The sun will get so hot that it boils our oceans.

Within 1o¹⁰ years the sun is gonna die. The changes in gravity will cause the charred remains of our solar system’s planets to collide with one another. Then they’ll spiral into our dead sun’s white dwarf core.

Within 1o¹¹ years the Milky Way is gonna die. It’ll merge with the neighboring galaxy Andromeda, which is gonna die, too. After eons of cosmic violence, their supermassive black hole cores will merge.

Within 1o¹⁵ years all stars are gonna die. There won’t be enough matter left to form new stars. It’ll be all used up. We’ll just have black dwarfs, black holes, and radiation. The universe will go black.

Within 1o³⁰ years matter is gonna die. Any protons that haven’t been consumed by black holes will start to decay into neutrinos.

Within 1o¹⁰⁰ years black holes are gonna die. They’ll evaporate completely. All that’ll be left is radiation.

For all we know, this is a one way trip. There’s no reason to expect that anything will ever exist again. And all that awaits us is absolute-zero blackness.

Lesson’s over. Go outside and play with your kids.