Learnable: Theory vs Applications
Marina Sapir


Neural sentence embedding using only in-domain sentences for out-of-domain sentence detection in dialog systems
    [
    December 30, 2023
===============================================================================================================




Two different views on machine learning problem: Applied learning (machine learning with business applications)  and Agnostic PAC learning are formalized and compared here.  I show that, under some conditions, the theory of PAC Learnable provides a way to solve the Applied learning problem. However, the theory requires to have the training sets so large, that it would make the learning practically useless. I suggest to shed some theoretical misconceptions about learning to make the theory more aligned with the needs and experience of practitioners.







§ INTRODUCTION



Machine learning includes a practical side as well as a theoretical side. Practitioners solve real life problems, theoreticians study theory of learning. Practitioners need help answering the questions the life poses. Theoreticians give the  answers. Unfortunately, they are, apparently,  answering different questions, about some-what different subjects. For example, practitioners deal with limited data and deadlines, while the theory talks about  what happens  when  training data increase indefinitely. There appears to be some disconnect here.

More the over, the practitioners often can not formulate their questions exactly,  because  the language of the existing theory  was developed by theoreticians to  study different issues and different situations.

Here I formulate the learning problem as it is encountered in practical applications, pose the related real life  questions and show the answers to these questions which follow from PAC learnable theory. To do it, I express both  questions of practitioners and the results of the PAC learnable theory in terms of problem solving.





§ PRACTICAL POINT OF VIEW




What is machine learning, practically speaking? Let us look  on the typical situation when such a problem arises.



 §.§ Business learning scenario



Machine learning is used when a business wants to model a relationship between some observed properties  and a hidden property of   objects of interest.

For example, a business may want to know which patients will be responsive to certain therapy based on their test results, or which engines require certain repairs based on the sensors data, which clients will default on loans and so on. If the business learns to predict the hidden property most of times, it can help with decision making about clients, patients or engines.

Often, this prediction is part of the company's product, and it  is used for decision making  outside of the company. For example, a doctor will use recommendations to prescribe the drug, and a mechanic will use the suggested diagnostics for engine repairs.


 To do the modeling,  the company would have accumulated data about both observed and the hidden properties of a limited set of such objects.  One way to proceed would be to have so many examples that any new example would be the same or very similar to the ones already known. Most of times, it is impossible: there are not enough patients, clients or engines in the world for that. Any way, the cost of gathering huge amounts of data about real life objects is, usually,  prohibitive.  It is exactly what makes application of  machine learning attractive. Machine learning, as any data modeling, is used to compensate for insufficient knowledge which can be gained form experience.


 There is common understanding that the observed features and the hidden property are affected by unknown, random, unaccountable factors. It means, the company has reasonably limited expectations for the accuracy of the prediction.

In a typical scenario, when a business encounters the research problem  requiring prediction of a hidden property, it supplies its machine learning scientists with the precious (but not precise) accumulated data on the observed and hidden properties of the objects, the threshold  of an admissible error rate, as well as a deadline.



 §.§ Definition of the Applied learning problem



Since classical theory of learning deals with binary classifications, let us give an exact definition of a learning problem for a case of binary classification as it is encountered in real life.

[Applied Learning  ]
Given: a threshold ϵ∈ (0,1) and a random  sample of m i.i.d. pairs S_D = {( x_i, y_i ),   x_i ∈χ,   y_i ∈γ = {0, 1}, i = [m]} generated  by unknown probability distribution D on χ×γ; To find:  a function h: χ→γ such that

    L_D(h) = P_(x,y) ∼ D [h(x) ≠ y]    ≤ϵ
.



The given random sample S  is called training set.
An instance of the AL problem with the threshold ϵ and the training set S generated by a distribution D will be denoted by (ϵ, S)_D.

The elements from χ are called “points”; the elements from γ “labels”.  The training set is, usually,  interpreted as past knowledge. The output function h: χ→γ is said to “predict” labels y given points x of the pairs (x, y).

The function L_D(h), the  probability that the function h incorrectly predicts a label, is called “generalization error”.

The output h with  generalization error below ϵ is the “solution” of (ϵ, S)_D, or h  (ϵ, S)_D.

 The procedure which defines a function χ→γ given the instance of the problem is called “learner”.  If, for a learner Δ, Δ(S)  (ϵ, S)_D the learner Δ succeeds on the  (ϵ, S)_D, otherwise it fails on this instance of the problem. The instance  (ϵ, S)_D is soluble, if there exists a learner Δ such that
 Δ(S)  (ϵ, S)_D.

The critical questions machine learning scientists will need to answer are:



    
  * Is given instance of the problem soluble?
    
  * How to find a solution? What may be the best approach for the given data?
    
  * How to verify the found function?





 §.§ Main Challenges of Learning


To understand the main challenges of learning we may look at the relationship between the Applied learning and a decidable computational problem.

 A computational problem is a   function  f: X → Y,  defined in a user-friendly language.

For example, “Given a Boolean formula x, to find  a combination y of values of its variables such that x(y) = 1”, or “Given a weighted graph  and two of its vertices x = ⟨ G, A, B ⟩, to find a shortest path y between A, B on G.”

If the problem is “decidable”, there is a procedure, which outputs f(x) given x ∈ X.  More the over,  an intended user of the problem's definition can reproduce this procedure. The goal is, usually, to develop an algorithm which does the same computation efficiently.

 In a learning problem, the function y= f(x) is represented by a  sequence  of its inputs and outputs S = {(x_i, y_i)}, with the similar goal to produce the procedure  which outputs f(x) on each instance x ∈ X.

Since the   function is not defined on its whole domain, there is no way of testing if, for some new input,  the predicted output is “correct”. More the over, while a computational problem defines a deterministic function, the relationship between inputs x and outputs y in the learning problem is a random function. An input x may have different outputs, each with its own probability.

Summarizing,   there are three major specific challenges presented by learning:


    
  * Uncertainty of  labels. If the distribution D is arbitrary, there is no way to predict the labels even  on the points X_S = {x_i, i = [m]} of the  training set.

    
  * Unpredictability. There is nothing in the conditions of the problem which would allow one to predict the labels on the points x ∈χ∖ X_S, even if one believes that the labels on the points of the training set have no uncertainty.

    
  * Unspecified Verification.  The problem does not supply a way to confirm that any function is the solution.


The challenges make the Applied learning problem not just ill posed, but somewhat incongruous. Generally speaking, the inputs have no bearing on the output, as in the famous problem by Good Soldier Shvejk (as I recall it): “the house has 2 floors, there are 6 windows on each floor; what is the name of my grandmother? ”


Each of these challenges is a serious, unavoidable issue in practical applications.


 Take, for example, the uncertainly of labels. Since many factors affecting the labels are unknown and not reflected in the descriptions x, the relationship between x and y are not deterministic. The level of uncertainty is impossible to evaluate  if the domain X is infinite: the training set's point are all different, usually.

To appreciate the difficulty the  labels uncertainty brings among other issues, let us consider a vastly simplified Toy problem where two other issues are irrelevant.

[Toy]
Input: The domain χ contains m points χ = {x_i}, i = [m]. The marginal distribution D_χ is uniform, and for every there exists q, 0 < q < 0.5 such that x_i,     D(x_i, 0) = q or D(x_i, 1) = q.
Any training set  S has m instances, with all the points of the domain χ.
Output:  a function  h: χ→γ such that

    L_D(h) = P_(x,y) ∼ D [h(x) ≠ y]    ≤ϵ
.


The Toy problem is a specific case of the Applied learning problem.  Each settings (m, q, ϵ) describe a collection of 2^m instances of the problem with different training sets.

In each instance of the Toy problem, the points of a training set cover whole domain χ, so one does not have to worry about unpredictability outside of the training set or the validation.

If ϵ < q, no solution of the Toy problem is possible.

If ϵ > q, there is a trivial solution: the function 
    h^'(x) = arg   max_(0,1) (D(x, 0), D(x, 1) ).

The function h^' has generalization error q, which satisfies the goal. The solution does not depend on the training set.

Yet, every learner fails on some training sets.


 There are settings of the Toy problem where the solution exists, but  any learner fails on at least 20% of training sets.



For each instance of the Toy problem, a “trivial learner” t is equivalent to its training set:   h_S^t: h_S^t(x_i) = y_i, i = [m], or h_S^t = S.




Let us notice that a training set S   splits domain χ on two parts: χ  = X_1 ⋃ X_2, such that if x_i ∈ X_1,   D(x_i, y_i) = 1 - q, and if x_i ∈ X_2,   D(x_i, y_i) = q. It is convenient to call the points X_1 “straight”, because they have the most likely labels in the training set, and the points in the part X_2 will be called “flipped”.

The probability z(k, m)  that the training set has exactly k > 0 flipped points out of m can be calculated by the Bernoulli formula: z(k, m) = C_m^k · p^k · q^m-k. The probability z(0, m) that there are no flipped points in the training set is t = q^m. The probability G that there is not more than ϵ of flipped points in the training set can be calculated by the formula

    G  = ∑_0^ϵ× mz(i, m).
 For  m = 50,   q = 0.1,  ϵ = 0.12. the calculations yield G = 0.77, G < 0.8. So, for a trivial learner, probability of success is less than 80%.

If the learner is not trivial, it changes some labels on the training set to produce the hypothesis. Since there is no way to know which points are straight,  it will change labels randomly on some straight points and some flipped. Changing labels on straight points increases error of the hypothesis, changing labels on flipped points decreases error of the hypothesis comparing with the trivial learner. For the settings m = 50,   q = 0.1,  ϵ = 0.12   there expected to be much more straight points (9 times more) than flipped points, the  expected number of changing labels  on straight points will be proportionally higher than the number of changed labels on flipped points. Then the expected number of errors of a hypothesis of the non-trivial learner will be higher than for the trivial learner.



It is obvious that the issue with Applied learning is that there is too much uncertainty in the problem. On another hand, many practical machine learning problems were solved. It means, there are commonly occurring situations when the problem is soluble.  To find the general approach to the learning problem, the problem needs to be reformulated with additional, natural constrains on input data and on on solutions. One path to reformulate the problem is explored in PAC learnable theory.



§ THEORETICAL APPROACH TO LEARNING


The main idea of learning in theory <cit.> is to
minimize generalization errors  to within arbitrary precision based only on a finite training set as the size of  the given training set tends to infinity. (The idea that the training set increases indefinitely sounds very theoretical.)



 §.§ The main concepts and results of PAC learning


Even though the theory of learning does not have an exact definition of the learning problem, there is the concept of “learnable”, which I will use to formulate the learning problem.


A function class H is agnostic PAC learnable if there exists a function m_H: (0,1)^2 → N and a learner Δ_H with the following property: For every ϵ, δ∈ (0,1), and for every distribution D over χ×γ, when running the learner Δ_H on m ≥ m_H(ϵ, δ) i.i.d. instances generated by D, it outputs a function h ∈ H such that, with probability of at least 1 - δ (over the choice of the training examples),

    L_D(h) ≤min_h^'∈ H L_D(h^') + ϵ.





