# What heuristics are there (if any) to know how close a circuit is to a function?

I'm working on an AI project for circuit minimization.

I'm trying to think of a heuristic to tell me how close a certain circuit is to representing a certain function.

For example, if I need to implement a XOR function, than a circuit consisting of a single OR gate will be closer to representing the XOR in comparison to a circuit consisting of a single AND gate (because all is missing is a single NOT gate).

Are there any such heuristics in order to sense how "close" a circuit is to the final circuit?

We have tried scoring the circuits by counting the number of correct outputs according to the truth table, but this fails. For example, if we have a circuit that for every input outputs the negation of the correct output, then its "score" would be 0 according to this heuristic, but in fact it is very close to the final design, and all that is missing is to not the output.

Thanks

• Interestingly both an AND gate and an OR gate are the same 'distance' away from an XOR function. If you meant NOR, then you could argue an OR is closer than an AND, for some methods of scoring it. Commented Jul 10, 2018 at 12:48
• Your question is flawed. Commented Jul 10, 2018 at 12:54
• This problem reminds me of following question: Is a clock not moving at all closer to being a perfect clock than a clock going 1 minute late? The first one shows twice a day exactly the correct time. The latter one never.
– Curd
Commented Jul 10, 2018 at 15:26
• It seems like primitive logic Commented Jul 12, 2018 at 22:03

You could base your "cost function" on DNF fault classes. For a start, you could consider the following set

• ENF: expression negation fault (a -> !a)
• TOF: term omission fault (a -> a | b)
• TIF: term insertion fault (a | b -> a)
• TNF: term negation fault (a | b -> a | !b)
• LOF: literal omission fault (a -> ab)
• LIF: literal insertion fault (ab -> a)
• LNF: literal negation fault (ab -> a!b)

For example, the distance from AND (a&b) to XOR (a&!b | !a&b) would be 1 LIF and 1 TOF, while a distance from AND to NAND would be 1 ENF. You'll have to experiment with weights you assign on different fault types in your cost function.

Another idea you may want to consider is to take the problem from the other end: instead of generating minimal functions and optimize for correctness, you could generate correct functions and optimize for minimalism. It's much easier to come up with a reasonable cost function in the latter case, and you don't have to actually reach the optimum in order to get an acceptable solution.

• This is a really good find. One thing grinds me, how would you calculate this metric for a given circuit, without actually having to first obtain the optimal implementation? That is to say, if the circuit is not correct, and this metric is obtainable, then there was no need for machine-learning in the first place, as the "steps for correction" are laid out. Excuse me if I missed something. Commented Jul 10, 2018 at 13:07
• Ah sorry, I think I see now, this can be used in a supervised training, and then the AI validated with unknown optimals. Upvote! Commented Jul 10, 2018 at 13:13
• @VicenteCunha I'm pretty sure this random PDF I found is not state of the art, and there's a lot of legitimate critique about the approach as I presented it. But I do believe that the OP should read a few articles about fault classes and fault equivalence. Commented Jul 10, 2018 at 13:32

Many other machine-learning algorithms (e.g. for perceptron training) use a performance metric such as quadratic estimation error, error covariance, or whatever makes most sense. Let's call this parameter $J$. In general, the goal of the algorithm is to reach an epoch (an iteration) in which $J$ is at a minimum (either local or global). This can be achieved by employing numeric optimization concepts, such as gradient-descent and second-derivative methods.

In the described example, where only a NOT operation would end up obtaining a correct answer, the performance $J$ is at a maximum (the circuit is wrong all the time). However, tweaking the system just a little bit results in $J$ at a global minimum (right all the time). This means that when evaluating the derivatives at the current point there should be a steep gradient vector pointing toward the correct solution.

Ideally, the algorithm employed would evaluate such gradient properly and iterate towards the correct solution. However, if this gradient is too steep, this may cause a numeric ill-condition, in the sense that changing the solution just a little bit causes huge fluctuations in $J$. If this happens, then a proper scaling of $J$ and better granulation of system parameters should be employed.

