4
$\begingroup$

In machine learning, for the task of classifying input data (called an example) which are in binary representation, $\mathbf{x}\in \mathbb{R}^D$, $\mathbf{x} \in \{0,1\}^D$ into its multiple class labels that are also binary $\mathbf{y} \in \mathbb{R}^L$,$\mathbf{y} \in \{0,1\}^L$ and $L \ll D$, we estimate/ learn the parameters $\mathbf{w}$ called weights using learning algorithm (called as training phase) based on the knowledge of the class labels, $\mathbf{y}$.

  • If the class label for the example is known, the problem of estimation becomes supervised or non-blind. One commonly known algorithm is Least Mean Square.
  • If the labels are unknown, the problem becomes unsupervised or blind. After training phase, any unknown example can be classified based on the learned parameters, $\mathbf{w}$. $$ y = h(x) = \mathbf{w}^T \mathbf{x} \tag{1} $$

    Where $\mathbf{w}^T = $ is the transpose of $ \mathbf{w} $.

    If, $ h(x) > 0$ assign $\mathbf{x}$ to class $y_1$, otherwise assign $\mathbf{x}$ to class $y_2$. In this way, $h(x)$ is the classifier. So, in essence we are learning the mapping $h(\cdot)$ $$ \textrm{Input: } \mathbf x{\longrightarrow}\boxed{h}{\longrightarrow}\textrm{Output: } \mathbf y $$

From signal processing viewpoint, $h$ is the system or the channel through which the input passes and at the receiver we can get the same output if the channel is noiseless. So, the classifier $h(\cdot)$ is the encoder. But in signal processing, the transmitted signal is convolved with the channel impulse to get the output.

Encoder-Decoder

The image shows that the observation is a vector $\mathbf{y}$ and is referred as incomplete data and $\kappa$ = $(\mathbf{x, y})$ as complete data. When $\kappa$ is available, maximum likelihood estimation can be performed to determine both source state information (SSI) and channel state information (CSI) at the decoder side. In a coded communication system, the incomplete data $\mathbf{y}$ is the only available observation to the decoder.

Questions :

  • Suppose, in machine learning the goal is to retrieve the information after the training phase. In response to a query the trained system returns the correct output, then, is this retrieval process correspond to Equalization that is information reconstruction whereby we want to get back an estimate of the input? How does the task of information retrieval be viewed from the perspective of signal processing?
  • What needs to be estimated in unsupervised setting so that the output corresponds to the actual input?What is being retrieved?
  • Is it the output $y$ or the input $x$ that is the unknown thing that would make it unsupervised learning? The input to the classifier is called as the observation but in signal processing (and seen in the picture above), the observation is the output of the channel $y$.
  • ML estimation of a parameter $\theta$ which includes both SSI and CSI is therefore obtained by maximizing the log-likelihood: $\hat{\theta} = \arg \max_\theta \log p(\mathbf{y|\theta})$. How can I formulate the same thing for information recognition problem?

Objective:

Please follow the link : https://charlesmartin14.wordpress.com/2015/04/01/why-deep-learning-works-ii-the-renormalization-group/

I want to understand how the task of information retrieval or image recognition can be viewed from the perspective of source estimation, channel estimation, equalization. In the first picture of the link,

recognition

it seems that the pipeline (b) can be replaced by a communication system; the mapping $h()$ looks like a channel or a filter.

How can I formulate the information retrieval or the recognition task using the idea presented in the image ?

Is it possible to view information retrieval as encoding and decoding task? Whether the two tasks are the same but called differently.

As in the task of information retrieval, where the information is the input $x$, the trained or the learnt model should be able to produce the almost exact output in response to a query. However, there is a block, a mapping function that transforms the input to a representation involving $L\ll D$ bits. I think that training involves estimate the channel coefficients (synonymous to the weights in neural network).
As mentioned under the Question, the input data is in binary and the output is also in binary with $L \ll D$. If the distribution of the impulse response is Gaussian with $L$ number of coefficients and the length of the input is $D$, then applying the concept of autoencoders or the specific task of classification, where given the input the output of the system should be able to give an exact representation of the input, roughly $\mathbf{y} = \mathbf{hx}$. But, $L\ll D$ and I want that in response to an unknown input, the learned system should be able to give as output the exact input.