The concept implies that “learning” means solving the next problem:


 [Agnostic PAC Learning] Given are: class of functions H: χ→γ, two numbers ϵ, δ∈ (0,1). To find: a learner  which,  for every large enough  randomly generated sequence of i.i.d. pairs S ∈  (χ×γ)^* from an arbitrary random distribution D on χ×γ,   finds a function h ∈ H such that 
    L_D(h) ≤min_h^'∈ H L_D(h^') + ϵ
 with probability of at least 1 - δ.



The learner, which solves the Agnostic PAC learning problem for the class H is called the successful learner of the class H. The number m_H(ϵ, δ)  of instances sufficient for probably approximately correct learning for the given ϵ, δ is the property of the  Agnostic PAC learnable class H. It can be  called a (ϵ, δ)-saturation point for the class H.




The differences between the Agnostic PAC learning problem and the Applied learning problem are summarized in the Table  <ref>.





In general, the problems are not comparable.

For example, a learner finding solution h ∈ H on the instance (ϵ, S)_D of Applied learning problem may not be a successful PAC learner for the class H if it does not work on many other distributions, regardless how large the training set is.

On another hand, a successful PAC learner for a class H may not produce a solution for the instance (ϵ, S)_D of Applied learning problem even if it has a  solution in the class H, if the size of the training set S is below the (ϵ, δ)-saturation point for the given class H  for a  small enough δ.


