Questions tagged [statistics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
15 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
12 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
6 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 ...
1
vote
1answer
14 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. ...
1
vote
1answer
43 views

Is this statistical group summation unambiguously reversible?

Given an (unordered) set of 2-tuples (X) of natural numbers (I'm using SQL here for easy reproducibility, and because I don't know better): ...
0
votes
0answers
16 views

what is instrument validation in computer science?

I'm writing an assignment involving some statistics comparing different implementation methods for web applications. I'll be using some downloaded software and web pages I create, on both virtualized ...
1
vote
0answers
18 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
49 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
17 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
27 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
42 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
26 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 ...
1
vote
0answers
35 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
37 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 ...
2
votes
2answers
58 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 ...
5
votes
1answer
188 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
37 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
32 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
73 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)}\...
0
votes
0answers
22 views

Difference between GA and ABC for inference

If I have an agent-based model and I want to infer the parameters, I would normally used ABC (approximate bayesian computation), but I was recently working with someone who was using GA (genetic ...
3
votes
1answer
160 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 ...
0
votes
0answers
94 views

vc dimension of binary decision trees of depth d?

how do i find the vc dimension of the hypothesis space H ,of the binary decision trees of depth d-2? will the hypothesis space H consist of{0,1} and the vc dimension is the number of ways in which we ...
1
vote
0answers
54 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
32 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 ...
2
votes
0answers
28 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 ...
2
votes
1answer
46 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
50 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
18 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
73 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
97 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
26 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
47 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
167 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
40 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. ...
0
votes
1answer
274 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
1k 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
28 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 ...
0
votes
1answer
46 views

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

My math level is very very poor so I can't get the statistics. Can anyone explain in simple words? I.e. if I have frequency data: ...
0
votes
1answer
26 views

Testing two distributions, both accept null hypothesis

I have a sample that is collected to verify the accuracy of a new random number generator. Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and ...
2
votes
0answers
90 views

Examples of bad statistics in Computer Science

I am preparing class materials for the applied statistics class for Ph.D. students and want to present them with examples of bad statistics in different fields of computer science. I am especially ...
1
vote
0answers
65 views

What is the reason behind getting same result by maximum likelihood estimate and smoothing?

I know that Good-Turing smoothing helps us to trim a bit of probability from some more frequent events and give it to the events we've never seen. Thus it keeps our model from assigning zero ...
0
votes
0answers
66 views

SimRank++ on a weighted graph (why the formula reflects the influncee of the weight)

In the paper "Simrank++:Query Rewriting through Link Analysis of the Click Graph"(http://www.vldb.org/pvldb/1/1453903.pdf), the formula to compute the similarity between $q$ and $q'$ is as follows: \...
1
vote
1answer
69 views

Inequality over the entropy of an integer-valued random variable

I stumbled upon this inequality over a course on Information Theory : If $Z\in\mathbb{N}​$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})​$ where $h$ is the binary entropy function ...
6
votes
2answers
185 views

Applying graph “adjustment” algorithms to Elo rating system

I'm trying to address what I perceive to be a potential shortcoming in the Elo Rating System (predominantly used by the international Chess community to rate + rank players). I have a two-player game ...
0
votes
1answer
346 views

maximizing inner product of vectors in an ellipsoid and a given vector

I have been wrestling with this for quite a long time but couldn't convince myself that the following is true: What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid....
1
vote
0answers
42 views

Update model parameter with new data, discarding old data

I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve,...
3
votes
1answer
32 views

HMM tagger - Baum Welch training

I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, ...
1
vote
0answers
32 views

Unsupervised learning: necessity of labels and dependency between features and labels?

I have logs of activities without labels, which describe whether an activity is normal or not. Assuming that normal behaviors will follow a Gaussian distribution, I fit Gaussian distributions on ...