How do we actually sample an action from a policy in policy gradient methods? Recently I started to look at policy gradient methods and policies are represented as functions with features for larger problems with many states. Many articles and pseudocodes of algorithms mention sampling an action from the policy, but it is unclear to me how.

Actions are something we do in the environment, like going left, right, etc... And functions take some feature values and parameters, make calculations, and 'spit out' some number. So how do we actually map that number to a certain action, and how do we know what action to take?

In those policy gradient algorithms, we typically have:

Input features $x(s)$ for any state $s$
A fixed action set $\mathcal{A}$ of a fixed size (in reinforcement learning (RL) it is often assumed that all actions are legal in all states. In some situations, like board games, we'll filter out illegal actions manually in a postprocessing step).
A function approximator $\pi(x)$ (often a neural network), which takes as input the features $x(s)$ of some state $s$, and produces as output a vector of probabilities, where the vector has a length equal to the size $\vert \mathcal{A} \vert$ of the action space.

Those bolded parts in the last point there are critical for your question. We do not normally have a function that "spits out some number" as you described, we typically have one that "spits out" multiple numbers; one for every action. Often, these numbers can also be directly interpreted as probabilities, because they are forced to all lie in $[0, 1]$ and sum up to $1$ (this is often done using a softmax layer at the end of a neural network for example).

Once you have such a vector of "probabilities", one for every action, it is relatively straightforward to sample from that. Just give every action a probability of being selected equal to its corresponding output.

Note that in some cases, people describe their function approximator as producing "logits" rather than "probabilities" as outputs. These are real-valued outputs which do not necessarily sum up to one, typically produced by a linear layer at the end of a neural network rather than a softmax layer (see e.g. AlphaGo Zero). It is then still implicitly assumed that we convert them into numbers that can be interpreted as probabilities through the application of a softmax, before sampling from it.


How exactly is the value of each node determined? Is it the same formula throughout the network? When it comes to neural networks, it's often only explained what abstract task they do, say for example detect a number in an image. I never understood what's going on under the hood essentially.

There seems to be a common structure of a directed graph, with values in each node. Some nodes are input nodes. Their values can be set. The values of subsequent nodes are then calculated based on those along the edges of the graph until the values for the output nodes are set, which can be interpreted a result.

How exactly is the value of each node determined? I assume that some formula is associated with each node that takes all incoming nodes as input to calculate the value of the node. What formula is used? Is the formula the same throughout the network?

Then I heard that a network has to be trained. I assume that such training would be the process to assign values to coefficients of the formulas used to determine the node values. Is that correct?

In layman's terms, what are the underlying principles that make a neural network work?

I will overly simplify ANNs in order to point how they work. Examples might not be 100% accurate.

In the simplest form, network is trained using the apriori information extracted from the ground truth. This basically means that ANN uses the relation between the input and output.

For instance, if you are to classify shrubs and trees, one of the input could be height and the other could be the width of the tree. Now, if you have only input and output layers, increasing height means increasing chance for the object to be a tree. Thus, input height would have a positive weight connecting to tree output and a negative weight to shrub output. However, as the plant gets wider, the chance of it being a shrub increases. Taller shrubs are wider than shorter ones. Thus input weight would have positive weight connecting to the shrub output. Finally, the chance of being a tree is not affected by the width and thus will have close to 0 weight between this input and output. This network will effectively work like a linear discriminant classifier.

Now instead of assigning weights by hand, you may use a learning algorithm that tries to adjust weights so that the output is correct when the series of input is supplied. Ideally this training algorithm should reach to the conclusion that we have made in the previous example. Most training algorithms are recursive. They supply the inputs multiple times, and in a simple sense, they reward pathways that are correct by increasing their weights and punishes pathways that are causing incorrect answer.

When hidden layers are used in a system, they would be able to correlate input on higher degrees. Thus, as the number of layers get higher, ANN learns the input set much better. However, this does not mean it gets better. If the ANN over fits the input set, it would be affected from the random noise that is in the dataset. This problem is generally referred as memorization. There are learning algorithms that try to minimize memorization and maximize generalization ability. But ultimately, the number of training samples should be high enough so that ANN cannot overfit to the data.


What are examples of good free books that cover the back-propagation algorithm? What are examples of good free books that cover the back-propagation used to train multilayer perceptrons? I've just started to learn about artificial neural networks, so I'm looking for books that cover the theoretical basics of back-propagation.

Deep Learning by Goodfellow et. al is a good book for anything related neural networks, and it's freely available online. Backpropagation is covered in Chapter 6.5.


How is the distance between pointers in Stochastic Universal Sampling determined? I'm studying about different selection methods in genetic algorithms. My question is about the Stochastic Universal Sampling (SUS) selection method. I know that each individual will occupy a segment of the line according to its fitness value and then equally spaced pointers will be placed over this line.
I want to know how the distance between pointers is determined. I have seen 1/6 and 1/4 as the distance between pointers. I want to choose the number of pointers dynamically according to the situation. I want to know what conditions or factors affect the determination of this distance. For example, when do we decide to choose 1/4 as distance? I want to know if it is possible to change the number of samples in each iteration according to different conditions or situations. If so, what are these conditions?

As originally conceived in James Baker's 1989 paper Reducing bias and inefficiency in the selection algorithm, Stochastic Universal Sampling accepts a population containing $N$ individuals, and a number of parents to sample, denoted $n$. Assuming fitness values are normalized so that they sum up to $N$, at each step, a new pointer is placed a step equal in size to the fraction $\frac{N}{n}$ ahead of the location of the previous pointer (and the location of the first pointer is set to a random value in the range [0, $\frac{N}{n}$) ). So, for example, if you want to sample 6 individuals from a population of size 10, you would make steps of size $\frac{10}{6}$, spacing your pointers at even intervals of $\frac{10}{6}$.

Modern implementations, like the one on Wikipedia sometimes do not document this fact clearly, although it is apparent what is intended if you already understand the method. They often write the step size as $\frac{F}{n}$, where $F$ is the total fitness of the population, without discussing its relation to the size of the population. The extra normalization step is actually not essential, so modern implementations generally seem to skip it.

So in summary, the step size $\frac{F}{n}$ used if fitness values of a population sum to $F$, and you want to select $n$ individuals. If you want to select more individuals, use a higher value for $n$. If you want to select fewer, use a lower value for $n$, which updates your step size accordingly.

Values of this parameter of $\frac{1}{4}$ or $\frac{1}{6}$ suggest that the implementation may be normalizing the sum of fitness values is being normalized to N, and then using the parameter as a multiplicative factor automatically. This is a fairly reasonable design. You could interpret these values as "Select $\frac{1}{4}$ of the population" and "Select $\frac{1}{6}$ of the population".

Note that this sort of bumps your question up a level: how do you pick the fraction of the population to keep? That question doesn't have a clean answer, and picking it is generally an art developed by experts through practice. It is very closely related to the exploration/exploitation tradeoff.

Some ways you might pick $n$:

Use a fixed value, for instance, keep half the population at each step. The exact proportion you will want to pick is not something you can know in advance. Expert practitioners can make effective guesses. Others will need to just try out different values using a technique like cross validation, and pick whichever one seems to work best.
You can use a value that changes over time. A common strategy for this would be to use one of the temperature schedules developed in the simulated annealing literature, and keep a portion of the population that was inversely proportionate to the temperature. That is, early on, you'd use a large $n$, and keep most of the population around (probably with mutations). Later, you'd use a small $n$ and keep only the best individuals around.
You could use a value of $n$ that changes in response to the fitness of the population. This is much like the adaptive learning rates used in some algorithms to train neural networks (most notably: the ADAM optimizer). When fitness levels have a lot of variety, use low values of $n$ to encourage more exploitation. When fitness levels are all within a narrow band, use high values of $n$ to encourage more exploration.


What is the general procedure to create an AI system that can detect fire in images? I have no experience with any kind of AI, but I really want to develop a system that can detect fire in images. I think I will need a labelled dataset with labels "fire" or "not fire", but I am not sure how I should proceed and which steps I need to take to develop this system.
So, what is the general procedure to create an AI system that can detect fire in images?
I heard about the Keras library, which could allow us to do this. How could I do this with Keras?

Many AI libraries allow the ability to feed them an Image, but others have to be modified to allow this.

Disregarding the information above, as it is just a notification, you can do this in many ways. Depending on the library you use, different methods give varying accuracy results.

The real questions are:

How complex do you want the NN to be?
Is this going to be commercial, or private?

For any of the answers above, you will have to find the best method that works for your needs. The more this matters to the world, the more complex it will have to be.


How to define states in reinforcement learning? I am studying reinforcement learning and the variants of it. I am starting to get an understanding of how the algorithms work and how they apply to an MDP.
What I don't understand is the process of defining the states of the MDP. In most examples and tutorials, they represent something simple like a square in a grid or similar.
For more complex problems, like a robot learning to walk, etc., how do you go about defining those states? Can you use learning or classification algorithms to "learn" those states?

The problem of state representation in Reinforcement Learning (RL) is similar to problems of feature representation, feature selection and feature engineering in supervised or unsupervised learning.

Literature that teaches the basics of RL tends to use very simple environments so that all states can be enumerated. This simplifies value estimates into basic rolling averages in a table, which are easier to understand and implement. Tabular learning algorithms also have reasonable theoretical guarantees of convergence, which means if you can simplify your problem so that it has, say, less than a few million states, then this is worth trying.

Most interesting control problems will not fit into that number of states, even if you discretise them. This is due to the "curse of dimensionality". For those problems, you will typically represent your state as a vector of different features - e.g. for a robot, various positions, angles, velocities of mechanical parts. As with supervised learning, you may want to treat these for use with a specific learning process. For instance, typically you will want them all to be numeric, and if you want to use a neural network you should also normalise them to a standard range (e.g. -1 to 1).

In addition to the above concerns which apply for other machine learning, for RL, you also need to be concerned with the Markov Property - that the state provides enough information, so that you can accurately predict expected next rewards and next states given an action, without the need for any additional information. This does not need to be perfect, small differences due to e.g. variations in air density or temperature for a wheeled robot will not usually have a large impact on its navigation, and can be ignored. Any factor which is essentially random can also be ignored whilst sticking to RL theory - it may make the agent less optimal overall, but the theory will still work.

If there are consistent unknown factors that influence result, and could logically be deduced - maybe from history of state or actions - but you have excluded them from the state representation, then you may have a more serious problem, and the agent may fail to learn.

It is worth noting the difference here between observation and state. An observation is some data that you can collect. E.g. you may have sensors on your robot that feed back the positions of its joints. Because the state should possess the Markov Property, a single raw observation might not be enough data to make a suitable state. If that is the case, you can either apply your domain knowledge in order to construct a better state from available data, or you can try to use techniques designed for partially observable MDPs (POMDPs) - these effectively try to build missing parts of state data statistically. You could use a RNN or hidden markov model (also called a "belief state") for this, and in some way this is using a "learning or classification algorithms to "learn" those states" as you asked.

Finally, you need to consider the type of approximation model you want to use. A similar approach applies here as for supervised learning:

A simple linear regression with features engineered based on domain knowledge can do very well. You may need to work hard on trying different state representations so that the linear approximation works. The advantage is that this simpler approach is more robust against stability issues than non-linear approximation
A more complex non-linear function approximator, such as a multi-layer neural network. You can feed in a more "raw" state vector and hope that the hidden layers will find some structure or representation that leads to good estimates. In some ways, this too is "learning or classification algorithms to "learn" those states" , but in a different way to a RNN or HMM. This might be a sensible approach if your state was expressed naturally as a screen image - figuring out the feature engineering for image data by hand is very hard.

The Atari DQN work by DeepMind team used a combination of feature engineering and relying on deep neural network to achieve its results. The feature engineering included downsampling the image, reducing it to grey-scale and - importantly for the Markov Property - using four consecutive frames to represent a single state, so that information about velocity of objects was present in the state representation. The DNN then processed the images into higher-level features that could be used to make predictions about state values.


How does the math behind heat map filters work? I am working on an app that generates heat/ thermal map given a picture. i have been able to get what i expected using python opencv builtin function cv2.applyColorMap(img, cv2.COLORMAP_JET). Everything works exactly as expected. But i want to understand how applyColorMap works at the back end. I am aware how several image filters (like image, edge filters) work by convolution / cross correlation with appropriate kernals, but i can't seem to pull the same concept for color maps.
For this question lets consider a color map where we want :

Brightest ones: (RED COLORED)

MEDIUM INTENSITY ONES: (YELLOW COLORED)

LOW INTENSITY ONES: (BLUE COLORED)

What i have done:

I tried dividing the pixels into 3 categories and replaced each pixel with the either of the colors (RED, YELLOW, BLUE ) depending upon it's value from gray scale image( 0-255).
This approach had a problem that there were solid 3 colors in the image with no variation in intensity of the individual color while in a good heat map there is blend of colors ( it decreases or increases ) based upon the intensity . I want to achieve that effect. I would appreciate any help or any lead to understand how heat maps work .

About your question concerning ColorMaps:
A cv2 ColorMap is basically just a lookup table which directly maps the intensity values of the input image to a predefined RGB color. In its essences it is exactly what you did by categorizing and associating with a specific color value.

Most of the cv2 ColorMaps just have a little more detail, most of them have either 64( "Rainbow", "Hot", ...) or 256 ("Jet", "Magma", ...) steps, some like "Winter" have 11. They come from the GNU Octave or Matlab color palettes.

If you really want to build this lookup table yourself the easiest way to achieve a high level of granularity for the individual steps is to use the HSV color space

import numpy as np
import cv2

N_STEPS = 20
h = np.linspace(0, 180, N_STEPS, endpoint=False) # cv2 Hue range is [0, 179]
s = np.ones_like(h)*255   # cv2 saturation range is from [0, 255]; adjust it to your liking
v = np.ones_like(h)*255   # cv2 value range is from [0, 255]; adjust it to your liking
hsv_colormap = np.dstack([h,s,v])

rgb_colormap = cv2.cvtColor(np.uint8(hsv_colormap), cv2.COLOR_HSV2RGB)

IMG_SIZE = 100
#intensities = np.random.random((IMG_SIZE,IMG_SIZE)) # from 0 to 1
intensities = np.array([np.linspace(0,1, IMG_SIZE, endpoint=False), ]*IMG_SIZE) # from 0 to 1
intensity_indices = np.uint8(N_STEPS*intensities) # map insity ranges to discretized intervals

color_mapped_intensities = rgb_colormap[0,intensity_indices,:]
cv2.imshow('colormap', color_mapped_intensities)

cv2.waitKey(0)

you can play around with the Hue values ranges to feed into the color map

Happy color mapping to you !


How can I improve this word-prediction AI? I'm relatively new to AI, and I've tried to create one that "speaks". Here's how it works:
1. Get training data e.g 'Jim ran to the shop to buy candy'
2. The data gets split into overlapping 'chains' of three e.g ['Jim ran to', 'ran to the', 'to the shop', 'the shop to'...]
3. User enters two words
4. Looks through the chains to find if the two words have been seen before.
5. If they have, finds out which word followed it and how many times.
6. Work out the probability e.g: if 'or' followed the two words 3 times, 'because' followed the two words 1 time and 'but' followed it 1 time it would be 0.6, 0.2 and 0.2
7. Generate a random decimal
8. If the random decimal is in the range of the first word (0 - 0.6) pick that one or if it's in the range of the second word (0.6 - 0.8) pick that word or if it's in the range of the third (0.8 - 1) pick that word
9. Output the word picked
10. Repeat from 4 but with the new last two words e.g if the last words had been 'to be' and it picked 'or' the new last two words would be 'be or'.

It does work, but it doesn't stick to a particular topic. For example, after training with 800 random Wikipedia articles:

  In the early 1990s the frequency had a plastic pickguard and separate hardtail bridge with the council hoped that the bullet one replaced with the goal of educating the next orders could revert to the north island or string of islands in a new urban zone close to the west.

As you can see the topic changes many times mid-sentence. I thought of increasing the number of words it considered from two to three or four, but I thought it might start simply quoting the articles. If I'm wrong please tell me.

Any help is greatly appreciated. If I haven't explained clearly enough or you have any questions please ask.

Seems like recurrent neural networks (RNN) should work for your use case. An excellent introduction is available at: The Unreasonable Effectiveness of Recurrent Neural Networks


Why is my implementation of Q-learning not converging to the right values in the FrozenLake environment? I am trying to learn tabular Q learning by using a table of states and actions (i.e. no neural networks). I was trying it out on the FrozenLake environment. It's a very simple environment, where the task is to reach a G starting from a source S avoiding holes H and just following the frozen path which is F. The $4 \times 4$ FrozenLake grid looks like this
SFFF
FHFH
FFFH
HFFG

I am working with the slippery version, where the agent, if it takes a step, has an equal probability of either going in the direction it intends or slipping sideways perpendicular to the original direction (if that position is in the grid). Holes are terminal states and a goal is a terminal state.
Now I first tried value iteration which converges to the following set of values for the states
[0.0688909  0.06141457 0.07440976 0.05580732 0.09185454 0. 0.11220821 0.         0.14543635 0.24749695 0.29961759 0. 0.         0.3799359  0.63902015 0.        ]

I also coded policy iteration, and it also gives me the same result. So I am pretty confident that this value function is correct.
Now, I tried to code the Q learning algorithm, here is my code for the Q learning algorithm
def get_action(Q_table, state, epsilon):
    """
    Uses e-greedy to policy to return an action corresponding to state

    Args:
        Q_table: numpy array containing the q values
        state: current state
        epsilon: value of epsilon in epsilon greedy strategy
        env: OpenAI gym environment
    """
    return env.action_space.sample() if np.random.random() < epsilon else np.argmax(Q_table[state])

def tabular_Q_learning(env):
    """
    Returns the optimal policy by using tabular Q learning

    Args:
        env: OpenAI gym environment

    Returns:
        (policy, Q function, V function)
    """

    # initialize the Q table
    #
    # Implementation detail:
    # A numpy array of |x| * |a| values

    Q_table = np.zeros((env.nS, env.nA))

    # hyperparameters
    epsilon = 0.9
    episodes = 500000
    lr = 0.81

    for _ in tqdm_notebook(range(episodes)):
        # initialize the state
        state = env.reset()

        if episodes / 1000 > 21:
            epsilon = 0.1

        t = 0
        while True: # for each step of the episode
            # env.render()
            # print(observation)

            # choose a from s using policy derived from Q
            action = get_action(Q_table, state, epsilon)

            # take action a, observe r, s_dash
            s_dash, r, done, info = env.step(action)

            # Q table update
            Q_table[state][action] += lr * (r + gamma * np.max(Q_table[s_dash]) - Q_table[state][action])

            state = s_dash

            t += 1

            if done:
                # print("Episode finished after {} timesteps".format(t+1))
                break
        # print(Q_table)

    policy = np.argmax(Q_table, axis=1)
    V = np.max(Q_table, axis=1)

    return policy, Q_table, V

I tried running it and it converges to a different set of values which is following [0.26426802 0.03656142 0.12557195 0.03075882 0.35018374 0. 0.02584052 0.         0.37657211 0.59209091 0.15439031 0. 0.         0.60367728 0.79768863 0.        ]
I am not getting, what is going wrong. The implementation of Q learning is pretty straightforward. I checked my code, it seems right.
Any pointers would be helpful.

I was able to solve the problem.
The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $-0.00005$ on the learning rate lr, and subsequently Q-Learning also converged to the same value as value iteration.


Can TensorFlow, PyTorch, and other mainstream ML frameworks be used for research-grade work in AI? Many authors of research papers in AI (e.g. arXiv) write their neural networks from the ground-up, using low-level languages like C++ to implement their theories. Can existing open source frameworks also be used for this purpose, or are their implementations too limited?
Can, for example, TensorFlow be used to craft an original network architecture that shows improvements on existing benchmarks? Can original mathematical work be coded into a high-level framework like TensorFlow such that original research on network architectures/approaches be demonstrated in a paper?
A quick search reveals many papers using C++ in their implementation:

https://arxiv.org/pdf/1904.04174.pdf
https://arxiv.org/pdf/1701.03980.pdf
https://arxiv.org/pdf/2005.07039.pdf
https://arxiv.org/pdf/2007.14236.pdf
https://arxiv.org/pdf/1908.05858.pdf

Your statement that researchers build their network from the ground-up using C++ or some other low level library couldn't be further from the truth.
You could take a look at this analysis showing the popularity of these two frameworks in the top ML conferences. The following Figure is taken from there.

In CVPR-2020, for example, TensorFlow and pytorch combined for over 500 papers! Furthermore, because the two most active research entities (Google and Facebook) are backing these two frameworks, they are used in some of the most impactful research studies.

I want to give some reasons that support the popularity of these frameworks, but first I'm going to rephrase your question a bit:

Why use TensorFlow/Pytorch in python rather than build your model on your own using C++?

Note: The reason I rephrased the question is because TensorFlow and PyTorch both have a C++ APIs.
Why are these frameworks so popular in contrast to lower-level programming languages?
Some reasons are the following

Rapid prototyping. Languages link C++, have bloated syntaxes, require low-level operations (e.g. memory management) and cannot be run interactively. This means it takes someone much less time to create and test a model in python than it does in C++.

No need to re-invent the wheel. Some operations are common in most networks (e.g. backpropagation), why re-implement them? Other functionalities are hard to implement on your own (e.g. parallel processing, GPU computation). Do data scientists need to have such a strong technical background to research neural networks?

Open-source. They benefit from being opensource and can offer a great deal of tools at your disposal for building neural networks. You want to add batchnorm to your network? No worries, just import it and add it in a single line! Also, they offer the perfect opportunity for sharing pretrained models.

They are optimized. These frameworks are optimized to run as fast as possible on GPUs (if available) or CPUs. It would be virtually impossible for someone to write code that runs as fast on his own.


How can we calculate the gradient of the Boltzmann policy over reward function? I'm struggling with an inverse reinforcement learning problem which seems to appear quite often around the literature, yet I can't find any resources explaining it.

The problem is that of calculating the gradient of a Boltzmann policy distribution over the reward weights $\theta$:

$$\displaystyle\pi(s,a)=\frac{\exp(\beta\cdot Q(s,a|\theta))}{\sum_{a'}\exp(\beta\cdot Q(s,a'|\theta')}$$

The $\theta$ are a linear parametrization of the reward function, such that

$$\displaystyle R = \theta^T\phi(s,a)$$

where $\phi(s,a)$ are features of the state space. In the simplest of the case, one could take $\phi_i(s,a) = \delta(s,i)$, that is, the feature space is just an indicator function of the state space.

A lot of algorithms simply state to calculate the gradient, but that doesn't seem that trivial, and I'm not managing to infer from the bits of code I found online.

Some of the papers using this kind of methods are Apprenticeship Learning About Multiple Intentions (2011), by Monica Babes-Vroman et al, and MAP Inference for Bayesian Inverse Reinforcement Learning (2011), by Jaedeug Choi et al.

The main point here is that you can write $Q(s, a|\theta) = R = \theta^\top \phi(s, a)$. For more details on this, you can read up on Policy Gradients (Chapter 13) from the 2nd edition of the Sutton and Barto book (in fact the expression you're looking for is equation 13.9)

For simplicity, I'm setting $\beta=1$, but you can always put it in once you get the idea. Therefore, the expression for $\pi(s,a,\theta)$ (I'm including $\theta$ here to make the dependence of $\pi$ explicit) is now:
$$
\pi(s,a,\theta) = \frac{exp(\theta^\top \phi(s, a))}{\sum_{a'} exp(\theta^\top \phi(s, a'))} = \frac{A}{B}
$$

Also, it is standard to compute $\nabla_\theta\log \pi(s,a,\theta)$ instead of $\nabla_\theta \pi(s,a,\theta)$ (although you totally can), so I'll go ahead and do that. To differentiate $\log \pi(s,a,\theta)$ with respect to the parameters, $\theta$, let's do some calculus:
$$
\nabla_\theta \log \pi(s,a,\theta) = \nabla_\theta \log \frac{A}{B} = \nabla_\theta \log A - \nabla_\theta \log B \\
= \nabla_\theta \left[ \theta^\top \phi(s,a) \right] - \nabla_\theta \left[ \log \sum_{a'} exp(\theta^\top \phi(s, a')) \right] \\
= \phi(s,a) - \frac{1}{\sum_{a'} exp(\theta^\top \phi(s, a'))} \sum_{b} exp(\theta^\top \phi(s, b)) \phi(s,b) \\
= \phi(s,a) - \sum_{b} \frac{exp(\theta^\top \phi(s, b))}{\sum_{a'} exp(\theta^\top \phi(s, a'))} \phi(s,b) \\
= \phi(s,a) - \sum_{b} \pi(s,b,\theta) \phi(s,b)
$$

Therefore, you can write $\nabla_\theta\log \pi(s,a,\theta) = \phi(s,a) - \sum_{b} \pi(s,b,\theta) \phi(s,b)$


Can models get 100% accuracy on solved games? I had a question today that I feel it must have an answer already, so I'm shopping around.
If we ask a model to learn the binary OR function, we get perfect accuracy with every model (as far as I know).
If we ask a model to learn the XOR function we get perfect accuracy with some models and an approximation with others (e.g. perceptrons).
This is due to the way perceptrons are designed -- it's a surface the algorithm can't learn. But again, with a multi-layered neural network, we can get 100% accuracy.
So can we perfectly learn a solved game as well?
Tic-tac-toe is a solved game; an optimal move exists for both players in every state of the game. So in theory our model could learn tic-tac-toe as well as it could a logic function, right?

So can we perfectly learn a solved game as well?

The short answer is yes. If your model has enough complexity it can theoretically learn any behavior you want.

So in theory our model could learn tic-tac-toe

Tic Tac Toe has already been solved. Another popular game that has been solved is Checkers, by the algorithm Chinook.
To be more specific, in Reinforcement Learning we make the assumption that any decision making process can be modeled as an MDP (Markov Decision Process). Once there, there are a host of different methods like Q-Learning and TD that theoretically converge towards the optimal policy - the one the plays perfectly.
Now, just because it is theoretically possible doesn't mean it will always empirically work. In games that are very complex and have a large state space it is extremely difficult to perfectly solve. This is because the only feasible way to go about them is to approximate and getting perfect play even in small edge cases becomes much more difficult as a result.
If you want to learn more about this topic I would highly recommend this series RL Course by David Silver


