Skip to main content
Share Your Experience: Take the 2024 Developer Survey
2 votes

Learning positive half-lines (in $\mathbb{N}$)

Yes, it's trivial. The learning algorithm consists of choosing the smallest positive example $x_0$, and taking the hypothesis to be $h(x)=1[x\ge x_0]$. All of the generalization guarantees proved for $...
Aryeh's user avatar
  • 10.6k
2 votes
Accepted

What is the current state of the art on exact identification of DFAs with a maximum N states

The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in ...
EXPTIME-complete's user avatar
2 votes

What is the current state of the art in black-box grammar induction?

Note that there is now a replication study (coauthored by Rahul Gopinath) of the 2017 paper Synthesizing Program Input Grammars, see https://publications.cispa.saarland/3607/1/pldi2022glade.pdf Two ...
Martin Berger's user avatar
1 vote

What is the intution on the TTT algorithm for regular grammar inference?

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the ...
Coping Forever's user avatar
1 vote
Accepted

An upper bound of pseudo-/VC-dimension

Consider two real-valued function classes, $\mathcal{F}_1$ acting on some set $\mathcal{X}_1$ and $\mathcal{F}_2$ acting on some set $\mathcal{X}_2$. I am going to bound the Pdim of $\mathcal{F}_3$ ...
Aryeh's user avatar
  • 10.6k
1 vote
Accepted

Learning arithmetic series

An arithmetic series is defined by the 1st term $t_1$ and the difference between terms $d$. If you stipulate that $\max(|t_1|,d)\le M$ then you have a finite hypothesis space and hence a finite ...
Aryeh's user avatar
  • 10.6k
1 vote

Information Bottleneck - Calculating the Mutual information between the Labels and the Features

This is only a partial answer. I might update it if I decide to look at the implementation. I understand this as being fixed network layers that don't get updated in training. Am I mistaken? Note ...
Nichlas L.R's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible