1
$\begingroup$

How can machine learning help extract a Boolean relationship in a given binary input-output data set?

Let us assume that the given data set is exhaustive - ie. it cover all possible input combinations, can we derive the boolean relationship between inputs and outputs? (Say we assume x inputs and 1 output)

Further, if the dataset is not exhaustive, can we predict the output for "(n+1)"th input vector if we know outputs for the previous "n" input vectors? (in other words, can we "learn" how the function behaves?)

I'd greatly appreciate if you can share what approach should I devise to work on this problem, and if possible, about any on-going research on this topic?


UPDATE: As rightly pointed out by @D.W. Several heuristics exist to tackle such NP-hard problems in logic synthesis and minimization.

The essence of my question is to find out if any Machine Learning algorithm can be adopted and developed, which potentially performs better than the currently known heuristics when deployed at scale.

And importantly, if any "recent" advances in ML can be of help in developing tools for Electronic Design Automation?

$\endgroup$
1
$\begingroup$

If you have an exhaustive list of all possible inputs, and the output for each, you already know the relationship between the input and output. You don't need fancy machine learning.

If you want to explicitly write a formula for this relationship, it is easy to write a DNF formula (each clause corresponds to a single input-output pair, i.e., a single row in the truth table). It's also easy to write a CNF formula, using a similar construction (each clause corresponds to a single input where the corresponding output is false).

If you want to find the minimal-length formula for this relationship, that is probably NP-hard (in fact it is "even harder" in some sense). However there are heuristics. Read about Karnaugh maps, Quine-McCluskey, the Espresso heuristic, and the fields of logic synthesis and circuit minimization.


I don't expect machine learning to perform better than existing methods. Existing methods have a lot of intelligence built in, based on this specific problem. ML methods wouldn't be able to benefit from any of that.

Ultimately, if you want to know whether some machine learning method performs better than standard methods, the only way to know for sure is to try it. But I don't expect it to yield useful results, without new insights.

$\endgroup$
  • $\begingroup$ Thank you very much for your time and sharing about several heuristics. Yes, my query is pertaining to target problems in logic synthesis and minimization which are NP-hard. The essence of my question is to find out if any Machine Learning algorithm can be deployed (at scale), which potentially performs better than currently known heuristics. And importantly, if any "recent" advances in ML can be of help in developing tools for Electronic Design Automation? Thanks again! $\endgroup$ – MightyInSpirit Dec 22 '16 at 13:44

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.