text:
Wasserstein GAN: Implemention of Critic Loss Correct?
The WGAN paper concretely proposes Algorithm 1 (cf. page 8). Now, they also state what their loss for the critic and the generator is.
When implementing the critic loss (so lines 5 and 6 of Algorithm 1), they maximize the parameters $w$ (instead of minimizing them as one would normally do) by writing $w \leftarrow w + \alpha \cdot \text{RMSProp}\left(w, g_w \right)$. Their loss seems to be $$\frac{1}{m}\sum_{i = 1}^{m}f_{w}\left(x^{\left(i\right)} \right) - \frac{1}{m}\sum_{i = 1}^{m} f_{w}\left( g_{\theta}\left( z^{\left( i\right)}\right)\right).\quad \quad (1)$$
The function $f$ is the critic, i.e. a neural network, and the way this loss is implemented in PyTorch in this youtbe video (cf. minutes 11:00 to 12:26) is as follows:
critic_real = critic(real_images)
critic_fake = critic(generator(noise))
loss_critic = -(torch.mean(critic_real) - torch.mean(critic_fake))
My question is: In my own experiments with the CelebA dataset, I found that the critic loss is negative, and that the quality of the images is better if the negative critic loss is higher instead of lower, so $-0.75$ for the critic loss resulted in better generated iamges than a critic loss of $-1.26$ e.g.
Is there an error in the implementation in the youtube video of Eq. (1) and Algorithm 1 of the WGAN paper maybe? In my opinion, the implementation in the video is correct, but I am still confused then on why I get better images when the loss is higher ...
Cheers!

Did you observe better images also with higher positive values? The Wasserstein loss is supposed to converge to 0, since it is basically the Wasserstein distance between the distribution of real images and fake generated ones. So I would say that in the example you provide it is normal to get better images with a critic loss of -.75, closer to 0 than -1.26, which tells you the discriminator is having a hard time distinguishing between fake and real images (hence better quality).

Hi Edoardo, okay, I see your point. Given that $-0.75$ is closer to $0$ than $-1.26$, it is good to see that I see better images, I guess. The only thing interesting/slightly confusing me is that I haven't a positive loss for the critic yet, is that normal?

In my experience it is possible to get negative scores using the Wasserstein loss. Again, cause rather than a usual loss the scores represent a distance between two means, that the discriminator tries to maximize. Negative scores simply means that the mean of the distribution of the generated images is bigger than the mean of the distribution of the real images. Positive scores means the other way around, but either way the game of the discriminator is just to maximize the distance, i.e. increase the absolute value, regardless of the sign in front of it.

Just a last advice: looking at the generator and discriminator losses is obviously important, but in my experience only for understanding if the training is stable or not. But ultimately, what you care about is the quality of the images produced, and you should implement some specific metrics to evaluate that, and check mostly those metrics to perform hyperparameters tuning. Don't waste too much time trying to get 'good values' on the discriminator and generator losses.

I know that this is an old question, but here are my two cents.

Yes, it is possible that the Wasserstein Loss goes negative.
Yes the implementation seems to be correct. However, it also depends on the implementation of the generator loss. You can implement it in an inverted manner, and it would also work. The key is to ensure that the generator and the discriminator compete against one another, not with one another.
Interpretation of the Wasserstein loss is a complex undertaking, and you should rarely make conclusions just based on whether the loss is going up or down. If have seen WGANs converge with all kinds of negative and positive losses in the critic. There are some resources out there that give you some tips on how to interpret the loss. However, the convergence of the loss highly depends on a bunch of factors such as the dataset, the type and size of the architecture, the learning rate and many more. You should assume that what works in the video on one dataset does not translate to any meaningful insights for training on another dataset with a different architecture.
If you have exactly the same implementation and dataset, you should see approximately the same behaviour. However, note that through updates on libraries/differences across libraries, those changes might be obscure. These can involve the initialization of weights or default parameters of often-used functionalities.
You should abstain from trying to compare different runs based on the trajectory of the loss. Please use a separate metric for that.


text:
What does "adding class weights for an imbalanced dataset" mean in the case of multi-label classification?
Suppose I have the following toy data set:

Each instance has multiple labels at a time.
You can see I have 2 instances for Label2. However, only one instance for the other labels. It means that we have class imbalanced issues.
I read about adding class weights for an imbalanced dataset. However, I could not understand how it actually works and why it is beneficial.
Can anyone explain this method generally, as well as according to my given toy data set?
In addition to that, how do we handle these missing labels (nan)?

The paper A systematic study of the class imbalance problem
in convolutional neural networks is a great overview on class imbalance approaches. Section 2 summarizes various methods commonly used. They categorize "Adding Class Weights for an imbalanced dataset" under the technique "Cost sensitive learning":

Cost sensitive learning. This method assigns different cost to misclassification of examples from different classes [44]. With respect to neural networks it can be implemented in various ways. One approach is threshold moving [22] or post scaling [23] that is applied in the inference phase after the classifier is already trained. Similar strategy is to adapt the output of the network and also use it in the backward pass of backpropagation algorithm [45]. Another adaptation of neural network to be cost sensitive is to modify the learning rate such that higher cost examples contribute more to the update of weights. And finally we can train the network by minimizing the misclassification cost instead of standard loss function

Without further context, "Adding Class Weights for an imbalanced dataset" can mean many things as enumerated by the above. But if I had to guess, the most common meaning is that they weigh the misclassification cost differently per label by multiplying it with a different weight variable.
For example, maybe label 1, 2, and 3, when misclassified, gets a 1x multiplier in the training loss (the standard weight), but label 4 gets a 3x multiplier because it is roughly 3x more important, and label 5 gets a 0.5x multiplier because it is 0.5x less important.
Here is an example of how to do this with Keras.
(FYI the paper above recommends you over-sample the minority class rather than using the cost-sensitive learning approach to help with class imbalance)
As for missing labels, the quickest solution is just to skip those training instances when training for that particular missing label. If you want to still use the training instances somehow, a common approach is to fix the missing label with semi-supervised learning approaches.
One way to do semi-supervised learning is self-training, where your model is trained on only the labeled instances, and then makes predictions on the missing labels. High-confidence predictions of the missing labels are then added to the training data, and the model is trained on the new training data. This process repeats until convergence of the training data.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Model-based RL for time series data
I have time-series data. When I take an action, it impacts the next state, because my action directly determines the next state, but it is not known what the impact is.
To be concrete: I have $X(t)$ and $a(t-1)$, where $X(t)$ is n-dimensional time-series data and $a(t)$ is 1-dimensional time-series data. At time $t$, they together represent the observation/state space. Also, at time $t$, the agent makes a decision about $a(t)$. This decision (action) $a(t)$ directly defines the next state space $X(t+1)$ and rewards, by some function $f$ & $g$, $f(a(t), X(t)) = X(t+1)$ and $g(a(t), X(t)) = R(t+1)$.
I have to estimate this impact, i.e. where I will end up (what will be the next state). I decided to use a model-based RL algorithm, because, from my knowledge, model-based RL does exactly this.
Can you advise me on a good paper and Github code, to implement this project?
As I noticed, there do not exist many works on Model-based RL.

DeepMind's MuZero algorithm learns both a model and policy using RL.

To my knowledge, there does not exist anything along the lines of model-based reinforcement learning with time-sensitive data. I think the best chance you have is to try to abstract the data that you have into a model which is not time-sensitive.
What would happen when you get past the timestamps of your original data? I am guessing that when testing this model, you will have states with time stamps past your original latest timestamp. Or are you only using your model in the time stamps of your training data? Is it going to be a useful model then?
Firstly, please note that the topics of this forum are mostly theoretical. This question leans on the boundary. If you frame your question a bit differently, ending your post with a clear question and also putting that question in the title, you will get more responses.
I feel like the question is 'What are the possibilities for model-based reinforcement learning for time-sensitive data?' But this question is inherently vague as it implies that you have a model according to the definitions of models in RL, which are not time sensitive. If you would like a better answer then please provide more information or ask your question on a more practical forum if it is more practical than what I guessed.
Disclaimer: would have just put some comments under the post as this is not a real sufficient answer, but my reputation is not high enough for that :P

It seems that your description perfectly matches the naive RL approach. What you can do with model-based RL is perform rollouts with the model to predict future states. In other words, with an accurate model you might predict the next state X(t + 1) given the current state X(t) and applying some action a(t). The following (and recently) paper shows how these rollouts works.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Do filters have as many layers as the depth of the input in CNNs?
Firstly as an example here is the architecture of YOLOv2

I am trying to understand the depth of an output of a convolutional layer. For example, the first convolutional layer has the shape 3x3x32. So there are 32 filters with shape 3x3, but each filter has 3 layers and these 3 layers convolve over 3 layers of the input. At the end, values of the 3 layers are summed up and to generate 1 layer. For 32 filters, we get an output with 32 layers.
If we look at the next layer, 64 filters with size 3x3 and each filter should have 32 layers. Because input has 32 layers. Is this inference true? If it is not, how does it work?

I think that this question is a duplicate of this. Please, let me know whether that is the case or not. In any case, to answer your question: yes, your reasoning is correct, but note that this only applies to 2d convolutions (the usual convolution operation in CNNs). In the case of 3d convolutions, as I write in my answer in the linked post, the depth of the kernels could be different than the depth of the inputs.

@nbro basically yes, they are same. Sorry, I did not see that one before asking mine.


text:
Strategy for playing a board game with Minimax algorithm
I want to build a player for the following game:
You have a board where position 1 is your player, position 2 is the rival player, -1 is a blocked cell and some positive value is a bonus. You can move up, down, left, or right. Also, each bonus has a timer until it disappears (number of steps). Furthermore, each move has a timeout limit.  At the end game, when at least one of the players is stuck, we check the scores and announce the winner.
Board example:
 -1 -1  0  0  0 -1 -1  -1
 -1  0 -1 -1 -1  0  0  340
 -1 -1  0  0  0 -1  0   0
 -1  0  0 -1  1 -1  0  -1
 -1  0  0 -1 -1  0  0   0
  0  0 -1 -1 -1  0  2  -1
  0 -1  0  0 -1  0  0  600
 -1 -1  0  0 -1 -1 -1  -1
  0 -1  0  0  0  0 -1  -1

