1
$\begingroup$

My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have the right terminology and just need a starting point so I can help myself.)

I'm trying to interpret the vector inputs to a black-box controller (which I can model as finite-state machine). I can see them and they look like a series of symbols but it is too variable (stochastic) to easily define an "alphabet" based on repetition and it isn't clear how the symbols are grouped. In other words it isn't clear whether they use something like block coding where each symbol is the same number of vectors in a sequence, or convolutional coding where symbols can have different numbers of vectors.

The controller operates a linear actuator (it just goes up and down) and the inputs are large vectors from a CNN. It's essentially a pong playing robot. I make predictions by modeling the controller as binary decision tree that maps each putative symbol to an exact position of the actuator. This is very similar to a language induction problem for a finite-state machine. Recall that a finite automaton can be a representation of a regular language. Also recall that finite automaton can characterized in terms of its memory requirements and computational complexity, hence a regular language can too.

  1. I know that the controller is optimal. There is no controller which has both less memory and less computational complexity. If I have two guesses at coding schemes and each are able to predict actuator position equally well then I want to pick the coding scheme which implies the least complexity and memory. So how does one go about evaluating the resource requirements of a coding scheme (raw inputs-> symbols) and grammar (rules about symbols) in combination?

  2. I need to keep in mind that I might be wrong that it digitizes its inputs into symbols at all. So what are the signs that it is not digital? (such as, if I divide the symbols into smaller symbols and it still works just as well, ad infinitum, that probably means the symbols are meaningless).

Question explained pictorially


If you don't think I've given enough information keep in mind that I don't expect a detailed answer (but I'm happy to offer more). An acceptable answer is something of the form "I think you need to look into ____.", "This sounds like ____ in which case we often use ____.", "This sounds like a paper I read, see ____.", or "The ____ metric compares the level of the difficulty of a task to the number of symbols in the language required to perform that task and tells you how efficient a language is at that task."

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! I'm a bit confused. Can you give us a bit more context? You mention an automata, a controller, and a coding scheme. What are they? What data do you have, and what are you trying to do with it? What are you trying to accomplish, and what approaches have you considered, and why have you rejected them? Are you given some input and trying to learn an automaton that will accept those input strings? What research have you done? Have you studied automata learning and grammar induction? What does this have to do with coding schemes? What do you mean by better? $\endgroup$ – D.W. Oct 5 '17 at 23:36
  • $\begingroup$ @D.W. the question seems to be misunderstood a little. The data are spike trains and the controller is a neural network (as mentioned in the original edit) but I doubt its relevant to a cogent answer since context is what I seek in the first place. Grammar induction is a possible context, but I'm not interested in the rules applied to symbols but uncovering the symbols themselves from a noisy channel. It may help me decide how to choose between two possible symbol sets, but the Wikipedia page does not discuss performance metrics. It's too high-level as I just need to compare existing sets. $\endgroup$ – Jojker Oct 6 '17 at 0:28
  • $\begingroup$ @D.W. better="The correct guess should imply both the least storage and the least complexity on the part of the controller. " Current approach=I thought to myself: "If two encoding schemes produce the same prediction but one has fewer symbols then the one with fewer symbols seems better. Hmm, I'm out of my ken here I better talk to some CS folks." How to make symbols: Do kmeans on spike rasters (from a RNN) to identify repeated patterns. These are symbols, now use decision trees to map symbols to the actuator position. Repeat in different ways and get same prediction quality, which is best? $\endgroup$ – Jojker Oct 6 '17 at 0:39
  • $\begingroup$ OK. Please edit the question to incorporate this information into the question, and to read well for someone who encounters it for the first time (don't just add "EDIT:", but revise your post). Make sure to include all relevant context. We want questions to be self-contained, so that people don't have to read the comments to understand your question, so all relevant information should be incorporated into your post. What's a spike train? Is it a sequence of numbers? Why do you say that a neural network is like an automaton? A neural network computes a continuous function and is stateless. $\endgroup$ – D.W. Oct 6 '17 at 1:07
  • $\begingroup$ I don't understand what a coding scheme is. What format would it take? Can you give a precise mathematical definition? How does a coding scheme influence the amount of storage and complexity? Storage of what? How does the coding scheme influence the neural network? How does an encoding scheme produce a prediction? What's an actuator position? What is given to us, what are we supposed to produce, and what is fixed in advance? It's hard to understand what's being asked without understanding what the words you're using refer to. $\endgroup$ – D.W. Oct 6 '17 at 1:09
1
$\begingroup$

The answer was just tree depth. What I needed to do was learn about evaluating the complexity of finite automata and how we can use a decision-tree model (decision-tree complexity) to put bounds on the complexity of an automata (analysis of algorithms). So I take my two coding schemes (call them A and B) and I make binary decision tree to predict the output of my system based on the inputs provided by the coding schemes. If both coding schemes A and B are equally useful for predicting the outputs but A requires a tree depth of 15 while B requires a tree depth of 54 then A is "better". This is because our decision-tree model of the system is simpler when using A than when using B and as stated before we strongly believe that our system is as simple as possible.

Of course I also need to include the complexity of the coding scheme itself but that just goes with alphabet size since it is a Nearest Neighbor search.

So it was under my nose, I just needed some context.

$\endgroup$

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.