Perhaps an appropriate choice for $J$ would be the Hamming distance between results.

• Hamming distance will still be at maximum when a single final NOT gate is missing. Commented Jul 10, 2018 at 12:42
• @DmitryGrigoryev Yes, it will. Another big concern that makes this a dubious choice for J is there's no guarantee of convexity. I have no knowledge of a "boolean operations distance" metric. If I (or anyone else) figure out a proper alternative for J, I will update this answer (with proper credit). At this instant, this is my answer, as if numeric ill-condition occurs I've explained the recourse. Commented Jul 10, 2018 at 12:52

Your score should be specialized to the circuit you are interested in.

From the sounds of it, you are looking to score a circuit as a black box. The actual configuration of the gates is not important, but the outputs are. Presumably, from the comments, you don't know the ideal circuit already.

Consider two cases. One is a simulation of a synapse. This is a rather smooth problem to solve. A solution which outputs a 99% answer is probably very close to a "correct" answer. Contrast this with a circuit designed to do SHA-1 checksums. A solution which outputs a 99.99999999% answer is unspeakably far from a "correct" answer for such a circuit, because the measure of "correctness" for a cryptographic checksum is very demanding.

It's the application of your circuit that will define your best scoring metric.

• I don't think so. If you figure you the score which works for SHA-1, I'm pretty sure it will work for the synapse too. Commented Jul 12, 2018 at 8:02
• @DmitryGrigoryev Perhaps. It depends on if the scoring algortihm you use to accomplish that goal is fine-tuned to the specifics of SHA-1 or if its more generic. You are right that if you have a generic scoring algorithm which works in the hard cases, it'll be fine for the simple cases. Commented Jul 12, 2018 at 14:54

Our intelligence is actually Analog with trillions of memory and sensor inputs each with different weighting or gain and offset factors which may be non-linear too. The time sequence or logical sequence and combinations may be also part of a decision with each potential result having different weighting factors on the inputs and consequences to decide upon.

So when you say almost , you can mean any of these thresholds or weighting or timing or sequence operations must be defined to make it “Artificial” or resemble human response. This is why experience for fuzzy logic is so powerful.

Would you like experiential testing with fuzzy logic and confidence factors or define all these “almost” factors up front?

e.g for 5V logic 2.2v is almost a logic “1” . If it is moving in that direction we need a linear or Proportional (P) and Derivative (D) gain factor to give it more binary “weight” for “almost”

Every memory decision we make is billions of these analog computations with multiple comparator outputs with negative and positive consequences and feedback loops.

It is NOT simply to be or not to be?

Of course it depends how “intelligent” this design wishes to become!

Answer: {Heuristics and present state} and “almost” of each, can have any importance, depending your spec for “almost”.

Cross correlation function is one analysis method for both analog and digital systems. Digital fault coverage with test vectors for detection and correction are another method.

Your question, and the various answers, focus on digital (logic state machine) behaviors.

I suggest you start with a FULL state table, or logic table if no flip flops are needed, and have your metric be the % of correct responses.

Now, in your question, you have already tried this. As you note, for certain non-solutions the addition of an output inverter is all that is needed to be completely successful. Your question then becomes "how can we have learning, unless the optimal answer, or at least one successful answer, is already known?" which is a superb question.

How do humans do learning in unknown environments? They try something, anything, in small pieces, in large pieces. They try something.

This means you need to define what are "small pieces" (add an inverter, randomly, in any or all paths.

You also need to define what are "large pieces", and this requires graph surgery, which brings up the need to "understand", or must a system understand? if random exploration is the path to enlightment?

Again, how do humans explore new situations? They make changes and see what happens. That means they need to have a grasp upon Inputs, and Outputs.

When you realized the addition of just one inverter, at output, would be the next and final step, how did you the human come to that conclusion? Likely you explored all possible changes, using your vision to examine a logic table. The table, and your vision/brain ability to find useful patterns (and you've trained your brain to recognize "useful" for digital systems), allow your realization "Oh. Just add an output inverter."