<jupyter_start><jupyter_text>Computational Learning Theory - Notes> A short summary of Computational Learning Theory.- toc: true - badges: true- comments: true- categories: [machine-learning, computational-learning-theory]- image: images/chart-preview.png  AboutThere are good and bad practices for human learning. Highlighting interesting quotes in a book usually makes us feel productive in the moment but, let's be honest, doesn't help much in terms of learning. Taking notes, on the other hand, is a much more effective way of interiorizing information and storing it in long-term memory, especially if we translate concepts with our own words instead of just copying a text.The same is true for learning algorithms, not the part about taking notes but the fact that there ar good and bad methods for learning. Computational Learning Theory (also known as Statistical Learning Theory) is **a branch of computer science focused on understanding how computational learning can happen efficiently and effectively, as well as discovering different impediments to learning**.This document contains my notes on Computational Learning Theory.  Is bias always a bad thing?Bias usually has a very negative connotation, often thought of as prejudice and we are encouraged to always keep an open mind.But don't confuse an open mind with an empty mind. We often learn by building new ideas on top of other ideas we have learned in the past. Keeping an open mind means that we have to remember that some of our foundational building blocks might be wrong and need to be corrected. But constantly throwing away previous knowledge would make learning practically impossible.**Pigeon superstition**One of B.F. Skinner's classical experiments supposedly showed "superstitious" behavior by pigeons. The experiment consisted in providing food to hungry pigeons in a cage through a mechanism that was guaranteed to be completely independent from any behavior by the pigeons. > "If a clock is now arranged to present the food hopper at regular intervals with no reference whatsoever to the bird's behavior, operant conditioning usually takes place. The bird tends to learn whatever response it is making when the hopper appears. The response may be extinguished and reconditioned. The experiment might be said to demonstrate a sort of superstition. The bird behaves as if there were a causal relation between its behavior and the presentation of food, although such a relation is lacking". *<NAME>. (1948). 'Superstition' in the pigeon. Journal of Experimental Psychology, 38(2), 168–172.*Let's say one of the pigeons was pecking on a prticular stain on the bottom of the cage when the first round of food was released. According to Skinner, the pigeon was then more likely to repeat this same behavior which, in turn, also made it more likely for the pigeon to be found pecking on the stain when the next round of food was released.Amusingly, each pigeon showed a different type of behavior that was reinforced (walking around the cage in a specific direction, bobbing the head, etc.) as if the behavior was causing more food to be released. We know that this is not the case, because the food was being released at regular pre-defined intervals.This can then be compared to different forms of human superstition. Have you or anybody you known ever had a special ritual at home before every game of our favorite football team? =D**Rats and selective association**The phenomenon above can be compared to the behavior of rats as studied by Garcia and Koelling in 1966. Imagine rats going for their regular snack. Some of the rats were then induced to feel ill through an injection or radiation. As could be expected these rats then avoided food with similar taste or smell in the future.Another batch of rats was administered a mild electrical shock in the foot. Interestingly, these rats did not show aversion to the food or water, but instead to an audiovisual cue that always happened while they were eating or drinking. This experiment is widely known as one of the first proofs of the so-called Selective Association Effect. This is related to the concept of biological constraints disccused by students of Skinner. Apparently some animals naturally resist certain types of conditioning, as if they had some kind of built in prior knowledge that some types of relationships could not causal. **Inductive bias**This takes us to the concept of inductive bias, which can be described as the set of assumptions or prior knowledge that biases learning by setting restrictions or constraints to the learning process. In our example, the rats seem to be biased towards detecting certain types of patterns between taste or smell and their health, while ignoring other types of seemingly correlated events. This is a well known concept in machine learning. We often talk about models that have high bias or high variance. The second type of models tend to be more complex and are more flexible in the type of functions they can model. But this often makes them more difficult to interpret or prone to overfitting (they memorize the training data, which in this case can be compared to finding superstitious patterns that only apply to that particular set of data).By restricting the types of patterns we are looking for we can often make the learning process easier and also extract valuable insights from the trained model. Linear regression is a great example with well-known assumptions and very powerful applications.**Deductive vs Inductive reasoning**Just as a refresher, we can think about deductive and inductive reasoning as taking to different routes (often described as top-down or bottom-up approaches). On one hand (deduction) we start with general theories about how things should work, we develop a hypothesis that we can then confirm through experiments and specific observations.Deductive reasoning:- Theory -> Hypothesis -> Observations -> ConfirmationOn the other hand, we might start with specific observations which we then use to try to discover a pattern in those observations. These patterns that we discover can then lead us to a more generalized understanding of the world. Inductive reasoning:- Observations -> Pattern -> Tentative Hypothesis -> Theory  Statistical Learning TheoryIn statistics it is common to to have well-defined assumptions about the distribution of our data (e.g. Gaussians). In SLT we have no or very general assumptions. Is all learning equal?Intuitively it would seem that there are different ways of learning. More formally, we can separate learning by different levels:1. Reproductive learningIt could be argued that this first level is not learning at all. Basically, imagine a class where students are allowed to to take all of their notes to class. It would be possible for a student to create a table with all the information he needs without interiorizing the concepts. Once the exam starts he simply looks up the answers to his questions in the table. So he basically reproduces the information.The negative side is that we need to store all of the relevant information beforehand. This can in many cases be very difficult or even impossible. 2. Rule-based learningThis level of learning can be thought of as encoding the knowledge of experts. Imagine a medical application created to automatically diagnose different types of diseases. One way to do this would be to get input from a group of doctors and create a flow-chart with nodes for every single decision that could be made. Now we don't need to store the raw data or the observations with their corresponding labels as we would do in reproductive learning. Instead we keep all of these rules that can lead us to an answer.The problem with this approach is that it is also very difficult or even impossible to encode every single use case and the rules are often very brittle. 3. Creative learningHere past experience is combined in different ways to solve new problems. This can often be a much more powerful approach as we are not limited to only reproducing past observations or following rigid rules.The main issue here is that it can be quite difficult to explain why a decision has been made. > "If the true classifier is a halfspace, then we should be able to find a very precise separation line with only a few random examples."**1-nearest neighbor algorithm**In this extreme example we store all observations and their lables. Any new lable receives the label of the closest point. Two main conclusions we notice are:- This algorithm will always classify all training samples correctly. - This algorithm will also be able to approximate any smooth function, even where halfspace classifiers perform poorly.<jupyter_code>def true_classifier(point) :
    return int(point[0] >= 0)


