6
$\begingroup$

I have a list of about 20 tasks that a machine need to be performed by a machine. Each tasks consists of a sequence of 3 to 5 actions that must be executed sequentially to complete a task. There are a total of 50 different actions.

I want an algorithm to learn which actions to execute to complete the tasks. To learn this I have a dataset of approximately 1000 samples. Each sample consists of a task with corresponding actions.

Given a task $T_n$, the machine needs to come up with the sequence of actions to complete the task.

Sample dataset ($T$ for tasks out of 20, $A$ for actions out of 50):
$T_1$ - $(A_5 \rightarrow A_1 \rightarrow A_3)$
$T_2$ - $(A_7\rightarrow A_12\rightarrow A_4\rightarrow A_1)$
$T_1$ - $(A_5\rightarrow A_3\rightarrow A_{13})$

What is the best way to solve this?

Based on my knowledge of linear regression and classification, I believe that both are not the right approach to solve the task at hand.

EDIT 1:

One way I can think to solve this problem. The machine doesn't have to come up with the whole sequence instantly.

If a new task has to be done, the machine has an option to choose the next action (first action) from, say, 5 available actions it can perform. After performing this action, it would have, say, 5 more actions and it has to choose it's next action to complete. And go on doing these actions to complete the given task.

Is this kind of a finite state machine?

$\endgroup$
9
  • $\begingroup$ Welcome to DataScience SE! Could you clarify your question? I don't see how a question about tasks and actions are related to data science. $\endgroup$
    – Stereo
    Feb 16, 2017 at 7:53
  • $\begingroup$ Thanks. I think the machine needs to complete tasks by learning from the dataset of samples on how to solve tasks by sequentially selecting actions. That is a machine learning problem. So, I asked here as the description suggests ML problems are welcome. $\endgroup$
    – SnShines
    Feb 16, 2017 at 7:58
  • 2
    $\begingroup$ I would store the data in a graph data base such as Neo4J and store the tasks and actions as nodes. You will quickly be able to detect the most frequently used path in the graph. It is not very clear from your description why a same task can have different actions, maybe you could clarify this? $\endgroup$
    – Stereo
    Feb 16, 2017 at 8:09
  • $\begingroup$ Could you clarify how strictly the tasks are defined, and how the data relates? Is it possible for instance to infer that a task $T_n$ can be completed using a minimal set of ordered actions, based on all instances of $T_n$ in the database. Or can tasks be completed in more than one way - so for example $T_1$ might have actions $(A_5→A_1→A_3)$ and $(A_7→A_4→A_9)$, there are at least two valid but entirely separate ways to get it done? $\endgroup$ Feb 16, 2017 at 8:16
  • 1
    $\begingroup$ If this was not phrased as a supervised learning problem, and there was a notion of current state (perhaps even defined by the available actions), then you could look into Reinforcement Learning. If you have some model of state you could potentially use simple Q-learning from the existing data, with a reward of -1 per action. $\endgroup$ Feb 16, 2017 at 8:22

2 Answers 2

1
$\begingroup$

What is the best way to solve this?

Based on my knowledge of linear regression and classification, I believe that both are not the right approach to solve the task at hand.

Not sure about the best way, but one indeed can formulate this kind of problem as a classification problem. I assume that additionally to the data included in your sample dataset you also have information about the environment for all 1,000 observations.

For example, one can reshape the dataset as follows.

Underlying data (I've inserted env as a placeholder for the information about environment, you might have several variables describing the environment):

|task |env |action1 |action2 |action3 |action4 |action5 |
|:----|:---|:-------|:-------|:-------|:-------|:-------|
|T1   |E1  |A5      |A1      |A3      |END     |NA      |
|T2   |E2  |A7      |A12     |A4      |A1      |END     |
|T1   |E3  |A5      |A3      |A13     |END     |NA      |

Transformed dataset that can be passed to the classifier

|task |env | num_action|prev_action |action |
|:----|:---|----------:|:-----------|:------|
|T1   |E1  |          1|START       |A5     |
|T2   |E2  |          1|START       |A7     |
|T1   |E3  |          1|START       |A5     |
|T1   |E1  |          2|A5          |A1     |
|T2   |E2  |          2|A7          |A12    |
|T1   |E3  |          2|A5          |A3     |
|T1   |E1  |          3|A1          |A3     |
|T2   |E2  |          3|A12         |A4     |
|T1   |E3  |          3|A3          |A13    |
|T1   |E1  |          4|A3          |END    |
|T2   |E2  |          4|A4          |A1     |
|T1   |E3  |          4|A13         |END    |
|T2   |E2  |          5|A1          |END    |

Then one can apply any multiclass classification (e.g. multinomial logistic regression) and try to predict the column action using the first four columns as predictors.

$\endgroup$
0
$\begingroup$

I am trying to solve a similar problem. However, I feel that Recurrent Neural Networks should work for this, as we can make the machine learn Sequence. But yes, I agree that it may not be the best way. Anyone else who can throw in some light ??

$\endgroup$

Your Answer

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

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