Questions tagged [algorithms]
An unambiguous list of computational steps involved in finding a solution to a class of problems.
950
questions
0
votes
0
answers
24
views
Why is the time complexity of a dot product between two n-vectors $2n$ and not $2n-1$ [closed]
In Golub's matrix computations(fourth edition page 4, algorithm 1.1.1) they provide the following algorithm for computing the dot product $c = x^Ty$:
...
0
votes
0
answers
28
views
65536 (2048 Game) optimization [closed]
This is a variant of 2048 game. Currently my max tile value is '4096' but I am trying to get the max tile above this. How should i optimize this code such that in less time it gives a higher max tile ...
2
votes
0
answers
38
views
What algorithm can find a gradient increase using the maximum value of small circles on a two dimensional plot?
I'm looking to make research on an algorithm that finds the maximum increase (gradient) on a 2D-landscape using the maximum values found on circles.
The algorithm looks at the values on each circle to ...
0
votes
0
answers
12
views
Classify text by topics using SVM: Derive the upper bound for the norm of the weight vector
In the section on SVM in one book I'm reading, the authors wrote:
Consider the problem of learning to classify a short text document according to its topic, say, whether the document is about sports ...
4
votes
1
answer
34
views
Why there are two different versions for batch perceptron algorithm?
In the book "Understanding Machine Learning, S. David Ben et al.", the authors describe the Batch Perceptron Algorithm as follows:
However, in the book "Python Machine Learning, ...
0
votes
0
answers
37
views
Explanation of a stratified randomization algorithm in R
In the book: Monte Carlo Simulation for Pharmaceutical Industry Concepts, Algorithms, and Case Studies, there is an algorithm for generating stratified randomizations:
What is the U_c(nG) notation? ...
1
vote
1
answer
14
views
Algorithm to determine sufficient range for numerical integration of PDF to get quantiles
Given a probability density function (PDF), we want to use numerical integration to find a quantile at $\alpha \in (0,1)$. Are there standard algorithms for determining a sufficient and optimal range ...
2
votes
0
answers
40
views
How to include parameter constraints in the Levenberg-Marquardt algorithm?
Every resource I found online doesn’t say what to do if the constraints aren’t satisfied. If my updated parameters is given by:
$$\theta_{k+1} = \theta_k - (JJ^T + \lambda I)^{-1}Jr, $$ where J is the ...
-1
votes
0
answers
47
views
Derivation of Gaussian mixture model where covariance matrix for each cluster is forced to be constant
Given $D = \{x_{i}\}^N_{i=1}$ i.i.d. samples from a Gaussian mixture distribution, I'm trying to determine the equations to update each of the model parameters, $\pi _{k},z_{k}$ and covariance matrix $...
0
votes
1
answer
41
views
Optimization and algorithms
I'm going over my practice midterm, and the last question has me stuck. It goes:
Let $n \geq 1$ be an integer and let A be a symmetric $n \times n$ matrix (not necessary
positive definite) for which ...
0
votes
0
answers
65
views
$(\alpha, \beta, \epsilon)$- DP-PAC learner with sample size polynomial, what is meant with that?
In the case of a $(\alpha, \beta, \epsilon)$- DP-PAC learner (with finite hypothesis class $H_d$), what is meant by sample size polynomial in different expressions for d, $\alpha$, $\beta$, $\epsilon$?...
0
votes
0
answers
19
views
Question on an algorithm picking assignments for employees
I have the following problem. I have X people that, on a weekly basis, will pick assignments out of Y different assignments. Each assignment has a different difficulty score, so at the end of each ...
2
votes
1
answer
54
views
What kind of logrank test is performed by survdiff function in R?
Information added: this question is not duplicate, neither my question nor the question in the link had been solved at all, I added more info to see if you can see the problem
I was trying to ...
0
votes
0
answers
18
views
Measuring the level of centrality of a matrix
I have simulated the moving and clustering of actors through Netlogo. I colour actors with a score higher than 60 as red, lower than 40 as green, and others as blue. Now I need a measurement of the ...
0
votes
1
answer
58
views
On the structure of Iterative Reweighted Least Squares(IRLS)
In Iterative Reweighted Least Squares (IRLS) algorithm, an optimization problem with the weight treated as known is solved in each iteration during solving the main optimization problem. For instance, ...
1
vote
0
answers
45
views
Improve HMM state estimation in latest data
I have a time-series dataset that is poisson-distributed, where each day I get a new additional datapoint. If I input all the data into a HMM (I am using code I found from hmmlearn in python) it does ...
1
vote
1
answer
24
views
How can I calculate response rate when I don't know how many people saw the item in the first place?
I have a count of how many people responded to an ad, but I don't have an official count of how many people saw the ad in the first place. I do have an estimate of how many people saw the ad though ...
2
votes
1
answer
46
views
Statistical Method for Accurately Detecting Seasonality in Monthly Sales Data
I have a dataset containing monthly sales data for different product categories spanning five years (60 months of data). I am using a Python process to calculate the seasonality for each category, ...
1
vote
2
answers
77
views
Sorting step in Decision and Regression Trees
Several papers and implementations require the tree building algoirithms specifically the split finding to have values of individual features in sorted order. For example, the XGBoost manuscript says ...
1
vote
0
answers
16
views
References for SIMPLS - Partial Least Squares
I am currently learning partial least squares analysis. I understand the idea, and the method I know to get PLS is NIPALS. Since I am currently writing a paper about this subject, I want to learn ...
2
votes
1
answer
37
views
How normalizing data cause not problem in prediction?
In algorithms that perform better with data normalization or deep learning problems such as classification, how normalizing data does not bias our algorithm? I mean, in training or even testing, we ...
1
vote
1
answer
52
views
Is K-Nearest Neighbor and Nearest Neighbor algorithm the same?
Does anyone know if there is a difference between K nearest neighbor (KNN) and nearest neighbor algorithm (NN)? And if they are how are they different?
So far all I know is that NN is unsupervised ...
1
vote
1
answer
24
views
How do I create random teams of people, each person has multiple parameters, and the parameters are equally distributed among teams
As the title suggests, I am trying to divide a group of people randomly into different teams of equal size. However, each person has parameters that go with them (such as age). If there is only one ...
1
vote
0
answers
9
views
How to analyze the effect of an exogenous variable on multiple financial variables in a model in R?
I am working on a financial analysis project where I have a dataset with daily observations for all variables from 2000 to 2023. The dataset includes an exogenous variable 'Y' and four financial ...
0
votes
0
answers
38
views
Is this algorithm for robust estimation of the covariance matrix sensible?
I have a high dimensional dataset $\bf{X} \subset \mathbb{R}^d$, which is multimodal and has outliers. I want to estimate a robust measure of association, something like the correlation between two ...
0
votes
0
answers
35
views
Is the Wikipedia Sample Entropy code wrong?
I'm following a tutorial paper on sample entropy, and I implemented the algorithm myself in Rust.
To check my work, I used Wikipedia's python code in this article. I have computed an example by hand ...
1
vote
1
answer
52
views
Which machine learning algorithm would be appropriate for this distribution of features and classes?
I have 10 features for 3 classes and all of them have a distribution similar to this (green, blue and orange is for class 0,1,2):
I tried with NBGausian and LogisticRegression however it looks like ...
1
vote
0
answers
49
views
Can I Have Some Insight Into This Probabilistic Clustering Algorithm?
I'm going over past exam papers and there's a question on probability clusterin algorithms that I'm not really sure how to approach. It goes as follows:
A probabilistic clustering algorithm based on a ...
3
votes
1
answer
63
views
Uniform sampling from intersection of hypercube and simplex
Background
Discussion from http://blog.geomblog.org/2005/10/sampling-from-simplex.html and https://cs.stackexchange.com/questions/3227/uniform-sampling-from-a-simplex have shown algorithms of sampling ...
0
votes
0
answers
20
views
How to find all the data on a box-and-whisker plot? Most importantly the mean
I am super stuck on the question. I looked up on how to find the mean on a Box-and-whisker plot, and never got a clear answer.
1
vote
1
answer
30
views
Cox survival statistic on Infractions made by bus companies
I have a Dataset that represents if in some date a bus company made any kind of traffic infraction, and how many infractions were made. This is a view of the dataset where i have the Companies, the ...
0
votes
1
answer
46
views
Implementing (R-)ALoKDE algorithm for data streams density estimation
I'm trying to implement the (R-)ALoKDE algorithm for the density estimation of the data streams. The algorithm has been published and presented in [1, 2]. Although the algorithm seems simple, I'm ...
0
votes
1
answer
229
views
What is the difference between a solver and an optimization algorithm?
In scikit-learn's LogisticRegression docs they write
This class implements regularized logistic regression using the ‘liblinear’ library, ‘newton-cg’, ‘sag’, ‘saga’ and ‘lbfgs’ solvers
Logistic ...
0
votes
0
answers
58
views
Kruskal's non-metric multidimensional scaling
I have been reading Kruskal's 1964 "Nonmetric multidimensional scaling: A numerical method" and I am slightly confused by some details, this is probably due to my lack of knowledge of ...
0
votes
0
answers
16
views
convergence rate for algorithms that stop in finite steps
I know that the k-means algorithm converges in finite steps, see Proof of convergence of k-means. This result implies that the algorithm converges in finite steps. The general definition of the rate ...
0
votes
0
answers
93
views
A multidimensional ELO rating with rock paper scissors playing styles: how to estimate
Consider the following latent variable model for a potential Elo rating with additional player type.
Each player has a performance level $r$ and a playing type $\theta$. Assume that a game between two ...
0
votes
0
answers
19
views
Sampling with replacement to achieve arbitrary variance of distances between items
Assume you want to draw a sample with replacement of size n from a large population with N items and known distances d(x,y) between them. Given an arbitrary value of distance variance A, are there any ...
2
votes
0
answers
35
views
Is there an algorithm to uniformly sample (order) lattices without generating all of them?
I'm planning out a project that involves lattices in the order theory sense of "lattice". I am assuming the number of vertices is known ahead of time.
Unfortunately I have only found ...
0
votes
0
answers
30
views
Measuring entropy of a binary matrix with biased probability
I tried to measure entropy of binary matrix like below using code at : https://github.com/cosmoharrigan/matrix-entropy
(I already saw the question : Measuring entropy/ information/ patterns of a 2d ...
1
vote
0
answers
199
views
Algorithm for Irwin Hall Distribution [closed]
I've been trying to create a function for the Irwin Hall distribution that doesn't face the same issue as the unifed package implementation. Because the function suffers from numerical issues, I ...
2
votes
1
answer
91
views
How testing (new data points) works in graph neural network
In machine learning, data is divided into train and test splits. The machine learns weights using training data and we can utilize weights to predict test data.
Similarly, we are also learning weights ...
0
votes
0
answers
10
views
Method to choose overall winner across multiple categories [duplicate]
I would like to create an algorithm that chooses an overall contest winner from an arbitrary number of participants where for each participant I have performance metrics across an arbitrary number of ...
0
votes
0
answers
26
views
How do the "C" step and robust weighting work in the FASTMCD algorithm for robust covariance estimation?
I am reading up on the FastMCD algorithm [https://arxiv.org/pdf/1709.07045.pdf#page=2] hoping to better understand its implemenation. I think I follow the high level concept for MCD
Its basically the ...
2
votes
1
answer
203
views
Choosing the best clustering algorithm and evaluating the results
I'm trying to separate my data into clusters using the k-means algorithm and the hierarchical algorithm, choose which algorithm fits my data the best, and evaluate the results. However, all of my ...
0
votes
0
answers
30
views
Could we code a program to compute VC-dimension of any given hypothesis class?
I've been studying machine learning theory and the fundamental theorem of the statistical learning for a while, but I still didn't found a general algorithm that could compute the VC dimension of any ...
0
votes
0
answers
37
views
What is reduce scatter? how it savea training time in lightGBM?
The lightGBM document mentions:
"Data Parallel in LightGBM:
We reduce communication cost of data parallel in LightGBM:
Instead of “Merge global histograms from all local histograms”, LightGBM ...
1
vote
1
answer
94
views
In $k$-means, how is it NP-hard if the dimensionality of the data is at least $2$ ($d\geq 2$)?
In $k$-means, how is it NP-hard if the dimensionality of the data is at least $2$ ($d\geq 2$)? Can someone justify or give reasons to this statement?
Any guidance would be appreciated.
0
votes
0
answers
27
views
Least angle regression algorithm in terms of gradient in lasso
I'm trying to understand an algorithm for a minimization problem but it is unclear. Here is the function we consider:
$\lVert Y - X\beta\rVert_{2}^{2} + \lambda\lVert\beta\rVert_{1}$ where $Y\in\...
0
votes
0
answers
61
views
What is the difference between mode and local minima/maxima?
Here are two definitions:
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the ...
0
votes
0
answers
20
views
Algorithm for sampling without replacement, provides consistent output given consistent input?
Problem
I'm looking for a sampling algorithm, which accepts two arguments: First, an array of integers, $x$, sampled with replacement from $range(low, high)$; and second, a set of elements, $y$, where ...