Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Probabilistic algorithms > Probabilistic algorithms > Flashcards

Probabilistic algorithms Flashcards

1
Q

heuristics

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

approximation algorithm

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

randomized algorithm

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

stochastic

A

describes something that was randomly determined

randomly determined; having a random probability distribution or pattern that may be analyzed statistically but may not be predicted precisely.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Probability density function

A

a probability density function (PDF), or density of a continuous random variable, is a function, whose value at any given point in the sample space (the set of possible values taken by the random variable) can be interpreted as providing a relative likelihood that the value of the random variable would equal that sample

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

pivot

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Probabilistic Algorithm paradigm

A

for each input make a random choice and hope that it is good.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Non-Deterministic execution of algorithm

A

for the same input different sequences of
operations are possible

vs. for the same input the same sequence of
operations is executed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Probabilistic Algorithm

A

A Probabilistic (or Randomized) Algorithm is an algorithm which employs a degree of randomness as part of its logic

  • > During execution, it takes random choices depending on those random numbers
  • > The behavior (output) can vary if the algorithm is run multiple times on the same input

=> probabilistic algorithms are often simpler and faster than their deterministic counterparts
=> however, in the worst execution case, the algorithm may be very slow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

positive vs negative probability

A

??

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

probabilistic algorithm

A

+ gain execution time

- loose correctness of answer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Las Vegas algorithms

A

a randomized algorithm that

  • always gives correct/optimal results
  • the execution time is variable
  • example: RandQSORT
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Monte Carlo algorithms

A

a randomized algorithm that

  • the running time is deterministic
  • the output may be incorrect with a certain probability
  • example: Check matrices equality
  • for Decision problem (Yes/No): one- or two-sided error
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

one-sided error

A

Monte Carlo algorithm: Yes or No always correct

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

two-sided error

A

Monte Carlo algorithm: a non-zero probability to err for both outputs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

E[X]

A

Expected value of discrete X: E[X]

The expected value of random variable X is often written as E(X)

sl. 15 lecture_01

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Random number generation

A
  • the kernel of Monte Carlo simulation
  • the heart of many standard statistical methods (bootstrap, Bayesian analysis)
  • cryptography
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

bisection method

A

d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

sucessive quadratic estimation method

A

d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Powell’s algorithm

A

d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

inflection point

A

An inflection point is a point on a curve at which the sign of the curvature (i.e., the concavity) changes. Inflection points may be stationary points, but are not local maxima or local minima.

http://mathworld.wolfram.com/InflectionPoint.html

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

first order condition

A

The first order condition means that the local maximum or local minimum of some continuous function within some range (not including the end points) must occur where the derivative of that function is equal to 0.

  • > At the highest and lowest points of a curve, the tangent to the curve at such points is horizontal.
  • > The slope of the curve is zero.

http://users.etown.edu/p/pauls/ec309/lectures/lec04_unconst.html

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

second order condition

A

SOC for a local max is that f’‘(x) < 0

SOC for a local min is that f’‘(x) > 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

loss function

A

a function that maps an event or values of one or more variables onto a real number intuitively representing some “cost” associated with the event.

