CODEWITHSUNDEEP
complexity-theory
Dzung Nguyen
Dzung Nguyen

Reputation: 3944

What is the computational complexity of machine learning problems?

Given a ML problem such as computer vision, or NLP, what is the computational complexity of those problems?

Can I think that using training model is an effective way to solve "hard" problems (intractable)??

Upvotes: 2

Views: 1214

Answers (2)

RUser4512
RUser4512

Reputation: 1074

The complexity of NLP is quite vague : what are you trying to achieve precisely ? In the case of Part Of Speech tagging, then you will need to specify what are the inputs you focus on : the length of the sentence, the size of your vocabulary... What tagger are you using ? Some are just pre-trained models that will predict a label from various features (the position of a word in the sentence, does it end by some specific characters...)

In this case, you would need to know the complexity of the prediction of a new data point of the underlying classifier.

But, in turn, evaluating the complexity of a classifier (or regressor) can be quite complex, as they rely on many other algorithms, which can be implementend in many ways (sparse data / dense data...). I wrote a detailed article on my blog : computational complexity of machine learning algorithms. The main conclusions were that theoretical complexities did not match observed complexities (or at least, for small samples), even for "simple" algorithms.

Now, coming back to the part of speech tagging, let's imagine that it is performed using support vector machines (it could be based on Hidden Markov Models and the conclusions would be radically different) on a sentence of length n. Note that the feature extraction contains a constant number of steps, each being evaluated in a constant time (neighboring words, binary features). For each word, feature evaluation is O(1).

With a linear kernel (the complexity of the prediction method will depend on the kernel you chose with SVMs) you have to predict the class of each word. The number of features associated to each word being bounded (roughly 40), you are just evaluating an inner product between two (sparse) vectors. Again, you can consider it a 0(1). So, performing part of speech tagging, based on linear SVM, on a sentence of n words is a O(n).

Even though I focused on a very simple example you see how big the topic can become...

Upvotes: 0

Deepu
Deepu

Reputation: 7610

Natural Language Processing and Computer Vision are areas of Computer Science where thousands of algorithms exist. So it may not be possible to give the computational complexity for such broad areas in general. The complexity of algorithms range from sub linear to NP Hard. For example sub string search is having a complexity O(mn) where m is the size of the sub string and n is the size of the text to be searched. Where as Automatic summarization in NLP is an AI-Complete problem making it one of the most difficult in NLP.

For the second part of your question, the answer is No. Using training models will not reduce the complexity of solving Hard (Intractable) Problems.

Upvotes: 1

Related Questions