A comparison of Expert Systems and Machine Learning approaches in terms of run-time-efficiency and time/space complexity

Question

For part of a paper I am writing on Clinical Decision Support Systems (computer-aided medical decision making, e.g. diagnosis, treatment), I am trying to compare Expert Systems with systems based on Machine Learning approaches (Deep Learning, Artificial Neural Networks, etc.).

Specifically, I am currently trying to make a general comparison (if possible) of expert systems with machine learning systems across dimensions of efficiency and complexity, i.e.

• run-time-efficiency
• time complexity
• space complexity

My current line of thinking, after having tried to find literature with limited success, is that, in the case where one is trying to answer questions in a very specific, limited, domain that only requires a few rules (for an expert system), expert systems are relatively "cheap" in terms of these three criteria. However, when a problem/domain becomes more complex, expert systems seem to suffer from the fact that the number of rules needed "explodes", which, I would think, could lead to things such as large search trees or other problems. My feeling from what I have generally read about machine learning approaches is that these adapt better to more complex problems with higher dimensionalities.

I would like to find some information that either confirms/backs up my general impression, or guides me to some other understanding of this.

Unfortunately, I can't seem to find any sources that specifically deal with this kind of comparison. I'm not sure if I this is because my problem statement is to wide/vague, I am not searching correctly, there just isn't much literature, or my question doesn't make sense.

Some of the sources I did manage to find are:

Expert systems are still used and important in areas such as robotics and monitoring. However, the complexity of advanced rules systems can lead to performance issues. ANNs are currently managing to overcome such performance issues through scale-out.

Source: Forbes

Unfortunately, this is the most explicit source I've found. However, it doesn't really provide any details on which this claim could backed up, nor would I consider this a solid source, especially not in an academic setting.

Checking for the logical consistency of a set of interrelated logical rules results in the formulation of a satisfiability (SAT) problem [Bezem, 1988]. If one assumes only binary variables, say n of them, then the corresponding search space is of size 2n . That is, it can become very large quickly. This is an NP-complete problem very susceptible to the “dimensionality curse” problem [Hansen and Jaumard, 1990]

Source: Yanase J, and Triantaphyllou E, 2019, A Systematic Survey of Computer-Aided Diagnosis in Medicine: Past and Present Developments, page 7

This mentions "dimensionality curse", but in the context of checking for logical consistency of the rules of an expert system, and not really in the context of run-time-efficiency & complexity.

I have found numerous other articles comparing expert systems and machine learning approaches, e.g. Ravuri et al., 2019, Learning from the experts: From expert systems to machine-learned diagnosis models, but none of them, from what I have seen, compare expert systems and machine learning approaches across the dimensions I am interested in.

Would anyone be able to provide some input on what would be aspects in comparing expert systems and machine learning approaches in terms of the efficiency and complexity criteria listed above, and/or, be able to point me in the right direction?

Answer 1

My feeling from what I have generally read about machine learning approaches is that these adapt better to more complex problems with higher dimensionalities.

Your intuition seems to align with the empirical results in these domains in the last few years. Expert System are in general not used for domains like Computer Vision, but there may be exceptions do this.

Specifically, I am currently trying to make a general comparison (if possible) of expert systems with machine learning systems across dimensions of efficiency and complexity

I will try to provide you with an approach to systematically compare them. You should create a set of tasks $T$ to evaluate your comparison. I will assume your metric to evaluate on is accuracy, but you can of course replace this with any score function of your choice.

Space Complexity

For all tasks implement the expert system and ML model you want to compare. Compare the amount of space they take and average this by the number of tasks to get an estimate of the complexity for each.

$ \hat{E}[\mathrm{space}] = \frac{1}{T} \sum_{t\in T} \mathrm{space}(t)$

Time Complexity

Similar to measuring space, but now time each of your model and expert system. You could do so for different functions on each of your tasks such as training or predicting. Training is more difficult, because if you're doing supervised learning for example you don't know when you will stop since more training time might be better. So you should set a time or some criteria of convergence and list them under your assumptions.

$ \hat{E}[\mathrm{time}] = \frac{1}{T} \sum_{t\in T} \mathrm{time}(\mathrm{predict}(t))$

Run-time-efficiency

Here is where things get tricky, because there isn't a single unified expression for this that I'm aware of. So I would suggest to evaluate this based on dividing the accuracy by the approximate number of operations. This could be done multiple times and averaged for example if training a neural net for each epoch. To reflect the actual run time in practice more accurately you might also just want to add a time comparison in the form of accuracy divided by runtime on fixed hardware.

All of this provides of course no strong theoretical explanation, but is more of a study to provide some empirical data. If this is done on a large enough scale your results become a lot more meaningful. Scale here means the number of different model types and expert systems and tasks you're testing on.