Problem:

We have a fairly big database that is built up by our own users. The way this data is entered is by asking the users 30ish questions that all have around 12 answers (x, a, A, B, C, ..., H). The letters stand for values that we can later interpret.

I have already tried and implemented some very basic predictors, like random forest, a small NN, a simple decision tree etc.

But all these models use the full dataset to do one final prediction. (fairly well already).

What I want to create is a system that will eliminate 7 to 10 of the possible answers a user can give at any question. This will reduce the amount of data we need to collect, store, or use to re-train future models.

I have already found several methods to decide what are the most discriminative variables in the full dataset. Except, when a user starts filling the questions I start to get lost on what to do. None of the models I have calculate the next question given some previous information.

It feels like I should use a Naive Bayes Classifier, but I'm not sure. Other approaches include recalculating the Gini or entropy value at every step. But as far as my knowledge goes, we can't take into account the answers given before the recalculating.

You don't need to re-train on the fly. What you're looking for is an embedded feature selection algorithm, and even more precisely, one that minimizes the number of responses required.

I think this might be one of the rare cases where genetic and evolutionary approaches are the obviously correct choice.

Genetic Programming is a technique for finding models that are simply computer programs. You generate a bunch of computer programs at random, and then breed the "better" ones together. Repeating this process over time leads to highly optimized programs.

A nice feature of GP is that it is extremely flexible when picking what to optimize. So instead of "better" meaning just "more accurate", "better" can mean the sum of accuracy and $\frac{1}{\#answers\_used}$. The algorithm works the same way, and, with carefully chosen rewards, you may be able to get the best of both worlds.

There are lots of variations on this. I would probably start with a simple toolkit like EJC, and standard, boring, genetic programming.

There are specialized techniques for things like your problem too, but you'll probably get 80% of the benefit without needing to pursue them.

  • You definitely don't want Naive Bayes, but you could also look at modeling this with a Bayesian Network. That requires you to have a fairly deep understanding of the problem domain though. – John Doucette Sep 14 at 12:56

The Problem Statement

It does not appear from the wording in the question that the semantics of the language in the questionnaire will be processed, so no knowledge of the associations in questionnaire questions and answers will be derived prior to its administration.

There are $M$ questions, with $N_m$ undifferentiated answers for each question, presented to human users. The administration of this questionnaire builds a set of data that will later be used to train an independent learning system.

This question pertains to both some subsequent training and the learning that may need to occur to achieve stated goals in the acquisition of data for the subsequent training.

  1. Reduce the burden on the system users that answer the questions.
  2. Reduce the storage requirements.
  3. Remove redundancy from the data to be used as examples for subsequent training.
  4. Utilize in real time early answers within a single user session to achieve the above three objectives.

Analysis

The assumption in the question that the above four can and should be achieved through the same mechanism may or may not prove true during the design process. These are some alternative ways to achieve goals.

  • Goal 2. can be achieved by employing bit-wise operations to pack the answer data into an innocuous payload.
  • Goal 3. can be achieved by auto-encoding independently of 1.

Goal 1. is the key to this problem, and its solution, utilizing goal 4., should be addressed first as the predominant technical risk. Afterward, if byproducts of the solution to goal 1. can be employed to assist in the solution of goals 2. and 3., then so be it.

There are at least three meanings of models in machine learning.

  1. The model of the concept being learned
  2. The model thorough which learning occurs
  3. The model of what is considered sufficient

This last model defines how accuracy and reliability are measured and what quality acceptance criteria are given regarding them.

It appears that none of the three models for either the data acquisition learning or the later learning using the data acquired are yet defined, however some architectural considerations can be addressed and some conclusions can be reached.

Structure of Information

Consider these structures of data that can aid learning.

  • The $M$ features of user linguistic response can be saved within a user session as a time series of vectors $\sigma(m, n, t)$.
  • Those series can be collected across $U$ users, each with an user ID $i$ indexed sequentially for mathematical purposes by $u$, as a structure of elements $\gamma(m, n, u, t)$.

It is the the second structure of $\gamma$ elements that contains information that can assist in the presentation of questions and answers to subsequent users, given the $\sigma$ time series in the current user's session state.

The Key Challenge

The challenge is not the application of probability and statistics to a single session, which is straightforward, outlined below. The difficulty is that once those of the $M$ questions are rated for their likely usefulness in later training, by reordering questions, defaulting them to the most likely response, or eliminating any answers, the system has changed the conditions driving the associations. This is the classic scenario when the measurement changes the item being measured. In such a feedback condition, the knowledge acquired about usefulness can produce unstable conditions, including oscillations or chaotic system behavior.

Important Early Design Choice

Real time learning is indicated, and the system must be stabilized using the same kind of stabilization techniques involved in electrical engineering, robotics, and balancing. Perhaps the best choice for current designs is Q-learning, pioneered by Watson and developed further by many others.

Applicable Probability and Statistics

The straightforward application of probability and statistics mentioned above is this. Using Bayes' Theorem (not the naive categorization precisely), one can calculate the probability that any given $\sigma$ will be selected, based on the multi-user sequence of $\gamma(m, n, u)$. However the most effective solution can be achieved via the application of Q-learning to the ordering, defaulting, and elimination of $\sigma$, given both the multi-user sequence of $\gamma$ and current user sessions sequence of $\sigma$. Where naive Bayesian categorization or feature extraction may be most useful is in the profiling of users to further enhance user experience. Even this can be contained within the Q-learning process. The key to Q-learning is the inverse exponential decay of past knowledge.

Application Architecture

The most scalable architecture would be to use JavaScript in the web browser to acquire learned behavior via AJAX and adjust answers order, defaulting, and hiding in real time with the must updated learned state.

A more sophisticated approach would be to encapsulate the learned information in fuzzy logic rules to essentially remove redundancy and compress the learned information.

Further Requirements Analysis Indicated

This may be the extent to which design can proceed without more analysis of the requirements of the system.

What must be defined first is how the training data will be labeled, if at all.

  • Is the goal to provide example data for supervised learning, where expected results are provided to the training process?
  • Or is the goal to provide example data for unsupervised learning, where no expected results are given, and the training is to proceed toward some defined goal that is universal across the examples used in training?

Another consideration is to decide whether intelligent defaulting will be employed.

  • Should the system guess what the next answer is going to be and intelligently select it, allowing the user to change the selection if the guess was wrong?

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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