An optimization problem seeks to minimize a loss function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Hessian matrix?
useful in characterizing the shape of L and to | distinguish, among the zeros of gradient g(d), the minimum points, the maximum points and the inflexion points
26
why an inverse matrix?
we can multiply by an Inverse, which achieves the same thing as "dividing by a number" remember: with Matrices the order of multiplication matters. AB is almost never equal to BA. https: //www.mathsisfun.com/algebra/matrix-inverse.html
27
Jacobian matrix
is the matrix of all first-order partial derivatives of a vector-valued function. When the matrix is a square matrix, both the matrix and its determinant are referred to as the Jacobian in literature The Jacobian matrix is important because if the function f is differentiable at a point x (this is a slightly stronger condition than merely requiring that all partial derivatives exist there), then the Jacobian matrix defines a linear map ℝ^n → ℝ^m, which is the best (pointwise) linear approximation of the function f near the point x. This linear map is thus the generalization of the usual notion of derivative, and is called the derivative or the differential of f at x.
28
Differenzierbarkeit / differentiable
Als Differenzierbarkeit bezeichnet man in der Mathematik die Eigenschaft einer Funktion, sich lokal um einen Punkt in eindeutiger Weise linear approximieren zu lassen.
29
TSP
find a Hamiltonian cycle with minimal path length in G
30
TSP extension
- Asymmetric TSP - optimum configuration for the ATSP - time dependent TSP - Vehicle Routing Problem - probabilistic VRP -
31
Branch & Bound
an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
32
Branch & Bound TSP
in B & B we try to reduce the search space:
33
linear programming
LP, also called linear optimization best outcome of a mathematical model (provided constraints)
34
convex set
a convex set is a subset of an affine space that is closed under convex combinations. in a Euclidean space, a convex region is a region where, for every pair of points within the region, every point on the straight line segment that joins the pair of points is also within the region
35
Convex polytope
a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space R^n
36
Steepest Descent algorithm
tbd
37
Newton-Raphson
tbd
38
Branch & Bound
tbd
39
Localized Random Search
tbd
40
Direct Random Search
tbd
41
convex
convex describes a surface that curves outward, or is thicker in the middle than on the edges. https://writingexplained.org/concave-vs-convex-difference
42
concave
Concave is an adjective that describes a surface that curves inward, or is thinner in the middle than on the edges.
43
hypercube
a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3)
44
multivariate
involving two or more variable quantities.
45
multivariate normal distribution
is a generalization of the one-dimensional (univariate) normal distribution to higher dimensions One definition is that a random vector is said to be k-variate normally distributed if every linear combination of its k components has a univariate normal distribution
46
Enhanced Localized Random Search
tbd
47
Simple Random ("Blind") Search
tbd
48
Direct methods for stochastic search
enlist...
49
Pattern search
describe...
50
Random search with noise-free measurements
describe...
51
slack variable
a slack variable is a variable that is added to an inequality constraint to transform it into an equality Introducing a slack variable replaces an inequality constraint with an equality constraint and a non negativity constraint By introducing the slack variable y >= 0, the inequality Ax <= b can be converted to the equation Ax + y = b
52
n-simplex
is a generalization of the notion of a triangle to arbitrary dimensions
53
Basic Pattern Search Algorithm
t
54
Compass search
t
55
Nonlinear Simplex (Nelder-Mead) Algorithm
t - derivative-free optimization algorithm -> derivatives are unavailable or expensive to compute - > derivative-free method - > recommended for solving optimization problems with noisy objective functions
56
convex hull
a polygon which is the smallest perimeter fence enclosing a set of N points
57
Constraints
limitation of the allowed values of the degree of freedom of the system e.g. boundaries (localisation constraints) e.g. deadline for event occurrence (temporal constraints) hard & soft constraints
58
penalty function
a solution which violates a constraint is not rejected, but "punished"
59
heuristics
is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.
60
Heuristic optimization algorithms
Two natural ways to design an heuristic algorithm: - Construction heuristics - Markovian improvement heuristics
61
configuration
t
62
construction heuristics vs. improvement heuristics
t
63
Insertion heuristic
the new node is inserted somewhere inside the sequence (not appended!) - How to choose the new node? - Where is the optimum place to insert it?
64
Construction heuristics for TSP
e.g. Nearest Neighbor Heuristic
65
Best insertion heuristic
you insert the next randomly chosen node between those two nodes where the increase in the total length is minimum until all nodes are visited.
66
Nearest Neighbor Heuristic
choose a random node. then choose a random node which is closest to the first node. Then choose a random node which is closest to the second node and so on... (the new node is *appended*!)
67
Best-Best insertion / cheapest insertion heuristic
t
68
Worst-best insertion / farthest insertion algorithm
t
69
nearest insertion heuristic
t
70
Shortest edge heuristic
t
71
Ruin & Recreate
t
72
Ruin & Recreate for TSP
t
73
energy landscape
The values of loss function + the search space form the energy landscape of the system
74
improvement heuristics
t
75
Markov improvement heuristic
t
76
local search approach
?
77
Swap move algorithm TSP
t
78
Translation move algorithm
t
79
Inversion move algorithm
t
80
Improvement heuristics for TSP
Swap move algorithm TSP Translation move algorithm Inversion move algorithm
81
Greedy algorithm for TSP
t
82
Simulated Annealing
t
83
TA is considered as a "first approximation" of SA
much faster than SA (no need to generate delta uniformly on (0,1))
84
i.i.d.
independent and identically distributed a sequence or other collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent
85
Noise:
independent, identically distributed (i.i.d.) measurement | errors
86
Steepest Descent with Noisy/Noise-Free Gradient
_09
87
Random Search Algorithms with Noisy Loss Function
Basic implementation of random search assumes perfect (noise-free) values of L
88
Statistical and Engineering Convergence Conditions
_09
89
Stochastic Approximation
_09 ???
90
stochastic gradient
_09 sl. 31
91
Stochastic Gradient Measurement and Algorithm (SGA=
_09
92
Gradient-Free Algorithms
_09
93
Finite-Difference Algorithm
_09
94
FDSA algorithm
_09
95
gain value?
_09
96
Simultaneous Perturbation Stochastic Approximation | Algorithm (SPSA)
_09
97
gain sequence
the sequence of a_k values used in the calculation of d^_k+1, as a factor to Y_k(d_k)
98
d*
d* e D* -> a global optimal solution D* is the solution space, the set of all solutions of an optimization problem d^ e D (problem space) is a solution candidate
99
The loss function L() | The gradient g(d)
The gradient g(d) of L(d) is the vector of first order derivatives
100
SP
Simultaneous Perturbation

Probabilistic algorithms (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions