0
$\begingroup$

I have been tasked with finding if a a function can be represented through threshold logic, and if that is the case to find the associated weights and threshold. The function is:

$$ f = x_7 + x_6 \cdot (x_5+x_4 \cdot (x_3 + x_2 \cdot x_1)) $$

The first step to check if it is a threshold function is check if it is unate, which I showed it is (each variable is positive), but moving beyond that appear my doubts. All the material I've read so far uses the truth table to build a set of inequalities, and then those are solved to find the weights and threshold. The problem is that all those examples are shown with functions of few variables, and in this example it gets out of hand to try to work over a truth table or the enormous set of equations.

It seems obvious there must be some consideration escaping me which helps solve the problem. So far, I've thought that many of the inequalities would reduce into not giving new information, but I'm at a miss on how to isolate those that do give useful information.

Any help with a general method to find the weights and threshold?

$\endgroup$
0
$\begingroup$

I asume that $f$ is meant to be a boolean-valued function of $x_1 \ldots x_7$.

A general method for any boolean expression without negation or exclusive or is:

  • All gates will be 2-input and have a threshold of $\frac12$

  • A $+$ operation is represented by two inputs with weight $1$ each.

  • A $\cdot$ input is represented by two inputs with weight $\frac38$ each.

  • Work from the innermost parentheses outward.

So your network can be represented by (all neurons have threshold $\frac12$):

Neuron 1 with inputs $x_1$ and $x_2$ each with weight $\frac38$ and output $N_1$.

Neuron 2 with inputs $x_3$ and $N_1$ each with weight $1$ and output $N_2$.

Neuron 3 with inputs $x_4$ and $N_2$ each with weight $\frac38$ and output $N_3$.

Neuron 4 with inputs $x_5$ and $N_3$ each with weight $1$ and output $N_4$.

Neuron 5 with inputs $x_6$ and $N_4$ each with weight $\frac38$ and output $N_5$.

Neuron 6 with inputs $x_7$ and $N_5$ each with weight $1$ will have the desired output $f$.

What would not be easy to show is that this is the least 2-input neurons that would do the job and that there is not more compact configuration using neurons with more than 2 inputs. In fact, finding the "optimal" net (in the sense of using as few neurons as possible) for the general boolean function of $k$ variables is probably an NP-hard problem.

$\endgroup$
  • $\begingroup$ Thank you. Indeed, I know I could solve it through multiple layers of minor threshold functions, but the idea is to find if it can be implemented in a single threshold function... You gave me the idea of trying an algorithmic approach, if there's no analytical easy way. $\endgroup$ – Ironil Jun 10 '16 at 8:30

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.