Model complexity

by: Kevin Broløs
(Feyn version 2.0.0 or newer)

---

When relating to the models that come out of the QLattice, it is often useful to look at complexity. For instance, this is already a measure when we sample models (max_complexity), and it is indirectly used when calculating aic or bic for the models when trying to choose parsimonious models.

For that reason, it's of course useful to understand how we measure complexity and what it means for the models, given the restrictions and ways we build and compose them.

Model complexity is an exact one-to-one metric with the amount of edges in the resulting model graph. This is useful, as adding more edges of course also means adding more features or interactions, which also increases complexity.

It also means, that by having a set complexity or a defined max complexity, there's a limit to how many features can be included in the model, as the amount of edges have a direct relationship to the depth of a binary tree, and we never allow more than two inputs into each interaction.

Thus, the maximum amount of features that can be represented is the complexity divided by 2 (rounding up), and the most amount of interactions (given that you have only one feature) is the complexity minus 1. The most interactions you can have is thus the complexity minus the amount of features in the model.

Below, we have composed a little table that'll help you reason about how many features and interactions you can at maximum expect to be present in models of different complexities:

Complexity	Max Features	Max Interactions
1	1	0
2	1	1
3	2	1-2
4	2	1-3
5	3	2-4
6	3	2-5
7	4	3-6
8	4	3-7
9	5	4-8
10	5	4-9
11	6	5-10
12	6	5-11
13	7	6-12
14	7	6-13
15	8	7-14
16	8	7-15
17	9	8-16
18	9	8-17
19	10	9-18
20	10	9-19
21	11	10-20
22	11	10-21
23	12	11-22
24	12	11-23
25	13	12-24
26	13	12-25
27	14	13-26
28	14	13-27
29	15	14-28
30	15	14-29
31	16	15-30