# Questions tagged [statistics]

The tag has no usage guidance.

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
61 views

### Infer probabilities, for concatenation of words

Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$. I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
• 140k
309 views

### Space complexity of statistic functions

When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be ...
• 141
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 ...
• 131
82 views

### Statistical anomaly detection in time series

I'm looking for some algorithms that detect statistical anomaly in time series. For example, Google Trend automatically detects peaks of a specific search query in time, and associates those peaks ...
• 131
43 views

### Algorithm for half-sample mode better than O(N^2)

The half-sample mode is a mode estimator that homes in on the highest density region of a set of samples in search of the mode. It is one of the better mode estimators, though it fails for J-shaped ...
22 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 ...
• 12.3k
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 ...
• 215
50 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. ...
• 121
52 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 ...
107 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 ...
120 views

### What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
37 views

### error measure (of ML agos) that takes confidence into account

when calculating the error measure such as mean absolute error, we use the real values and the predicted values. Many machine learning algorithms can give a confidence measure of each value being ...
51 views

### Do online quantile estimation algorithms that support deletions exist?

There are several online quantile estimation algorithms, but I haven't seen any that supports deletions (i.e. unobserve elements observed in the past). Are there any such known algorithms? To ...
• 213
288 views

### Efficiently estimating latency quantiles of a distributed system

I'm building a load test harness for a distributed system. Currently I'm using the "Cormode, Korn, Muthukrishnan, and Srivastava" method to estimate latency quantiles of system responses. I'm now ...
• 121
1 vote
29 views

### Precise definition of Universal Learner in Machine Learning

It is surprising to me that I cannot find a precise definition of universal learner on the internet. I can guess what it should bebut I don't want to make a mistake, therefore I have come here. Here's ...
• 11
1 vote
70 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
26 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 ...
• 125
1 vote
13 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 ...
• 389
1 vote
16 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
14 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 ...
• 111
1 vote
41 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 ...
• 249
1 vote
93 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 ...
• 386
1 vote
35 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 ...
1 vote
69 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 ...
• 11
1 vote
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,...
• 11
1 vote
34 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 ...
• 111
1 vote
82 views

### Approximate conditional entropy

Given a set of random variables $X = \{x_1, x_2, \dots, x_n\}$. If the conditional entropy for all $Y \subset X - \{X_i\}$ where $|Y| \leq 5$. How to approximate conditional entropy when $|Y| = 10$ ...
• 19
1 vote
238 views

### EM-algorithm for categorical hidden variables

I have the following model: Let's say two indepentent weighted six-sided dice $X$ and $Y$ with unknown probabilities (i.e. probability of 1 is unkown etc) and they have not necessarily the same ...
• 11
1 vote
58 views

### Known distributions that generate sparse vectors?

I have data that comes in the form of a vector. Each vector is sparse. Is there a commonly used distribution that will generate sparse vectors? I am working on a project where I am passing a bunch ...
• 39
1 vote
246 views

### Linear regression - iterative approach

I have a single output variable $y$ and a number of inputs $x_1$, $x_2$, etc. These are time series. Each $x_i$ explains the changes in $y$ in specific circumstances, and the goal is to have a linear ...
1 vote
192 views

### Formula for number of parameters in an undirected graphical (probability) model

I have googled endlessly, and I cannot find it. Can anyone point me to a reference that gives a way to calculate the number of parameters in an undirected Graphical Model? Adapting from the similar ...
• 29.1k
1 vote
99 views

### Applications of algorithms to stock trading analysis

There is a new Quantitative Finance SE site. However, I am interested in asking the "CS crowd": What are some interesting key references or surveys on applying algorithms to stock trading analysis?...
• 10.8k
53 views

• 263
399 views

### What is role of parameter learning rate, lr, and momentum constant, mc in Neural Networks?

can anyone describes the more simplified mathematical formulation of learning rate, lr, and momentum constant, mc in Neural Networks while training the data?
• 101
251 views

### Merging two disconnected graphs

Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's. I have two ...
• 101
88 views

### TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
• 101