Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

An unambiguous list of computational steps involved in finding a solution to a class of problems.

6
votes
0answers
165 views

Scope of non-linear least squares

edit: tl;dr: I can coerce a lot of optimization problems to take the form of a non-linear least squares problem, but does it make sense to do so? Suppose we have some empirical data $P=\{(x_i', y_i')\...
5
votes
0answers
107 views

Good choices of PRNG for uniform circular (directional) data?

I'm planning to simulate iid one-dim variates with continuous uniform distribution on a normalized circle (which circumference is $1$ instead of $2\pi$). Namely, a sample consists of $n$ points ...
5
votes
0answers
227 views

Similarity algorithms

Let's say I have 300 restaurants that I want to compare to each other on the basis of a "similarity score". To try and determine similarity scores, I pick a reference restaurant and pick 3 other ...
5
votes
0answers
2k views

Sorting/Clustering similarity matrices

I wonder, what are the available libraries in R or Python to do correlation matrix clustering (sometimes it is referred to clustering). I also, wonder, after clustering/grouping each point. What is ...
4
votes
0answers
163 views

Mathematically Describing PCA chained with Logistic Regression

Python's scikit-learn package has a convenient pipe function that can combine machine learning techniques into one model with ...
4
votes
0answers
91 views

What is the feasibility to run linear model for large amount of data?

I am looking for empirical approximations and guidelines on how many operations are required to run a linear model on a given amount of data, or if it's even feasible. Let's assume we use QR ...
4
votes
0answers
144 views

What is the fastest way to compute PC1 scores, without performing the whole PCA?

I want to compute only the first principal component's scores $t_1$ of a large number $n$ of data points x with a high dimensionality $p$. Assume the data has been centered about zero. Data points ...
4
votes
0answers
144 views

Optimization by random sampling

Around the internet, I have seen scattered references to the idea of rescaling an objective function and using that as a PDF for the purpose of optimization. (On this site for example: Do optimization ...
4
votes
0answers
91 views

Can I use HMM to predict the spread of Ebola?

1) Can Hidden Markov Model be used across both a large number of categories (districts) and cases (weeks)? 2) Is HMM appropriate for trying to model such a problem? 3) Would I need to develop a ...
4
votes
0answers
38 views

Calculating error of MCMC algorithms?

If for example the Transitional MCMC algorithm is used (or does it matter which one?), what are the common approaches for calculating an error (some sort of distance from the actual PDF), or ...
4
votes
0answers
1k views

Decision tree with adaboost

Helllo! I'm currently learning the AdaBoost algorithm to use it with Decision Tree. I want to implement everything myself (that's the way I learn - implement everything from scratch and later use redy-...
4
votes
0answers
302 views

Efficient algorithm to enumerate all member DAGs of a Markov equivalence class

I'm working on a research project involving Bayesian networks. BNs are directed acyclic graphs (DAGs) used to compactly represent joint distributions of variables. In many cases, multiple DAGs can ...
3
votes
0answers
38 views

Algorithmic Complexity of Estimators

I am interested in evaluating the algorithmic complexity of an estimator of the form: $$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$ where $Q_n(\theta)$ denotes some objective function ...
3
votes
0answers
227 views

How can I approximate the median with a linear function?

From this thread I learned why the median is a nonlinear function. In the context in which I'm working I need to use a linear function. Googling "approximate the median"+"linear" didn't reveal ...
3
votes
0answers
388 views

Nearest/farthest neighbour between-group distance: an efficient way to find it

This question might be better suited for StackOverflow as it is programming (so you are free to suggest to move it), but it is about a data analysis programming task. The Q: do you know any "elegant" ...
3
votes
0answers
129 views

Computational entropy and Monte Carlo simulation

Is there a point at which the statistical properties of the random number generator will start to influence the results of Monte Carlo simulation? I have a scenario where I need to calculate the ...
3
votes
0answers
176 views

Nodes placement in knowledge map of Khan Academy

I have been through the Khan Academy blog regarding construction of knowledge map. However after going through it, it left me confused regarding how are they placing the nodes (hierarchically) and ...
3
votes
0answers
1k views

How does NIPALS algorithm work?