def nearest_neighbor(train_set, test_point):
    closest_dist = float('inf')
    closest = -1

    for features, label in train_set:
        dist = sum([(p2-p1)**2 for p1,p2 in list(zip(features, test_point))])
        if dist < closest_dist:
            closest_dist = dist
            closest = label

    label = closest
    return label


def error_probability(train_set) :
    mistakes = 0
    no_test_points = 2000
    for i in range(0,no_test_points):
        point = (2*i/no_test_points - 1,)
        if true_classifier(point) != nearest_neighbor(train_set, point) :
            mistakes += 1
    return mistakes/no_test_points

train_inputs = [-1.0, -0.1, 0.1]
new_input = -0.0001
#-0.0010000000000000009

S = [((x_val,), true_classifier((x_val,))) for x_val in train_inputs]
error_S = error_probability(S)
new_point = (new_input,)
S.append( (new_point, true_classifier(new_point)) )

print(error_S, error_probability(S))
assert error_S < error_probability(S)<jupyter_output>0.0005 0.025
{'fraction_non_alphanumeric': 0.03721500869031796, 'fraction_numerical': 0.007974644719353849, 'mean_word_length': 4.583333333333333, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '182104', 'license': 'Apache-2.0', 'n_tokens_mistral': 2278, 'n_tokens_neox': 2138, 'n_words': 1467, 'path': '_notebooks/2021-03-09-computational-learning-theory.ipynb', 'repo_name': 'KalleBylin/bylin', 'size': '9788'}