12
$\begingroup$

I was watching a very interesting video with Yoshua Bengio where he is brainstorming with his students. In this video they seem to make a distinction between "credit assignment" vs gradient descent vs back-propagation. From the conversation it seems that the credit assignment problem is associated with "backprop" rather than gradient descent. I was trying to understand why that happened. Perhaps what would be helpful was if there was a very clear definition of "credit assignment" (specially in the context of Deep Learning and Neural Networks).

What is "the credit assignment problem:?

and how is it related to training/learning and optimization in Machine Learning (specially in Deep Learning).

From the discussion I would have defined as:

The function that computes the value(s) used to update the weights. How this value is used is the training algorithm but the credit assignment is the function that processes the weights (and perhaps something else) to that will later be used to update the weights.

That is how I currently understand it but to my surprise I couldn't really find a clear definition on the internet. This more precise definition might be possible to be extracted from the various sources I found online:

Also, I found according to a Quora question that its particular to reinforcement learning (RL). From listening to the talks from Yoshua Bengio it seems that is false. Can someone clarify how it differs specifically from the RL case?

Cross-posted:

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
+25
$\begingroup$

Perhaps this should be rephrased as "attribution", but in many RL models, the signal that comprises the reinforcement (e.g. the error in the reward prediction for TD) does not assign any single action "credit" for that reward. Was it the right context, but wrong decision? Or the wrong context, but correct decision? Which specific action in a temporal sequence was the right one?

Similarly, in NN, where you have hidden layers, the output does not specify what node or pixel or element or layer or operation improved the model, so you don't necessarily know what needs tuning -- for example, the detectors (pooling & reshaping, activation, etc.) or the weight assignment (part of back propagation). This is distinct from many supervised learning methods, especially tree-based methods, where each decision tells you exactly what lift was given to the distribution segregation (in classification, for example). Part of understanding the credit problem is explored in "explainable AI", where we are breaking down all of the outputs to determine how the final decision was made. This is by either logging and reviewing at various stages (tensorboard, loss function tracking, weight visualizations, layer unrolling, etc.), or by comparing/reducing to other methods (ODEs, Bayesian, GLRM, etc.).

If this is the type of answer you're looking for, comment and I'll wrangle up some references.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you please add some references you consider significant within this context? Thank you very much! $\endgroup$
    – Penelope Benenati
    Jun 14, 2021 at 15:04
4
$\begingroup$

I haven't been able to find an explicit definition of CAP. However, we can read some academic articles and get a good sense of what's going on.

Jürgen Schmidhuber provides an indication of what CAP is in "Deep Learning in Neural Networks: An Overview":

Which modifiable components of a learning system are responsible for its success or failure? What changes to them improve performance? This has been called the fundamental credit assignment problem (Minsky, 1963).

This is not a definition, but it is a strong indication that the credit assignment problem pertains to how a machine learning model interpreted the input to give a correct or incorrect prediction.

From this description, it is clear that the credit assignment problem is not unique to reinforcement learning because it is difficult to interpret the decision-making logic that caused any modern machine learning model (e.g. deep neural network, gradient boosted tree, SVM) to reach its conclusion. Why are CNNs for image classification more sensitive to imperceptible noise than to what humans perceive as the semantically obvious content of an image? For a deep FFN, it's difficult to separate the effect of a single feature or interpret a structured decision from a neural network output because all input features participate in all parts of the network. For an RBF SVM, all features are used all at once. For a tree-based model, splits deep in the tree are conditional on splits earlier in the tree; boosted trees also depend on the results of all previous trees. In each case, this is an almost overwhelming amount of context to consider when attempting an interpretation of how the model works.

CAP is related to backprop in a very general sense because if we knew which neurons caused a good/bad decision, then we could leverage that information when making weight updates to the network.