Notations :

  • $\mathbf{x}$ as the source. It is the input to a filter. The source, $\mathbf{x}$ has $D$ number of bits and $x$ are the elements of the vector $\mathbf{x}$

  • Output $\mathbf{y}$ is also a vector of $D$ bits, for the task of recognition. However, the picture from the webpage has the input $\mathbf{x}$ is of D bits and that is is fed into (b) which acts as the mapping function - the encoder $h(x):x↦z$. It appears that the input is transformed into $L<<D$ bits. This I called as $\mathbf{y}$ that is the intermediate block similar to dimensional reduction from D bits to L bits. The mapping function $f()$ regenerates the target output from L bits. In essence, the recognition task is solved in the reduced feature space. The training and testing examples undergo dimension reduction and the vector is called $\mathbf{z}$ which is of $L<<D$ bits. Eventhough, the training occurs using the $L$ bits of the input (after some dimension reduction), we still get the reconstructed image having $D$ bits. So, there is another block after the channel that generates $\mathbf{y}$ of $L$ bits because the recognition occurs using $\mathbf{y}$ in the reduced feature space. After that, the trained system regenerates the $D$ bit input image in the recognition stage in response to an unknown query. I don't know if this is the function of a decoder or not.

$\endgroup$
  • $\begingroup$ i friggin' up-arrowed this just based on the title. now i'm gonna read it. $\endgroup$ – robert bristow-johnson Jul 8 '16 at 1:37
  • $\begingroup$ What, exactly is "$x$"? (not "$\mathbf{x}$" nor "$x_n$".) then the next question is: What is "$h(x)$"?, but that might get answered consequentially from answering the first question. $\endgroup$ – robert bristow-johnson Jul 8 '16 at 1:49
  • $\begingroup$ if "the channel" is a "Moving Average", then $\mathbf{w} = \{1/L, 1/L, ... 1/L\}$ and $h(\cdot)$ defined similarly, i think. but that seems to conflict with some other optimal definition of $\mathbf{w}$ or $h(\cdot)$ for whatever purpose of classification into $y_1$ or $y_2$. so it's still not clear to me exactly how the problem is defined. $\endgroup$ – robert bristow-johnson Jul 8 '16 at 2:03
  • $\begingroup$ And how, exactly, is "$y$" related to "$\mathbf{y}$"? Is, somehow, $y$ the elements of vector $\mathbf{y}$? $\endgroup$ – robert bristow-johnson Jul 8 '16 at 2:10
  • $\begingroup$ too late to modify. in my comment above, i think replace "$L$" with "$D$". or is $\mathbf{w}$ a $L \times D$ matrix? $\endgroup$ – robert bristow-johnson Jul 8 '16 at 2:13
6
$\begingroup$

There are, a few discrepancies that might be making a difference here. My suggestion would be to edit the question for clarity. There are quite a few assumptions that lead to non-straightforward thinking about the problem which I have tried to address to an extent and I would be happy to modify the response in light of more information.

In machine learning, for the task of classifying input data (called an example) which are in binary representation, $\mathbf{x}\in \mathbf R^D$, $\mathbf{x} \in \{0,1\}^D$ into its multiple class labels that are also binary $\mathbf{y} \in \mathbf R^L$,$\mathbf{y} \in \{0,1\}^L$ and $L \ll D$, we estimate/ learn the parameters $\mathbf{w^T}$ called weights using learning algorithm (called as training phase) based on the knowledge of the class labels, $\mathbf{y}$.

This is a very specific example of a classifier. It looks like it can only accept a vector of binary features and output an activation vector. In general, a classifier is a mapping. It takes features from the feature space (set) and maps them to the class space. It would therefore look like a simple $f : X \rightarrow C$ where $X$ is the feature space and $C$ is the class space. Elements of $X$ could be tuples describing each example's features and $C$ could well be $C \subset \mathbb{Z}$ (a subset of positive integers). If you have more than one outputs, then $C$ would also become a set of tuples.

You could extend this to say $C = f(X, \Theta_f)$, to include a set $\Theta_f$ of parameters that are specific to the classifier $f$ and this could include some $w^T$. Again, this $w^T$ business is very specific. Weights mean one thing for Neural Networks and quite a different one for k-means clustering.

After training phase, any unknown example can be classified based on the learned parameters, $\mathbf{w^T}$. $$ y = h(x) = \mathbf{w^T x} \tag{1} $$

That's very specific again and it cannot be generalised. This is a very simple mapping and it has its limitations. What is described starts to look like Neural Networks however.

From signal processing viewpoint, $h$ is the system or the channel through which the input passes and at the receiver we can get the same output if the channel is noiseless. So, the classifier $h(\cdot)$ is the encoder.

Yes...and no. What has been described so far COULD be seen as a decoder. It could map tiny little waveforms or "words" to a zero / one output.

