Temporal and spatial Analysis of TClass

How long will TClass take to learn and how much memory/space will it take in order to calculate the results? A rather informal analysis of each will be presented. First, some notation: Let $n$ be the number of streams in the training set. Let $m$ be the number of metafeatures we are applying to the domain. Furthermore, let us assume that applying a particular metafeature will on average generate $i$ instantiated features. Also, assume that on average, the length of the streams is $t$.

The instantiated feature extraction consists of an inner loop that examines each of the $n$ streams in turn. Within that inner loop, the function extract is called for each instance. Assuming that the extract function is linear in the length of the stream (i.e. is $O(t)$), then the feature extraction will take $O(tn)$ time. However, the function is called once for every metafeature, and hence the extraction stage is $O(tnm)$.

As to space, under the previous assumptions, the amount of data to be stored is to be stored is $O(nim)$: for $n$ streams, and for $m$ metafeatures, $i$ instantiated features must be stored.

Synthetic feature construction is called once for each metafeature. It is flattened into a single layer, but the amount of data for each metafeature is still $O(ni)$. Consider the random search algorithm. At each stage, it chooses a random subset of points with some upper bound (in the default case eight). It then compares each point (of which there are $O(ni)$) to each of the elements of the subset. This operation is repeated a fixed number of times, so this is still $O(ni)$. Since it is called once for each metafeature, the total amount of time is also $O(nim)$.

Since there is some upper bound on the number of regions that will be produced, then there will be $O(m)$ centroids which need to be stored.

Then there is the attribution stage. For each instance, of which there are $n$, $i$ instances (on average) with $m$ metafeatures must be compared. This involves looking against a set of centroids with an upper bound. Hence this too is an $O(nim)$ operation.

The data storage requirements are $O(nm)$, since for each instance, there are a certain maximum number of metafeatures and a maximum number of centroids per metafeature.

The final stage is the learning stage. However in general, we do not know what the amount of time for the learning algorithm is. Let us assume that the learning algorithm depends linearly on the number of attributes and the number of instances. Then in this case, there are $n$ instances, each with $O(m)$ features, so the learner will take $O(nm)$ time.

The global feature extraction will generate $O(ng)$ features. Since many global features depend on things like working out the mean, each one may take up to $t$ time. Hence the total time is $O(ntg)$.

Hence finally, the total time is $O(tnm) + O(nm) + O(ntg)+ O(nim)$, or after simplifying, it is $O(ntm) + O(nim) + O(ntg)$. As for the space, the most space is required to store the data is $O(ntm) + O(nim) + O(ntg)$.

This is good. It means that the total time and space used is linear in five components:

• The number of training instances.
• The number of metafeatures applied in the domain.
• The average length of each training instance.
• The average number of metafeatures extracted from each instance.
• The number of global variables.