The main idea of Agnostic PAC learning  is to identify the classes of functions, where large enough training sets allow to approximate the function on whole domain reliably, regardless of distribution.  The “uniform convergence” property  defines such classes.

 A hypothesis class H has the uniform convergence property if for every ϵ, δ∈ (0, 1) there exists M such that for every probability distribution D  over χ×γ, if the sequence of i.i.d. pairs S ∈ (χ×γ)^*,   S ∼ D has the length over M then then with probability at least 1- δ  S satisfies the condition:  for every h ∈ H

    | L_S(h) - L_D(h) | ≤ϵ  .




In the definition, the threshold M depends only on ϵ, δ, and the class H. The definition implies that the class H with uniform convergence can be characterized by its function M = m^u_H(ϵ, δ).

 The  results of PAC Learnable theory are neatly summarized in The Fundamental Theorem of Statistical Learning (<cit.>, p48).


The next conditions are equivalent:


  * H is agnostic PAC learnable;

  * H has property of uniform convergence.

  * Any empiric risk minimizer on H is a successful PAC  learner for this class;

  * H has finite VC-dimension.



The empirical risk in the theorem refers to average of errors of a hypothesis on the training set: L(h, S)= ∑( |h(x_i) - y_i| ) / m .

The term “empiric risk minimizer on H”  in the theorem refers to a procedure which, given a training set S   finds a function  h ∈ H minimizing the empiric risk. It is convenient to denote ERM_H(S) a hypothesis obtained by an empiric risk minimizer in a class H on the training set S.



 §.§ Implications for Applied Learning


