hypothesis space search in decision tree learning in machine learning

ID3 Algorithm and Hypothesis space in Decision Tree Learning

The collection of potential decision trees is the hypothesis space searched by ID3. ID3 searches this hypothesis space in a hill-climbing fashion, starting with the empty tree and moving on to increasingly detailed hypotheses in pursuit of a decision tree that properly classifies the training data.

In this blog, we’ll have a look at the Hypothesis space in Decision Trees and the ID3 Algorithm. 

ID3 Algorithm: 

The ID3 algorithm (Iterative Dichotomiser 3) is a classification technique that uses a greedy approach to create a decision tree by picking the optimal attribute that delivers the most Information Gain (IG) or the lowest Entropy (H).

What is Information Gain and Entropy?  

Information gain: .

The assessment of changes in entropy after segmenting a dataset based on a characteristic is known as information gain.

It establishes how much information a feature provides about a class.

We divided the node and built the decision tree based on the value of information gained.

The greatest information gain node/attribute is split first in a decision tree method, which always strives to maximize the value of information gain. 

The formula for Information Gain: 

Entropy is a metric for determining the degree of impurity in a particular property. It denotes the unpredictability of data. The following formula may be used to compute entropy:

S stands for “total number of samples.”

P(yes) denotes the likelihood of a yes answer.

P(no) denotes the likelihood of a negative outcome.

• Calculate the dataset’s entropy.
• For each feature/attribute.

Determine the entropy for each of the category values.

Calculate the feature’s information gain.

• Find the feature that provides the most information.
• Repeat it till we get the tree we want.

Characteristics of ID3: 

• ID3 takes a greedy approach, which means it might become caught in local optimums and hence cannot guarantee an optimal result.
• ID3 has the potential to overfit the training data (to avoid overfitting, smaller decision trees should be preferred over larger ones).
• This method creates tiny trees most of the time, however, it does not always yield the shortest tree feasible.
• On continuous data, ID3 is not easy to use (if the values of any given attribute are continuous, then there are many more places to split the data on this attribute, and searching for the best value to split by takes a lot of time).

Over Fitting:  

Good generalization is the desired property in our decision trees (and, indeed, in all classification problems), as we noted before. 

This implies we want the model fit on the labeled training data to generate predictions that are as accurate as they are on new, unseen observations.

Capabilities and Limitations of ID3:

• In relation to the given characteristics, ID3’s hypothesis space for all decision trees is a full set of finite discrete-valued functions.
• As it searches across the space of decision trees, ID3 keeps just one current hypothesis. This differs from the prior version space candidate Elimination approach, which keeps the set of all hypotheses compatible with the training instances provided.
• ID3 loses the capabilities that come with explicitly describing all consistent hypotheses by identifying only one hypothesis. It is unable to establish how many different decision trees are compatible with the supplied training data.
• One benefit of incorporating all of the instances’ statistical features (e.g., information gain) is that the final search is less vulnerable to faults in individual training examples.
• By altering its termination criterion to allow hypotheses that inadequately match the training data, ID3 may simply be modified to handle noisy training data.
• In its purest form, ID3 does not go backward in its search. It never goes back to evaluate a choice after it has chosen an attribute to test at a specific level in the tree. As a result, it is vulnerable to the standard dangers of hill-climbing search without backtracking, resulting in local optimum but not globally optimal solutions.
• At each stage of the search, ID3 uses all training instances to make statistically based judgments on how to refine its current hypothesis. This is in contrast to approaches that make incremental judgments based on individual training instances (e.g., FIND-S or CANDIDATE-ELIMINATION ).

Hypothesis Space Search by ID3: 

• ID3 climbs the hill of knowledge acquisition by searching the space of feasible decision trees.
• It looks for all finite discrete-valued functions in the whole space. Every function is represented by at least one tree.
• It only holds one theory (unlike Candidate-Elimination). It is unable to inform us how many more feasible options exist.
• It’s possible to get stranded in local optima.
• At each phase, all training examples are used. Errors have a lower impact on the outcome.