Should I use my redundant feature as an auxiliary output or as another input feature? For example, given a face image, and you want to predict the gender. You also have age information for each person, should you feed the age information as input or should you use it as auxiliary output that the network needs to predict?

How do I know analytically (instead of experimentally) which approach will be better? What is the logic behind this?

For extra input that does not matter, you should not input it to the network.

  Feature selection, the process of finding and selecting the most
  useful features in a dataset, is a crucial step of the machine
  learning pipeline. Unnecessary features decrease training speed,
  decrease model interpretability, and, most importantly, decrease
  generalization performance on the test set.

Source: A Feature Selection Tool for Machine Learning in Python

As the source says, unnecessary features decreases accuracy and training speed. Moreover, they have no mapping to the labels, so they won't end up being used. They are unnecessary and adding them will only cause you trouble. Hope this helps you and have a nice day!


What does the term "closed expression" mean? In the field of logic systems there is a property for reasoning algorithms called incompleteness or incompletion. In this context the phrase "any closed expression that is not derivable inside the same system" appeared. My question is what means "closed expression that is not derivable".

A closed expression refers to a formula which has no free variables [1]. This is also called sentence. In a logic system you have a set of axioms which are sentences and rules which state how to derive a sentence from this [2]. If a sentence can be derived from the axioms, this means that the axioms entail this sentence. If a sentence is not derivable, it is not entailed by the axioms.


How can we compare the intelligence of AI systems? One way of ranking human intelligence is based on IQ tests. But how can we compare the intelligence of AI systems?

For example, is there a test that tells me that a spam filter system is more intelligent than a self-driving car, or can I say that a chess program is more intelligent than AlphaGo?

There are different ways to compare different kinds of AI techniques.

