Skip to main content
11 votes
Accepted

Showing that Bayes classifier is optimal

The true error of a classifier $h$ is $$ \begin{align*} L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \begin{cases} \Pr[y \neq 0|...
Yuval Filmus's user avatar
10 votes
Accepted

How best to statistically verify random numbers?

You can't. Randomness is a property of the source, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some ...
D.W.'s user avatar
  • 161k
6 votes
Accepted

Is there a fast algorithm for computing the rolling mode of an array of integers?

Maintain two data structures as you move along. A hash $H$ table of frequencies. An array of sets $A$ containing the integers in each frequency. So $A[1]$ is the set of all integers that occur once ...
orlp's user avatar
  • 13.6k
5 votes
Accepted

How good (or bad) is my makeshift PRNG?

There is no such test. All automated tests for examining the randomness of a PRNG have limitations. If you read some papers in the literature that propose PRNGs, you might notice that they do more ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Hash multiple integers directly using FNV-1a

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing. The core step that offers mixing of the bits is multiplication by ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Is it okay to select the best performers of test cases for scientific publication in neural network machine learning

No. You must use the test set only once. Otherwise your result will not be representative of the true performance of your scheme. That's bad. Instead, use the validation set for checking the ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Median of two sorted arrays of different size in logarithmic time?

Given two sorted arrays $A[1],\ldots,A[\ell]$ and $B[1],\ldots,B[m]$, the goal is to find the median. Let's assume for simplicity that $n := \ell+m$ is odd, and that all elements are distinct. ...
Yuval Filmus's user avatar
4 votes
Accepted

Measures of performance in machine learning

Precision and recall are the two basic measures and most of the other measures can be written in terms of them. If a model has both better precision and better recall, then it can be seen as strictly ...
Laakeri's user avatar
  • 1,339
3 votes

how to interpret the coefficients of binary logistic regression?

I don't have the rep to comment, but the answer to your question is "sort of." It would take me too long to answer this question completely and with the proper care, so i will point you to a good ...
mm8511's user avatar
  • 206
3 votes

Z-score relations to perceptrons

Why does this help? Part of the reason is because of properties of the activation function. Typically, most activation functions have their most interesting behavior around 0. For instance, the ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Z-score relations to perceptrons

There are two parts to your question that need to be addressed. What transformation are you performing? Why does that help learning? The transformation of taking your input and turning ...
Nicholas Mancuso's user avatar
3 votes

How to calculate IV, EV and optimal k for K-means?

How to get the optimal value for $k$? You have to define a measure for optimiality. The problem with that is that with bigger $k$ most measures become smaller (better). One measure which is ...
Martin Thoma's user avatar
  • 2,360
3 votes
Accepted

How to calculate IV, EV and optimal k for K-means?

$C$ is a cluster, $c$ is centroid, $d$ is provided distance function, $\delta$ is Dirac measure, $x$ is element. $IV = \sum \limits_C \sum \limits_{x \in C} d(x, c)$ meaning for each cluster calculate ...
Evil's user avatar
  • 9,465
3 votes

How good (or bad) is my makeshift PRNG?

If you want just some basic ideas what you might test. The simplest test just generates a million random numbers and puts them into say 100 buckets depending on their value. Each bucket should ...
gnasher729's user avatar
  • 30.5k
3 votes

How can we get small test error reducing only train error?

Well, I have to say that the question is rather complicated. I also spent considerable time investigating this issue. Other SE questions (see here, here and here) are strongly related to this one and ...
neoglez's user avatar
  • 31
3 votes
Accepted

What is the optimal algorithm for playing the hangman word game?

It is possible to compute the optimal strategy, but the computation might be fairly intensive, and I'm not sure whether it will give you much of a gain over simple heuristics. I'll explain how below. ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Efficiently selecting a random subset of size $m$ from a set of size $n$

The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$. If you put $1$ in your ...
Yuval Filmus's user avatar
3 votes
Accepted

Information content of a real number

In some sense I agree that $\mathcal{U}_{[0,1]}$ has "infinite information" but we should be a little more careful formalizing it. As indeed, Shannon entropy is only defined for discrete ...
Benjamin Kuykendall's user avatar
2 votes

Achieving better than the theoretical False Positive Rate for Bloom Filters

Your question includes the equation $$ (1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k} $$ But that is not actually an equation; it is only an approximation.
jbapple's user avatar
  • 3,380
2 votes
Accepted

Least squares fit of a 1D lattice of points to a 2D dataset

Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are. Then, use any standard black-box optimization algorithm (e.g., gradient descent) ...
D.W.'s user avatar
  • 161k
2 votes

Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix

Yes. You can. You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$. Small simplifications. Note that $d$ is ...
D.W.'s user avatar
  • 161k
2 votes

How best to statistically verify random numbers?

The best-effort verification is to estimate min-entropy. There are many, many ways to do that, each having their own pitfalls. One interesting approach is to use algorithms that try to predict the ...
Extrarius's user avatar
  • 771
2 votes

What is the theory behind testing fixes for intermittent bugs?

You juggle with "probabilities" without defining any. There are two different questions here. For practical programs, can I use random testing to establish that any given execution has close to 100%...
Raphael's user avatar
  • 72.6k
2 votes
Accepted

Inequality over the entropy of an integer-valued random variable

Man, that's a nasty inequality. Anyways, given a certain expectation $E[Z]=\mu$, it is known that the distribution that maximizes $H(Z)$ while keeping $E[Z]=\mu$ is the the Geometric Distribution ...
Ran G.'s user avatar
  • 20.7k
2 votes

Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape

Here is a simple algorithm. Suppose that the shape is given by a sequence $$ (x_0,y_0), \ldots, (x_n,y_n). $$ Define $A_i = (x_i - x_{i-1}) \cdot (y_{i-1} + y_i)$ for $1 \leq i \leq n$, and let $A = \...
Yuval Filmus's user avatar
2 votes
Accepted

How to find a possibility of match in Naive Bayes Classifier?

Let $A$ and $O$ be the events apple and orange (fruit). Let $R$ and $S$ be the events red and sphere. By Bayes' law, $$\Pr[A | R \wedge S] = \frac{ \Pr[R \wedge S | A] \Pr[A] }{ \Pr[R \wedge S] };$$ $...
Reinstate Monica's user avatar
2 votes

identify abrupt frame changes in a video

Easiest is to capture video with an h.264 encoder, which uses key frames to identify switches. (It’s a bit more complicated, h264 will handle situations where frames come alternatively fro two ...
gnasher729's user avatar
  • 30.5k
2 votes

How good (or bad) is my makeshift PRNG?

I can't argue with the second paragraph of D.W.'s answer, and D.W. is right that all tests have limitations: That's intrinsic to PRNG-testing. But TestU01 is still pretty much state of the art. You ...
Mars's user avatar
  • 716
2 votes
Accepted

Is this statistical group summation unambiguously reversible?

The answer is no . I found it helpful to think of the information in the form of a picture: mark each pair $(a, b)$ as a point on a grid, then in each column and row write both the count of the ...
Joppy's user avatar
  • 266
2 votes
Accepted

What empirical evidence do we have for or against a correlation between fault density and LOC?

Not an easy question to answer, because LOC can mean many different things: A large function A large class (or module in FP) A large library A large file A large code-base In some of these cases (...
Olle Härstedt's user avatar

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