Recently I'm studying machine learning algorithms among them linear regression and decision tree so I have a question regarding the scalability of both algorithms. Can anyone provide what is the scalability of both algorithms and examples?
1
-
$\begingroup$ What exactly do you mean when you say "scaleability"? $\endgroup$– PeterCommented Apr 15, 2020 at 15:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
If you use the standard OLS formula :
$$ \beta = (X^TX)^{-1}X^Ty$$
the overall linear regression complexity is $O(np^2)$, where n is the number of exemple and p the number of features.
For simple trees the theoretical complexity if of the same order $O(np^2)$.
In practice other techniques are used, like gradient descent for the regression. Also you may have simplifications depending on your problem ($n>>p$ for exemple, may lead to the use of sparse matrices).
Practical implementation like sklearn have following complexities (see https://www.thekerneltrip.com/machine/learning/computational-complexity-learning-algorithms/):
LinearRegression : $O(n^{0.72}p^{1.3})$
ExtraTreesRegressor: $O(n^{1.03}p^{0.88})$
Overall they are relatively simple algos and thus are pretty much as scalable as you can get. (or conversely we wouldn't use algorithms that are not scalable)
answered Apr 15, 2020 at 15:33
-
$\begingroup$ Good explanation for the performance part. What about prediction capability. Please also add that point. $\endgroup$– 10xAICommented Apr 16, 2020 at 5:04
-
$\begingroup$ It’s an entirely different question than what was asked. There is no general answer as prediction capabilities entirely depends on your problem / data set. Intuitively they are the simplest models so their prediction capability is expected to be lower than other models. $\endgroup$ Commented Apr 16, 2020 at 5:58