As a starting point, be aware that "AI System" can mean an incredibly broad range of things. In popular culture, we usually think of a deployed system that uses AI techniques. These systems can only be compared on the basis of their performance, and their performance may have relatively little to do with AI itself (e.g. their behaviours might be more strongly affected by user interface decisions, not the AI techniques under the hood).

In contrast, AI researchers are usually more interested in comparing the performance of different AI algorithms at solving the "AI-ish" parts of the problem a fully developed system aims to solve. A common way to do this is with benchmark problems. For example, in machine learning it is common to compare two algorithms by running each of them on a commonly used dataset, and comparing the performance of the models they create. In AI Planning, it is common to issue planning challenges to the community, and compare the quality of the plans on several different axes (e.g. average wait times, maximum wait times, whether goals were accomplished, how long it took to create a plan, etc.).

There is no generally agreed upon way to compare techniques across different areas of AI, but a commonly adopted approach is the Turing Test. In the Turing Test, we care only about the ability of the system to mimic something like human intelligence. It's fair game to ask about planning problems, or learning problems, or other topics, so you could in some sense judge one technique to be better than another. However, most judgements made in the Turing Test are subjective, so it's not clear that it really solves the problem you posed.


What are the known ways to test AI black boxes? Is there any conmprehensive paper or site that describes an overview of the known black box testing techniques?

On the applicability of Artificial Intelligence in Black Box Testing (Khanna, 2017) might be a good place to start. It classifies some black box testing techniques based on the AI branch it belongs to.


Using graph searching to solve peg solitaire? Problem:
I've been reading research papers on how to solve a peg solitaire using graph searching, but all the papers kind of assume you know how to do the reduction(polynomial time conversion) from the peg solitaire to the graph, which I do not, but this is how I assumed it was done.
For those of you unfamiliar:
https://www.youtube.com/watch?v=Bt6GpGvUNeQ

The goal is to only have one peg on the board and you get rid of pegs by jump one peg over another. A peg can only jump if the it's jumping into an empty space as shown in the picture above.

What I've tried:
I had the idea of converting the problem to a tree where each node represents the state after an action is taken and each edge represents the action taken. So the root node would the initial state which is the board shown above then it's children would be the state of the board after any of the possible legal actions that can be taken. So for example:

Then the children of each of those nodes would be the possible moves for them and you can find a solution once you've reached depth 31 in the tree because there are 32 pegs and you win the game where there's only 1 left.

Is this the right approach? It feels a little too abstract because I'd have to represent the edges as peg moves, but that's weird cause they're usually numbers or constraint.

Your approach seems reasonable to me. The edges do not necessarily have to be numbers, but, if you wish, you could also encode the actions as numbers. For example, the weight of an edge could represent the "cost" of the corresponding action. If there's no natural cost associated with an action, then you can add a unit cost for each action.


What is the best measurement for how good an action of a reinforcement learning agent really is? Even when we get a valuable reward signal after every single action, this immediate reward only approximates the short term goodness of the action.

To consider the long term effect of an action, we can use the return of an episode, the action value function $Q(s,a)$ or the advantage $A(s,a) = Q(s,a) - V(s)$. However, these measures do not rate the action in isolation but take all the following actions until the end of an episode into account.

Are there ways to more precisely approximate how good a single action really is considering its short and long term effects?

Are there ways to more precisely approximate how good a single action really is considering its short and long term effects?

To understand the short-term effects of an action, just take each of the available actions from the current state and observe the reward for each of them. The action that gives you the highest immediate reward is the best action. However, note that the reward function may change or could be stochastic. In those cases, you may need to estimate the best action e.g. by executing it multiple times.

If you want to know the action that gives you the highest amount of reward in the long run (i.e. that gives you the highest return), then you can use one of the available RL algorithms, which were invented exactly to solve this problem. Basically, you're asking us what is the best RL algorithm. It depends on the problem, as usual.

If you want to know the effects of an action in e.g. $n$ steps ahead, then you can probably formulate this problem as a truncated version of the typical reinforcement learning problem. In practice, you probably can achieve this by changing the discount factor so that the next $n$ rewards are more valuable (or are the only ones considered) than the rewards after $n$ steps. If you aren't familiar with discount factors, I encourage you to have a look at this concept from a reference book.