I'm using the MiniMax algorithm with a time limit to play the game. If we got to children, we return $\infty$ for a player win, $-\infty$ for the rival win, and $0$ for a tie. If we got to a specific depth, we calculate the heuristic value. If we got timeout in some place in MiniMax, then we return the last calculated direction.  I'm trying to figure out a good strategy to win this game or get to a tie if no solution is possible.
What heuristic function would you define?
What I thought - four factors:

$f_A$ - The number of steps possible from each direction from the current position.
$f_B$ - The analytical distance from the center.
$f_C=\max_{b\in Bonus}\frac{X * I}{Y}$ - where $X$ is value of the bonus,  $I$ is $1$ if we can get to the bonus, before it disappears (otherwise $0$) and $Y$ is the distance between the bonus and the player.
$F_D$ - The distance between the players.
The final formula:
$$
f(s)=0.5\cdot(9-f_A(s))+0.2\cdot f_C(s)-0.2\cdot f_D(s)-0.1\cdot f_B(s)
$$

I'm not sure if it will be a good strategy for that game or not. How would you define the heuristic function? It should also be quick to calculate it because the game has a timeout for each move.
In order words, what will give us the best indication that our player is going to win/lose/tie?

I'm not familiar with your game so I can't tell you what a good heuristic woul be in your specific case, but I can give you some advice on how to look for a good heuristic function.
As a rule of thumb, the heuristic function for a MiniMax algorithm is best kept simple and efficient, so you can get deeper into the tree. But it depends on how costly it is to compute the heuristic function compared to simulating moves in the game.
If the heuristic takes longer than simulating a game move, it might be worth simplifying it so it runs faster and you can look ahead further. This often leads to more emergent and advanced strategies that are hard to express mathematically. An extreme example of a simple heuristic would be the current player score minus the opponent's score. Since scores only change when someone lands on a bonus tile, many paths you take down the tree would have equal value, so you need to be able to look ahead many moves to find a non-zero heuristic and be able to prune parts of the tree. But because the heuristic is so fast to compute, you can do this and discover more non-obvious strategies, simply by brute force simulation. This leads to more emergent behavior, and would tell you more about different ways to play the game (if that is your goal).
If simulating a game move takes longer than your current heuristic, it's probably not worth making the heuristic faster since the game simulation is the dominating factor in how deep you can go down the tree. This case is much more difficult because it means you have to find optimal strategies (and how to express them as a heuristic function) yourself. This is more of an art than a science - ask any chess grandmaster. I'd look up existing literature on the game and see if any existing strategies can be translated into a heuristic function. If there is no literature (e.g. because the game is new or unpopular), you could spend some time playing it yourself to discover what works. Alternatively (and perhaps more interesting), you could use a simple heuristic function with more emergent behavior, increase the time the MiniMax algorithm has to make moves, and play against your NPC opponent a few times to see what strategies it discovers. Or even have two NPCs with different heuristic functions play against each other. Then try to incorporate those into your final heuristic function. This is also a way to determine which heuristic function is better, if you have multiple candidates.
There are ways to optimize the heuristic function automatically using machine learning (specifically reinforcement learning), but it's probably not worth opening that can of worms in your case.


text:
What is the space complexity for training a neural network using back-propagation?
Suppose that a simple feedforward neural network (FFNN) contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_l$ nodes in each layer. What is the space complexity to train this FFNN using back-propagation?
I know how to find the space complexity of algorithms. I found an answer here, but here it is said that the space complexity depends on the number of units, but I think it must also depend on the input size.
Can someone help me in finding its worst-case space complexity?

Are you only interested in simple feed-forward neural networks (or MLPs)? I suppose so. If yes, edit your post to specify that and add the appropriate tag. If you were also interested in other more complicated neural networks, such as RNNs, the space complexity could be higher. For example, in the case of RNNs, you also need to store the matrices for the recurrent connections, so those already use more memory.

I want to know the space complexity analysis of normal feed forward NN with 3 hidden layers in particular

In the link it is mentioned that space complexity is measured in terms of units but I want to ask do input size has no role to play in this respect?