• Machine Learning Tutorial
• Data Analysis Tutorial
• Python - Data visualization tutorial
• Machine Learning Projects
• Machine Learning Interview Questions
• Machine Learning Mathematics
• Deep Learning Tutorial
• Deep Learning Project
• Deep Learning Interview Questions
• Computer Vision Tutorial
• Computer Vision Projects
• NLP Project
• NLP Interview Questions
• Statistics with Python
• 100 Days of Machine Learning
• SEMMA Model
• Azure Virtual Machine for Machine Learning
• Orthogonal Projections
• CNN | Introduction to Padding
• "Hello World" Smart Contract in Remix-IDE
• Brain storm optimization
• Cubic spline Interpolation
• The Ultimate Guide to Quantum Machine Learning - The next Big thing
• Power BI - Timeseries, Aggregation, and Filters
• ML | Naive Bayes Scratch Implementation using Python
• Kullback-Leibler Divergence
• Well posed learning problems
• How L1 Regularization brings Sparsity`
• Hierarchical clustering using Weka
• FastText Working and Implementation
• ML - Candidate Elimination Algorithm
• Open AI GPT-3
• Differentiate between Support Vector Machine and Logistic Regression
• Introduction to Speech Separation Based On Fast ICA

Hypothesis in Machine Learning

The concept of a hypothesis is fundamental in Machine Learning and data science endeavors. In the realm of machine learning, a hypothesis serves as an initial assumption made by data scientists and ML professionals when attempting to address a problem. Machine learning involves conducting experiments based on past experiences, and these hypotheses are crucial in formulating potential solutions.

It’s important to note that in machine learning discussions, the terms “hypothesis” and “model” are sometimes used interchangeably. However, a hypothesis represents an assumption, while a model is a mathematical representation employed to test that hypothesis. This section on “Hypothesis in Machine Learning” explores key aspects related to hypotheses in machine learning and their significance.

A hypothesis in machine learning is the model’s presumption regarding the connection between the input features and the result. It is an illustration of the mapping function that the algorithm is attempting to discover using the training set. To minimize the discrepancy between the expected and actual outputs, the learning process involves modifying the weights that parameterize the hypothesis. The objective is to optimize the model’s parameters to achieve the best predictive performance on new, unseen data, and a cost function is used to assess the hypothesis’ accuracy.

What is Hypothesis Testing?

Researchers must consider the possibility that their findings could have happened accidentally before interpreting them. The systematic process of determining whether the findings of a study validate a specific theory that pertains to a population is known as hypothesis testing.

To assess a hypothesis about a population, hypothesis testing is done using sample data. A hypothesis test evaluates the degree of unusualness of the result, determines whether it is a reasonable chance variation, or determines whether the result is too extreme to be attributed to chance.

How does a Hypothesis work?

In most supervised machine learning algorithms, our main goal is to find a possible hypothesis from the hypothesis space that could map out the inputs to the proper outputs. The following figure shows the common method to find out the possible hypothesis from the Hypothesis space:

Hypothesis Space (H)

Hypothesis space is the set of all the possible legal hypothesis. This is the set from which the machine learning algorithm would determine the best possible (only one) which would best describe the target function or the outputs.

Hypothesis (h)

A hypothesis is a function that best describes the target in supervised machine learning. The hypothesis that an algorithm would come up depends upon the data and also depends upon the restrictions and bias that we have imposed on the data.

The Hypothesis can be calculated as:

• m = slope of the lines
• b = intercept

To better understand the Hypothesis Space and Hypothesis consider the following coordinate that shows the distribution of some data:

Say suppose we have test data for which we have to determine the outputs or results. The test data is as shown below:

We can predict the outcomes by dividing the coordinate as shown below:

So the test data would yield the following result:

But note here that we could have divided the coordinate plane as:

The way in which the coordinate would be divided depends on the data, algorithm and constraints.

• All these legal possible ways in which we can divide the coordinate plane to predict the outcome of the test data composes of the Hypothesis Space.
• Each individual possible way is known as the hypothesis.

Hence, in this example the hypothesis space would be like:

Hypothesis in Statistics

In statistics , a hypothesis refers to a statement or assumption about a population parameter. It is a proposition or educated guess that helps guide statistical analyses. There are two types of hypotheses: the null hypothesis (H0) and the alternative hypothesis (H1 or Ha).

• Null Hypothesis(H 0 ): This hypothesis suggests that there is no significant difference or effect, and any observed results are due to chance. It often represents the status quo or a baseline assumption.
• Aternative Hypothesis(H 1 or H a ): This hypothesis contradicts the null hypothesis, proposing that there is a significant difference or effect in the population. It is what researchers aim to support with evidence.

Frequently Asked Questions (FAQs)

1. how does the training process use the hypothesis.

The learning algorithm uses the hypothesis as a guide to minimise the discrepancy between expected and actual outputs by adjusting its parameters during training.

2. How is the hypothesis’s accuracy assessed?

Usually, a cost function that calculates the difference between expected and actual values is used to assess accuracy. Optimising the model to reduce this expense is the aim.

3. What is Hypothesis testing?

Hypothesis testing is a statistical method for determining whether or not a hypothesis is correct. The hypothesis can be about two variables in a dataset, about an association between two groups, or about a situation.

4. What distinguishes the null hypothesis from the alternative hypothesis in machine learning experiments?

The null hypothesis (H0) assumes no significant effect, while the alternative hypothesis (H1 or Ha) contradicts H0, suggesting a meaningful impact. Statistical testing is employed to decide between these hypotheses.

Please Login to comment...

Similar reads.

• Machine Learning
• What are Tiktok AI Avatars?
• Poe Introduces A Price-per-message Revenue Model For AI Bot Creators
• Truecaller For Web Now Available For Android Users In India
• Google Introduces New AI-powered Vids App
• 30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Decision Tree Learning

• Tom M. Mitchell. Machine Learning. [1] McGraw Hill. 1997. Chapter 3.
• and his slides [2] .

1 Introduction

• Decision Trees are among the most widely used methods for inductive inference.
• It is a method for approximating discrete-valued functions.
• Robust to noisy data and can learn disjunctive expressions.
• The hypothesis is represented using a decision tree.
• Has been used for everything from medical diagnosis to assessing the credit risk of loan applications.
• Example : Tree to predict C-Section risk
• Learned from medical records of 1000 women.
• Negative examples are C-sections

2 Representation

• Each node in the tree specifies a test for some attribute of the instance.
• Each branch corresponds to an attribute value.
• Each leaf node assigns a classification.
• How would this tree classify: \[\langle Outlook=Sunny, Temperature = Hot, Humidity = High, Wind = Strong \rangle\]
• Decision trees represent a disjunction (or) of conjunctions (and) of constraints on the values. Each root-leaf path is a conjunction. \[ (Outlook=Sunny \wedge Humidity=Normal) \vee (Outlook = Overcast) \vee (Outlook=Rain \wedge Wind=Weak)\]

3 When to Consider Decision Trees

• Instances describable by attribute-value pairs.
• Target function is discrete valued.
• Disjunctive hypothesis may be required.
• Possibly noisy training data.
• The training data may contain missing attribute values.
• Problems in which the task is to classify examples into one of a discrete set of possible categories are called classification problems .

4 Building a Decision Tree

• Basic Top-down algorithm:
• $A \leftarrow$ the best decision attribute for next $node$.
• Assign $A$ as decision attribute for $node$.
• For each value of $A$, create new descendant of $node$.
• Sort training examples to leaf nodes.
• If training examples perfectly classified, Then STOP, Else iterate over new leaf nodes.
• This is basically the ID3 algorithm.
• What do we mean by best ?

4.1 Choosing the Best Attribute

• There are 9 positive and 5 negative examples.
• Humidity = High has 3 positive and 4 negative.
• Humidity = Normal has 6 positive and 1 negative.
• Wind = Weak has 6 positive and 2 negative.
• Wind = Strong has 3 positive and 3 negative
• Which one is better as a root node, Humidity or Wind?

4.2 Entropy

• $S$ is a sample of training examples
• $p_{\oplus}$ is the proportion of positive examples in $S$.
• $p_{\ominus}$ is the proportion of negative examples in $S$.
• Entropy measures the impurity of $S$ \[ Entropy(S) \equiv - p_{\oplus} \log_{2} p_{\oplus} - p_{\ominus} \log_{2} p_{\ominus} \]
• For example, if $S$ has 9 positive and 5 negative examples, its entropy is \[Entropy([9+,5-]) = -\left(\frac{9}{14}\right)\log_2\left(\frac{9}{14}\right) - \left(\frac{5}{14}\right)log_2\left(\frac{5}{14}\right) = 0.94\]
• This function is 0 for $p_{\oplus} = 0$ and $p_{\oplus} = 1$. It reaches its maximum of 1 when $p_{\oplus} = .5$
• That is, it is maximized when there degree of “confusion” is maximized.

4.3 Entropy as Encoding Length

• We can also say that $Entropy(S)$ equals the expected number of bits needed to encode class ($\oplus$ or $\ominus$) of randomly drawn member of $S$ using the optimal, shortest-length code.
• Information theory: optimal length code assigns $- \log_{2}p$ bits to message having probability $p$.
• Imagine I'm choosing elements from $S$ at random and telling you whether they are $\oplus$ or $\ominus$. How many bits per element will I need? (We work-out encoding beforehand).
• If message has probability 1 then its encoding length is 0. Why?
• If probability .5 then we need 1 bit (the maximum).
• So, the expected number of bits to encode whether a random member of $S$ is $\oplus$ or $\ominus$ is: of $S$: \[ p_{\oplus} (-\log_{2} p_{\oplus}) + p_{\ominus} (-\log_{2} p_{\ominus}) \] \[ Entropy(S) \equiv - p_{\oplus} \log_{2} p_{\oplus} - p_{\ominus} \log_{2} p_{\ominus} \]

4.4 Non Boolean Entropy

• If the target attribute can take on $c$ different values we can still define entropy \[Entropy(S) \equiv \sum_{i=1}^c -p_i\log_2p_i\]
• $p_i$ is the proportion belonging to class $i$.
• Now the entropy can be as large as $\log_2c$.

4.5 Information Gain

• The information gain is the expected reduction in entropy caused by partitioning the examples with respect to an attribute.
• Given $S$ is the set of example, $A$ the attribute, and $S_v$ the subset of $S$ for which attribute $A$ has value $v$: \[ Gain(S,A) \equiv Entropy(S) - \sum_{v \in Values(A)} \frac{|S_{v}|}{|S|} Entropy(S_{v}) \]
• That is, current entropy minus new entropy.
• Original Entropy = 0.94
• Humidity = High entropy = 0.985
• Humidity = Normal entropy = 0.592
• $Gain (S,Humidity) = .94 - \left(\frac{7}{14}\right).984 - \left(\frac{7}{14}\right).592 = .151$
• Wind = Weak entropy = 0.811
• Wind = Strong entropy = 1.0
• $Gain (S,Wind) = .94 - \left(\frac{8}{14}\right).811 - \left(\frac{6}{14}\right)1.0 = .048$
• So Humidity provides a greater information gain.
• Create a root node
• If all Examples have the same Target value, give the root this label
• Else if Attributes is empty label the root according to the most common value
• Calculate the information gain for each attribute, according to the average entropy formula
• Select the attribute, A, with the lowest average entropy (highest information gain) and make this the attribute tested at the root
• Add a new branch below the root, corresponding to A = v
• Let Examples(v) be those examples with A = v
• If Examples(v) is empty, make the new branch a leaf node labeled with the most common value among Examples
• Else let the new branch be the tree created by ID3(Examples(v), Target, Attributes - {A})

4.7 ID3 Example

• $Gain(S,Outlook) = 0.246$
• $Gain(S,Humidity) = 0.151$
• $Gain(S,Wind) = 0.048$
• $Gain(S,Temperature)= 0.029$
• So, Outlook would be the root. The Overcast branch would lead to a Yes classification.
• $Gain(S', Humidity) = .97$
• $Gain(S', Temperature) = .57$
• $Gain(S', Wind) = .019$

5 Hypothesis Space Search by ID3

• ID3 searches the space of possible decision trees: doing hill-climbing on information gain.
• It searches the complete space of all finite discrete-valued functions. All functions have at least one tree that represents them.
• It maintains only one hypothesis (unlike Candidate-Elimination). It cannot tell us how many other viable ones there are.
• It does not do back tracking. Can get stuck in local optima.
• Uses all training examples at each step. Results are less sensitive to errors.

6 Inductive Bias

• Given a set of examples there are many trees that would fit it. Which one does ID3 pick?
• This is the inductive bias.
• Approximate ID3 inductive bias: Prefer shorter trees.
• To actually do that ID3 would need to do a BFS on tree sizes.
• Better ID3 inductive bias: Prefer shorter trees over longer trees. Prefer trees that place high information gain attributes near the root.

6.1 Restriction and Preference Biases

• ID3 searches a complete hypothesis space but does so incompletely since once it finds a good hypothesis it stops (cannot find others).
• Candidate-Elimination searches an incomplete hypothesis space (it can only represent some hypothesis) but does so completely .
• A preference bias is an inductive bias where some hypothesis are preferred over others.
• A restriction bias is an inductive bias where the set of hypothesis considered is restricted to a smaller set.

6.2 Occam's Razor

• Occam's razor [3] : Prefer the simplest hypothesis that fits the data.
• Why should we prefer a shorter hypothesis?
• a short hypothesis that fits data unlikely to be coincidence
• a long hypothesis that fits data might be coincidence.
• e.g., all trees with a prime number of nodes that use attributes beginning with Z.
• What's so special about small sets based on size of hypothesis?

7 Issues in Decision Tree Learning

• How deep to grow?
• How to handle continuous attributes?
• How to choose an appropriate attributes selection measure?
• How to handle data with missing attributes values?
• How to handle attributes with different costs?
• How to improve computational efficiency?
• ID3 has been extended to handle most of these. The resulting system is C4.5 [4] .

7.1 Overfitting

• A hypothesis $h \in H$ is said to overfit the training data if there exists some alternative hypothesis $h' \in H$, such that $h$ has smaller error than $h'$ over the training examples, but $h'$ has smaller error than $h$ over the entire distribution of instances.
• That is, if \[ error_{train}(h) < error_{train}(h') \] and \[ error_{D}(h) > error_{D}(h') \]
• This can happen if there are errors in the training data.
• It becomes worse if we let the tree grow to be too big, as shown in this experiment:

7.1.1 Dealing With Overfitting

• Either stop growing the tree earlier or prune it after-wards. Pruning has been more effective.
• Use a separate set of examples (not training) to evaluate the utility of post-pruning nodes.
• Use a statistical test to estimate whether expanding a node is likely to improve performance beyond the training set.
• Use explicit measure of the complexity for encoding the training examples and the decision tree. Stop when this encoding size is minimize. Minimum Description Length principle (later).

7.1.2 Reduced-Error Pruning

• Split data into training and validation sets.
• Evaluate impact on validation set of pruning each possible node (plus those below it)
• Greedily remove the one that most improves validation set accuracy
• Produces smallest version of most accurate subtree.
• Requires that a lot of data be available.

7.1.3 Rule Post-Pruning

• Infer tree as well as possible.
• Convert tree to equivalent set of rules.
• Prune each rule by removing any preconditions that result in improving its estimated accuracy.
• Sort final rules by their estimated accuracy and consider them in this sequence when classifying.
• The tree on the left becomes the set of rules: IF $(Outlook=Sunny) \wedge (Humidity=High)$ THEN $PlayTennis=No$ IF $(Outlook=Sunny) \wedge (Humidity=Normal)$ THEN $PlayTennis=Yes$ IF $(Outlook=Overcast)$ THEN $PlayTennis=No$ ...and so on

7.2 Continuous-Valued Attributes

• For example, we might have a Temperature attribute with a continuous value.
• Create a new boolean attribute that is true when the value is less than $c$ (the threshold).
• To pick $c$ sort the examples according to the attribute. Identify adjacent examples that differ in their target classification. Generate candidate thresholds at the midpoints.
• The candidate thresholds can be evaluated by computing the information gain associate with each one.
• The new discrete-valued attribute can then compete with the other attributes.

7.3 Attributes with Many Values

• The information gain tends to favor attributes with many values.
• One approach: use $GainRatio$ instead \[GainRatio(S,A) \equiv \frac{Gain(S,A)}{SplitInformation(S,A)} \] \[ SplitInformation(S,A) \equiv - \sum_{i=1}^{c} \frac{|S_{i}|}{|S|} \log_{2} \frac{|S_{i}|}{|S|} \] where $S_{i}$ is subset of $S$ for which $A$ has value $v_{i}$
• The $SplitInformation$ term discourages the selection of attributes with many uniformly distributed values.

7.4 Unknown Attribute Values

• What if some examples are missing values of some $A$?
• Use training example anyway, sort through tree:
• If node $n$ tests $A$, assign most common value of $A$ among other examples sorted to node $n$, or
• assign most common value of $A$ among other examples with same target value, or
• assign fraction $p_{i}$ of example to each descendant in tree.
• Classify new examples in same fashion

7.5 Attributes With Costs

• For example, in the medical field applying a test costs money, in a robotic setting applying a test takes time and power.
• How do we learn a tree that also minimizes cost?
• Replace gain by \[ \frac{Gain^{2}(S,A)}{Cost(A)}. \] or by \[ \frac{2^{Gain(S,A)} - 1}{(Cost(A) + 1)^{w}} \] where $w \in [0,1]$ determines importance of cost
• Machine Learning book at Amazon, http://www.amazon.com/exec/obidos/ASIN/0070428077/multiagentcom/
• Slides by Tom Mitchell on Machine Learning, http://www-2.cs.cmu.edu/~tom/mlbook-chapter-slides.html
• Wikipedia definition of Occams Razor, http://www.wikipedia.org/wiki/Occam%27s_Razor
• C4.5 source code page, http://www.cse.unsw.edu.au/~quinlan/

This talk available at http://jmvidal.cse.sc.edu/talks/decisiontrees/ Copyright © 2009 José M. Vidal . All rights reserved.

22 January 2003, 07:51AM

Machine Learning

Artificial Intelligence

Control System

Supervised Learning

Classification, miscellaneous, related tutorials.

Interview Questions

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Cloud Computing

Data Science

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Data Mining

Data Warehouse

Proceedings of the Future Technologies Conference

FTC 2021: Proceedings of the Future Technologies Conference (FTC) 2021, Volume 1 pp 599–615 Cite as

In Search of Machine Learning Theory

• Eugene Eberbach 10 &
• Dominik Strzalka 11  
• Conference paper
• First Online: 24 October 2021

1144 Accesses

1 Citations

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 358))

Machine Learning (ML) and Artificial Intelligence (AI), in general, are based on search algorithms. In this paper, we use paradoxically the same search techniques again to look for the general theory of machine learning itself. In other words, we search for a unifying machine learning theory. For this purpose, we turn out for a help to the general theory of computation, called $-calculus, that is based on meta-search and super-turing/hypercomputational models. We hope that in such a way, we can unify machine learning and this should be useful in the development of new methods, algorithms, embedded devices and computer programs in the future. Firstly, we overview main machine learning areas as our training examples, and by applying our background knowledge we hand pick-up a hypothetical reasonable theory of ML. Next, we justify that this is a good generalization of ML. The open research question remains whether by applying various ML techniques we can induce automatically the optimal ML theory from the hypothesis space of possible theories. Thus, hopefully, the follow-up paper would be titled “In search of the optimal machine learning theory”.

The 1st author is a retired Professor of Practice, RPI Hartford, CT. This paper was written in memory of my friend Professor Houman Younessi from RPI Hartford. The work of 2nd author has been financed by Polish Ministry of Science and Higher Education under the program “Regional Initiative of Excellence” in 2019–2022, project number 027/RID/2018/19.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Burgin, M.: Super-Recursive Algorithms. Springer, Heidelberg (2005)

MATH   Google Scholar  

Burgin, M., Eberbach, E.: Evolutionary automata: expressiveness and convergence of evolutionary computation. Comput. J. 55 (9), 1023–1029 (2012)

Article   Google Scholar  

Eberbach, E.: Approximate reasoning in the algebra of bounded rational agents. Intern. J. Approx. Reasoning 49 (2), 316–330 (2008)

Article   MathSciNet   Google Scholar  

Eberbach, E.: The $-Calculus process algebra for problem solving: a paradigmatic shift in handling hard computational problems. Theoret. Comput. Sci. 383 (2–3), 200–243 (2007)

Eberbach, E.: $-Calculus of bounded rational agents: flexible optimization as search under bounded resources in interactive systems. Fund. Inform. 68 (1–2), 47–102 (2005)

MathSciNet   MATH   Google Scholar  

Eberbach, E., Goldin, D., Wegner, P.: Turing’s ideas and models of computation. In: Teuscher, C. (ed.) Alan Turing: Life and Legacy of a Great Thinker, pp. 159–194. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-662-05642-4_7

Eberbach, E.: Toward a theory of evolutionary computation. BioSystems 82 (1), 1–19 (2005)

Garzon, M.: Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks. Springer, Heidelberg (1995)

Book   Google Scholar  

Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. The MIT Press, Cambridge (2016)

Haykin, S.: Neural Networks: A Comprehensive Foundation. Macmillan College Publishing, New York (1994)

Hertz, J., Krogh, A., Palmer, R.G.: Introduction to the Theory of Neural Computation. Addison-Wesley, Redwood City (1991)

Google Scholar  

Kearns, M.J., Vazirani, U.M.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)

Michalewicz, Z., Fogel, D.B.: How to Solve It: Modern Heuristics, 2nd edition, Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-662-07807-5

Motooka, T., Kitsuregawa, M.: The Fifth Generation Computer: The Japanese Challenge. Wiley, New York (1984)

Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice-Hall, Hoboken (2010)

Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (1999)

Siegelmann, H.T.: Neural Networks and Analog Computation: Beyond the Turing Limit. Birkhauser (1999)

Turing, A.: Intelligent machinery, 1948. In: Ince, D.C. (ed.) Collected Works of A.M. Turing: Mechanical Intelligence (1992)

Vapnik, V.: Statistical Learning Theory (1998)

Deisenroth, M.P., Faisal, A.A., Ong, C.S.: Mathematics for Machine Learning, Cambridge University Press, Cambridge (2020)

Kleinberg, J., Tardos, E.: Algorithm Design. Pearson/Addison Wesley, New York (2006)

Gödel, K.: Uber formal unentscheidbare Satze der Principia Mathematica und verwander Systeme. Monatschefte fur Mathematik und Physik 38 , 173–198 (1931)

Download references

Author information

Authors and affiliations.

Rensselaer Polytechnic Institute, Hartford, CT, USA

Eugene Eberbach

Rzeszów University of Technology, Rzeszów, Poland

Dominik Strzalka

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Eugene Eberbach .

Editor information

Editors and affiliations.

Faculty of Science and Engineering, Saga University, Saga, Japan

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Eberbach, E., Strzalka, D. (2022). In Search of Machine Learning Theory. In: Arai, K. (eds) Proceedings of the Future Technologies Conference (FTC) 2021, Volume 1. FTC 2021. Lecture Notes in Networks and Systems, vol 358. Springer, Cham. https://doi.org/10.1007/978-3-030-89906-6_40

Download citation

DOI : https://doi.org/10.1007/978-3-030-89906-6_40

Published : 24 October 2021

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-89905-9

Online ISBN : 978-3-030-89906-6

eBook Packages : Intelligent Technologies and Robotics Intelligent Technologies and Robotics (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research