Note that, in this answer, I am just trying to give you the idea and intuition behind a possible answer to your question (also because your question isn't really suited to provide more detailed or rigorous answers).


Convolutional Sequence to Sequence Learning kernel parameters I am reading the paper Convolutional Sequence to Sequence Learning by Facebook AI researchers and having trouble to understand how the dimensions of convolutional filters work here. Please take a look at the relevant part of the paper below.

Let's say the input to the kernel X is k*d (say k=5 words of d=300 embedding dimenisonality). Therefore the input is 5*300. In a computer vision task a kernel would slide over parts of the image, in NLP you usually see kernel taking up the whole width of the input matrix. So I would expect kernel to be m*d (e.g. 3*300 - slide over 3 words and look at their whole embeddiings).

However, the kernel here is of dimensionality 2d x kd which in our hypothetical example would be 600*1500. I don't understand how this massive kernel would slide over an input that is by far lower dimensional (5*300). In computer vision you could zero-pad the input, but here zero-padding would basically turn the input matrix into mostly zeros with only a handful of meaningful numbers.

Thanks for shedding some light on it!

They are doing a matrix multiplication: consider $y = Ax, y \in \mathbb{R}^m, x \in \mathbb{R}^n, A \in M_\mathbb{R}(m,n)$. In the paper $x$ is a concatenation of $k$ elements of $\mathbb{R}^d$, so $x$ is long $kd$; $y$ is long $2d$.


Can we apply ANN to cryptography? If a group of computers have identical ANN with exact same set of learning data and all have functionality of encryption and decryption, would there be any way for interceptors to interpret encrypted data?

+
Applying the fact that people with more background information obtaining more knowledge from same source than those who don't, would it be possible for ANN to interpret data based on their access level?
(Each level has different amount of "background information")

For example, if there is a encrypted text file, a computer with highest access level would fully decrypt the data to a plain text while a computer with lower access level would only decrypt half of them (and this decrypted half becomes a plain text).

If above methods can exist, what would be their pros and cons compared to pre-existing technologies? (AES, Blowfish and so on)

I know that in order to discuss your question, I must have a background in cryptography, which I don't have! But there is something that I know for sure:

First of all, a simple search gave me this. It might help.
To lots of us, ANN looks like a magic wand which can turn almost everything into anything. But the point is, ANN is only a ML algorithm, but absolutely a powerful one. You should be aware that there are random and multiple weight initializations in ANNs, and this means a fairly stochastic behavior of your network, which vanishes only in shallow networks with high amount of training data. Your network's specifications are even likely influenced by the order of feeding the instances in the training phase. So if what I think of the encryption/decryption process "certain rules for message transformation" is true, then a stochastic network is indeed a sophisticated option (but according to scientists in neural cryptography research area, completely possible)
You're probably thinking of auto-encoding networks, one kind that maps X to X and has a bottle neck, such that if successfully trained, it has developed the power of reducing the number of data features from say 10'000 to 500, and then successfully retrieving the original data with 10'000 features from that 500-features one; such that If I feed a new instance to a trained auto-encoding network, grab it in the bottle neck layer and send it to you, you must be able to feed the message to the bottle neck layer and receive the full decoded message from the output layer. However there's (always) a catch! and that is you need a really "BIG" dataset to train your deep network. Besides you cannot expect it to work well on every kind of data after being trained by a fixed amount. for example your network cannot successfully retrieve an image of a dog, if all you've fed in the training phase was cats' and lizards' images. So can you guarantee that new messages to be encoded have the same type as the ones in the training set?! If no, then you might also take this challenge into account.


Is intersection of labels acceptable in computer vision? I have a dataset, where objects are very close to each other. So, the question is: what is the best approach to label them?
There are two possible options:

mark objects so that they will not intersect (it is difficult, surroundings are not included in the label area)
mark a larger area of objects, but labels will intersect

What is more practical?

In my opinion, the second option will be more general. You can refer to some famous datasets for object detection task such as COCO or Pascal VOC, they usually accept the intersect annotations. As the image below, image from this link where they process the annotation of COCO dataset.
I think the reason is that the model will be easier to separate the intersect patterns in the bounding box than interpolate the missing patterns of the object to understand it


Is Kaggle a good place to find projects in ML to work on? I am starting to learn machine learning (ML). I'm thinking about starting to take part in some projects in ML.

Is Kaggle is a good place to find projects in ML to work on?

Yes, Kaggle is a great place to start working on ML projects.
You will start using ML algorithms (at first, using scikit-learn or any other ML library of your choice), learn the concepts of cross-validation (very important concept). You will cope with imbalanced classes, various size of datasets. Moreover, you will be able to ask questions and receive feedback from the community.

It's a great place to start and keep learning, but do not limit yourself at using ML algorithms blindly. Try to understand them, even re-write them if you want.

But it's definitely a lot of fun and there are always several competitions running so you can choose whatever dataset you prefer.


Would this work to prevent forgetting: train a neural net with N nodes. Then, add more nodes and stop training the original nodes Would this work at all?

Idea is to start training a neural net with some number of nodes. Then, add some new nodes and more layers and start training only the new nodes (or only modifying the old nodes very slightly). Ideally, we would connect all old nodes to the new layer added since we might have learned many useful things in the hidden layers. Then repeat this many times.

Intuition is that if the old nodes give bad information the new layer of nodes will weight the activations of old nodes close to zero and learn new/better concepts in the new nodes. The benefit is that we will keep old knowledge forever.

Caveat is that the network can still temporarily "forget" concepts if a new layer weights old information close to zero, but it can potentially remember it again too.

If this completely fails, I'm curious if there's some known way to prevent a neural network from forgetting concepts it learned.

Per Neil's line of questioning:

If you're doing offline, supervised or reinforcement learning, where you have the dataset and decide what to show to the network next, there's no reason to do this. It's better to just adjust your training to show rare examples to the network more often.
If you're doing online reinforcement learning, then the agent typically controls which examples it sees next through its choice of actions. Increasing the agent's exploration rate will cause it to see a more diverse set of examples, but these examples are also less likely to be useful for solving the task the agent is working on.
If you're doing supervised, online, learning, and you don't control the order in which examples appear, it might be useful to freeze some of the weights, but it might be better, and would certainly be simpler, to increase the learning rate for rare classes instead (in effect, showing the network a given rare example repeatedly when it does show up, so that it takes longer to forget it).


Is there any good source for when the pole actually starts all the way at the bottom, in the cartpole problem? There are a lot of examples of balancing a pole (see image below) using reinforcement learning, but I find that almost all examples start close to the upright position.

Is there any good source (or paper) for when the pole actually starts all the way at the bottom?

It is difficult to prove a negative, but I doubt there will be a paper on that specific problem. It should be relatively easy to adjust the environment or write a new one that does this if you wished though.

A very similar environment that does have a lot more written about it is Acrobot, which does have a OpenAI Gym version. Instead of a cart on a track with forces applied and a free join to the pole, there is a longer pole fixed to a free joint, with an active joint in the middle (that the agent can apply forces to). It can be thought of as a very simple model of an acrobat on a trapeze swing (with poles instead of chains, so the swing is stable balanced upside-down)

The degrees of freedom and difficulty of the Acrobot task are similar to CartPole - I would rate it as a harder problem overall, but if you started CartPole with the pole hanging down in fact the two problems are very similar. Usually the joint motor is made too weak to achieve the goal of balancing in a single clean action, and the agent must learn to build momentum over a few swings, before moving to the balance point. That also makes both your alternate start position CartPole and Acrobot similar to MountainCar.

For a low-effort look at a very similar problem you could try Acrobot. Otherwise you will likely need to do some custom work on CartPole.


Is an SVM the same as a neural network without a hidden layer? A neural network without a hidden layer is the same as just linear regression.

If I then use squared hinge loss and encoporate the l2 regularisation term, is it fair to then call this network the same as a linear SVM?

Going by this assumption, then if I need to implement a multiclass SVM, i can just have n output nodes (where n is the number of classes). Would this then be equivalent to having n number of SVMs, similar to a one-vs-rest method?

If I then wanted to encoporate a kernel into my SVM, could I then use an activation function or layer prior to the final output nodes (where I compute loss and add regularisation) which would then transfer this data into another feature plane the same as that of an SVM kernel?

This is my current hunch, but would like some confirmation or correction where my understanding is incorrect.

First, what makes the neural network different than linear regression is the non-linearity (activation function), not the number of layers. So, a neural network with $n$ layers with no non-linearities is still the same as linear regression. Second, SVM finds the hyperplane of maximum margin. You are not guaranteed to find that hyperplane that has maximum margin with a neural network (using non-linearities).


What qualifies a Voice Assistant to be an AI? If some claim they are doing Artificial Intelligence by providing a Voice Assistant, what shall we expect from this Voice Assistant for the claim of doing "Artificial Intelligence" to be correct?

Examples of potential qualifications:

is replying "Hello" to "Hello" enough?
is repeating any word you said enough?
is identifying you by your voice enough?
shall it support corrections? "what is my favorite color?"/"red!"/"no, it's blue. What is my favorite color?"/"blue!"
shall it support emotions? "I would offer you better service if you could say thank you sometimes"
shall it support self-awareness? "Dear master, may I ask you a question about me?"
etc.

Usually, this sort of encoded 1to1 response is not considered to be AI or ML. This is because a chatbot that simply responds to a designated string with a response string is hard programmed(for the most part). A lot of companies/individuals have tried to package this as true AI but it is not.

One of the simpler examples of an AI chatbot system is a model that does some sort of tree-search or similar for the input. This is more often than not, extremely naive but would be an example of a true AI system.

So to more concisely answer your question, the categorization as an AI chatbot would have less to do with the responses, and more to do with how the model selects/comes up with those responses.


Ideas on how to make a neural net learn how to split sequence into sub sequences How can I train a neural network to recognize sub-sequences in a sequence flow?

For example: Given the sequence 111100002222 as an input sample from a stream, the neural network would recognize that 1111 , 0000 , 2222 are sub sequences (so 111100 would not be a valid subsequence) and so on for ~ 50 to 100 different subsequences.

There is no particular order in which the subsequence would appear in the flow.
No network architecture restriction.
Subsequences are of variable length.

General concepts, ideas, and theory are welcome.

The problem in the original question is akin to that of inducing a context-sensitive grammar (CSL), except that it is harder because a CSL is assumed to be composed of fixed-length subsequences. It is probably closer to the problem of inducing a Reber grammar, but that in turn seems like an overkill.

LSTMs are known to be able to learn both CSL and Reber grammars. However, I doubt that this is what you really need because of the following comment:

  [...] given an entire book where there is NO spaces anywhere, only characters (including special characters, like commas), in what way can we make the network learn the 'word boudaries' of this book.

This is called morphology induction, and it is a much harder problem than that of simple Reber grammar induction. Note that finding word boundaries is a special case of the problem of finding morpheme boundaries. There have been many attempts to solve this (also see this survey paper for more details and references).

Most approaches developed seem to rely on statistical principles (like MDL) and do not use neural networks (a counterexample using LSTMs). My intuition is that the extreme morphological variability across languages (ranging from Finno-Ugric languages with highly inflectional morphology to Sino-Tibetan languages with hardly any morphology at all) makes it hard to train neural networks in a language-agnostic way. However, you might have better luck if you focus on a single language.

Hope that helps.


What makes a machine learning algorithm a low variance one or a high variance one? Some examples of low-variance machine learning algorithms include linear regression, linear discriminant analysis, and logistic regression.
Examples of high-variance machine learning algorithms include decision trees, k-nearest neighbors, and support vector machines.
Source:

What makes a machine learning algorithm a low variance one or a high variance one? For example, why do decision trees, k-NNs and SVMs have high variance?

What this is talking about is how much a machine learning algorithm is good at "memorizing" the data. Decision trees, for their nature, tend to overfit very easily, this is because they can separate the space along very non-linear curves, especially if you get a very deep tree. Simpler algorithms, on the other hand, tend to separate the space along linear hyper surfaces, and therefore tend to under-fit the data and may not give very good prediction, but may behave better on new unseen data which is very different from the training data.


Selecting the right algorithm to predict disease from questions I'm trying to come up with the right algorithm for a system in which the user enter symptoms and we starts triggering questions related to that symptoms and his answers will result a disease which is related to the answer which is given by the user

Let's assume that the user entered the following input:

Symptom - Deafness

Q1. How long have you had a problem with deafness

A)From few days B)From few weeks to months C)More than month D)Since Birth

Q2. What was the onset of the deafness

A) Sudden B) Gradual

Now we have a knowledge base like if a user select option 1 from question 1 and option 2 form question 2 then we will give him some disease. But i need an algorithm which will give % of success in backend so that i can throw the results of disease for example if a user select option 2 from question1 and option 1 from question 2, then when we compare from our knowledge base there will be one set over there which has  option 1 from question 1 and option 2 from question 2 then its a "SOME" disease.. now if we compare from our knowledgebase and we found even 50% of the choices is resulting this disease we will throw that disease name.

NOW i am confused what algo should be use for this approach for ai.

There is no defined rules for choosing a machine learning algorithm to learn some type of pattern. However, there are some guidelines to help you better select an algorithm which will yield a higher probability of success.

Some important considerations are:

Number of features: This is the number of questions that each patient had to answer.
Number of instances: This is the number of patients that took your survey.
Number of output classes: This is how specific you want your diagnosis of the disease. Is this a yes/no, or a 5-stage progression.

The larger your feature space and the more output classes you have, the higher the complexity of your model. This is problematic because a more complex model will require more instances of data to learn the underlining patterns. You need to have a good balance between the number of examples you have in your dataset and the complexity of your model.

If you have limited data then you will want to stay very far away from deep learning. In such cases, I prefer to use shallow methods such as SVM, Naive Bayes or Random Forests. These techniques have been shown to be able to capture non-linear relationships. SVM is particularly powerful, you can use the kernel trick! This will transform your feature space into a space that makes the differentiation between the classes easier to distinguish. Do not underestimate the power of this algorithm.

If you have a very large dataset (i.e. 100,000 instances) then you will want to use deep learning. Recently, these techniques have been shown to outperform shallow machine learning algorithms in almost all categories where data is plentiful. You will want to start with a shallow neural network and then increase the complexity of your graph as you see fit. By adding additional nodes per layer, or by adding additional layers. Each node you add will increase the number of variables you need to tune, thus increasing the complexity of your model. If your data is expected to have some type of time dependency which often the case in medical data. Then you can use a long-short term memory neural network (LSTM). These are capable of capturing latent relationships. You can also try a stacked auto-encodder.


Is a decision tree less suitable for incremental learning than e.g. a neural net? I can recall that a professor once said that decision trees are not good for incremental learning, as they have to be rebuilt from the ground up if new training examples arrive.

Is this basically true? Quick googling just brought me to a lot of papers trying to fit decision trees into incremental learning
What other algorithms fall under this category?
Are Neural Nets good for incremental learning? What other algorithms would be good?

