S Lecture 9: Relevancy in problem solving
TODO: Rename this to "Kwisthout - Relevancy in Problem Solving: A Computational Framework"
Riddle:
In 1990, a person is 15 years old. In 1995, that same person is 10 years old.
Riddle is impossible to solve if you do not know what the relevant information is. Will you get closer to a solution, the more effort you put in (linear progress)? In case of difficult problems, most of the effort is trying to find out what is needed and relevant to solve the problem.
Hint: Julius Caesar.
You need to relax an assumption: we are taking about years before Christ.
Schedule
- Motivating example: finding your way back home
- Background information, state of the art
- Formalization of "Relevance Problem"
- Revisiting relevance (in relation to Most Frugal Explanations)
- When is the relevance problem difficult?
Kwisthout is not actively researching this anymore, but he would like to pick it up in the context of a master thesis, for example.
For a change, we are not exploring this in the context of Bayesian networks, but the concepts are still relevant.
Description from lecture notes that starts with the observation that for some problems it seems easy to capture the relevant aspects whereas for others it is not. Why is that?
I try to capture the concept of ‘hardness of abstraction of a real-world problem (like finding the way to your hotel in an unknown city) to a representation suitable for solving it (like a weighted graph between crossings and landmarks)’ as something that comes before analysing how hard it is to actually solve the problem (using the abstraction, i.e., solving a shortest paths problem).
How can we distinguish problems whose relevant aspects are hard to represent with one that is easy? The paper offers some indication for a subjective measure to distinguish hard and easy problems, but a formal account of why some problems are inherently harder to represent correctly is future work.
So this paper concerns the complexity sources of the relevance problem, further specified more narrowly as an abstraction problem. Not how we in fact solve it (i.e. this is a computational-level paper).
Finding your way home
Input: Graph problem, with graph G=(V,E).
Output: sequence of edges (S,X)...,(Y,T) connecting to S to T with minimal total weight.
Algorithm: Dijkstra's, A* etc.
This problem is relatively easy to solve (typical first year CS problem).
However, the problem is already cast into a proper formalization! What about this step?
The complexity view
Translate problem into Turing-compatible form, using a reasonable encoding (i.e. it does not ramp up the difficulty and complexity of the problem).
Problem -> (reasonable) -> encoding -> (feasible) -> computation.
Reasonable:
E.g. a natural number can be encoded with binary notation, and not with unary notation (e.g. turven).
Feasonable:
From encoding to computation should be polynomial.
The enhanced complexity view: representation
But we are not faced with graph problems in real life. We are instead in some (unknown) city where we are trying to find our way.
What information is relevant to even find the appropriate representation?
The step of finding a relevant representation is usually left out in complexity analysis. We should include the first step if we care about AI acting in the real world:
Problem -> (relevant) -> Abstraction -> (reasonable) -> encoding -> (feasible) -> computation.
What's the relevance problem?
Paper discusses the 9-bridge problem of Euler (and the invention of graph theory, essentially). Is there an Euler tour?
Insights:
- The used abstraction is important for solving the problem
- The used abstraction contributes to the complexity of the problem
Euler captures the absolute minimum of the problem, i.e. representing it as what we now know as a graph. Meaning: he also did not leave out any relevant aspect (e.g. it is not a connectivity problem).
Why is the problem of finding a relevant abstraction sometimes easy and sometimes hard?
What is solving a problem?
We have one big state space, in which we have:
- Begin with a problem state p -> (function f maps) -> end state s in solution region of the state space.
There are of course many other interpretations of problem solving (e.g. explain why Y=f(x), or find Y=f(x)).
This paper focuses on the problem of finding a path from X to Y and computing Y from X.
Formalizing the abstraction step
The aforementioned state space is massive, $C^N$ with C the maximal cardinality/resolution of the dimensions, and N dimensions.
We then define the relatively very small set of relative dimensions (properties) as M. Because M is defined as the subset of relevant dimensions, we seek a path from p to s and define that it is independent of anything outside M (we defined those to be the relevant dimensions after all).
Problem solving as going from one point in a N-dimensional hypercube to another point in that hypercube.
- First N denotes naturals
- What does that mean?
- This differs from the paper, where Kwisthout uses $C^N$
- Second N dimensions
- N^N represents universe of all features, describing both current and desired state
- Some dimension are relevant, some are not.
- Most are irrelevant for a given problem
Abstraction step:
- Find a subset N^M with M considerable smaller than N.
- The characteristics of the problem remain the same.
Connection to Frame problem & Isotropy:
Consider this citation from the lecture notes:
It relates to the (holistic) frame problem in the sense that I do not try to ‘solve’ it or explain how human cognizers happen to ‘solve’ it, but that I try to formalize the function that selects relevant aspects from the space of all possible aspects. (56)
Also interesting in this context, from the paper:
However, there is increasing evidence from psychology (see, Ash, Cushen, & Wiley, 2009 for an overview) that finding a useful representation of a problem can be as hard as computing a solution to the (representation of the) problem. (20)
It departs from the insight that some problems are inherently hard to abstract.
This need not surprise us, as the abstraction problem closely relates to the frame problem in artificial intelligence: the fundamental problem of deciding which information is relevant in order to make inferences, where in potential everything might be relevant (Fodor, 1987) (24)
Isotropy theorem of Jerry Fodor ( TFCA-3-Frame_problem.md ), translated into the terms of this paper: for all problems and for all dimensions d in N there exists an instance for which d is a relevant dimension - everything is potentially relevant.
This implies that M=N.
Isotropy in practice: determining what is relevant
- Some dimensions are relevant in almost all instances
- Some are practically never relevant, only in very extraordinary circumstances.
Fodors: we cannot theoretically separate them. We as humans are able to reason about these extraordinary circumstances. We can imagine a weird scenario, following some sequence of thought steps; even this is not our usual behavior. This is what makes a detective story interesting.
So it is still somehow part of our belief system; we can make some connection.
Takeaway from Fodor (in context of frame problem): We cannot encapsulate the relevant information and completely separate it from all other information.
And yet this is very close (if not exactly) what we have to do: find a subset M with relevant features.
But can't we still meaningfully separate those dimensions that are almost always relevant, from those that are only in high exceptions?
If the isotropy theorem is true, then M=N, i.e. you can always depict one dimension to be relevant, even if it is extremely extraordinary.
Do we want to take into account these extraordinary scenarios? Even though we may come up with a story about how an unlikely scenario may occur, in practice we can perhaps compute in probabilistic terms something is simply not going to happen (E.g. John Littlewood on how long a mouse can survive for a week on the surface of the sun.)
I.e. can't we still meaningfully speak of expected relevancy?
Relaxed formulation: We assume M is a strict subset of N, i.e. we can ignore at least some dimensions as being irrelevant.
Surprise (not): determining relevancy in this way is still NP-hard.
We do not explicity search the whole problem space
Refer to p. 25.
Expected relevancy
See p. 25 of paper where the subjective measure of expected relevancy is introduced.
0 indicates absolute irrelevance; 1 absolute relevance.
Typically, the expected relevancy $\delta_d$ for a dimension d would be low if variation along the value of the dimension is not considered likely to affect the outcome of the problem solving activity. (25)
This measure is used to describe (informally still) how hard a problem is to represent/abstract. So to be clear, this measure is not explicitly computed "in" the brain (cf. 26), but...
We do suggest that expected relevancy may be a measure that can be used to describe why some problems are harder to abstract than others. Likewise, we suggest that it may be a useful way of explaining individual differences in finding an abstraction, as well as explaining why people sometimes (like in insight problem solving) make unsuitable abstractions. (26)
Examples are given in the discussion section (25-29).
A clear example is the nine-dot problem. This is an insight problem, meaning that we require a suitable representation and then the solution suddenly becomes relatively straightforward. This problem is hard because the feature that is relevant for the solution has a low expected relevancy. This is clear: we are used to thinking about dots as mathematical points without area. But in the problem, the area can in fact be used and must be used for the solution.
How do we define irrelevance?
Dealing with isotropy in practice:
- Variation in dimension only changes outcome by a tiny amount
- Variation may change the outcome considerably, but only in very exceptional cases.
Formalisation and complexity
See appendix of paper. The proof is actually quite straightforward.
The proof assumes binary features for the intractability proof. This means that the dimension of features is irrelevant for intractability.
We defined the relevancy of a variable as: if you vary it, does the outcome change?
A characteristic function $1_\phi$ is one that maps satisfied instances to 1, not satisfied instances to 0.
So relevance is defined as $1_\phi(x_1=1) \neq 1_\phi{x_1=0}$ i.e. if you change the value of variable $x_i$ this changes the outcomes (i.e. satisfiability).
For irrelevance, they stay the same (i.e. replace the not equals with '=').
Now we construct $\phi = \psi \land x_{n+1}$.
The reasoning is simple and is based on this being a conjunction.
- If $\psi$ is not satisfiable, the whole formula will not be satisfiable due to the conjunction. As a result, $x_{n+1}$ will never influence the satisfiability of $phi$ and thus is irrelevant according to our definition.
- If $\psi$ is satisfiable, then in an instance where $\psi$ is satisfied, $x_{n+1}$ will be relevant, as it now determines whether $\phi$ will have the characteristic function output of 1 or 0.
If we can show the relevance of $x_{n+1}$ we have also solved SATISFIABILITY. If $x_{n+1}$ is relevant, then we know $\phi$ is satisfiable. If $x_{n+1}$ is irrelevant, then we know that $\phi$ is not satisfiable.
As a result, we have reduced SATISFIABILITY to our relevance problem (we can reconstruct an instance of SATISFIABILITY as an instance of this relevance problem), which means that the relevance problem is at least as hard as SATISFIABILITY. But SATISFIABILITY is NP-complete, so our relevance problem is also NP-complete and is only solvable in polynomial time if P=NP.
Now, we can construct this as a special case of the abstraction problem, which is also intractable as a result.
Ok, intractable. What about why this is hard for humans?
We make errors in making abstractions:
- We either choose M too small and leave out a relevant dimension (cf. nine dot problem).
- We choose M too big and allow irrelevant dimensions.
- Missionairies and cannibals toy example: move missionaries from one edge of the river to the other
- Irrelevant: we don't care about what happens while you are on the boat on the river.
- Both
Are some problems inherently harder to abstract?
Easy: find path from A to B. Relevant factors are clear.
Hard: Make X fall in love with me (what is the "path" from "X not loving me" to end state "X loves me")
Some problems indeed appear to be harder, probably because they are. This is underpinned with the intractability proof, so this follows from the computational formalization.
Hypotheses
Assumed heuristic in problem solving: we only include dimensions with a high expected relevancy.
- H1: making abstractions is hard when there are many dimensions with high expected relevancy.
- "everything seems relevant!"
- H2: making abstractions is hard when there are many dimensions where the expected relevancy is hard to asses/unclear
- "I don't know what's relevant!"