I was wondering if there exist any algorithms for finding the "best possible" Boolean function whose output will approximate a binary target vector.

My data consist of roughly 100k observations (rows). I have around 100 logical statements (features) that evaluate to either 0 or 1. I also have a related Boolean target vector. I'd like to find a Boolean function that will get "reasonably" close to describing this Boolean target (I'm not trying to necessarily have them match perfectly!). I'd like to evaluate the closeness using one of the standard scoring metrics, e.g. the Matthews Correlation Coefficient (MCC), which in this case is nothing else but the Pearson Correlation Coefficient.

My only constraint (that I can think of thus far, at least) is that I allow for AND and OR operators only (so no NOT, XOR, etc.), and I'd like the Boolean function to be as succinct as possible (so a Boolean function combining 3 or 4 logical statements and with a decent performance is better than a function combining 20 statements and having a not-so-much better performance) - I was hoping I could somehow set the ceiling on how many statements the algorithm can use at any time.

I thought of doing some pre-processing of data where I'd get rid of statements that aren't very informative (i.e result in a very low MCC when compared to the target Boolean), but I'm concerned that by focusing on only the most correlated statements I'm essentially throwing away potentially useful information. That is, while the statement itself might not be very correlated with the target, its combination with another statement via one of the two Boolean operators could very well be...

Ideally, I'm going to arrive at something fairly succinct and short, like "(a OR b) AND (c OR d)", and if this describes the target vector well enough that's all I'm looking for.

I wrote a brute-force algorithm that generates such nested combinations and that allows me to set the ceiling for the number of logical statements, but even if I choose that number to be fairly low there's simply too many possible combinations to consider. I'd like to do this in some smarter (and hopefully quicker) way. So far, the only thing I found was this link to a similar(?) question on HN: Ask HN: Machine learning for boolean functions?. Also, I've considered doing some sort of dimensionality reduction or directly classifying the target based on my binary features, but can't think of any ML algorithms that would effectively result in two lists (one for features to be combined and the other for features discarded - of course, this still doesn't say how the to-be-combined features should be combined in the subsequent step anyway).

I'd very much appreciate some pointers as I'm guessing this is probably a problem others have worked on before. Perhaps I'm just missing something very obvious? Thanks!

PS - Happy to provide more information if needed!

PPS - I cross-posted this on stats.stackexchange.com too, but since this question is somewhat in-between stats/ML and mathematics I thought it would make sense to post it here as well. I hope that's OK!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.