I will try to answer all three questions to the best of my ability.

Is this basically true? Quick googling just brought me to a lot of papers trying to fit decision trees into incremental learning.

The problem with decision trees in an online learning setting is that the model should be able to update when experiences (i.e. state, action, reward, new state) of the environment are collected. Any data that does not reflect the structure of the tree will cause the decision tree to fall apart and requires you to rebuild the model again. This is not necessarily a problem, but it is something you have to take into consideration when building a model.

What other algorithms fall under this category?

Other algorithms which assumes that the data is known beforehand (offline). For example K-NN or Learning Vector Quantization (LVQ). However it should be noted that these algorithms can be adapted to work in an online fashion.

Are neural nets good for incremental learning? What other algorithms would be good?

Neural networks can capture changes from online experiences fairly well. The reason is that each weight in such a network is adapted when a new experience comes in. The weights are adapted with regards to an error function and this allows to update the model relatively easy.

In 2016, Venkatesan, et al proposed a novel progressive learning technique for multi-class classification. You might want to look into this as the system that they use allows for online learning. Other techniques exists as well and should be found when googling for online learning methods.


How to implement an artificial network that outputs an integer within a range? The goal is to implement an artificial network that, based on training samples labelled with positive integers, outputs a positive integer.

Perhaps I am not searching for the correct thing but all the examples I have found have shown classifiers using a sigmoid function that outputs a fixed or floating point number within the range $<0 \to 1>$.

Any point in the right direction or python/toy code would be very appreciated!

First of all, sigmoid does not output 0 or 1, it outputs any real number in the range between 0 and 1.

Furthermore, normal neural networks doesn't output binary values, unless the output layer uses the step function as activation function (which is rare).

I'm not really sure if you want the NN to be a classifier or regressor, but it sounds like you want a regressor.

Regression is when you are interested in the value of the output nevron(s) itself. A simple example is if you want the network to predict the sum of two input neurons.

If you want to change the network from a classifier to a regressor you should probably reduce the number of neurons in the output layer to 1, and change the activation function of that neuron from softmax to the identity function (f(x)=x; which is the same as no activation function at all).

Hope this helps. Provide some more details if this didn't answer your question.


How do you perform a gradient based adversarial attack on an SVM based model? I have an SVM currently and want to perform a gradient based attack on it similar to FGSM discussed in Explaining And Harnessing
Adversarial Examples.

I am struggling to actually calculate the gradient of the SVM cost function with respect to the input (I am assuming it needs to be w.r.t input).

Is there a way to avoid the maths (I am working in python if that helps?)

A way to avoid computing the SVM loss by hand is to use a differentiable programming framework, such as JAX. These frameworks will automatically calculate gradients using automatic differentiation.

If you can write down the SVM loss using numpy operations then you can use the framework's tools to get a function which evaluates the gradient with respect to any argument.

In JAX this would look like:

import jax.numpy as np
def hinge_loss(x, y, theta):
    # x is an nxd matrix, y is an nx1 matrix
    y_hat = model(x, theta) # returns nx1 matrix, model parameters theta
    return np.maximum(0, 1 - y_hat * y)

hinge_loss_grad = grad(hinge_loss)
# hinge_loss_grad takes an x, y, theta and returns gradient of hinge loss wrt x


Is there a mathematical theory behind why MLP can classify handwritten digits? I'm trying to really understand how multi-layer perceptrons work. I want to prove mathematically that MLP's can classify handwritten digits. The only thing I really have is that each perceptron can operate exactly like a logical operand, which obviously can classify things, and, with backpropagation and linear classification, it's obvious that, if a certain pattern exists, it'll activate the correct gates in order to classify correctly, but that is not a mathematical proof.

The approximation theorem says you can approximate anything. But this is kind of meaningless in so far as you can do KNN and get an arbitrary approximation of your training data also.

Proving CNN correctly extract features is, I don't think possible. Or if it is, something involving VC theory is probably the best you can do.


How are kernel's input values initialized in a CNN network? I am currently learning about CNN's and I am confused on how filter/kernels are initialized beside their size? Say if you want a filter of 3x3 how are the inner values initialized a the start?

http://setosa.io/ev/image-kernels/

Do you just use those predefined image-kernels as a start? Or are they randomly initialized and retrained from backpropagation? I am pretty confused on this matter because so far of all the lecture I have taken no one really talk about this yet and I want to know it now.

The kernels are usually initialized at a seemingly arbitrary value and then you would use a gradient descent optimizer to optimize the values so that the kernels solve your problem.

There are many different initialization strategies.

Set all values to 1 or 0 or another constant
Sample from a distribution, such as a normal or uniform distribution
There are also some heuristic methods that seem to work very well in practice, a popular one is the so-called glorot initializer named after Xavier Glorot who introduced them here. Glorot initializers also sample from a distribution but truncate the values based on the kernel complexity.
For specific types of kernels, there are other defaults that seem to perform well. See for example this paper.

Exploring initialization strategies is something I do when my model is not able to converge (gradient problems) or when the training seems to be stuck for a long time before the loss function starts to decrease. These are signs that there might be a better initialization strategy to look for.


What are the challenges for recognising the handwritten characters? This 2014 article saying that a Chinese team of physicists have trained a quantum computer to recognise handwritten characters.

Why did they have to use a quantum computer to do that?

Is it just for fun and demonstration, or is it that recognising the handwritten characters is so difficult that standard (non-quantum) computers or algorithms cannot do that?

If standard computers can achieve the same thing, what are the benefits of using quantum computers to do that then over standard methods?

Handwritten digit recognition is a standard benchmark in Machine Learning in the form of the MNIST dataset. For example, scikit-learn, a python package for Machine Learning uses it as a tutorial example.

The paper you cite uses this standard task as a proof of concept, to show that their system works.


What is the KWIK Framework? "...for learning transition dynamics...in the KWIK framework."

The above is part of a paper's conclusion - and I don't really seem to understand what the KWIK framework is. In the details of the paper, is a brief highlight of the KWIK conditions for a learning algorithm, which go as follows (I paraphrase):

All predictions must be accurate (assuming a valid hypotheses class)
However the learning algorithm may also return $\perp$, which indicates that it cannot yet predict the output for this input.

A quick Google Search brought me to this paper from ICML 2008, but it is a little difficult to comprehend without a detailed read.

Could someone please help me understand what the KWIK framework is, and what implication does it have for a learning algorithm to satisfy KWIK conditions? An explanation that starts at simple and goes to fairly advanced discussions is appreciated.

Thanks a lot!

Based on the presentation by Praveen Venkateswaran on the same paper, KWIK framework is any learning algorithm that makes the following:

if it knows (by its learning) the answer already, it does tell that
if it is uncertain, it tells the "I don't know" mark
"I don't know" marks should have an upper limit, which is the accuracy/error term of the algorithm.

The idea is that algorithm has a trainer who knows the correct answers, like in any machine learning case, but the difference is that the algorithm agent should know when it has enough knowledge to give the result right away, and when is time to ask and learn. In learning phase the trainer does not calculate errors, only he gives right answers if asked.

There I see two implications: algorithm should know when it has not all the necessary data to answer (when to use "I don't know" answer) and a mechanism to be sure you're correct when the answer is e.g. 1 or 0 in binary case.

How to put that in mathematics, it varies by your chosen algorithm. Also there is a formal equation set for this, but I leave here only this literal definition to give the basic idea.


Why is the n-step tree backup algorithm an off-policy algorithm? In reinforcement learning book from Sutton & Barto (2018 edition), specifically in section 7.5 of the book, they present an n-step off-policy algorithm that doesn't require importance sampling called n-step tree backup algorithm.

In other algorithms, the return in the update consisted of rewards along the way and the estimated value(s) of the node(s) at the bottom, but, in tree backup update, a return consists of things mentioned before plus the estimated values of the actions that weren't picked during these n steps, all weighted by the probability of taking the action from the previous step.

I have a few questions about things in this algorithm that are unclear to me.

Why is this algorithm considered an off-policy algorithm? As far as I could notice, only a single target policy is mentioned and there is no talk about behaviour policy generating actions to take.
In control we want our target policy to be deterministic, greedy policy, so how do we exactly generate actions to take in this case since behaviour policy isn't used? If we generate actions from the greedy policy, we won't explore, so we won't learn the optimal policy. What am I missing here?
If I understood something wrong and we are actually using behaviour policy, I don't understand how would the update work in the case where our target policy is greedy. The return consists of estimates taken from actions that weren't picked, but, because our policy is greedy, the probabilities used in calculating those estimates would be 0, so the total estimate of those actions would be 0 as well. The only non 0 probability in our target policy is the one of the greedy action (which is the probability of 1), so the entire return would fall down to n-step SARSA return. So, basically, how are we allowed to do this update in this case, why is this return allowed to replace the one with importance sampling?

As for your first two questions: there is indeed a behaviour and a target policy, which can be different. In the example image of the $3$-step tree-backup update in the beginning of the section you mention, the actions $A_t$, $A_{t+1}$, and $A_{t+2}$ are assumed to be selected according to some behaviour policy, whereas a (different) target policy is used to determine weights for the different leaf nodes.

As for your third question, in the case where our target policy is greedy, lots of terms will indeed have $0$ weights and therefore entirely drop out. However, this is not always going to fall down to the same return as $n$-step Sarsa returns; that would not be correct, because ($n$-step) Sarsa is an on-policy algorithm.