But in signal processing, the transmitted signal is convolved with the channel impulse to get the output. Assuming, the channel is modeled as Moving Average, my questions are:

The "channel" cannot be "modeled as a Moving Average". IF the channel is a medium that can support WAVES, then it COULD be modeled via its impulse response. Yes, some channels do indeed have a "low pass filter" effect on signals, in which case, their impulse response could be something like: $ h = [0.5,0.5]$ or $h = [0.25,0.25,0.25,0.25]$ or, in general a vector $V$ of elements where each element is $\frac{1}{|V|}$. In this case, it could be seen as a moving average filter.

In machine learning and classification task, the input ... [...] In signal processing, when the signal...

Can I please ask what is the motivation behind this attempt to create a parallel between these two disciplines? Different things. Different disciplines, different problems, different models, different objectives, different motivations. The whole "how is this called in Machine Learning because it's called differently in DSP" is not a productive discussion. "Observation" and "Measurement" are just terms. They could well be applied to the same things from the point of view of the scientific method too.

Would learning $h(\cdot)$ as a classifier imply that we are estimating the filter taps of the unknown channel $h(\cdot)$?

Yes. BUT! "Classifier" is very specific and the classifier you have been "building up" so far, does not correspond (as a model) to this question. Neural networks CAN be used for interpolation in which case, they could be seen as "low pass filters" and in THAT case, the network would be learning the weights (according to some criterion of what constitutes good weights, for example see this link). Another thing you might find useful is the LMS filter. It adjusts its weights based on a "known template".

Suppose, in machine learning the goal is to retrieve the information after the training phase.

No. The goal of machine learning is to train the model.

In response to a query the trained system returns the correct output, then, is this retrieval process correspond to Equalization that is information reconstruction whereby we want to get back an estimate of the input?

No. There is no "retrieval process". There is nothing stored. You COULD say that adapting the weights provides some sort of memory for the neural network but this only applies DURING the training process. Once the network is trained and is put to operation, it only maps input vectors to output vectors. Nothing is stored so there is no "retrieval".

What needs to be estimated in unsupervised setting so that the output corresponds to the actual input?

If an "output" has to "correspond to an actual input" (i.e. we know both, but try to recover the mapping that links them) then we cannot be talking about unsupervised learning. This is supervised. You check where you are and where do you want to go and adjust the weights accordingly.

Can somebody please give a mathematical expression as how $h$ would perform as a classifier so that the learned system can reconstruct the information, and how this goal generalizes to encoding and decoding?

Please see above links on using neural networks for interpolation. Also, it would be useful if you were to clarify the original question with more information on what you are trying to achieve. Why does it have to be in the context of a "classifier" that works as an "encoder"? Reconstruct what information? How does this information look like? What is the point of encoding and decoding? The problem could have a solution involving neural networks but it is not entirely clear how.

Hope this helps.

EDIT:

