Memory in Human and Artificial Computation

Computational problems tend to leverage the utility of memory to increase efficiency in human and artificial cases. In their review of Memory as a Computational Resource, Dasgupta et al. argue that memory is an often overlooked component of efficient computation. The efficacy of integrating memory usage into a computer scientist’s algorithms is highlighted and compared to how memory is utilised in cognitive algorithms in our brains as well.

from ScienceABC

Leveraging Memory in Programming

Problems that entail many repeated computations rely on memoization to avoid inefficiency. In short, memoization involves storing results of computations and returning these cached results when called again in the same algorithm. Optimisation using memoization can speed up algorithms and have been used to solve problems for a while now. A common scenario familiar to all Computer Science students where memoization is prevalent is in the sphere of Dynamic Programming (DP). This particular method of programming was developed by Richard Bellman in the 1950s and has immense applications in a variety of disciplines. DP concerns itself with trying to solve a problem by breaking it down into similar sub-problems recursively and using memoization to ensure that no sub-problem is computed more than once.

See how Dynamic Programming employs computational reuse with memoization to speed up function executions by not re-computing redundant function calls in the simple Fibonacci example. The Fibonacci Series is famously defined recursively as follows:

f(n) = f(n-1) + f(n-2) where f(0) = 0 and f(1) = 1

This can be implemented naively as the following algorithm in any standard programming language.

function fib(n)
    if n <= 1 return n
    else return fib(n − 1) + fib(n − 2)

The implementation that involves memoization would look like the example below. The algorithm now consults the memo-table m each time and only computes a value if the table does not have the n it is trying to compute. Every time a computation takes place, it is stored in the memo-table that then ensures that no repeated computation takes place.

global table m[]
function fib(n)
    if n is not in table m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

The figure shows the computation graph in the naive implementation and the memoized implementation using DP. The redundant function calls are in blue and are not repeated when a memo table is consulted. From Dasgupta et al.

The example highlights the space-time trade-off where the increased efficiency in terms of the time taken for the algorithm to execute comes at the cost of decreased efficiency in terms of space used by the algorithm. These type of algorithms that rely on memory for faster execution can be seen in fields like Aerospace Engineering, Economics and Bioinformatics. More interestingly, memoization might be an integral part of human cognitive computations and a critical reason for its speed.

Leveraging Memory in Human Cognitive Computations

Using memory as a form of computational reuse to optimising computations occurs in our cognitive mechanisms as well. The review paper by Dasgupta et al. outline 4 distinct cases where memory is leveraged to optimise algorithmic efficiency in cognition. These cases include the domains of mental arithmetic, image recognition, probabilistic inference and planning. These observations shed light on the underlying mechanisms of these cognitive domains.

Mental Arithmetic

When humans learn to count and solve arithmetic problems, we start off with ‘naive’ algorithms that do not leverage memory. Let’s take the example of simple addition. At early stages of life, children solve single addition problems (e.g. 2+3) by starting a counter at the first addend (2)and incrementing it by 1 until it equals the second addend (3). This naive implementation can be represented in pseudocode below. It is clear that this isn’t a very efficient algorithm as the time taken linearly scales with the size of one of the addends.

function addition(a,b)
    answer = a
    i = 0
    while (i < b):
        answer++
        i++
    return answer

from startteachertraining.com

As we grow older, we ‘optimise’ this addition algorithm by relying on memory rather than the arithmetic logic to reach the answer faster. We rely on previous experiences where we might have calculated 10+18 in math class a week ago and remember the answer we obtained then which is faster than trying to solve the problem once again algorithmically. The same is at play when we were made to memorise the times tables in schools to become more competent in multiplication.

This is an application of Gordan Logan’s Instance Theory of Automaticity. The overarching idea in the theory is that output of an algorithm can be stored and reused for later. Future problem solving then becomes a race between the algorithm and memory, the winner determines the behavioural output.

Image Processing

Studies that involved mental image processing have drawn similar conclusions as ones that have researched mental arithmetic — there is a similar level of memoization used to optimise computations. The review mentions one specific study conducted by Shepard and Metzler which asked participants to identify if two drawings (manipulated by rotating the drawing through a certain angle) depicted the same object. The results showed a linear relation between the response times and the angular difference the drawing had been rotated. This suggests that the participants were mentally rotating the images in their mind (similar to the naive iterative counting in the arithmetic) before making the decision. Later studies showed that these response times reduced over time after extensive practice using the same images which matches the theory of computational reuse using memoization. Similar to how we rely on remembering previously computed mathematical operations to solving problems in front of us to some extent, it is highly probable that we rely on previously processed images of scenes around us to process scenes going on in front of us right now.

Probabilistic Inference

Probabilistic Inference can be described as deriving the probability of a certain event given certain information. We use this phenomenon in our daily lives when we try to figure out causality for certain events in our lives. An example could be trying to figure out why our friend is upset today. We have information on what sort of things in general upset him and can assign probabilities for these stimuli. Figuring out the causal stimuli is important to us because we want to be a good friend and help him in the best way possible which will be easier if we know what upset him.