In the case where the target policy is a greedy policy, the return will depend very much on how many actions happened to get selected by the behaviour policy which the greedy target policy also would have "agreed" with. If the behaviour policy already happened to have made a "mistake" (selected an action that the greedy policy wouldn't have selected) for $A_{t+1}$, you'll end up with a standard $1$-step $Q$-learning update. If the behaviour policy only made a "mistake" with the action $A_{t+2}$ (and agreed with the target policy on $A_{t+1}$), you'll get something that kind of looks like a "$2$-step $Q$-learning update" (informally here, because $n$-step $Q$-learning isn't really a thing). Etc.

You can see that this is the case by closely inspecting Equation 7.16 from the book:

$$G_{t:t+n} \doteq R_{t+1} + \gamma \color{blue}{\sum_{a \neq A_{t+1}} \pi (a \mid S_{t+1}) Q_{t + n - 1}(S_{t+1}, a)} + \gamma \color{red}{\pi (A_{t + 1} \mid S_{t + 1}) G_{t + 1 : t + n}}.$$

Suppose that the target policy $\pi$ is greedy, and the behaviour policy already selected action $A_{t+1}$ differently from what $\pi$ would have selected (meaning that $\pi(A_{t+1} \mid S_{t+1}) = 0$). Then we know that the $\color{red}{\text{red}}$ part of the equation will evaluate to $0$. In the $\color{blue}{\text{blue sum}}$, the $\pi(a \mid S_{t+1})$ term will only evaluate to $1$ for $a = \arg\max_a Q_{t+n-1}(S_{t+1}, a)$ (because that is the action $a$ to which the greedy target policy would assign a probability of $1$), and $0$ again for all other elements of the sum. So, in this example situation, we end up using the return $G_{t:t+n} = R_{t+1} + \gamma \max_a Q_{t+n-1}(S_{t+1}, a)$. This is exactly the return also used by the standard $1$-step $Q$-learning update rule.
Now suppose that the behaviour policy and a greedy target policy happened to "agree" with each other on $A_{t + 1}$, but disagree again on $A_{t + 2}$. In this case, the entire $\color{blue}{\text{blue sum}}$ for $G_{t:t+n}$ will evaluate to $0$, but the $\pi(A_{t+1} \mid S_{t+1})$ in the $\color{red}{\text{red part}}$ will evaluate to $1$. Then, "inside" the recursive $\color{red}{G_{t+1:t+n}}$, we'll get a very similar situation to the example above, with a single non-zero term in the blue sum and a red part that evaluates to $0$. In this case, the total return will be $G_{t:t+n} = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 \max_a Q_{t + n - 1}(S_{t + 2}, a)$. Note that this is different from a $2$-step Sarsa return. $2$-step Sarsa would use a return with $\gamma^2 Q_{t+n-1}(S_{t+2}, A_{t+2})$ at the end (where $A_{t+2}$ is sampled according to the behaviour policy), rather than that term involving $\max_a$.

What you essentially end up getting in these cases is returns similar to those of $n$-step Sarsa, but they automatically get truncated as soon as there is disagreement between the behaviour policy and a greedy target policy (all subsequent reward observations get replaced by a single bootstrapping value estimate instead).

In the examples above, I assumed completely greedy target policies, since that is what you appeared to be most interested in in your question (and is probably also the most common use-case of off-policy learning). Note that a target policy does not have to be greedy. You can also have non-greedy target policies if you like, and then the returns will obviously change quite a bit from the discussion above (fewer $\pi(S, A)$ terms would evaluate to $0$, there'd be more non-zero terms).


What are the characteristics of a deep learning AI? I have experience in making several Artificial Neural Networks and some programs which may be classified as an Artificial Intelligence by using Tensorflow.js and Brain.js. In order to produce something that may be classified as a deep learning AI, what are the characteristics of a Deep Learning AI?

As you can see from the picture above (In courtesy to this guy post). Deep learning is a field inside machine learning which involves using deep neural networks to solve machine learning problems.

Tensorflow.js and Brain.js are software architectures built in order to assemble and develop ML models inside the browser.

If you would like to delve into this field of deep neural networks you should start from the theory to really understand why we are using neural networks to solve problems and which problems they are intended to solve.

You can start with this awesome video by 3blue1brown : Intro video

And this standford class for CNN: Stanford class


What does 'clock rate' mean in the context of recurrent neural networks (RNNs)? I have often encountered the term 'clock rate' when reading literature on recurrent neural networks (RNNs). For example, see this paper. However, I cannot find any explanations for what this means. What does 'clock rate' mean in this context?

It seems this paper defines a "clock period ${T}_n$" that it uses to express the topology of the network: "Each module is internally fully-interconnected, but the recurrent connections from module j to module i exists only if the period $T_i$ is smaller than period $T_j$.".
This definition is, however, only in this paper, as far as I know. It wouldn't make sense to have a "clock period" (or "clock rate") on other, more self-similar, RNNs. However "time t" is something that is defined to express the amount of times the RNN has recursed, "t times".


Are humans superior to machines in chess? A friend of mine, who is an International Master at chess, told me that humans were superior to machines provided you didn't impose the time constraints that exist in competitive chess (40 moves in 2 hours) since very often games were lost, to another human or a machine, when a bad move is made under time pressure.

So, with no time constraints and access to a library of games, the human mind remains superior to the machine is my friend's contention.  I'm an indifferent chess player and don't really know what to make of this.  I was wondering if any research had been made that could back up that claim or rebut it.

Losing games to computers because of mistakes made under time pressure was probably a thing about 20 years ago, when Kasparov lost to DeepBlue after such a mistake(correction: it was Kramnik with the blunder, not Kasparov (see edit 2)). But after Kramnik's loss in early 2000s, no world champion ever tried to play against a computer (to my knowledge). Nowadays, there are computer only tournaments among programs with ratings well above 3300 (for comparison, Carlsen's peak rating was around 2880), and it is not uncommon for computers to make moves with no apparent meaning to humans.
No time limit for humans also mean no time limit for computers so I doubt any human can win a single game against a computer. Older models like Stockfish 8 depend on their computational power as it can look at several millions of position per second, Google AlphaZero  managed to beat Stockfish with 80000 positions per second: they don't seem to depend on brute force calculations any more. Keep in mind that this is without any prior knowledge of openings etc, they are trained using reinforcement learning, starting from the rules of the game only. From there, they can develop their own strategies and implement them without making any mistakes. They create their own openings from scratch, so existing libraries is not going to be very useful.
I am not aware of any research on this but lack of a challenge from humans is probably enough evidence. Also, Grand Masters regularly use chess engines in their training routine to analyze positions, so there is that.
A few years ago there was a game between Stockfish against GM Nakamura + Rybka, which Stockfish won. It is possible that human GM + Stockfish might have better chances against AlphaZero in correspondence without any time limits, but we probably will never know.
Here is an interview with Carlsen after a game, very interesting to show what he thinks about AlphaZero.
Both Kramnik and Kasparov made serious mistakes in their matches against computers. Kasparov resigned in a drawn position and missed a knight sacrifice, and Kramnik missed a mate in 1.


Class imbalance and "all zeros" one-hot encoding? I tried this example for a multi class classifier, but when looking at the data I realized two things:

There are many examples of "all zeros" vectors, that is, messages that don't belong in any classification.
These all-zeros are actually the majority, by far.

Is it valid to have an all-zeros output for a certain input? I would guess a Sigmoid activation would have no problems with this, by simply not trying to force a one out of all the "near zero" outputs.

But I also think an "accuracy" metric will be skewed too optimistically: if all outputs are zero 90% of the time, the network will quickly overfit to always output 0 all the time, and get 90% score.

I understand your questions as follows:

Is it valid to have an all-zeros output for a certain input?

Yes its possible in some cases like:

In the tutorial "jigsaw-toxic-comment-classification-challenge", the data is taken from wikipedia comments, so generally there is no toxic behavior in people's comment, it is very rare that a person posts "bad" comments in an informative source like wikipedia, this might lead to all the labels being zero for a particular example.
In a single label classification like predicting whether a person has a rare disease,the dataset would contain labels that are mostly "zero"-(no disease)-skewed towards zero

This happens in datasets where the positive output to be predicted is a very rare case.

I guess your second question is -whether "accuracy" is a good way of evaluating a model for this type of a problem

You are right, in such a case even a simple program/model that outputs zeros for all the inputs would achieve an accuracy of more than 90%, so here accuracy is not a good metric to evaluate the model on.

You should go through the metrics f1_score,recall, and precision which are ideal for this type of problems.

Basically here we are interested in "out of those which are predicted positive, how many are really positive -precision" and "out of those which should have been predicted positive, how many are really predicted positive"

If my definitions seem confusing to understand, please got through the link below:

f1_score/recall/precision

Hope I was helpful


How can AI help developer to develop things I have seen an AI create a game it self, AI act as a lawyer, call center etc.

There are many problems (Example for mobile development)

1. New api/technology or even new language every year.
2. New design
3. New hardware
4. Good code architecture, design pattern
5. Security
6. Image/Animation optimization
7. Automate testing

etc.

I wonder that AI can help developer solve that problems.

1.1 May be I want to get the location then AI suggest the best api for specific platform.

1.2 AI help to refactoring and optimizing the code

Help on design e.g. golden ratio, Material theme color
Suggest or determine the limit of the hardware e.g. screen size, ram
Can convert to another design pattern
Help to waring the latest vulnerable and automate pentest etc.
Help to optimize image by learning how much can we reduce the image size while people still ok with it.
Generate automate-testing

Is there any solution existed?

If not, what can we do?