I am going to leave the response largely unmodified because certain things do hold still and I am going to add a few points here in bullet points. I can see "where you are coming from" but it is not clear to me why are you trying to create a similitude with the communications field.

  • The $h$ as it is constructed until the $x \rightarrow h \rightarrow y$ diagram, is called a Perceptron. On its own, a Perceptron is not a filter. For the weights described by $h$ to apply the filtering operation, the $x$ buffer should be a stream of data in the sense implied by the operation of convolution (Also important to be aware of is the MAC operation). IF one had to absolutely replicate a MAC with Perceptrons then this would imply a specific structure of interleaving Perceptrons with a linear activation function....which is getting us very close to convolutional networks.

    But in the way the question has been formulated, it looks as if the Perceptron is "pitched" as a filter that replicates some sort of image degradation. Because that is what a channel would do to an image. But!, image degradation because of some channel impulse response would imply something happening to the image along its optical (i.e. in the camera) or signal processing path up to the point of capture. When we are at the stage of processing, $h$ is not a "channel" any more. I hope that this is clear. If it is not, it is not clear to me too.

  • Is this like equalisation? My immediate answer would be "No". It could be described as equalisation but it takes a lot of abstraction. Here is why: An equaliser usually is trying to COUNTERACT the effect of a specific distortion on the signal path. For example, in communications, you are trying to make the transmission line transparent. How do you do this? Prior to sending data, you send a pilot tone, or sequence, down the line of which you know its spectrum and upon reception, you modify the weights of a filter to (usually) boost the frequencies that get attenuated. Notice here, there is indeed breakdown of the signal and recomposition. THE SPECIFIC CLASSIFIER that is hinted throughout this discussion doesn't work like that. When the classifier is trained, the statistical characteristics of the training dataset are captured by the model. Then, given some random example, the classifier answers the question "Well, given that my cluster of statistical characteristics looks this way, then the maximum likelihood for this incoming signal that I haven't seen before is to be of that class". For example, eigenfaces. You literally train the classifier with the dominant structure of the dataset as this is described by the eigenvectors and eigenvalues of the training dataset's covariance matrix. You could say, that these are now your basis functions, just as you would say in the case of equalisation. Then, given some random face, you check its proximity to the eigenfaces. This is the closest I can get to what you call "reconstruction" by equalisation. But as you can see the two operations do not share common building blocks. There is no Maximum Likelihood in an equaliser. Equalisation and some classifiers COULD be seen as similar in an abstract sense for SOME cases.

  • How does the task of information retrieval be viewed from the perspective of signal processing? I don't understand the question but I have a feeling that it is too broad.

  • I want to understand how the task of information retrieval or image recognition can be viewed from the perspective of source estimation, channel estimation, equalization. In an ABSTRACT sense, you could create a parallel between Forward Error Correction and Pattern Recognition the way it is posed here. I am referring specifically to Convolutional Codes and their decoding by the Viterbi Decoder, which gives us the Maximum Likelihood of the code that was transmitted. In this latter case, your "training dataset" is your code repertoir (the dictionary that maps symbols to codewords) which gets degraded by noise and on reception you decide in an optimal way which of the KNOWN codes was likely to have been sent. BUT! there is also a conceptual leap that you are making which complicates things. More about this further below.

  • ...it seems that the pipeline (b) can be replaced by a communication system; the mapping h looks like a channel or a filter. No, it doesn't! We just made a leap by blurry abstraction. Here is why: A typical comms signal pathway is like this: Source->Encoder->Modulation->Channel->Demodulation->Decoder->Target. The Channel distorts the Source symbols and the receiver is trying its best to counteract these distortions. IF YOU ABSOLUTELY HAD to create a SIMILITUDE (but I mean, you are held at gunpoint) between this and pattern recognition, then you could say that your training dataset is your Source, the Encoder/Modulation is the Training, the Channel REPRESENTS THE IMPERFECTIONS THAT ARE CONTAINED IN SOME RANDOM IMAGE and the Demodulator/Decoder represents the classifier in operation. But this is doing London->Singapore->Milan....You better have a good reason for it and this is what I am not getting and at the same time I am intrigued by. What is the gain from shoehorning this problem into a comms framework? Are you encoding your lighting? (By the way, just to clarify, this similitude I just tried to demonstrate here is only remotely close to figure 2 of the question. In fact, figure 2 is only half the story, the demod/decode bit).

I hope this helps.

$\endgroup$
  • $\begingroup$ Thank you for your reply. I must clarify certain points from my Question which I think is a bit vague. The first diagram in the link charlesmartin14.wordpress.com/2015/04/01/… shows the problem statement - how to reconstruct the output given the known image by applying a map f(x) or h(x) where $x$ is the input. Looking at the diagram, the mapping appears like an encoder. $\endgroup$ – Srishti M Jul 7 '16 at 15:11
  • $\begingroup$ Is it possible to apply a non-linear function as the map and if so then what are the unknown parameters i.e., the objective function to be minimised so that in response to a query, the learned model returns the (correct) image. I was looking at the problem from the viewpoint of estimating the channel coefficients assuming that the input image passes through a channel whose impulse response is modeled like moving average, so the mapping is done by the channel whose parameters are unknown. I do not want to use neural network. $\endgroup$ – Srishti M Jul 7 '16 at 15:14
  • $\begingroup$ I want to know if the activation function or the mapping function are the same things. Any ideas on how I can apply a nonlinear recursive function as the map between the image and the output? $\endgroup$ – Srishti M Jul 7 '16 at 15:15
  • $\begingroup$ Thank you for clarifying but please consider adding this to the original question, possibly under a heading "edit". Messages are only a few hundred characters long. Yes it is possible, just as interpolation guesses the gaps. If you are looking for "a nonlinear recursive function as the map between the image and the output" you are looking for neural networks. Activation is different that mapping, because the mapping is the sum of many different activation functions from different layers. $\endgroup$ – A_A Jul 7 '16 at 19:50
  • $\begingroup$ I have updated the Question. Could you please modify your answer, if it is needed? Thank you very much for your time and effort. $\endgroup$ – Srishti M Jul 7 '16 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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