I'm working on NIPALS algorithm and I found this procedure from here: I'm just confused with the 4th step which stated, "using the $k$th scores, re-estimate the eigenvalues". As I understand, ...
3
votes
0answers
890 views

Normal Equation for logistic regression

In OLS regression we estimate the parameters of the Linear regression with multiple variables using the "Normal Equation": Would it be possible to do something similar when estimating the parameter ...
3
votes
0answers
642 views

EM algorithm: With prior vs. not prior

I have a working EM algorithm without prior. I am asking for some advice on how to add prior on latent variables. Define: $t_i \in \{ +1, -1 \} $: variables of interest to be predicted $p_j \in [0,...
3
votes
0answers
1k views

Algorithm recommendation for string classification

I have numerous (hundreds to low-thousands) of pre-classified short strings of text, each string is just a few words long, some just a single word. The strings have been divided into a few dozen ...
3
votes
0answers
62 views

Reconstruct a “blocky” picture?

Consider a finite set $A$. Let the sample space be $A\times A$. We have an unknown probability distribution $f$ on this sample space. Now this probability distribution has a "blocky" property, which I ...
3
votes
0answers
156 views

List of sample arrangements at a given Wilcoxon / Mann-Whitney test statistic

Consider a Wilcoxon-Mann-Whitney test statistic, either in the form (i) "W = sum of ranks in sample A"; or in the form (ii) "sum of ranks in sample A - the minimum possible sum of ranks in sample ...
3
votes
0answers
146 views

Best practices for MCMC early stopping?

What are best and / or standard practices for MCMC early stopping? I have an algorithm which I want to compare with existing non-MCMC algorithms for accuracy and speed. When assessing the speed it's ...
3
votes
0answers
117 views

Why is data grouped or binned in this way?

I am dealing with an existing algorithm where data is processed as follows: We have a large sample of data taken every minute, this is grouped into 'buckets' of data for every hour. (Each bucket ...
3
votes
0answers
152 views

Kavosh uses a different switching process in its MCMC; how concerned should I be?

Kavosh is a recent package designed for network motif discovery. To give a comparison, Kavosh generates a collection of similar networks using an MCMC process. The networks in consideration are ...
2
votes
0answers
25 views

Statistically determining the median of a data set via quantiles of a sample

I was thinking of algorithms for statistically determining the median of a large data set. To estimate the complexity of my idea I need the following Probability: I have a dataset $\left\{x_i \right\}...
2
votes
0answers
28 views

Computing Wassertein Distance

For two probability measures $\mu$ and $\nu$, the Wassertein Distance is defined as $$W_p (\mu , \nu) = \left[ \inf\limits_{\gamma \in \Gamma} |x-y|^p \, d\gamma (x,y) \right] ^{\frac{1}{p}} \, , $$ ...
2
votes
0answers
14 views

What are the simple methods to do an unsupervised cluster to stock return time series?

I am a student in finance and I am working on my thesis project. I am interested in doing a clustering to stock time series. I first read the paper 'Time-series clustering – A decade review' from ...
2
votes
0answers
45 views

Efficient linear regression given columns of A rather than rows of A

I'm analyzing a large problem with a large $N \times M$ data matrix $A$, where $N$ is the number of observations, $M$ is the number of explanatory variables, and $N \gg M$. I'd like to perform single-...
2
votes
0answers
104 views

Vapnik-Chervonenkis Dimension

My question has to do with the VC dimension of the class of convex polygons with $m$ vertices. A solution to this problem is given in the following: Advanced Algorithms. Call the class of all ...
2
votes
0answers
56 views

Stability of maximum likelihood algorithm with indeterminate forms

Assume that I want to estimate a copula model, where the copula has a single parameter, $\theta$. When this parameter takes a specific value, say $\theta_I$, this copula converges to the Independence ...
2
votes
0answers
239 views

How does R calculate the acf() function as quickly as it does?

I noticed that R computes the acf(data,n) in order $O(n)$ time, not $O(n^2)$, so it cannot compute it brute force using double for loops. How does R calculate it ...
2
votes
0answers
26 views

Adaptable statistical power

In software development, unit testing is (basically) executing an algorithm with a fixed input and test if the output is as expected. Example : "test that MyFactorial(4) returns 24" where "MyFactorial"...
2
votes
0answers
17 views

Space-filling design algorithms from a discrete domain

Given $S = (X_1, \ldots, X_n)$, where each $X_i \in \mathbb{R}^2$, are there algorithms that produce $(X_{(1)}, \ldots, X_{(m)})$, where $m << n$ and the $X_{(i)}$ are sampled from $S$ to fill ...
2
votes
0answers
166 views

Elastic net for general GLMs (in particular the Gamma family)

I am trying to understand the state of the art of a Gamma GLM regression with an elastic net penalty because I need to recreate it in a SAS environment (pity me). To my knowledge, the only package, in ...
2
votes
0answers
62 views

Which approach and statistical hypothesis test should I choose when testing performance results of many algorithms?

I have 4 algorithms which are doing the same thing in different ways. Let's name them A,B,C,D. I assume that one of them may have better results than others. I'd like to confirm this by test. I'm ...
2
votes
0answers
28 views

Best way to form patterns in data relevant to commonly used ports in the your networks?

We have data from the border firewalls pertaining to all ports used on our networks. For example, we have counts of all connection attempts to all ports each day on our networks. ...
2
votes
0answers
137 views

Why does original paper introducing DBSCAN state it takes only one input parameter?

I am reading about the DBSCAN clustering algorithm from the original paper by Ester et al. In this paper, the authors state in the abstract, the introduction, and the conclusion that their algorithm ...
2
votes
0answers
33 views

Measurements: Calculate start of gradient

let's assume you have 1000 measurements (temperature in this case), all having a similar shape. It's a temperature profile inside a production line measured by a reference block mounted with ...
2
votes
0answers
23 views

Randomly Generating Combinations From Variable Weights

The Question I have a list A of n unique objects. Each object Ai has a variable percentage Pi. I want to create an algorithm that generates a new list B of k objects (k < n/2 and in most cases ...
2
votes
0answers
486 views

How would I determine statistical significance for ad impressions?

I'm programatically adding keywords to bid on. Some keywords will trigger ads and impressions, and some impressions will trigger clicks. Clicks / impressions = CTR (click-through-rate). Clicks cost. ...
2
votes
0answers
124 views

Find good next pair for comparison based total ranking

I want to obtain a total ranking from pairwise binary comparisons. For this, I can use algorithms like Balanced Rank Estimation or Bradley-Terry Model. However, I wonder if you need fewer comparisons, ...
2
votes
0answers
243 views

Different behaviors for different Ridge implementations in R

I am having trouble reconciling the different behavior of different Ridge implementations in R. As the following code demonstrates it seems that MASS:lm.ridge ...
2
votes
0answers
137 views

On accept-reject method for unknown function

My problem is this I have a posterior as $Gamma(\alpha, \beta) \times exp(\lambda)$. $$Y_{1}^{n} \sim Gamma(\alpha, \beta)$$ $$\alpha \sim Exp(\lambda)$$ $$\beta \sim Exp(\lambda)$$ Now $n=50, \...
2
votes
0answers
184 views

Support Vector Machine with zero bias term

I'm looking for an algorithm to solve SVM with zero bias term. So dual form of such SVM is $max_\alpha \sum_i^n \alpha_i -1/2\sum_i^n \sum_j^ny_iy_jK(x_ix_j)\alpha_i\alpha_j$ subject to: $0 \leq \...
2
votes
0answers
416 views

Random forest - proof of convergence

I'm having some trouble understanding Leo Breiman's proof that the generalization error of a random forest converges as the number of trees increases (here's a link to the paper). At Appendix I he ...
2
votes
0answers
53 views

Iterative or Lazy Reservoir Sampling

I'm fairly well acquainted with using Reservoir Sampling to sample from a set of undetermined length in a single pass over the data. One limitation of this approach, in my mind, is that it still ...
2
votes
0answers
353 views

A binomial random number generating algorithm that works when n*p is very small

I need to generate binomial random numbers: For example, consider binomial random numbers. A binomial random number is the number of heads in N tosses of a coin with probability p of a heads on ...
2
votes
0answers
138 views

Statistically comparing two different cache hit algorithms

I am comparing two different cache hit algorithms using four different training and testing sets. The training sets are related: 1 is a subset of 2 is a subset of 3 is a subset of 4. The same goes for ...