I will not tell you what the exact space complexity of training an FFNN with GD and BP is (because that actually depends on the specific implementation of GD and BP and I don't want to dive into the details of some specific implementation now, maybe later!), but I will guide you towards the specific answer, which you should be able to figure out alone (although it may take some time because you need to understand all the details of the BP algorithm), if you understand this answer.
The space complexity of an algorithm is just the amount of memory that you need to use during the execution of the algorithm. The space complexity, like the time complexity, is typically expressed as a function of the size of the input (or the number of inputs that you have) and, usually, in big-O notation, i.e. in the limiting case. So, $n$ is not the same thing as $\mathcal{O}(n)$, $\Omega(n)$ or $\Theta(n)$. Moreover, you can also express the space/time complexity both in the worst, best, or average case, and this is orthogonal to upper (expressed with $\mathcal{O}$), lower ($\Omega$), or tight ($\Theta$) bounds (check this).
If you use gradient descent (GD) and back-propagation (BP) to train an FFNN, at each training iteration (i.e. a GD update), you need to store all the matrices that represent the parameters (or weights) of the FFNN, as well as the gradients and the learning rate (or other hyper-parameters). Let's denote the vector that contains all parameters of the FFNN as $\theta \in \mathbb{R}^m$, so it has $m$ components. The gradient vector has the same dimensionality as $\theta$, so we need at least to store $2m + 1$ parameters.
Depending on how you implement BP, you may need more memory. For example, if you need to store all the intermediate terms of the partial derivatives, that will require more memory. To compute exactly the amount of required memory, you will have to expand the gradient vector into all their components (which may not be a pleasant experience). As I just said, this only contributes to the space complexity if you need to store these intermediate components, so, ultimately, the space complexity of an algorithm depends on the specific implementation of the algorithm.
Moreover, to be precise, we cannot just say that the space complexity is $2m + 1$ or whatever the amount of memory that you require is (although many careless or ignorant people will just say that), because we are not expressing this complexity as a function of the size of the input in the limiting case (which is usually done when expressing the space complexity of an algorithm), the number of layers or the number of units per layer (and you probably want to express the space complexity as a function of these 3 possible variable hyper-parameters).
If you take a look at this answer, where I describe how to compute the time complexity of the forward pass of an MLP (or FFNN) as a function of the number of inputs and outputs, the number of layers, and units per layers, then you can express the space complexity for training an FFNN in the same way. Given that you are already familiar with how space and time complexities of an algorithm are calculated (and given that this answer is already quite long), I will not repeat the description here.
In any case, to answer one of your questions more directly, yes, the space complexity will depend on the number of inputs that you have, because the number of inputs will determine the number of weights in the first layer, which you need to store in memory. This is true in the case of FFNNs (or MLPs) but note that this would not be true in the case of CNNs (i.e. the number of parameters in the convolutional layers does not depend on the size of the input), and that's why CNNs are often said to be more memory efficient.

In the post attached by you, you only did the time complexity analysis of FFNN but I want a complexity analysis like this: https://ai.stackexchange.com/questions/5728/what-is-the-time-complexity-for-training-a-neural-network-using-back-propagation/20281?newreg=92fccd4d6b51442db4e6d1dcc1dcfccf   for space with backprop as I used it for training my model

@RitikaGupta I'm telling you exactly how to do it. I'm not doing it because basically it's already done in my other answer: you just need to think a little bit and understand that and this answers.

I am unable to figure it out. In that post you only talked about the number of multiplications, in the link attached by me ,they are talking about number of units in each layer and in this post you talked about inputs also. I am confused.

@RitikaGupta In principle, you don't have to store the outputs of a unit (or neuron or node, or whatever you want to call it). You just need to store the parameter (during the forward pass). These parameters is what you need to store in memory during the forward pass. During the backward pass, you also need to store the partial derivatives with respect to each parameter. Now, depending on how you implement back-propagation (aka forward pass), you may require more or less memory, but, as I say in this answer, you need at least $2*n + 1$ parameters.

As I also say in this answer, you can express this number of parameters as a function of the input, the number of layers, and the number of units. To do that, you just need to follow the same reasoning as in my other answer (that's why I'm saying that you can just look at that other answer). However, what you need to note is that you may also need to store more parameters than $2*n + 1$. This is because, to compute the gradient vector, you may need to compute intermediate components. This the part that is missing from this answer.

The specific answer to this question (i.e. how many intermediate components do you need to store in memory to compute the gradient vector) actually depends on the implementation of BP, that's why I'm avoiding doing it here. As you noticed, this answer is already long, so what you're asking for is a lot of effort, but this answer should guide you towards the right answer. If I have more time later, I may try to complete this answer, but, to be honest, I don't really want to go into the details of some implementation of BP.

I used BP of keras

BTW Thanks a lot for your help and time @nbro. I am highly thankful to you for the valuable insights.

@RitikaGupta I may come back later to this answer and try to complete it. I don't know when, though. Meanwhile, I suggest that you focus on the back-propagation of an MLP with 1 hidden layer and keep track of all components that you need to store in memory. Then do the same thing for an MLP with 2 hidden layers and try to see how the memory scales. I think you can find the equations of back-propagation for these simple cases on the web or in some good book.


text:
Searching for 3D cad AI synthesis project (New CAD file form two similar CAD model)
I saw this post: Google AI generates images of 3D models with realistic lighting and reflections.

Is there any project to test this capability for combining two 3d cad files of a similar model and get a new combined model as shown (Hoogle AI ...)? I would like to use software such as Blender, SolidWorks or some project via Google Colab (testable without the need to install any software).

What do you mean by "project"? Do you mean a library? Do you mean a model?  If you are looking for a library, this question seems to be off-topic. Please, edit your post to clarify that.

I am searching one project which is a combination of model and ... which I could test it and use for achieving one new 3d model based of two input 3d cad files (by AI Algorithms like GAN or ...)


text:
How to obtain the policy in the form of a finite-state controller from the value function vectors over the belief space of the POMDP?
I was reading this paper by Hansen.
It says the following:

A correspondence between vectors and one-step policy choices plays an important role in this interpretation of a policy. Each vector in $\mathcal{V}'$ corresponds to the choice of an action, and for each possible observation, choice of a vector in $\mathcal{V}$. Among all possible one-step policy choices, the vectors in $\mathcal{V}'$ correspond to those that optimize the value of some belief state. To describe this correspondence between vectors and one-step policy choices, we introduce the following notation. For each vector $\mathcal{v}_i$ in $\mathcal{V}'$, let $a(i)$ denote the choice of action and, for each possible observation $z$, let $l(i,z)$ denote the index of the successor vector in $\mathcal{V}$. Given this correspondence between vectors and one-step policy choices, Kaelbling et al. (1996) point out that an optimal policy for a finite-horizon POMDP can be represented by an acyclic finite-state controller in which each machine state corresponds to a vector in a nonstationary value function.

I am unable to guess how the left-side finite-state controller is formed from the right side belief space diagram. Does the above text provide enough explanation for the conversion? If yes, I am not really able to fully get it. Can someone please explain?


text:
When is using weight regularization bad?
Regularization of weights (e.g. L1 or L2) keeps them small and standardized, which can help reduce data overfitting. From this article, regularization sounds favorable in many cases, but is it always encouraged? Are there scenarios in which it should be avoided?


text:
What is meant by "the number of examples is reduced", and why is this the case?
I am currently studying the paper Learning and Evaluating Classifiers under Sample Selection Bias by Bianca Zadrozny. In section 3.2. Logistic Regression, the author says the following:

3.2. Logistic regression
In logistic regression, we use maximum likelihood to find the parameter vector $\beta$ of the following model:
$$P(y = 1 \mid x) = \dfrac{1}{1 + \exp(\beta_0 + \beta_1 x_1 + \dots + \beta_n x_n)}$$
With sample selection bias we will instead fit:
$$P(y = 1 \mid x, s = 1) = \dfrac{1}{1 + \exp(\beta_0 + \beta_1 x_1 + \dots + \beta_n x_n)}$$
However, because we are assuming that $y$ is independent of $s$ given $x$ we have that $P(y = 1 \mid x, s = 1) = P(y = 1 \mid x)$. Thus, logistic regression is not affected by sample selection bias, except for the fact that the number of examples is reduced. Asymptotically, as long as $P(s = 1 \mid x)$ is greater than zero for all $x$, the results on a selected sample approach the results on a random sample. In fact, this is true for any learner that models $P(y \mid x)$ directly. These are all local learners.

This part is unclear to me:

However, because we are assuming that $y$ is independent of $s$ given $x$ we have that $P(y = 1 \mid x, s = 1) = P(y = 1 \mid x)$. Thus, logistic regression is not affected by sample selection bias, except for the fact that the number of examples is reduced.

What is meant by "the number of examples is reduced", and why is this the case?

I think what he means is that, while distribution $P(y  \mid x,s)$ has three variables, $P(y  \mid x)$ has two variables. The number of parameters required to describe a distribution (or samples to approximate it) grows exponentially with the number of variables (for more info see for instance Ian goodfellow, .. deep learning").

I do not think this is correct.


text:
Policy gradient: Does it use the Markov property?
To derive the policy gradient, we start by writing the equation for the probability of a certain trajectory (e.g. see spinningup tutorial):
$$
\begin{align}
P_\theta(\tau) &= P_\theta(s_0, a_0, s_1, a_1, \dots, s_T, a_T) \\
& = p(s_0) \prod_{i=0}^T \pi_\theta(a_i | s_i) p(s_{i+1} | s_i, a_i)
\end{align}
$$
The expression is based on the chain rule for probability. My understanding is that the application of the chain rule should give up this expression:
$$
p(s_0)\prod_{i=0}^T \pi_\theta(a_i|s_i, a_{i-1}, s_{i-1}, a_{i-2}, \dots, s_0, a_0) p(s_{i+1} | s_i, a_i, s_{i-1}, a_{i-1}, \dots, a_0, s_0)
$$
Then the Markov property should be applicable, producing the desired equality. This should only depend on the latest state-action pair.
Here are my questions:

Is this true?

I watched this lecture about policy gradients, and at this time during the lecture, Sergey says that: "at no point did we use the Markov property when we derived the policy gradient", which left me confused. I assumed that the initial step of calculating the trajectory probability was using the Markov property.

in the first equation you show, you definitely are using the Markov Property. When deriving the policy gradient you don’t explicitly use the Markov property, if you refer to the Sutton and Barto derivation this is clear. However, I am still of the opinion that the Markov property is used, as the underlying assumption of the MDP is that the Markov property holds (eg our policy is only conditioned on the current state, not the whole trajectory)

I watched the videos you’re watching and I would argue that the way he derives the policy gradient definitely does use the Markov property — he directly uses the probability of the trajectory that you have in your question and the LHS = RHS only if you assume the Markov property holds, otherwise as you say you would end up with a term like the second equation you have written.

I still have to read the policy gradient chapter in Sutton & Barto. Maybe comparing the two derivation can clear it up. I wonder if conditioning on policy is the answer, so it should be $P(\tau | \pi)$. I just realized thats how its written in the spinning up docs.

I don’t know what they mean by ‘conditioning on a policy’ — that is analogous to conditioning on a density function.

Sergey Levine's comment does seem confusing, here's the clarification. The policy gradient derivation itself does not explicitly require the Markov property. Instead, it operates on the probability distribution of trajectories under the parameterized policy $\pi_{\theta}$, which uses the Markov assumption since in most RL with fully observable states any trajectory is generated by a MDP.

I think the equation doesn't check out, when $i$ runs to $T$, we don't have $s_{T+1}$ to plug in to $s_{i+1}$ in your first equation. Sorry it's not an answer.


text:
Is the performance of a neural network, which was trained with encrypted data and weights, affected if the weights are decrypted?
Suppose that a neural network is trained with encrypted (for example, with homomorphic encryption and, more precisely, with the Paillier partial scheme) data. Moreover, suppose that it is also trained with encrypted weights.
If the neural network's weights are decrypted, is the performance of the neural network theoretically preserved or affected?

I tried to clarify your question and post. Please, make sure that it's consistent with your original question/intentions. Also, please, next time, try to ask a clearer question by also providing more context (including links to relevant resources).


text:
Bayesian hyperparameter optimization, is it worth it?
In the Deep Learning book by Goodfellow et al., section 11.4.5 (p. 438), the following claims can be found:

Currently, we cannot unambiguously recommend Bayesian hyperparameter
optimization as an established tool for achieving better deep learning results or for obtaining those results with less effort. Bayesian hyperparameter optimization sometimes performs comparably to human experts, sometimes better, but fails catastrophically on other problems. It may be worth trying to see if it works on a particular problem but is not yet sufficiently mature or reliable

Personally, I never used Bayesian hyperparameter optimization. I prefer the simplicity of grid search and random search.
As a first approximation, I'm considering easy AI tasks, such as multi-class classification problems with DNNs and CNNs.
In which cases should I take it into consideration, is it worth it?

Efficiently integrating HPO frameworks into an existing project is non-trivial. Most common datasets/tasks already have established architectures/hyperparameters/etc. and require only a few additional tuning parameters. In this case, the benefits (assuming they exist) brought by Bayesian HPO techniques lack behind development time (simplicity), and this is one dominant reason that users prefer grid search or random search over some more sophisticated Bayesian optimization techniques.
For a very large scale problem and an entirely new task (or dataset) for which the user has no intuition on "good hyperparameters", Bayesian HPO may be a good option to consider over random or grid search. This is because there may be a very large number of hyperparameters (due to insufficient domain knowledge), and integrating HPO into the project may result in far less time than grid search over all possible hyperparameters.

You claim "Efficiently integrating HPO frameworks into an existing project is non-trivial", but you do not explain why. There are many hyper-parameter optimization packages, so I am not sure why you're saying it's non-trivial to integrate BO into your project. Compared to a random search or grid search, yes, sure, BO is slightly more complicated, because RS and GS are super trivial, but that doesn't make BO really difficult to integrate into your project, so I don't think that this is the main reason why BO is worth it or not.

Moreover, in many cases (especially in RL), to achieve the best performance, you really need to perform hyper-parameter optimization, because, even if there are already default hyper-parameters' values, they are typically not optimal for your specific problem.

OP is considering "easy AI tasks such as multi-class classification". In such cases, HPO is definitely an overkill. There are plenty of resources with already-optimized HPs. Of course, running additional searches may increase overall performance by 0.xx%, but if you consider scraping some DL tutorial or writing a training script, even using HPO frameworks would take significantly longer as suggested in first paragraph. In more complicated scenarios (second paragraph / RL as you suggest), one could and should integrate HPO frameworks. I think my response is an adequate fit to what OP considers.


text:
In the update rule of RMSprop, do we divide by a matrix?
I've been trying to understand RMSprop for a long time, but there's something that keeps eluding me.
Here is a screenshot from this video by Andrew Ng.

From the element-wise comment, from what I understand, $dW$ and $db$ are matrices, so that must mean that $S_{dW}$ is a matrix (or tensor) as well.
So, in the update rule, do they divide a matrix by another matrix? From what I saw on google, no such action exists.

Yes, you are correct, $S_{dW}$, in this case, is the matrix/tensor and it will have the same shape as gradient matrix/tensor. The update rule divides each element in gradient to each gradient in $S_{dW}$ or you can say "element-wise division".
To avoid the zero variable in $S_{dW}$, the equation usually like this:
$$
W=W-\alpha \frac{dW}{\sqrt{S_{dW}+\epsilon}} \text{  where } \epsilon=10^{-8}
$$
If you want to implement it manually with Python, you can take a look at this link


text:
Can the attention mechanism improve the performance in the case of short sequences?
I am aware that the attention mechanism can be used to deal with long sequences, where problems related to gradient vanishing and, more generally, representing effectively the whole sequence arise.
However, I was wondering if attention, applied either to seq2seq RNN/GRU/LSTM or via Transformers, can contribute to improving the overall performance (as well as giving some sort of interpretability through the attention weights?) in the case of relatively short sequences (let's say around 20-30 elements each).

They shouldn't have any issues with short sequences, as short dependencies are easier to learn. The only difficult cases are long dependencies which is where most of the research is geared at. However, this is assuming that by "short sequence" you mean a sequence of text that is fully contained within itself, i.e. there is no cross-sequence dependencies.
For example, if you have a really long paragraph that doesn't fit in a transformer model, you would have to break that paragraph into many "short sequences", but each of these sequence may have a dependency that depends on another sequence, i.e. cross-sequence dependencies. For these cross-sequence dependencies, any model with recurrence should do better than ones without (e.g. RNN, LSTM, Transformer-XL).
If each short sequence is self-contained, then all of the models should perform pretty well.

Thank you very much for the explanation. I am not really dealing with NLP, but with sequences which have a reasonably similar representation. All those sequences are self-contained. My idea was to exploit attention (I was using plain LSTMs, with quite good performance) to leverage the fact that I know that some elements of my input sequence are more relevant to predict certain elements of the output sequence (the problem is encoded as a seq2seq one). So, in this context, attention, even if I am dealing with short sequences, could be helpful?

Yes, if your task parallels a seq2seq task, then it is very likely Transformers will do better than LSTM on ideal conditions. But if you have a small transformer model, small dataset, or small hardware, transformers will likely to perform worse than LSTM. The reason transformers push state of the art is because companies can train extremely huge models on extremely huge datasets very quickly. But if you are training a model from scratch and you do not have powerful hardware and millions of data points, I think LSTM would be more practical.


text:
In the Binary Flower Pollination Algorithm (using the sigmoid function), is it possible that no feature is selected?
I'm trying to use the Binary Flower Pollination Algorithm (BFPA) for feature selection. In the BFPA, the sigmoid function is used to compute a binary vector that represents whether a feature is selected or not. Here are the relevant equations from the paper (page 4).
$$
S\left(x_{i}^{j}(t)\right)=\frac{1}{1+e^{-x_{i}^{j}(t)}} \tag{4}\label{4}
$$
\begin{equation}
x_{i}^{j}(t)=\left\{\begin{array}{ll}
1 & \text { if } S\left(x_{i}^{j}(t)\right)>\sigma \\
0 & \text { otherwise }
\end{array}\right.
\tag{5}\label{5}
\end{equation}
In my case, I noticed that my algorithm sometimes returns a zero vector (i.e. all elements are zeros, such as $[0,0,0,0,0,0,0,0,0]$), which means that no feature is selected (a feature would be selected when it is $1$), which makes the fitness function returns an error.
Is it correct that sigmoid returns result like that?

Which $\sigma$ are you using in your case? Clearly, if $\sigma$ is very big, then it's possible that most features will not be selected, according to formula 5.

σ is a random value between 0 and 1 ..

If you have a link to a Github repository that contains your implementation of the BFPA algorithm, it may be a good idea to edit your answer and provide such a link. However, note that programming issues are off-topic here. I'm suggesting you to include the link in case someone wants to take a look at the source code for more info.

unfortunately, I didn't put it at Github yet,,, I am just asking about sigmoid function, Is it possible to return a zero vector like what I explained in my question? or it always returned at least one selected feature?

It's not clear to me if you're getting a zero vector after the sigmoid or after the threshold operation (operation 5). Can you clarify this?

after sigmoid .. there is no threshold used with binary selection ..

Are you following this paper https://repositorio.unesp.br/bitstream/handle/11449/177329/2-s2.0-84926656505.pdf?sequence=1? Check section 2.1.1. So, yes, there's a threshold operation after the sigmoid and I've also included it in your post above!!!

Please, provide a link to your source code. For example, create a public Github gist here to share your code. That may be helpful.


text:
What is the difference between zero-padding and character-padding in Recurrent Neural Networks?
For RNN's to work efficiently, we vectorize the operations, which results in an input matrix of shape
(m, max_seq_len)

where m is the number of examples, e.g. sentences, and max_seq_len is the maximum length that a sentence can have. Some examples have smaller lengths than this max_seq_len. A solution is to pad these sentences.
One method to pad the sentences is called "zero-padding". This means that each sequence is padded with zeros. For example, given a vocabulary where each word is related to some index number, we can represent a sentence with length 4,
I am very confused

by
[23, 455, 234, 90]

Padding it to achieve a max_seq_len=7, we obtain a sentence represented by:
[23, 455, 234, 90, 0, 0, 0]

The index 0 is not part of the vocabulary.
Another method to pad is to add a padding character, e.g. <<pad>>, in our sentence:
I am very confused <<pad>>> <<pad>> <<pad>>

to achieve the max_seq_len=7. We also add <<pad>> in our vocabulary. Let's say its index is 1000. Then the sentence is represented by
[23, 455, 234, 90, 1000, 1000, 1000]

I have seen both methods used, but why is one used over the other? Are there any advantages or disadvantages comparing zero-padding with character-padding?

At least in Keras it is the default. Sure, you can pad_sequences and use a Masking layer with an arbitrary value. But the Embedding layer, the most frequent consumer of these encodings, provides a "mask_zero" boolean parameter.


text:
What are the different types of goals for an AI system called?
I remember reading about two different types of goals for an intelligence. The gist was that the first type of goal is one that "just is" - it's an end goal for the system. There doesn't need to be any justification for wanting to achieve that goal, since wanting to do that is a fundamental purpose for that system. The second type of goal is a stepping stone, for lack of better words. Those aren't end goals in and of themselves, but they would help the system achieve its primary goals better.
I've forgotten the names for these types of goals and Googling didn't help me much. Is there a standard definition for these different types of goals?

goals are also important in Prolog like systems

AI researcher Rob Miles uses the terms 'terminal goal' and 'instrumental goal' for the first and second types respectively. I'm not sure if these are standard parlance in the field, however Rob explains them in this video:
https://youtu.be/hEUO6pjwFOo?t=363

I LOVE Rob Miles! That's an underrated channel.
https://www.youtube.com/channel/UCLB7AzTwc6VFZrBsO2ucBMg

Do you mean weak AI and strong AI?
The former is roughly about pretending to be intelligent, ie do intelligent things, but without trying to work the same way an actually intelligent system would work. The latter attempts to replicate how an intelligent system works, so would require us to understand a lot more about cognition than if we just mocked up a quick little chatbot to try and compete the Turing Test.

I don't think the OP was referring to "weak AI vs strong AI" (but it's also possible). To me, it seems they are talking about "intermediate goals", "motivational goals" and "main goals" (I don't think this is standard terminology anyway) .

@nbro Yes, it's a bit of a vague question.


text:
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.
Why are the following statements true?

$A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as long as the optimal path.
$h_2(n)  + 1$ is guaranteed to be inadmissible for any $h_1(n)$

Hello. You can use latex/mathjax on this site, so please edit your post to format it properly with it. Moreover, this seems to be a homework problem. Is this true? If yes, tell us what have you tried so far.

The sketch of the proof for your first question:
for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3  h_1(n)$. Hence, all the time for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of Chapter 3 in "Heuristics Intelligent Search Strategies for Computer Problem Solving" book by Judera Pearl), i.e., for the node $n^*$ with optimal value, $f_1(n^*) \leqslant C^*$ that $C^*$ is the optimal value. Therefore, A* with $h_2$ will return a solution in node $n'$ by the cost of $f_2(n') \leqslant 3 f_1(n^*) \leqslant 3C^*$, as $f_1(n') \leqslant 3 f_1(n^*)$ (see more details of the proof in Theorem 13 of Chapter 13 in the same reference).
You can find more about $h_2$ under the title of $\epsilon$-admissibility as it is $(1 + \epsilon) h_1$ that $h_1$ is an admissible heuristic function. In your case, $\epsilon = 2$.


text:
Does Linear Discriminant Analysis make dimensionality reduction before classification?
I'm trying to understand what LDA exactly does when used as a classifier. I've understood how the dimensionality reduction works and I've understood that the classification task is carried out with the application of Bayes' theorem, but I still can't figure out if LDA executes both operations when used as a classification algorithm.
Is it correct to say that LDA, as a classifier, executes by itself dimensionality reduction and then applies Bayes' theorem for classification?
If that makes any difference, I've used LDA in Python from the sklearn library.


text:
What's up with Neural Stochastic Differential Equations from a practical standpoint?
I've spent a few days reading some of the new papers about Neural SDEs. For example, here is one from Tzen and Raginsky and here is one that came out simultaneously by Peluchetti and Favaro. There are others which I plan to read next. The basic idea, which are attained via different routes in each paper, is that if we consider the input data arriving at time $t=0$ and the output data arriving at time $t=1$, and with certain assumptions on the distribution of network weights and activations, the evolution of the data from one layer to the next inside the network is akin to a stochastic process. The more layers you have, the smaller the $\Delta t$ is between the layers. In the limit as the number of layers goes to infinity, the network approaches a true stochastic differential equation.
I am still working on the math, which is my main objective. However, what I find missing from these papers is: Why is this important? The question is not, why is this interesting?. It is certainly interesting from a purely mathematical perspective. But what is the importance here? What is the impact of this technology?
I was at first excited about this because I thought it proposed a way to apply a neural network to learn the the parameters of an SDE by fitting it to real time-series data where we don't know the form of the underlying data generation process. However I noticed in the experiment of Peluchetti and Favaro is simply the MNIST data set, while the data experiment from Tzen and Raginsky is in fact a simulated SDE. The later fit more with my intuition.
So, again, my question is, what is the general importance of Neural SDEs? And a secondary question is: am I correct in thinking this technology proposes a new way to fit a model to data which we suppose is generated by a stochastic process?


text:
What are the main differences between YOLOv3 and RetinaNet object detection algorithms?
I am looking at a certain project that compares performance on a certain dataset for an object detection problem using YOLOv3 and RetinaNet (or the "SSD_ResNet50_FPN" from TF Model Zoo). Both YOLOv3 and RetinaNet seem to have similar features like detection at scales, skip connections, etc.
So, what is the exact main difference between YOLOv3 and SSD_ResNet50_FPN?

There are several key differences between YOLOv3 and RetinaNet.

RetinaNet is an object detection model that utilizes two-stage cascade and sampling heuristics to address class imbalance during training. whereas YOLOv3 is a real-time, single-stage object detection model that builds on YOLOv2 with several improvements.

RetinaNet uses a ResNet50 backbone, while YOLOv3 uses a Darknet53 backbone.

RetinaNet uses Focal Loss to prevent the easy background examples from overwhelming the network during training, while YOLOv3 uses Cross-Entropy loss.

YOLOv3 is fast and accurate in terms of mean average precision (mAP) and intersection over union (IOU) values as well.

YOLOv3 predicts bounding boxes and class probabilities directly from full images in a single pass, while RetinaNet first classifies proposal regions and then predicts bounding boxes and class probabilities for each region. This makes YOLOv3 faster and simpler, but also less accurate than RetinaNet. hence suitable for use where the priority is real-time performance with FPS: 51. RetinaNet has a high mAP 82.89%, but the detection speed FPS: 17 is not fast enough for real-time application.

The accuracy of detecting objects with YOLOv3 can be made equal to the accuracy when using RetinaNet by having a larger dataset, making it an ideal option for models that can be trained with large datasets.

The loss function of YOLOv3 converges faster, indicating that the training time of the YOLOv3 model is shorter than RetinaNet.

RetinaNet is better at detecting rotated objects.

YOLOv3 can be trained on more data more quickly than RetinaNet

The loss functions used by each algorithm are different.

YOLOv3 may not be ideal for using niche models where large datasets can be hard to obtain but its sutible for models like traffic detection, where plenty of data can be used to train the model since the number of images of different vehicles is plentiful.

Precision for Small Objects:
The chart below (taken and modified from the YOLOv3 paper) shows the average precision (AP) of detecting small, medium, and large images with various algorithms and backbones. The higher the AP, the more accurate it is for that variable.

Source: Focal Loss for Dense Object Detection
YOLOv3 increased the AP for small objects by 13.3, which is a massive advance from YOLOv2. However, the average precision (AP) for all objects (small, medium, large) is still less than RetinaNet.
Speed:
YOLOv3 is fast and accurate in terms of mean average precision (mAP) and intersection over union (IOU) values as well. It runs significantly faster than other detection methods with comparable performance (hence the name – You only look once). Moreover, you can easily trade off between speed and accuracy simply by changing the model’s size, without the need for model retraining.

References:

RetinaNet(PapersWithCode)

YOLOv3(PapersWithCode)

Comparison of RetinaNet, SSD, and YOLO v3 for real-time pill identification

A Practical Guide to Object Detection using the Popular YOLO Framework – Part III (with Python codes)

Object Detection for Dummies Part 3: R-CNN Family

Comparison of YOLOv3 and SSD Algorithms


text:
Does it make sense to combine classifiers trained on the same dataset?
I am working on a classification problem.
I have a dataset $S$ and I am training several prediction algorithms using S: Naive Bayes, SVM, classification trees.
Intuitively, I was planning to combine my models, and, for each data point in the test sample $S'$, take the majority vote as my prediction.
Does that make sense? I feel this is a very simplistic way to combine different models.

These are generally known as ensemble methods. Your method is essentially what Scikit-Learn's VotingClassifier does, which is perfectly reasonable and might give you better results. Of course, if you have an ensemble of classifiers and some of them perform quite poorly, the ensemble might not be able to beat the best classifier: you'll need to check this in your cross-validation. Be aware that any confidence or probability estimates may not be well-calibrated, so the predictions from the ensemble may not be particularly meaningful.
There are more elaborate ways of ensembling classifiers. Random forest classifiers, for example, are just ensembles of decision trees; a technique called bagging is also used here to improve performance.
The technique of using a second model to weight the predictions from an ensemble is known as stacked generalisation. It was introduced by Wolpert in 1991 [1], and you can find plenty of interesting examples of using the technique, e.g. on Kaggle.
[1] David H. Wolpert. Stacked generalization. Neural Networks 5.2 (1992), pp. 241-259.

It is a simple way to do it but it is not wrong.
If you are getting probabilities for each model, then, you can average them. Then, you can do the classification.
Also, you assign weights to each model based on a validation set and regressing the weights for each models prediction.


text:
How to deal with a variable number of channels of the inputs?
I have a problem in which my input data may have a varying number of channels. Let me explain with an example.

Imagine we have a classification problem in which we wish to identify
if certain species are present in wildlife photographs. This can be
done via a neural network including maybe some convolutions. For the
first layer of the network we could set up a convolutional layer with
3 input channels (one for R, G and B respectively) and this would
probably work well enough.
Now imagine that someone comes along with some new data for us and
this time they have not only taken regular RGB images but they have
used an IR-camera as well. Great, but how do we treat this data, we
have one more channel?! One could of course simply add an extra channel
and re-train the network but that would mean that our old data (without
IR-info) is useless and what if someone comes along with a
UV-camera.....

My situation is similar but I will most definitely be dealing with varying numbers of channels and the range can be quite wide (from 5 channels all the way up to maybe 50). Is there a good way of dealing with a situation like this?

A naive way will be to 0-pad all the training samples to fit the maximum number of channels.

@DuttaA Do you care to expand on that? I've never heard of meta learning and learning with privileged information before.

Given the enormous range of the number of channels per input, I would suggest treating each channel as a step in a time series. So create some kind of RNN with convolutions throughout that accepts a channel of the input. That way it will be able to deal with varying input sizes and still give valid predictions.


text:
How to define machine learning to cover clustering, classification, and regression?
How to define machine learning to cover clustering, classification, and regression? What unites these problems?

I report three definitions of machine learning (ML) and I also explain that ML can be divided into multiple sub-tasks or sub-categories in this answer. However, it may not always be clear why classification, regression, or clustering can be considered machine learning tasks or can be solved with ML algorithms/programs, so let me explain why these tasks can be solved with ML, based on Tom Mitchell's definition of an ML algorithm that I report below for completeness.

A computer program is said to learn from experience $E$ with respect to some class of tasks $T$ and performance measure $P$, if its performance at tasks in $T$, as measured by $P$, improves with experience $E$.

So, according to this definition, for a computer program to be a "machine learner", we need to identify $E$, $T$, and $P$, and show that the computer program improves with $E$ at performing the task(s) $T$, according to $P$.
For the case of classification or regression (these are the tasks, which is just a synonym for problems), let's suppose that we are given the training labelled dataset $D = \{(x_1, y_i), \dots, (x_N, y_N) \}$ of $N$ tuples $(x_i, y_i)$, where $x_i$ are the inputs to the program (or model) and $y_i$ (the label, aka class, hence the name classification) is the output that the program should produce. In the case of classification, $y_i$ is an element of a discrete set, e.g. $\{0, 1\}$ in the case of binary classification, while, in the case of regression, $y_i \in \mathbb{R}$ is a real number.
So, in this case, the experience $E$ is $D$ (the training labeled dataset). The task $T$ is classification or regression, depending on whether $y_i$ belongs to a discrete or continuous space. The performance measure $P$ can be e.g. the cross-entropy (which is typically used to solve the classification task) or the mean squared error (which is typically used to solve the regression task). (I will not recall the definitions of these performance measures here: you can take a book on ML for the details).
So, we have identified $E$, $T$ and $P$. Now, we also need to argue why a program's performance measured by $P$ would improve with $E$. Let's suppose that you are using a neural network trained with gradient descent to solve these tasks. After one epoch/iteration of gradient descent, the loss will be smaller, so the performance of the program will be higher. So, this would indeed be a machine learner, according to Mitchell's definition of ML.
In the case of clustering (the task $T$), the only difference is that the dataset $D$ (i.e. the experience $E$) is unlabelled, i.e. we do not have labels, but we are given only the inputs, and the goal, as you know, is to group these inputs based on their similarity, according to some notion of similarity, which is your performance measure $P$.
The other definitions of ML that I report in the other answer are also consistent with Mitchell's definition. More precisely, most of these definitions are based on the idea that an ML algorithm is an algorithm that "finds patterns in data". To solve the classification, regression and clustering tasks/problems, an ML algorithm/program needs to find patterns in the data (either explicitly, like in the case of clustering, or indirectly, like in the case of classification), in order for the program's performance to improve.
Moreover, given that you brought this up in the now-deleted comments, I don't think that the definition of machine learning necessarily implies prediction (i.e. the use of a model to forecast something about future data), but, yes, ML is often used for prediction.
It's also important to note that, when someone says "machine learning" without further details or information (like you did in your post/question), one may refer to

the field/area of study that studies and applies ML algorithms, or
an ML algorithm (and sometimes model).

Mitchell's definition is the definition of what it means for an algorithm/program to be called an ML algorithm/program. However, my definition of ML as a field immediately follows from the definition of an ML algorithm.
Finally, we could say that a problem that can be formulated in such a way that an ML algorithm can be applied is an ML problem. Note that Mitchell's definition does not mention "ML problem" anywhere, but just "problem", so this is not a circular definition. So, we could say that classification, regression, and clustering are "ML problems" because they can be solved with ML algorithms. More generally, all these three problems can be thought of as "function approximation" problems, i.e., in all these cases, the solutions are functions.

This assumes asymptotic learning. This approach agrees with the Statistical Learning Theory, which expects training set to go to infinity. But in the particular ML problems as described in textbooks, as well as in real life, the training set is fixed. It is not increasing. So, it does not make sense for me to define ML problem through increasing training set. Besides, I do not see how clustering fits here: will the performance of clustering algorithms improve with increase of training set? I doubt it.

We do find patterns in data, but we find very specific patterns. For example, we do not look for sequences of identical numbers. So, to understand what patterns the definition has in mind, one needs to know what ML is.

@Marina Why do you think that this assumes asymptotic learning? When one says "it improves with experience", one is not specifying exactly how or for how long, the only requirement is that it improves with experience at some point. It doesn't always have to improve with experience. In fact, if the learner is already optimal, you don't need more experience, so you can stop learning. So, yes, the training dataset can be fixed and finite, and this is true in almost all cases, and it's always true in practice that the dataset is finite.

I've just explained how clustering fits into this framework. As long as it improves with data/experience according to some performance measure, then it's a machine learning algorithm/program (or machine learner). E.g., you can take k-means. In k-means, we want to minimize a certain objective function. That objective function is the performance measure and, if k-means finds a local optimum of that objective function starting from some randomly located point in the search space, then it's improved with experience, so k-means is an ML algorithm.

Your definition says: IF experience increases THEN the performance increases. It says nothing about the case when experience does not increase.

Your definition requires to define the class of tasks T. Is not it the same as define ML?

@Marina That's not my definition of machine learning, but Tom Mitchell's definition, which I think is good enough to describe most ML algorithms. Yes, it's true that it doesn't say anything about when the experience does not increase, but the point/idea of this definition is to define what it means "for a program to learn". If a program respects what is written in that definition, then it's learning, i.e. it's an ML program, otherwise, it's not.

Let us continue this discussion in chat.

You give example of defining tasks of classification or regression, then you give examples of criteria. Then you say " So, we have identified E, T and P. " No, we have not.

@Marina Can you explain why not? I'm saying what they are in my answer.

@nbro In the definition should the word "improves" interpreted literally? I mean we can have an algorithm that becomes worse (as measured by P) with experience. So is it correct to say that"improves" give the idea of learning? It is like in school, if you are doing good at exams it should be the case that you have learned something in order to be able to get good grades, otherwise not.

@adosar If your performance doesn't improve, then have you learned with respect to that performance measure or specific goal? I don't think so. Maybe you learned other things, with respect to other vaguely defined performance measures or goals. That's maybe what confuses you. For instance, if your goal is to learn quantum mechanics, but your performance at the exercises never improves, then you have not learned anything, unless you're making mistakes on purpose, but that's a different story. Maybe you learned about general relativity, but that may not help you with the QM exam.

@nbro Thats what I wanted to say but you stated it and made it more clear.

@nbro Thank you for this answer; it really helped me understand Mitchell's definition (especially how to interpret "Experience").  May I ask a clarification question?  In the case of clustering, should I imagine T is "divide this dataset into clusters" and E is "the entire dataset"?  It feels a little circular or vacuous in that case... of course you improve at clustering the dataset using the dataset.  Do you see what I'm confused by?


text:
Which meta-learning approach selection methodology should I use for similarity learning of an image?
Meta-learning has 3 broad approaches: model, metric and optimization-based approach. Each of them has its own sub-approach, like matching network, meta-agonistic and Siamese-based network, and so on.
How do I decide which approach to select for a task? For my case, I have a noisy image, and they need to be compared with 10 different new images every time. Do I have to start with the trial and error method, or there is some methodology behind this approach selection?

Could you please provide a reference where you read about these "meta-learning approaches"?

The only principled approach is to see if the problem you are working has been worked on before. If yes, then, use what they used for your problem. It is the alternative to go through all the models one-by-one.
Like, in your case, it bears a semblance with face models, so, Siamese network with ArcFace loss for getting your embeddings is a good bet for you.


text:
Is a team of ML scientists an "intelligent agent"?
I am writing about the role of machine learning scientists in developing a solution. Is there a term for the humans who do learning?
Can we call a "team of machine learning scientists with their computers working on some ML problem"   an intelligent agent? Is "cognizer" the right term? I know that "learner" is reserved for an ML algorithm. I just want a shorter term for their role in cognition, learning.

We already had 2 related questions in the past. Check them here and here.

Is there a term for the humans who do [machine] learning?

Typically you will see "AI researchers" for people studying machine intelligence in general, or "data scientists" for people working with statistics or studying specific solutions in machine learning. Both those terms are used quite flexibly, and generally understood to be scientists/engineers that work on machine intelligence problems. There are also other specialisms that might apply, such as "computer vision researcher".
If you are writing only about researchers who are focused mostly on learning systems - such as new types of learning model, or the best way to train a model for some group of tasks - then "machine learning researchers" or "ML researchers" would be fine. If they are specific people, you may want to ask them directly what title they prefer, in case you accidentally misrepresent their role and work.

Can we call a "team of machine learning scientists with their computers working on some ML problem" an intelligent agent?

No. That might be confused with something that the team is working on or creating. An "intelligent agent" can be the product of specific AI research. For instance, it is reasonable to consider AlphaZero to be an "intelligent agent" (not everyone would call it that, it depends on context, but not relevant to your question).

Is "cognizer" a right term?

No. That is an obscure term meaning something like "a being that perceives or knows". No-one will naturally associate that word with a team of researchers and their computers.

I just want a shorter term for their role in cognition, learning.

I think the most usual way to do this is to describe the team, and name them. For example:

"The MIT computer science researchers are using the X1000 system to investigate  learning of abstract spaces. The MIT team said yesterday . . ."

"Professor Hilary Smith is working with a team of graduates on the Learny McLearnface framework. Smith's team have discovered that . . ."

This is the normal way that you see a research team introduced and referred in science journalism in e.g. New Scientist or Scientific American.
If you need to describe some abstract approach about a team working in general, then you can use a similar approach, naming your teams according to how you need to differentiate between them.

I am writing about epistemology and role of general machine learning team in working on  a machine learning problem. So, I would like to use some general term.

There is Russian term "субъект познанания" which would fit, but literal translation "subject of cognition" does not make much sense, does it?


text:
How do you pass the image from one convolutional layer to another in a CNN?
I am currently trying to write a CNN from scratch, but I don't understand how to feed the information from a max-pooling layer to the next convolutional layer. Specifically, I don't know what to do with the 6 filtered and pooled images from the first convolutional and max-pooling layers. How do I feed those images into the next convolutional layer?

The application of 1 kernel (aka filter) to an input (with a 2d convolution) is a matrix (a 2d array), which is often known as a feature map (aka activation map). The application of $k$ kernels to the same input is a 3d array (sometimes called tensor, though this may not be exactly correct, or 3d volume) with depth $k$, i.e. you have $k$ concatenated feature maps. This 3d array is the input to the next convolutional layer, which needs to have 3d kernels of depth $k$: this is the main requirement in the case of 2d convolutions (in the case of 3d convolutions, the kernels can have a different depth than the input 3d volume, but you can ignore this for now!).
Another thing that you need to take care of is the padding that you can add around this 3d volume. This, along with the stride (i.e. the step with which you move the kernel), determines the height and width of the output of the convolutional layer.
So, to recapitulate, what you have to do is set the depth of the kernels in the convolutional layer $l+1$ to be equal to the number of kernels that you use in the convolutional layer $l$. So, let's say that the number of kernels is a hyper-parameter (note that this is usually the case!), and that the user sets the number of kernels $k=8$ in the convolutional layer $l$, and, for simplicity, assume that all kernels are $3 \times 3$, then, in layer $l$, you will perform $8$ convolutions, one for each kernel. These $8$ convolutions produce a 3d array of dimensions $w \times h \times 8$ (where $w$ and $h$ depend on the dimensions of the input to layer $l$, the stride, and padding). Consequently, in the convolutional layer $l+1$, the kernels need to be $3 \times 3 \times 8$.
If it's the pooling layer that produces the 3d array to be passed to the next convolutional layer, you should still set the depth of the kernels in the convolutional layer $l+1$ to the number of kernels in the convolutional layer $l$ (provided that, in the pooling layer, you only redimension the width and height of the 3d array, which is usually the case).


text:
Why does regular Q-learning (and DQN) overestimate the Q values?
The motivation for the introduction of double DQN (and double Q-learning) is that the regular Q-learning (or DQN) can overestimate the Q value, but is there a brief explanation as to why it is overestimated?

The overestimation comes from the random initialisation of your Q-value estimates. Obviously these will not be perfect (if they were then we wouldn't need to learn the true Q-values!). In many value based reinforcement learning methods such as SARSA or Q-learning the algorithms involve a $\max$ operator in the construction of the target policy. The most obvious case is, as you mentioned, Q-learning. The learning update is
$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$
The Q-function for the state-action tuple we are considering is shifted towards the max Q-function at the next state where the $\max$ is taken with respect to the actions.
Now, as mentioned our initial estimates of the Q-values are initialised randomly. This naturally leads to incorrect values. The consequence of this is that when we calculate $\max_aQ(s', a)$ we could be choosing values that are grossly overestimated.
As Q-learning (in the tabular case) is guaranteed to converge (under some mild assumptions) so the main consequence of the overestimation bias is that is severely slows down convergence. This of course can be overcome with Double Q-learning.
The answer above is for the tabular Q-Learning case. The idea is the same for the the Deep Q-Learning, except note that Deep Q-learning has no convergence guarantees (when using a NN as the function approximator) and so the overestimation bias is more of a problem as it can mean the parameters of the network get stuck in sub-optimal values.
As someone asked in the comments about always initialising the values to be very low numbers, this would not really work.
Consider the following MDP taken from Sutton and Barto:
We start in state A, from which we can either go right with reward 0 leading to a terminal state or go left with reward 0 to state B. From state B we can take, say, 100 different actions, all of which lead to a terminal state and have reward drawn from a Normal distribution with mean -0.1 and variance 1.
Now, clearly the optimal action from state A is to go right. However, when we go left and take an action in state B there is an (almost) 0.5 probability of getting a reward bigger than 0. Now, recall that the Q-value is shifted towards $r(s, a) + \max_a Q(s', a)$; because of the stochastic rewards when transitioning out of state B and the fact that we will likely see a positive reward the $\max_a Q(s', a)$ will be positive.
This means that when we take the left action the Q-value (Q(A, left)) is shifted towards a positive value, meaning that when we are in state A the value of moving left will be higher than moving right (which will gradually be being shifted towards the true value of 0) and so when following the $\epsilon$-greedy policy the greedy action will be to go left when in fact this is sub-optimal.
Now, of course, we know that the true Q-values will eventually converge but if we do have, say, 100 actions then you can probably see that the time it will take for the Q-values to converge to the true value will potentially be a long time as we would have to keep choosing all the overestimated values until we had convergence.

Why couldn't you then initialize everything with let's say $-\infty$ or very negative value to prevent this overestimation, if this is really because of random initialization, why would you then need double Q-learning.

You may find a more rigorous explanation in the original double Q-learning paper.

@brale you’re right, my answer isn’t satisfactory. I’ll expand on it tomorrow. I have a nice example where rewards are stochastic that can illustrate the example.

Unfortunately, I haven't received a solid explanation for overestimation. To the end, it doesn't stack up, and there's no reason to overestimate if it finally converges.
Ultimately, the question is how much faster learning can be done by modifying this expression than other methods that streamline learning.
Do you have the resources to compare with other learning efficiency methods?

@groundclown I just finished making another edit, could you let me know whether this clears things up for you, please. You say there is 'no reason' to overestimate - could you elaborate on this as I'm not sure what you mean. The reason we overestimate is clear - because we are taking the $\max$ of a noisy estimate. The reason it is an issue is because it severely slows down convergence.

This starts to be an exact duplicate of this: https://ai.stackexchange.com/q/22776/2444. The original question was why Q-learning overestimates the values. The question was not something different, such as "Why would we need Double DQN" or "Could we initialize the values to minus infinity?". So, your original answer already answered the original question. It's probably better to just link to your other answer, if it contains the exact info, rather than writing everything here again. This is just my suggestion.

Thanks @nbro, I thought as much (and also didn't want to have to repeat myself!).


text:
$\nabla \log \pi$ with respect to some parameters constantly being zero
I am new to reinforcement learning. May I ask a simple (and maybe a bit silly) question here? I am trying to use the "one-step actor-critic" method to train a robot on a gridworld. Let's focus on the actor as there is nothing puzzling me for the critic.
I used a feedforward ANN with one hidden layer to parameterize the action preference function (i.e. the $h$ function). The ANN has one bias node in the input layer to connect to all the hidden nodes. Therefore, there are three sets of weights associated with the $h$ function -- the weights connecting the inputs to the hidden nodes (let's call it $W1$ matrix), the weights connecting the hidden nodes to the outputs (let's call it $W2$ matrix), and the weights connecting the bias node to the hidden nodes (let's call it $c$ vector).
I used the exponential soft-max as the policy function (i.e. the $\pi$ function). That is,
$$\pi(a|s,W1,W2,c) = \displaystyle\frac{e^{h(a,s,W1,W2,c)}}{\sum_be^{h(b,s,W1,W2,c)}}.$$
The inputs to the ANN are the state/feature vector, and the outputs of the ANN are the action preference values (i.e. the $h$ values). With these action preference values, the $\pi$ function can compute the probabilities for each action to be chosen.
It is easy to derive that
$$\nabla_{W1/W2/c} \log \pi(a|s,W1,W2,c) = \nabla_{W1/W2/c} h(a,s,W1,W2,c)-\sum_b \big[\nabla_{W1/W2/c}h(b,s,W1,W2,c)\pi(b|s,W1,W2,c)\big]$$
In the above, $/$ means "or".
My puzzle is, I found that $\nabla_{W2} h(\cdot,s,W1,W2,c) \equiv \sigma$, where $\sigma$ is the vector of the sigmoid activation values. That implies, $\nabla_{W2}$ is independent of actions!? Consequently, $\nabla_{W2} \log \pi(\cdot|s,W1,W2,c) \equiv 0$, which implies that $W2$ will not be updated at all...
Where did I get wrong?
(Actually, the above puzzle of mine extends to any policy gradient method as long as $\nabla \log \pi$ is involved and a feedforward ANN is used to approximate the action preferences.)


text:
Is my reward function non-Markovian?
I am working on an RL problem where the time when the agent obtains the reward for taking action $a$ in time step $t$ is stochastic. In fact, there is no immediate reward for taking action $a$ in time step $t$, and, for example, the agent may obtain the reward in time step $t+k$ (where $k>1$). I was wondering if this kind of reward function is categorized as a non-Markovian reward function, and which RL method works better (to approximate/find the optimum policy) in this environment?
PS: It differs from the sparse reward problems. In my problem, there is a non-zero reward associated with every action taken. However, the agent does not receive any reward immediately. In fact, once the agent takes an action, like $a$, at a time step like $t$, the agent does not have any control over when he/she will receive the reward associated with that action. The time when the reward is received is stochastic.

The Markov property is typically defined for states, so I'm curious to know what you mean by "Markovian reward function". So, what definition of "Markovian" do you have in mind for a reward function? Moreover, when you say "realizes the reward", do you mean "get/obtain the reward"? Please, edit your post to clarify these two points. To me, it seems that you're only talking about sparse reward functions. However, you first need to answer these 2 questions in order to properly give an answer.

Are you also user xuan? If so, you have attempted to edit the question under a different account to that used to ask the question. You can ask moderators to merge accounts if you have done this in error. Running two accounts might get you in trouble, if for example you use one account to upvote posts made by the other.

This question was also asked on Stack Overflow.

@xuan Do you care about explaining what you mean by non-Markovian in this case?


text:
What is the definition of pre-training?
I want to pre-train a model (combined by two popular modules A and B, and both are large blocks), then fine-tune it on downstream tasks.
What if for the weight initialization for pre-training, module A is initialized from some checkpoints, while B's is from random? Can I still claim the process as pre-training? Or the modules in the model must all be initialized from random, and so we can call it pre-training?
If parts of the module's weights are 'contaminated' by checkpoints, it is only can be called fine-tune?


text:
When computing the ROC-AUC score for multi-class classification problems, when should we use One-vs-Rest and One-vs-One?
The sklearn's documentation of the method  roc_auc_score states that the parameter multi_class can take the value 'OvR' (which stands for One-vs-Rest) or 'OvO' (which stands for One-vs-One). These values are only applicable for multi-class classification problems.
Does anyone know in what particular cases we would use OvR as opposed to OvO? In the general academic literature, is there a preference given to one?

The linked scikit-learn page already references three (3) academic publications on this - did you check them?

This time I decided to clarify your post by editing it, but it's not my job to do it: it's yours. Please, next time, provide the necessary details to answer the question and do not assume that we have been reading what you have also read or know what you're talking about. As someone pointed out above, some acronyms may not be well-known, for instance.


text:
What is the use of the regular convolutional layer in expansion path of U-Net?
I was going through the paper on U-Net. U-net consists of a contracting path followed by an expanding path. Both the paths use a regular convolutional layer. I understand the use of convolutional layers in the contracting path, but I can't figure out the use of convolutional layers in the expansive path. Note that I'm not asking about the transpose convolutions, but the regular convolutions in the expansive path.

The point is that in the expansive path you have two forms of information:

the information from the contracting path, which includes all high-level features extracted from the original image.
the information from the skip-connections, which copy a cropped version of the feature maps in the contracting path. Because, as we go forward through the expansive path these originate from earlier stages in the contracting path, these are progressively richer in detail.

Intuitively you can think of it as this: high-level features help the network tell which areas to group together, while details help it tell where each group starts and ends at the pixel level.
The idea is to combine these two forms of information, i.e. the high-level features and the details, optimally.  To do this you need trainable layers that learn this optimal combination. Here is where the convolution layers come to play.

It may be worth mentioning that in the expansive path we do both convolution and transpose convolution (and that's one case where people may get confused).

I know that convolutional layers extract features in the form of a feature map. The feature map stores the spatial location of different features(like edge, circle, etc.). Do convolution layers also combine the features?

@BhuwanBhatt they combine the feature maps, which are in the channels dimensions.


text:
How to update the observation probabilities in a POMDP?
How can I update the observation probability for a POMDP (or HMM), in order to have a more accurate prediction model?
The POMDP relies on observation probabilities that match an observation to a state. This poses an issue as the probabilities are not exactly known. However, the idea is to make them more accurate over time. The simplest idea would be to count the appeared observation as well as the states and use Naive Bayes estimators.
For example, $P(s' \mid a,s)$ is the probability that a subsequent state $s'$ is reached, given that the action $a$ and the previous state $s$ are known: In that simple case I can just count and then apply e.g. Naive Bayes estimators.
But, if I have an observation probability $P(z \mid s')$ (where $z$ is the observation) depending on a state, it's not as trivial to just count up the observation and the states, as I can not say that a state really was reached (Maybe I made an observation, but I was in a different state than wanted). I can just make an observation and hope I was in a certain state. But I can not say if e.g. I was in $s_1$ or maybe $s_2$. I think the update of the observation probability is only possible in the late aftermath.
So, what are good approaches to estimate my state?

Ok, now I think I fully understand this post. You want to estimate the probability distribution over the observations given e.g. the next states, $P(z \mid s')$, so that you can perform more accurate calculations (e.g. of the belief states) when that probability distribution is required. However, you don't know exactly in which state you are in, so you think that you cannot estimate $P(z \mid s')$, and that's why you're asking how you can estimate the state you're in. This looks like a circular problem.

Exactly, it is some sort of a circular problem, because the reliability of the observation is crucial to estimate the state. But if I can't even trust the observation (if I can't even trust my eyes) how will I determine that I was in a certain state. But I think, there must be a way to handle that problem, because how will ever a POMDP work, when I can't estimate my observation probability or if I can't have a more accurate propability distribution that matches the real systems behaviour.


text:
How is few-shot learning different from transfer learning?
To my understanding, transfer learning helps to incorporate data from other related datasets and achieve the task with less labelled data (maybe in 100s of images per category).
Few-shot learning seems to do the same, with maybe 5-20 images per category. Is that the only difference?
In both cases, we initially train the neural network with a large dataset, then fine-tune it with our custom datasets.
So, how is few-shot learning different from transfer learning?

Can you please put your main specific question in the title? "Few shot and transfer learning" is not a question and it's not specific. Take a look at this for the motivation.

I edited your post to remove the question "Can somebody help me understand how approaches like meta-learning are different from transfer learning?", because it's a completely different question than "How is few-shot learning different from transfer learning?". By the way, we already have that question here. I also try to clarify certain parts of your post. Please, make sure that I didn't change the meaning of the post.

They use the same techniques, but study different problems.
Transfer learning always does not imply that the novel classes have very-few samples (as few as 1 per class). Few-shot learning does.
The goal of transfer learning is to obtain transferrable features that can be used for a wide variety of downstream discriminative tasks. One example is using an ImageNet pretrained model as an initialization for any downstream task, but note that we need to train on large amounts of data on those novel classes for the model to be suitable to that task.
Note that you can't finetune an ImageNet classifier on few examples of COCO and expect it to generalize well, because it won't. It wasn't explicitly optimized for few-sample learning.
In few-shot learning, our aim is to obtain models that can generalize from few-samples. This could be transfer learned (with certain changes to the usual transfer learning scenario), or it could be meta-learned. It might not need both, it could just be augmented with data from the novel classes during the test time, and a classifier could be trained from scratch.


text:
How do gradients are flown back into the Siamese network when branching is done?
I am curious about the working of a Siamese network. So, let us suppose I am using a triplet loss for my network and I have instantiated single CNN 3 times and there are 3 inputs to the network. So, during a forward pass, each of the networks will give me an embedding for each image, and I can get the distance and calculate the loss and compare it with the output, so that my model is ready to propagate the gradients to update the weights.
The Question: How do these weights get updated during the back propagation? Just because we are using 3 inputs and 3 branches of the same network and we are passing the inputs one by one (I suppose), how do the gradients are updated? Are these series? Like the one branch will update, then the second and then the third. But won't it be a problem because each branch would try to update based on its output? If in parallel, then which branch is responsible for the gradients update? I mean to say that I am unable to get the idea how weights are updated in Siamese network. Can someone please explain in simpler terms?

It may be worth providing a link to both the siamese network paper, the paper that describes what you call "triple loss" (I suppose the Siamese paper), which I am not aware of, and what you mean by "single CNN 3 times". I suppose that whoever is familiar with the details of the Siamese network will understand your question, but it may still be useful to provide more context (and the links).


text:
What is the number of neurons required to approximate a polynomial of degree n?
I learned about the universal approximation theorem from this guide. It states that a network even with a single hidden layer can approximate any function within some bound, given a sufficient number of neurons. Or mathematically, ${|g(x)−f(x)|< \epsilon}$, where ${g(x)}$ is the approximation, ${f(x)}$ is the target function and  is $\epsilon$ is an arbitrary bound.
A polynomial of degree $n$ has at maximum $n-1$ turning points (where the derivative of the polynomial changes sign). With each new turning point, the approximation seems to become more complex.
I'm not necessarily looking for a formula, but I'd like to get a general idea on how to figure out the sufficient number of neurons is for a reasonable approximation of a polynomial with a single layer of the neural network (you may consider "reasonable" to be $\epsilon = 0.0001$). To ask in other words, how would adding one more neuron affect the model's ability to express a polynomial?

If the network has one hidden layer, there are papers like A closer look at the approximation capabilities of neural networks (Kai Fong Ernest Chong) saying "... given approximation threshold $\epsilon$ ... if $X$ in $\mathbb R^n$ is compact, then a neural network with $n$ input units, $m$ output units, and a single hidden layer with $\binom{n+d}{d}$ hidden units (independent of $m$ and $\epsilon$), can uniformly approximate any polynomial function $f:X \to \mathbb R^m$ whose total degree is at most $d$ for each of its $m$ coordinate functions."

@Vepir - that sounds much more like an answer than a comment.

Not an answer, but I find that simple neural networks are quite expressive. I suspect that any complete answer will have to address the network topology in some way.

Not sure this is answering your question but, one way to get a general idea of the number of neurons needed is to consider the number of turning points in the polynomial.
Each turning point in a polynomial corresponds to a change in the sign of its derivative, and the more turning points a polynomial has, the more complex its shape. For a polynomial of degree n, there can be at most n-1 turning points. This means that a polynomial with many turning points will require more neurons in the hidden layer to be accurately approximated.
In general, increasing the number of neurons in the hidden layer can improve the model's ability to express a polynomial. Adding one more neuron to the hidden layer can allow the network to capture more complex patterns in the data, which can lead to a more accurate approximation of the polynomial.
I have found these two sources very useful in visualising the above. Hope it helps.
http://neuralnetworksanddeeplearning.com/chap4.html
https://cs.stanford.edu/people/karpathy/convnetjs/demo/regression.html


text:
What is the smallest upper bound for a number of functions in a range that are computable by a perceptron?
I'm reading this book chapter, and I'm looking at the questions on the last page. Can someone explain question 2 on the last page to me, or show me an example of a solution so I can understand it?
The question is:

Consider a simple perceptron with $n$ bipolar inputs and threshold $\theta = 0$. Restrict each of the weights to have the value $−1$ or $1$. Give the smallest upper bound you can find for the number of functions from $\{−1, 1 \}^n$ to $\{−1, 1\}$ which are computable by this perceptron. Prove that the upper bound is sharp, i.e., that all functions are different.

What I understand:

A perceptron is a very simple network with $n$ input nodes, a weight assigned to each input nodes, which are then summed to be above/not above a threshold ($\theta$).

In this example, there are $n$ input nodes, and the value of each input node is either $−1$ or $1$. And we want to map them to outputs of either $−1$ or $1$.

What I'm confused about:
Is it asking how many different ways can you map input values of $\{−1, 1\}$ to $\{−1, 1\}$ output?
For example, is the answer, where each tuple in this list is input1, input2 and label, as described above:
$$[(1,1,1), (1,1,-1), (-1,1,-1), (-1,1,1), (1,-1,1), (1,-1,-1), (-1,-1,-1)]$$

Maybe you should explain exactly which part of the exercise you don't really understand what you understand about perceptrons. Do you know what an upper bound is? Please, edit this post to clarify what you don't really understand about the exercise. In any case, as far as I understand, you need to state something like this "A perceptron with such a threshold can learn at most $m$ functions of the form $f: {-1, 1}^n \rightarrow {-1, 1}$". So, the inputs are vectors of $n$ dimensions, where each element can either be $-1$ or $1$ and the outputs are either $-1$ or $1$.

Of course, you cannot just state it without knowing what you're talking about, but you need to say why $m$ is what you say. So, an upper bound would be infinity, but that's not the smallest upper bound. Note that an upper bound is just a number that is greater than or equal to the number you're interested in (in this case, the number of functions that such a perceptron can compute). So, the number that you give (i.e. your solution) cannot be smaller than the actual number of functions that the perceptron can compute (because that would not be an upper bound).


text:
Why do we need importance sampling?
I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the practical example of importance sampling.
For instance, in a video, it is said that we need to calculate the expected value of a biased dice, here $g(x)$, in terms of the expected value of fair dice, $f(x)$. Here is a screenshot of the video.

Why do we need that, when we have the probability distribution of the biased dice?

Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the distribution is only known up to a multiplicative constant, such as in Bayesian statistics where it is intractable to calculate the marginal likelihood; that is
$$p(\theta|x) = \frac{p(x|\theta)p(\theta)}{p(x)} \propto p(x|\theta)p(\theta)$$
where $p(x)$ is our marginal likelihood that may be intractable and so we can't calculate the full posterior and so other methods must be used to generate samples from this distribution. When I say intractable, note that
$$p(x) = \int_{\Theta} p(x|\theta)p(\theta) d\theta$$
and so intractable here means that either a) the integral has no analytical solution or b) a numerical method for computing this integral may be too expensive to run.
In the instance of your die example, you are correct that you could calculate the theoretical expectation of the bias dice analytically and this would probably be a relatively simple calculation. However, to motivate why importance sampling may be be useful in this scenario, consider calculating the expectation using Monte Carlo methods. It would be much simpler to uniformly sample a random integer from 1-6 and calculate the importance sampling ratio $x \frac{g(x)}{f(x)}$ than it would be to draw samples from the bias dice, not least because most programming languages have built in methods to randomly sample integers.
As your question is tagged as reinforcement learning I will add why it is useful in the RL domain. One reason is that it may be our policy of interest is expensive to sample from, so instead we can just generate actions from some other simple policy whilst still learning about the policy of interest. Second, we could be interested in a policy that is deterministic (greedy) but still be able to explore, so we can have an off-policy distribution that explores much more frequently.
NB: it may not be clear how you can use importance sampling if the distribution is only known up to a constant so see this answer for an explanation.