test ¶This program demonstrates basic features of actor algorithms used in QSMM. The paper “An Approach to Optimal Action Generation for a System that Interacts with the Environment” describes them. Starting from QSMM version 1.16, the package distribution does not include that paper, because despite being informative, the paper contains serious unfixed mistakes.
The program performs interaction between a system and an environment represented by a deterministic finite automaton. The system is either homogeneous or consists of two subsystems, where the first subsystem identifies a current environment state, and the second subsystem generates an adaptive action based on the current state. The program can read the description of a deterministic finite automaton representing the environment from a file specified by a program argument or generate the automaton randomly on the fly.
The files test.c, eemat.h, eemat.c, findcyc_ee.h, and findcyc_ee.c in the subdirectory samples in the root of the package distribution contain source code of this example program.
A text file describes a deterministic finite automaton representing an environment. A text file example is below:
Non-empty line #1
Non-empty line #2
...
Non-empty line #n
2 5 3 0
1 0 0 0 0
1/3 2/4
2/1 1/2
0/4 1/0
The parser of an automaton file ignores all lines before the first empty line. The first line after that empty line has the format
number_of_input_signals number_of_output_signals number_of_states initial_state_index
Indices of signals and states start from 0.
The second line after the empty line contains floating-point numbers specifying spur increments for all output signals. The increments take place when the automaton emits corresponding output signals.
Starting from the third line after the empty line, there go descriptions of transitions between states on receiving input signals. The third line corresponds to transitions from state 0, the fourth—from state 1, the fifth—from state 2, and so on. Each line contains number pairs corresponding to input signals. The first pair corresponds to input signal 0, the second—to input signal 1, the third—to input signal 2, and so on. Each pair has the format
target_state/output_signal
and specifies a transition from a source state to a target state with emitting an output signal on receiving an input signal.
Use the following command to generate a random deterministic finite automaton:
qsmm-example-test -o out_file -i random_seed [ -C VAL ] num_in_sig num_out_sig num_states
This command creates a file out_file containing the description of a deterministic finite automaton generated using seed random_seed. The automaton has specified numbers of input signals, output signals, and states. If a random seed not specified, the program uses a standard fixed random seed. The first output signal has spur increment 1, and all other output signals have spur increment 0.
If the program receives the option -C VAL, and VAL is not 0, the automaton has its state graph connected. If VAL is positive, the program simplifies the automaton, makes it to have not more than VAL cycles in the graph, and finds the best cycle in the graph. See a description of -C VAL option in “Options Common for Both System Types” for what the automaton simplification is. Continuous repeating the best cycle supplies the maximum amount of spur to the system. If VAL is relatively small, the program may not generate the automaton at one push. If an attempt to generate the automaton fails, the program prints a warning message and makes another attempt. If VAL is relatively large, an attempt to generate the automaton may take a long time, so the impression can be that the program has hung.
The special option argument VAL=‘c’ makes the program provide state graph connectivity and find the best cycle in the graph using an algorithm analogous to Viterbi one. The special option argument VAL=‘cs’ makes the program provide state graph connectivity, simplify the state graph by a method also used when VAL is positive, and find the best cycle in the graph by an algorithm analogous to Viterbi one.
The program writes the random seed value to comment lines before the first empty line in out_file. If the option -C VAL has a non-zero VAL, the program also writes to the comment lines information on the best cycle in the state graph:
Use the following command to run a test of algorithm efficiency consisting of num_passes passes with a new random deterministic finite automaton that has specified numbers of input signals, output signals, and states generated at each pass:
qsmm-example-test -t num_passes [ -C VAL ] [ additional options ] \
num_in_sig num_out_sig num_states
On passing the option -C VAL with a non-zero VAL, the program provides connectivity for generated automaton state graphs and finds best cycles in them. An example of a test log printed by the command is below:
$ qsmm-example-test -t10 -Ccs 20 20 20
DFA inputs: 20
DFA outputs: 20
DFA states: 20
Input signals: dfa-state
Passes: 10
Steps per pass: 10000
Large: off
R. prob. type: 1
N-gram length: 1
Algorithms v.: 0
K*temp.: 1.000000000000000E+00
Max. cycles: -2
Random seed: 0
pass earned random maximal cl % efr % efa
---- ------------ ---------- ------------ -- -------- -------
1 5821.000 331.000 7500.000 4 1758.610 76.580
2 5826.000 441.000 10000.000 2 1321.088 56.334
3 5656.000 359.000 6666.667 3 1575.487 83.977
4 6443.000 414.000 10000.000 2 1556.280 62.894
5 7901.000 462.000 10000.000 2 1710.173 77.993
6 5949.000 329.000 7142.857 7 1808.207 82.479
7 4272.000 281.000 6666.667 3 1520.285 62.499
8 8781.000 411.000 10000.000 2 2136.496 87.288
9 8144.000 648.000 10000.000 2 1256.790 80.154
10 4671.000 270.000 6000.000 5 1730.000 76.806
TOTL 63464.000 3946.000 83976.190 3 1608.312 74.369
stddev efr: 252.956
stddev efa: 10.430
The log begins with a description of test modes used followed by a table, where each row corresponds to a test pass, followed by a summary row. The columns of the table have the following meaning:
passA test pass index. In the summary row—‘TOTL’.
earnedThe amount of spur the system received during interaction with the automaton according to the algorithm. In the summary row—the sum of values in the column.
randomThe amount of spur the system received during random interaction with the automaton when the system was equiprobably selecting output signals from a set of allowed signals. In the summary row—the sum of values in the column.
maximalThe amount of spur the system would receive during the most optimal interaction with the automaton. The program calculates this amount on passing the option -C VAL with a non-zero VAL. Otherwise, the amount is equal to the number of steps in a test pass. In the summary row—the sum of values in the column.
clBest cycle length. The program calculates the length on passing the option -C VAL with a non-zero VAL. Otherwise, the length is equal to 0. In the summary row—the average length of best cycles for all test passes.
% efrRelative efficiency equal to (earned/random)*100%. For the summary row, the formula uses the variables from that row.
% efaActual efficiency equal to (earned-random)/(maximal-random)*100%. For the summary row, the formula uses the variables from that row.
At the end of the log, the program prints a standard deviation of values in the column ‘% efr’ and a standard deviation of values in the column ‘% efa’.
Use the following command to run a specific number of test passes for an automaton defined in FILE according to the format described in “The Format of an Automaton File”:
qsmm-example-test -t num_passes [ -C VAL ] [ additional options ] -f FILE
The program verifies the connectivity of an automaton state graph. If VAL is positive, the program also verifies that the number of cycles in the graph is less than or equal to VAL. If VAL is not 0, the program prepends the test log with information on the best cycle in the automaton state graph as described in “Generating Random Automatons”.
Below there is a description of program options applicable to both system types: a homogeneous system and a system comprised of two subsystems, where the first subsystem is an environment state identification subsystem, and the second subsystem is an action emission subsystem.
Parameters related to automaton state graphs: state connectivity, simplification, limiting the number of cycles, and best cycle search. In the description of test modes—‘Max. cycles’. Supported option arguments:
Do not provide the state connectivity, do not perform the simplification, do not limit the number of cycles in the graph, and do not find the best cycle. This is default mode.
Provide the state connectivity, perform the simplification, limit the number of cycles in the graph by VAL, and find the best cycle.
Provide the state connectivity and find the best cycle by an algorithm analogous to Viterbi one. In the description of test modes—‘Max. cycles: −1’.
Provide the state connectivity, perform the simplification, and find the best cycle by an algorithm analogous to Viterbi one. In the description of test modes—‘Max. cycles: −2’.
The simplification of an automaton state graph consists in replacing transitions from (source) states to other states with transitions to the same (source) states on condition that resulting transitions do not yield positive spur increments, and each replacement does not break graph connectivity.
On searching the best cycle in the state graph, the program prints in the table column ‘maximal’ the maximum amount of spur the system would receive during the most optimal interaction with the automaton.
A file with an automaton definition. On omitting this option, generate a random automaton. In the description of test modes—‘Automaton file’.
A seed to initialize the pseudo-random number generator. The default value is 0. In the description of test modes—‘Random seed’.
The temperature (multiplied by some constant) of the homogeneous system or the temperature of the environment state identification subsystem and action emission subsystem. The default value is 1. This option requires testing mode turned on by the option -t, --test=INT. In the description of test modes—‘K*temp.’.
The number of steps of interaction with a deterministic finite automaton at each test pass. The automaton receives an input signal and emits an output signal in each step. The default value is 10000. This option requires testing mode turned on by the option -t, --test=INT. In the description of test modes—‘Steps per pass’.
A file to write program output to instead of stdout.
A file to write a table consisting of lines where each line contains two numbers separated by a space: step index and the actual efficiency (‘% efa’) of interaction between a system and deterministic finite automaton calculated for the step range from 0 to the step index. By default, do not write the table. This option requires testing mode turned on by the option -t, --test=INT.
A file to write a table consisting of lines where each line contains two numbers separated by a space: step index and the relative efficiency (‘% efr’) of interaction between a system and deterministic finite automaton calculated for the step range from 0 to the step index. By default, do not write the table. This option requires testing mode turned on by the option -t, --test=INT.
Perform the test a specified number of passes. This option turns on testing mode. On passing the option -f FILE, the program uses a supplied automaton for all test passes. Otherwise, at each test pass, the program generates a new random automaton with the number of input signals, output signals, and states specified by arguments at the end of command line. In the description of test modes—‘Passes’.
A system interacting with an automaton is homogeneous unless the program receives the option -s, --nstate=INT. For this kind of a system, the program supports a special list of options described below. All options require testing mode turned on by the option -t, --test=INT.
Compatibility level of algorithms assigned to the field compat of qsmm_actor_desc_s structure.
The default value is 0.
This option conflicts with the option -L, --large[=INT].
In the description of test modes—‘Algorithms v.’.
The type of informational signals for the system:
automaton states (default mode)
automaton output signals
In the description of test modes—‘Input signals’.
The length of a system state n-gram. The default value is 1. If the type of informational signals for the system is ‘dfa-out’, n-gram length 2 may lead to better efficiency. In the description of test modes—‘N-gram length’.
Use a large actor with a specified tree arity. The default value is 2. By default, use a small actor. In the description of test modes—‘Large’ and ‘Tree arity’.
The type of a function returning the relative probability of an output signal:
QSMM_RELPROB_USER1 without a helper function provided
QSMM_RELPROB_BUILTIN1 (default mode)
QSMM_RELPROB_BUILTIN2
QSMM_RELPROB_BUILTIN3
In the description of test modes—‘R. prob. type’.
If the program receives the option -s, --nstate=INT specifying the number of tracked environment states, a system interacting with an automaton representing an environment consists of two subsystems, where the first subsystem identifies a current environment state, and the second subsystem generates an adaptive action based on the current state. For the interaction with the automaton to be efficient, the number of interaction steps in each test pass should be much greater than in the case of a homogeneous system. In this mode of operation the program supports the following special list of options.
The temperature (multiplied by some constant) of the environment state identification subsystem. The default value is 1 unless overridden by the option --kt=FLOAT. In the description of test modes—‘K*temp. env.’.
The temperature (multiplied by some constant) of the action emission subsystem. The default value is 1 unless overridden by the option --kt=FLOAT. In the description of test modes—‘K*temp. opt.’.
The number of tracked environment states. To achieve better efficiency, specify that number twice or more times greater than the number of states of a deterministic finite automaton representing an environment. This option requires testing mode turned on by the option -t, --test=INT. In the description of test modes—‘Tracked states’.
In QSMM 1.19, the program test supports a simple method for producing the plots of dependency of actual efficiency of interaction with deterministic finite automatons on interaction step index.
The paper “An Approach to Optimal Action Generation for a System that Interacts with the Environment” mentioned at the beginning of test includes similar plots.
To generate a dataset FILE for creating a plot (e.g. by the program gnuplot), pass the new option --out-step-efa=FILE to the program test.
The dataset contains two columns: the number of steps in a test pass and corresponding actual efficiency (in percents) of interaction with deterministic finite automatons.
Example:
$ qsmm-example-test -t20 -s20 -n100000 -Ccs -o test.log \
--out-step-efa=ds_10_10_10_s20 10 10 10
$ tail -n8 test.log
18 73419.000 10324.000 100000.000 3 711.149 70.359
19 49915.000 6017.000 71428.571 7 829.566 67.110
20 84545.000 15664.000 100000.000 7 539.741 81.674
TOTL 1117415.000 163148.000 1701428.571 4 684.909 62.035
stddev efr: 283.697
stddev efa: 23.567
$ wc -l <ds_10_10_10_s20
100000
$ head -n4 ds_10_10_10_s20
0 0
1 -9.66851
2 -2.12572
3 -3.17173
$ tail -n4 ds_10_10_10_s20
99996 62.0346
99997 62.0346
99998 62.0346
99999 62.0347