The next theorem shows how and when this theory can help to solve the Applied learning problem.

 


Suppose, an instance  (ϵ, S)_D, of the Applied learning problem satisfies
   
    |S| >   max( m_H^u(ϵ /2 , δ), m_H(ϵ /2 , δ))
  for a class H with finite VC-dimension and 0 < δ < 1.


Then, for h = ERM_H(S),  if L_S( h ) ≤ϵ / 2, h is the solution for (ϵ, S)_D with probability at least 1 - δ.  If L_S(h) > 2 ϵ the instance does not have a solution within class H.




According to the Fundamental theorem, the class H has uniform convergence and is agnostic PAC learnable.

Since |S| >  m_H^u(ϵ /2, δ),   the uniform convergence implies that for any hypothesis h ∈ H, | L_S(h) - L_D(h) | ≤ϵ /2. If L_S(h) ≤ϵ / 2, then L_D(h) < ϵ  with probability at least 1 - δ. It means, h is a solution of the (ϵ, S)_D with probability at least 1 - δ.


Suppose, L_S(h) >  2 ϵ. By the property of uniform convergence  then L_D(h)  >  1.5 ϵ.
By the property of PAC learnable L_D(h) - min_H( L_D(h') ) < ϵ / 2. Then min_H(L_D(h')) > ϵ. Therefore, the instance (ϵ, S_D) does not have a solution in H.



In the conditions of the Theorem <ref>, we can answer all the critical questions in relation to the class H:


    
  * Does the instance (ϵ, S)_D of the problem have a solution in class H? It does, if the empiric risk minimizer has the empiric risk below ϵ / 2. It does not,  if the empiric risk is above 2 ϵ.
    
  * What is the best approach to solve the problem? Applying any empiric risk minimizer.
    
  * How to verify the solution? There is not need to verify it  if empiric risk is below ϵ /2 and the probability of not finding a solution  δ is small enough.




But how often do Applied problems satisfy the requirement on the size of the training set  in the Theorem  <ref>?

There is the estimate of the saturation points  in <cit.>, p 341.  The table  <ref> shows the estimates of saturation point depending on the thresholds ϵ, δ and the VC dimension of H.




To anybody familiar with real life applied problems these estimates look very wrong, excessive. For comparison, the table  <ref> shows sizes of the classification problems with not more than 4 classes among the most popular problems in UCI Machine Learning Repository.




The comparison between the tables  <ref> and  <ref> gives a hint  on why the theory is never used in the applications. The theory can be applied only in the cases, when the function we are trying to approximate is assumed to have low variability and known on so many points, that we already know  (almost) everything there is to know. The issue is, in this case there is no need in machine learning.





§ CONCLUSIONS


The learning problem presents formidable challenges with too much uncertainly,  unknowable and unverifiable. The only way to find some solution is to narrow the search, impose some restrictions on solutions.

The theory of PAC learnable explores searching for a solution (1) within classes of function with limited complexity (finite VC dimension) , and (2) with huge training sets.

Imposing these requirements reduces the uncertainty of a problem to such a degree that the problem can be either solved  with a simple function approximation algorithm, or it can be shown not to have  a solution within the given class of functions.

However, these requirements are virtually never satisfied in applications, because they would contradict the goal of learning: to compensate for  deficiency of accumulated data.

The theory does not help to solve the real life problems, and it does not explain, why so many machine learning tasks with relatively small training sets are being solved successfully. It does not explain why so many algorithms developed specifically for machine learning work, when empiric risk minimization does not.

Perhaps, there shall  be another theory which allies better with machine learning practitioners' experience and needs.

And here is what I would expect from this theory of practical machine learning :


  * The concept of learning process shall not involve indefinite increase in the training set size, nor  an indefinite improvements in accuracy.  Neither is possible or desirable in applications. Learning is one time event with the specific distribution, training set, and desired accuracy.

  * The concept of  learning shall not involve the idea that we need to evaluate generalization error based on the error on the training set. In real life, people use the set aside data for that.

  * The concept of a learning process shall include the set aside data as its integral part.

  * The study of learning shall find desirable properties of distributions which make real life learning possible.

  * Perhaps, the study of learning can find some desirable properties of the training sets, besides their size.

  * The popular machine learning algorithms (such as Naive Bayes, SVM, kNN)  can be used as case studies to demonstrate that the tasks with desirable properties can be solved by  most of them.





authordate1


