7
$\begingroup$

I have a stateful black box with four real-valued inputs and one real-valued output. My problem is to predict the output at each moment in time, given the sequence of inputs seen up to that point. During a learning phase, I can vary the inputs however I want and observe the output. There's a little noise, of course, and the black box doesn't appear to be completely deterministic.

Specifically, I'm modeling a hard drive, and I want to predict the access time of the latest request given all previous requests. I want a more black-box approach, though, because of the complexity of explicit models, and because I want this to work for other similar devices such as SSDs.

A couple of people have suggested that signal processing might be appropriate to analyze the sequences of input and output values.

Are there any ideas from signal processing that could help me to predict the output, or to characterize the input?

$\endgroup$

2 Answers 2

2
$\begingroup$

Generally, for non-linear systems the aren't any tools that are guaranteed to work. You need to know something about the nature of the box. If you can model it with a system with unknown parameters, "learning" by observing input-output relationships can help you estimate those parameters, but I doubt that you can blindly "learn" the system model, especially if it has memory/states. Having said that, a more or less generic method of estimating nonlinear systems up to a polynomial degree is using Volterra kernels with some sort of gradient descent method for recursive error minimization. Methods like LMS and RLS are widely used.

Volterra kernels help you estimate a system of the form

$$y(t) = k_0 + \sum_{n=1}^{\infty} \int_{-\infty}^{\infty}\cdots \int_{-\infty}^{\infty}k_n(t_1,t_2,\ldots,t_n)x(t-t_1)x(t-t_2)\cdots x(t-t_n)dt_1dt_2\cdots dt_n$$

One way to look at the following system is to notice its similarity to convolution with addition of non-linear terms in $x$. Note, however, that if non-linearity of your system cannot be modeled with a polynomial (exponential, logarithmic and many other functions) this will require infinity complexity to estimate your system correctly.

There aren't many papers on the topic available online for free, but you can look at this one and this one to get an idea of what this is all about.

$\endgroup$
4
  • $\begingroup$ That's certainly interesting, but I have an input vector at each time step, and this seems to only work with scalars. $\endgroup$
    – Adam Crume
    Jan 27, 2012 at 18:35
  • $\begingroup$ I'm sure you can find a state-space representation of the above equation. That will deal with multiple inputs quite easily. $\endgroup$
    – Phonon
    Jan 27, 2012 at 18:47
  • $\begingroup$ After looking at it for a while, I think I did something similar. I built a polynomial from x1(t), x2(t), ..., x1(t-1), x2(t-1), ... and tried to learn the coefficients using gradient descent. The problem is, just an order four polynomial looking back two time steps requires something like a thousand parameters. $\endgroup$
    – Adam Crume
    Jan 30, 2012 at 16:29
  • $\begingroup$ @AdamCrume Indeed. These problems are very computationally demanding and many papers published on this stuff actually deal with algorithm optimization rather that with new ways to approach the problems. $\endgroup$
    – Phonon
    Jan 30, 2012 at 16:38
1
$\begingroup$

If your box is (mostly) linear that is a very simple problem, if it mainly non-linear that it can arbitrarily complicated. If we assume linearity, than simple superposition holds. You can measure the transfer function from each input to the output (while the other inputs are zero) and then calculate the output as the sum of the individual input responses. In the frequency domain we would write

Y(w) = X1(w)*H1(w) + X2(w)*H2(w) + X3(w)*H3(w) + X4(w)*H4(w); 

where Y(w) is the output spectrum, Xn is the input spectrum for input "n" and Hn the transfer function from input "n" to the output. In the time domain it would be

y(t) = x1(t)**h1(t) +  ... + x4(t)**h4(t);

where '**' is the convolution operator, y(t) is your output signal, xn(t) the input signals, and hn(t) the impulse responses from input n to the output. The two equations are basically the Fourier Transforms of each other.

$\endgroup$
1
  • $\begingroup$ Unfortunately, it is non-linear. $\endgroup$
    – Adam Crume
    Jan 26, 2012 at 22:27

Your Answer

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

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