However, we can distinguish CAP from backpropagation and gradient descent because using the gradient is just a specific choice of how to assign credit to neurons (follow the gradient backwards from the loss and update those parameters proportionally). Purely in the abstract, imagine that we had some magical alternative to gradient information and the backpropagation algorithm and we could use that information to adjust neural network parameters instead. This magical method would still have to solve the CAP in some way because we would want to update the model according to whether or not specific neurons or layers made good or bad decisions, and this method need not depend on the gradient (because it's magical -- I have no idea how it would work or what it would do).

Additionally, CAP is especially important to reinforcement learning because a good reinforcement learning method would have a strong understanding of how each action influencers the outcome. For a game like chess, you only receive the win/loss signal at the end of the game, which implies that you need to understand how each move contributed to the outcome, both in a positive sense ("I won because I took a key piece on the fifth turn") and a negative sense ("I won because I spotted a trap and didn't lose a rook on the sixth turn"). Reasoning about the long chain of decisions that cause an outcome in a reinforcement learning setting is what Minsky 1963 is talking about: CAP is about understanding how each choice contributed to the outcome, and that's hard to understand in chess because during each turn you can take a large number of moves which can either contribute to winning or losing.

I no longer have access to a university library, but Schmidhuber's Minsky reference is a collected volume (Minsky, M. (1963). Steps toward artificial intelligence. In Feigenbaum, E. and Feldman, J., editors, Computers and Thought, pages 406–450. McGraw-Hill, New York.) which appears to reproduce an essay Minksy published earlier (1960) elsewhere (Proceedings of the IRE), under the same title. This essay includes a summary of "Learning Systems". From the context, he is clearly writing about what we now call reinforcement learning, and illustrates the problem with an example of a reinforcement learning problem from that era.

An important example of comparative failure in this credit-assignment matter is provided by the program of Friedberg [53], [54] to solve program-writing problems. The problem here is to write programs for a (simulated) very simple digital computer. A simple problem is assigned, e.g., "compute the AND of two bits in storage and put the result in an assigned location. "A generating device produces a random (64-instruction) program. The program is run and its success or failure is noted. The success information is used to reinforce individual instructions (in fixed locations) so that each success tends to increase the chance that the instructions of successful programs will appear in later trials. (We lack space for details of how this is done.) Thus the program tries to find "good" instructions, more or less independently, for each location in program memory. The machine did learn to solve some extremely simple problems. But it took of the order of 1000 times longer than pure chance would expect. In part I of [54], this failure is discussed and attributed in part to what we called (Section I-C) the "Mesa phenomenon." In changing just one instruction at a time, the machine had not taken large enough steps in its search through program space.

The second paper goes on to discuss a sequence of modifications in the program generator and its reinforcement operators. With these, and with some "priming" (starting the machine off on the right track with some useful instructions), the system came to be only a little worse than chance. The authors of [54] conclude that with these improvements "the generally superior performance of those machines with a success-number reinforcement mechanism over those without does serve to indicate that such a mechanism can provide a basis for constructing a learning machine." I disagree with this conclusion. It seems to me that each of the "improvements" can be interpreted as serving only to increase the step size of the search, that is, the randomness of the mechanism; this helps to avoid the "mesa" phenomenon and thus approach chance behaviour. But it certainly does not show that the "learning mechanism" is working--one would want at least to see some better-than-chance results before arguing this point. The trouble, it seems, is with credit-assignment. The credit for a working program can only be assigned to functional groups of instructions, e.g., subroutines, and as these operate in hierarchies, we should not expect individual instruction reinforcement to work well. (See the introduction to [53] for a thoughtful discussion of the plausibility of the scheme.) It seems surprising that it was not recognized in [54] that the doubts raised earlier were probably justified. In the last section of [54], we see some real success obtained by breaking the problem into parts and solving them sequentially. This successful demonstration using division into subproblems does not use any reinforcement mechanism at all. Some experiments of similar nature are reported in [94].

(Minsky does not explicitly define CAP either.)

Improve this answer
$\endgroup$
1
$\begingroup$

An excerpt from Box 1 in the article "A deep learning framework for neuroscience", by Blake A. Richards et. al. (among the authors is Yoshua Bengio):

The concept of credit assignment refers to the problem of determining how much ‘credit’ or ‘blame’ a given neuron or synapse should get for a given outcome. More specifically, it is a way of determining how each parameter in the system (for example, each synaptic weight) should change to ensure that $\Delta F \ge 0$. In its simplest form, the credit assignment problem refers to the difficulty of assigning credit in complex networks. Updating weights using the gradient of the objective function, $\nabla_WF(W)$, has proven to be an excellent means of solving the credit assignment problem in ANNs. A question that systems neuroscience faces is whether the brain also approximates something like gradient-based methods.

$F$ is the objective function, $W$ are the synaptic weights, and $\Delta F = F(W+\Delta W)-F(W)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.