# Questions tagged [machine-learning]

Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference

293 questions
Filter by
Sorted by
Tagged with
169 views

### Doubt in John Langford's “Tutorial on Practical Prediction Theory for Classiﬁcation” paper

I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion. The paper says that binomial tail inversion is the ...
59 views

### How to define the _regret_ in multiagent systems? Any good definition please?

I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent ...
263 views

### What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = (YY^T)^½Y$...
165 views

### How useful is program search in the field of programming-language theory?

I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter ...
237 views

### Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
418 views

### Is testing easier/harder than learning?

How is the Property testing is related to PAC model of learning? More precisely, Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which ...
376 views

### Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
384 views

### Representation of procedural knowledge

I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system. Can a network of procedural knowledge also be created ...
3k views

### When to use the Johnson-Lindenstrauss lemma over SVD?

The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to ...
222 views

### How to deal with concept classes with exponential value of VC dimension

Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how ...
180 views

### Is this variant of PAC learning known?

Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has ...
714 views

### Objective function for stochastic optimization

Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
180 views