from Adobe Stock

Traditional probability theory dictates that optimal inference can be derived from the Bayes’ rule where we can infer which of the multiple latent variables, z (here, causal stimuli that could have upset our friend) has the highest probability of being true when the possibility that the prior, d (the possibility of friend being upset) is true. For example, z1 could be that he has not gotten enough sleep and z2 could be that he has gone through a rough breakup. Here, intuition tells us that P(z1|d) > P(z2|d). Similarly, we would have to compute all these probabilities to find the stimulus most likely to be at fault, which we can confidently infer.

from Dasgupta et al.

This type of computation is expensive considering that there is significant combinatorial overhead to think of. There could be multiple hypotheses for causal stimuli that may even be nonexclusive (i.e. not getting enough sleep and going through a rough breakup). This leads to an exponentially high time complexity that would be extremely difficult to accurately compute. Therefore, we rely on a more optimised approach.

As rational agents, we can make use of the Markov property. The property states that a future process or event’s likelihood is dependent only on the present state of the environment. What does this mean? Referring back to our example, this means that the computation becomes a lot easier because we only need to use the information we know about our best friend in his current state to infer the reason for his unhappiness. We do not need to consider stimuli and their probabilities from his past or future or stimuli that we are confident would never be exposed to our friend. This could mean eliminating events like a rough breakup if our memory tells us that he is in a happy relationship or not in a relationship at all; or increasing the likelihood that he might have gotten bad sleep last night due to his new job that he got recently where he overworks himself. The implication here is that we only need sufficient statistics from memory to infer the probabilistic likelihood of an event. Once again, memoization is prevalent in a very commonly used cognitive mechanism.

This Markovian probabilistic inference shares roots with the Kalman Filter, a model of learning popular in Neural Networks. The success of the Kalman Filter lies in a cache that it consults which stores important intermediate results (the sufficient statistics) which is updated every forward pass. The cache reduces computational costs as these intermediate computations need not be repeated.

Planning

Planning refers to the series of actions chosen to maximise the cumulative reward given a certain scenario. The scientific study of how humans plan has been a critical part in the Cognitive Sciences and designing Artificial Intelligence — especially Reinforcement Learning (RL). Studies usually centre around planning in games like Chess and Go.

A naive approach to deconstructing how humans might plan is that we evaluate every possible outcome and iteration of the scenario and choose the most optimal one which maximises cumulative reward. However, studies show that we plan in a more optimise manner that involves a degree of memoization. In the example of Chess, a player is more likely to evaluate the game states based on their own memory of different games they have played and all the board positions they have come across. It is theorised that a degree of memoization is involved in efficient planning but there is no concrete understanding of the cognitive mechanism at play. Nevertheless, Mathematicians and Computer Scientists have abstracted the planning process into a simple computational problem called the Markov Decision Process (MDP).

MDP draws from the Markov Property from before and is implemented such that an agent is able to move between states by selecting actions which correspond to the reward it obtains. The expected cumulative reward can be expressed as the Bellman Equation (yes, the same Bellman from before).

from Dasgupta et al.

Q(s,a) is the cumulative reward which comprises of the individual reward for that state and action, — R(s,a) and the average of the cumulative reward function — E[Q(s’, a’)] — over the next steps (s’) and actions (a’). This recursive equation is at the heart of many efficient planning algorithm in the computing field. The equation is also responsible for the rise of artificial agents via Reinforcement Learning algorithms which compute the expectation by interacting with the environment and remembering the the reward obtained at specific states and actions. MDP could be a heavily abstracted alternative to the cognitive computation of efficient planning which hints at the significant role of memory in planning.

from KDnuggets

Additionally, behavioural studies have also showed how memoization is at play when we tend to reuse old plans to try and solve new problems. Studies showed that planning tasks saw participants not choosing the optimal path of solving a problem rather choosing familiar subpaths from previously planned problems. Even though we may not yet understand the intricacies of human decision making, it is safe to say that relying on memory is an integral part to speed up these computations.

Concluding Thoughts

Dasgupta et al. provided a consolidated review that outlined memory’s critical role as a computational resource in artificial and human computational problems. Speeding up processes by not relying on repeated computations using memoization can be found in both of these types of computation. The review manages to argue the importance of memory as an integral aspect of intelligent behaviour. Knowing this, how could we apply processes similar to memoization and computational reuse to build agents with human-levels of intelligence? The answer would have something to do with our understanding of when to rely on memory and when it will fall short. Further research in knowing the point till we can confidently rely on previously solved problems to solve a novel problem will help in transferring this aspect of human intelligent behaviour to AI.

References:

• Memory as a Computational Resource — https://www.scienceabc.com/humans/can-technology-boost-human-memory.html