Questions tagged [statistics]
The statistics tag has no usage guidance.
136
questions
1
vote
0answers
62 views
Hoeffding's inequality applicability for sample complexity
I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
1
vote
0answers
18 views
Computational complexity of median filter in image processing
I found this paper http://nomis80.org/ctmf.pdf, that describes an efficient algorithm for applying a median filter to an image. Though this works for non-HDR images, I am not sure how well it scales ...
4
votes
2answers
821 views
What empirical evidence do we have for or against a correlation between fault density and LOC?
LOC = lines of code
KLOC = Thousand lines of code
Fault (or defect) density = number of reported bugs per line of code.
Software artifact = function, class, module
Reading research papers on fault ...
0
votes
1answer
30 views
Efficient random sampling from large discrete distribution
I have a random variable $X$ that can take finite values in $\{X_1, ..., X_n\}$ with probabilities $\{p_1,..., p_n\}$. Is there a computationally efficient way to sample a number from this set? My ...
1
vote
0answers
11 views
Distributed Graph Consensus to fit a distribution?
$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance.
The objective is for ...
1
vote
0answers
15 views
Distribution independence property testing
I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
1
vote
2answers
66 views
Sliding window max/min algorithm without dynamic allocations
I'm working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, RMS, min, max, median, etc) on streams of floating-point samples. For ...
0
votes
0answers
22 views
Simple Bayesian Question
I have the following Bayesian Network.
I have worked out the following:
P(H) = P(H|D) + P(H|¬D) = 0.5 + 0.1 = 0.6
P(D|H) = (D)∗(P(H|D) +P(H|¬D)) = 0.3∗(0.5 + 0.1) = 0.18
How do I compute the ...
1
vote
1answer
47 views
EM algorithm - What happens with the standard deviation?
What have you tried?
So I watched this video.
According to the video, we've to calculate the variance $\sigma^2$ as follows:
$$
\sigma_{k}^{2} =
\frac
{
p_{1} \left(x_{1} -...
0
votes
1answer
38 views
PCA applicability
I understand that PCA takes a data set with input size, with output labels, and reduces the inputs to a set of principal components size r, where r < n.
My question is whether or not this can be ...
0
votes
0answers
51 views
Most popular path in weighted cylic directed graph
Context
I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
1
vote
1answer
161 views
Approximate max weight path in directed graph
Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
0
votes
1answer
120 views
Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not
This is what do I have to solve:
Byron Book: Exercise 8.3 chapter 8
Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population
mean is indeed 48.2333 and the ...
2
votes
0answers
21 views
Separating labelled points with a plane, minimizing label variance
Suppose we have observations with associated labels $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$.
Can we efficiently ...
1
vote
0answers
13 views
Tracking approximate values of specific percentiles
At the moment I use HdrHistogram to track approximate distribution of a stream of values. But I don't really need all percentiles, just three of them. Is there some algorithm to track specific ...
1
vote
0answers
34 views
Differential Privacy with only positive noise
The Laplace mechanism is a standard way of making the output of a function $f$ differentially private.
More concretely, let $\Delta_f$ be the sensitivity of $f$, i.e. the maximum value by which the ...
0
votes
1answer
40 views
How to implement conditional probability distribution on set-valued Random Variables
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
2
votes
1answer
39 views
Averaging a list of variances
In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. ...
2
votes
1answer
55 views
Is this statistical group summation unambiguously reversible?
Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation:
$A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$...
2
votes
0answers
24 views
Algorithm to mapping given probabilities to empirical probabilities
Consider following problem statement:
You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
0
votes
1answer
95 views
Find the average number of steps to sort an array by randomly selecting two elements
I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then ...
1
vote
1answer
19 views
SGD statistical guarantee
I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value?
Thank you ...
0
votes
0answers
30 views
How to handle distribution of values with same attributes into different classes
I'm a student studying a data mining course and have come across a problem.
I need to explain the problem with the help of an example scenario as I do not know how to explain the problem in any other ...
1
vote
1answer
48 views
Chebyshev inequality comparison
Given $n$ distinct values $(x_i)_{i=1}^{n}$ with mean $\mu$ and standard deviation $s$, for all $i$, we have $|x_i−\mu| ≤ s \sqrt{n − 1}$.
How does this inequality compare with Chebyshev inequality as ...
1
vote
1answer
414 views
Efficiently selecting a random subset of size $m$ from a set of size $n$
This is a cross post of my question here on math.se.
I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all ...
2
votes
0answers
48 views
In a machine learning system, why use differentially private SGD if our input data is already perturbed by a DP mechanism?
I'm trying to implement my own version of a deep neural network with differential privacy to preserve the privacy of the parties involved in the training dataset.
I'm using the method by Abadi et al. ...
0
votes
1answer
39 views
Gaussian distribution with condition?
What does this expression mean?
Normal distribution with condition
I am reading a research paper and found the following expression (Eq.28 in the paper below).
It means a Gaussian distribution, but ...
1
vote
2answers
66 views
Algorithm for Estimating Number of Unique Monthly Visitors
Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
6
votes
1answer
910 views
What is the optimal algorithm for playing the hangman word game?
Suppose we are playing the game hangman. My opponent and I both have access to the dictionary during the game. My opponent picks a word from the dictionary with knowledge of the algorithm which I will ...
1
vote
1answer
38 views
Minimizing Trimmed Distances
I'm trying to understand what is the minimum of the following function,
$$
f(\mu) = \frac{1}{n}\sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) (x_i - \mu )^2
$$
where $F$ is a step function that assign $...
0
votes
0answers
32 views
Does this problem have a formal name?
I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
0
votes
0answers
50 views
How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points
I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
1
vote
1answer
169 views
Amount of expected loop iterations when searching an array by random index
Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n
If we have a search algorithm like ...
0
votes
0answers
16 views
Kullback-Liebler Divergence
For $P(x)=N(\mu,\sigma^2)$ and $Q(x)=N(0,1)$ I am supposed to calculate $KL(P(x)||Q(x))$, here is what I did
\begin{align*}
KL(P(x)||Q(x)) & = \int P(x) \cdot \log\left(\frac{P(x)}{Q(x)}\...
3
votes
1answer
165 views
Measures of performance in machine learning
I'm new to machine learning and struggle to interpret the results I get from different measures of performance. If for several prediction models I have e.g. accuracy, precision, recall, F1, FPR, and ...
1
vote
0answers
80 views
Suggestion for a good statistics book for computer scientists, in preparation of machine learning
We (a group of CS postdocs and Ph.D. students) are starting a shared reading of a machine learning book ("An Introduction to Statistical Learning", James, Witten, Hastie, Tibshirani).
Before diving ...
2
votes
0answers
46 views
The No-Free-Lunch Theorem and K-NN consistency
In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large ...
3
votes
0answers
31 views
What is the purpose of standardization in machine learning?
I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying
When ...
3
votes
1answer
57 views
Estimation of the number of solutions by Counting
This is a question from a quantum computation textbook.
Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
0
votes
0answers
57 views
What kind of standard deviation must be used in optimization algorithms?
I would like to ask about the standard deviation of objective function value.
There are two types of standard deviations:
Population standard deviation
Sample standard deviation
In metaheuristic ...
0
votes
1answer
31 views
Assumption of a generation of the dataset by a probability distribution
Consider the following paragraph from the deeplearningbook
The training and test data are generated by a probability distribution
over datasets called the data-generating process. We typically ...
0
votes
1answer
88 views
How can we get small test error reducing only train error?
My question is about mathematical part of machine learning algorithms, especially about using it in neural networks. We train network reducing train error and I was thinking about how then test error ...
3
votes
3answers
118 views
How good (or bad) is my makeshift PRNG?
Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
1
vote
0answers
33 views
How to go about designing a quiz that changes difficulty based on user performance?
I thought about using a machine learning algorithm to learn the performance patterns of the quiz taker and model the next quiz based on how he/she performed. So each question will have a difficulty ...
2
votes
2answers
71 views
identify abrupt frame changes in a video
The frames of live streams or videos, in general, do not flow smoothly. A sports game would have multiple cameras recording the game and hence, there will be camera switches in the stream. I am ...
1
vote
2answers
307 views
probability of collision
my data's range is from 1 to 9 and I have two subsets of integers from this range.
the hash function takes each of this subsets and calculate product of these three integers and maps this set to the ...
0
votes
0answers
44 views
Optimize Algorithm For Shut in Box Game
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices.
Each round, the player rolls the 2 dices and their sum is S.
...
1
vote
1answer
642 views
Is there a fast algorithm for computing the rolling mode of an array of integers?
I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers.
By rolling mode I mean that we have an array of integers of size $n$ and a sliding ...
2
votes
1answer
2k views
Median of two sorted arrays of different size in logarithmic time?
The solution given in Cormen is as follows:
Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary ...
0
votes
0answers
30 views
Locality sensitive hashing with non-scalal values
Locality sensitive hashing works well when matching is between vectors of scalars, but I now need to extend LSH to compare matrices. Each matrix is formed of n readings from m sensors forming a n by m ...