An umbrella term for the application of heuristic techniques to software development is 'Search Based Software Engineering' (SBSE).

SBSE emerged as a distinct activity around the turn of the century, with a strong initial focus on automating the generation/prioritization of test cases.

With respect to some of your specific queries:

1.2 Paper on Automated refactoring

Automatically choosing screen colour to minimize energy consumption.
This sort of thing is not usually done heuristically, since it needs platform-specific code.
Automated refactoring to patterns.
AFAIK, penetration testing has yet to be successfully automated.
As stated, this doesn't really require AI. More generally, I don't know of any specific work automating for HCI preferences, but something like 'Interactive Genetic Algorithms' could be used.
There's a lot of SBSE literature on testing. See this paper for a general overview.


How can I draw a conceptual dependency for the statement "Place all ingredients in a bowl and mix thoroughly"? I stumbled across a question asking to draw a conceptual dependency for the following statement:

  Place all ingredients in a bowl and mix thoroughly

My attempt so far

Explanation: Both the sender and recipient are the same, except that the states of their contents are different.

Something feels like it isn't right. I would appreciate if you could correct errors, if any.

As it's two clauses ("place in bowl" and "mix"), I would actually use two separate CD structures. The first one is a PTRANS (not ATRANS, as you don't change ownership, but location); the second one is a bit trickier.

Mix can be paraphrased as stir, or move around. You would typically do this with a spoon or similar implement. I would do it as a PROPEL with the instrument spoon and the object the ingredients. PROPEL, according to Schank (1975) is the "application of a physical force to an object".

So the first one is:

(PTRANS
  (ACTOR *you*)
  (OBJECT "all ingredients")
  (TO "bowl"))

And the second is:

(PROPEL
  (ACTOR *you*)
  (OBJECT "ingredients")
  (INSTRUMENT "a spoon")
  (DIRECTION "circular"))

It's debatable if you PROPEL the ingredients with the instrument spoon, or you PROPEL the object spoon with the target/location/direction ingredients.

If you draw them in a graphical representation, you can have both ACTs leading off the shared actor '*you*'; or you could have them as separate graphs linked by 'then' or some other indicator of sequentiality.

Schank, Roger (1975) The primitive ACTs of conceptual dependency, Proc of 1975 workshop on theoretical issues in natural language processing, 34-37


The are some fundamental learning theories for developing an AI that imitates human behavior Most if not all AI systems are not to imitate human, but to finally out-perform human. Examples include using AI to play a game, classification problems, auto-driving, and goal-oriented chatbots. Those tasks usually comes with an easily and clearly defined value function, which is the objective function for the AI to optimize.
My question is, how is DNN reinforcement learning or related techniques to be applied to AI system that are designed to just imitate human but not outperform human? Note this is different from a human-like system. Our objective here is to let the AI become a human rather than a super intelligence. For example, if human consistently makes a mistake in image identification, then the AI system must also make the same mistake. Another example is the classic chatbot to pass the Turing test. Is DNN reinforcement learning useful in these kind of tasks? I find it is really hard to start with because the value function cannot be easily calculated. What are some theory behind this?

There is an interesting discussion the progress achieved in this field by far in the paper of Francois Chollet - https://arxiv.org/abs/1911.01547. At the present time, many architectures are able to outperform the human in particular tasks, because they have a strong priors coded into them and ability to process a huge amount of data.
However, when it comes to generalization, or even more difficult task of doing the things, that the coder has not put into the model, the present algorithms do no perform well. There is a rather sophisticated and developed mathematical definition of what is required from the system to be called intelligent. And in a nutshell, it is ability to develop a sensible behaviour and enough accuracy for new tasks without putting strong priors and large amount of experience.
In the end of the paper, there is proposed a benchmark to measure the intelligence of AI system.


Do smaller loss values during DQN training produce better policies? During the training of DQN, I noticed that the model with prioritized experience replay (PER) had a smaller loss in general compared to a DQN without PER. The mean squared loss was an order of magnitude $10^{-5}$ for the DQN with PER, whereas the mean squared loss was an order of magnitude $10^{-2}$.

Do the smaller training errors have any effect on executing the final policy learned by the DQN?

I think it says something about the training progress, while another approach you can make sure is to look at the gradient norm. Sometimes, the training loss is really noisy while the gradient norm is much more clear.


What are the best algorithms for image segmentation tasks? I recently started looking for networks that focus on image segmentation tasks related to biomedical applications. I could not miss the publication U-Net: Convolutional Networks for Biomedical Image Segmentation (2015) by Ronneberger, Fischer, and Brox. However, as deep learning is a fast-growing field and the article was published more than 4 years ago, I was wondering if anyone knows other algorithms that yield better results for image segmentation tasks?  And if so, do they also use a U-shape architecture (i.e. contraction path then expansion path with up-conv)?

U-Net and U-Net inspired architectures have been quite popular in the medical image-related tasks ever since it was first introduced. There have been several improved versions of U-Net designed for specific tasks that followed. One such example is Attention U-Net, extremely popular for Pancreas Segmentation.

Other examples of architectures that have achieved state-of-the-art results in image segmentation tasks in recent years include Multi-Scale 3DCNN + CRF, popular for Brain and Lesion images, Multi-Scale Attention for MRIs, etc. A recent paper that describes an interesting 3D FCNN architecture is HyperDense-Net, widely used for multi-modal tasks in medical image segmentation.


Can a purely policy convolution neural network based game learn to play better than its opponents? This question has come from my experiment of building a cnn based tic-tac-toe game that I'm using as a beginner machine learning project. The game works purely on policy networks, more specifically -

During training, at the end of each game, it trains itself on the moves the winner/drawer made for each board position. That is, its training data consists of board positions and the moves made by the winning player on each position.
While playing, it predicts its own moves solely based on that training (that is, it predicts what move would a winning player make with the current board). It doesn't use any type of search or value networks.

I'm seeing that if I train it against a player that predicts the perfect move (using a recursive search) every time, the AI gets good at drawing about 50% games. But if I train it against a player that makes random moves, it doesn't get better at all.

Wouldn't one expect it to learn well (even if slower) regardless of the level of its opponent? Since each game ends in a draw or win for one player, shouldn't it be able to extract features for the winning/drawing strategies even when learning from random players? Or does this behavior mean that the model is not optimal?

(I'd leave this in the comments but sadly I can't.)

Here's a great paper (leveraging formal game theory) in which "players" make strategic choices based on each event ("move") and an algorithm calculates the best strategy for all players based on each player's abilities throughout the multi-stage "game". So instead of learning from winning and predicting what the next perfect move the player thinks (based off of learning) will lead to a "win", the player calculates an optimal strategy and moves to win the game itself over multiple moves.

https://users.ece.cmu.edu/~youzhib/paper/bao2017csf.pdf

Note: This paper deals with cyber war games so is heavily tilted towards that domain, but if you take away the game theoretics and concept of strategy over a multi-stage game like ti-tac-toe, you should be able to improve your overall outcomes. That being said, how the model would accommodate a random "player" with random moves would be interesting to see.


Does quiescence search even improve the minimax algorithm? Consider this game state:

d5 captures c6
Quiescence search returns about 8.0 as evaluation because after dxc6 and bxc6 Qxd6 would be played (then Qxd6 by black). A normal player would not play this move but quiescence search includes it in the evaluation and it would result in this end state:
which would result in a huge advantage for black.
Is my interpretation of quiescence search wrong?

Your logic is flawed because you negated "stand-pat" (i.e. do nothing) and alpha-beta. Let's take a look at the pseudocode (https://www.chessprogramming.org/Quiescence_Search#Pseudo_Code):

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;

    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();

        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

Your Qxd6 capture will make return a score far below the alpha. The line:

  if( score > alpha )

will prevent your blunder being reported. Instead the engine would report either stand_pat (do nothing), or something like Nf3, Nc3 etc.


Can non-Markov environments also be deterministic? The definition of deterministic environment I am familiar with goes as follows:

  The next state of the agent depends only on the current state and the action chosen by the agent.

By exclusion, everything else would be a stochastic environment.

However, what about environments where the next state depends deterministically on the history of previous states and actions chosen? Are such environments also considered deterministic? Are they very uncommon, and hence just ignored, or should I include them into my working definition of deterministic environment?

Markov Environment is not about deterministic or stochastic. "Depends only on the current state and your action" does not mean you know what will happen(deterministic).

We can have Markov + deterministic, Markov + Stochastic, Non-Markov + deterministic, and Non-Markov + stochastic.

The definition you have is not a definition of deterministic. It is a definition of Markov property.

Refer to Wikipedia.

  A stochastic process has the Markov property if the conditional
  probability distribution of future states of the process (conditional
  on both past and present values) depends only upon the present state;
  that is, given the present, the future does not depend on the past. A
  process with this property is said to be Markovian or a Markov
  process. The most famous Markov process is a Markov chain. Brownian
  motion is another well-known Markov process.

Markov property is assumed mostly in stochastic problems.
Brownian motion is the motion of molecules of ink in the water and used to model the movement of a stock price, which is stochastic.

Deterministic means when you are in the same state and choose the same action your next state will be always the same.

Stochastic means even you are in the same state and choose the same action, you next state can be different than the previous time.

Example) You toss a coin and roll a die. Every time you roll a die you get pennies as many. If the coin gets head, you get a chance to roll a die twice next time.
Your state can be (money you collect so far, coin head/tail in the previous time).

In this problem, your next state will not be affected by the past. the only thing you need to know is the current state, the money you got and head or tail. It has a Markov process/environment. However, still, it is stochastic because you don't know what will be the next state.