Computational complexity theory is a field of computer science that studies the inherent difficulty of solving computational problems. It provides a framework for analyzing the resources required to solve problems, such as time and space.
The most common measure of computational complexity is time complexity, which is the amount of time required for an algorithm to solve a problem as a function of the input size. Space complexity, on the other hand, measures the amount of memory required by an algorithm.
The analysis of algorithms, on the other hand, is the study of how efficient an algorithm is. It involves evaluating the performance of an algorithm by analyzing its time and space complexity, as well as its practical performance on various inputs.
Algorithm analysis involves characterizing the worst-case, best-case, and average-case behavior of an algorithm. This characterization helps to determine how the algorithm performs under different conditions and inputs.
There are several techniques used for analyzing algorithms, including asymptotic analysis, which characterizes the performance of an algorithm as the input size approaches infinity, and empirical analysis, which involves measuring the performance of an algorithm on various inputs.
Overall, computational complexity theory and the analysis of algorithms are important fields in computer science that help us understand the fundamental limits of computation and design more efficient algorithms.
Theoretical results in machine learning mainly deal with a type of inductive learning called supervised learning. In supervised learning, an algorithm is given samples that are labeled in some useful way. For example, the samples might be descriptions of mushrooms, and the labels could be whether or not the mushrooms are edible. The algorithm takes these previously labeled samples and uses them to induce a classifier. This classifier is a function that assigns labels to samples, including samples that have not been seen previously by the algorithm. The goal of the supervised learning algorithm is to optimize some measure of performance such as minimizing the number of mistakes made on new samples.
In addition to performance bounds, computational learning theory studies the time complexity and feasibility of learning.[citation needed] In computational learning theory, a computation is considered feasible if it can be done in polynomial time.[citation needed] There are two kinds of time complexity results:
Positive results – Showing that a certain class of functions is learnable in polynomial time.
Negative results – Showing that certain classes cannot be learned in polynomial time.
Negative results often rely on commonly believed, but yet unproven assumptions,[citation needed] such as:
Computational complexity – P ≠ NP (the P versus NP problem);
Cryptographic – One-way functions exist.
There are several different approaches to computational learning theory based on making different assumptions about the inference principles used to generalise from limited data. This includes different definitions of probability (see frequency probability, Bayesian probability) and different assumptions on the generation of samples.[citation needed] The different approaches include:
Exact learning, proposed by Dana Angluin.
Probably approximately correct learning (PAC learning), proposed by Leslie Valiant;
VC theory, proposed by Vladimir Vapnik and Alexey Chervonenkis;
Bayesian inference[citation needed];
Algorithmic learning theory, from the work of E. Mark Gold.
Online machine learning, from the work of Nick Littlestone.
While its primary goal is to understand learning abstractly, computational learning theory has led to the development of practical algorithms. For example, PAC theory inspired boosting, VC theory led to support vector machines, and Bayesian inference led to belief network.
Comments
Post a Comment