'@GSMC' 카테고리의 글 목록 (2 Page)

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Kolman & Beck <Elementary linear programming with applications> 2nd ed.

2009. 3. 9. 15:47 @GSMC/서용덕: Convex Optimization

Elementary linear programming with applications

By Bernard Kolman, Robert Edward Beck

Contributor Robert Edward Beck

Edition: 2, illustrated

Published by Academic Press, 1995

ISBN 012417910X, 9780124179103

449 pages

Prologue
: Introduction to Operations Research

Definitions

Operations research (OR) is a scientific method for providing a quantitative basis for decision making (that can be used in almost any field of endeavor).

http://en.wikipedia.org/wiki/Operations_research

The techniques of OR give a logical and systematic way of formulating a problem so that the tools of mathematics can be applied to find a solution (when the established way of doing things can be improved.

A central problem in OR is the optimal allocation of scarce resources (including raw materials, labor, capital, energy, and processing time).

eg. T. C. Koopmans and L. V. Kantorovich, the 1975 Nobel Prize awardees

Development

WWII, Great Britain
the United States Air Force
1947, George B. Dantzig, the simplex algorithm (for solving linear programming problems)
programmable digital computer (for solving large-scale linear programming problems)
1952, the National Bureau of Standards SEAC machine

Phases

> Steps
1. Problem definition and formulation

to clarify objectives in undertaking the study
to identify the decision alternatives
to consider the limitations, restrictions, and requirement of the various alternatives

2. Model construction

to develop the appropriate mathematical description of the problem
: limitations, restrictions, and requirements -> constraints
: the goal of the study -> quantified as to be maximized or minimized
: decision alternatives -> variables

3. Solution of the model

: the solution to the model need not be the solution to the original problem

4. Sensitivity analysis

to determine the sensitivity of the solution to changes in the inpuit data
: how the solution will vary with the variation in the input data

5. Model evalution

to determine whether the answers produced by the model are realistic, acceptable and capable of implementation

6. Implementation of the study

The Structure of Mathematical Models

There are two types of mathematical models: deterministic and probabilistic.

A deterministic model will always yield the same set of output values for a given set of input values, whereas a probabilistic model will typically yield many different sets of output values according to some probability distribution.

Decision variables or unknowns

to describe an optimal allocation of the scarce resources represented by the model

Parameters

: inputs, not adjustable but exactly or approximately known

Constraints

: conditions that limit the values that the decision variables can assume

Objective function

to measures the effectiveness of the system as a function of the decision variables
: The decisin variables are to be determined so that the objective function will be optimized.

Mathematical Techniques

mathematical programming

Mathematical models call for finding values of the decision variables that maximize or minimize the objective function subject to a system of inequality and equality constraints.

Linear programming

Integer programming

Stochastic programming

Nonlinear programming

network flow analysis

standard techniques vs. heuristic techniques (improvised for the particular problem and without firm mathematical basis)

Journals

Computer and Information Systems Abstracts Journal
Computer Journal
Decision Sciences
European Journal of Operational Research
IEEE Transactions on Automatic Control
Interfaces
International Abstracts in Operations Research
Journal of Computer and System Sciences
Journal of Research of the National Bureau of Standards
Journal of the ACM
Journal of the Canadian Operational Research Society
Management Science (published by The Institute for Management Science - TIMS)
Mathematical Programming
Mathematics in Operations Research
Naval Research Logisics (published by the Office of Naval Research - ONR)
Operational Research Quarterly
Operations Research (published by the Operations Research Society of America - ORSA)
Operations Research Letters
OR/MS Today
ORSA Journal on Computing
SIAM Journal on Computing
Transportation Science

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

SeDuMi (0)	2009.03.11
[Kolman & Beck] Chapter 1 Introduction to Linear Programming (0)	2009.03.11
[Boyd & Vandenberghe] Chapter 4 Convex Optimization Problems (0)	2009.03.04
[Boyd & Vandenberghe] Chapter 3 Convex Functions (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23

posted by maetel

Sartaj Sahni <Data Structures, Algorithms, and Applications in C++> 2nd ed.

2009. 3. 9. 14:46 @GSMC/서용덕: Multimedia Programming C++

Data Structures, Algorithms, and Applications in C++

By Sartaj Sahni

Edition: 2, illustrated
Published by Silicon Press, 2005
ISBN 0929306325, 9780929306322
792 pages

1st ed. : http://www.mhhe.com/engcs/compsci/sahni/
2nd ed.: http://www.cise.ufl.edu/~sahni/dsaac/

COP 3530 : Data Structures and Algorithms
Department of Computer and Information Sciences and Engineering, University of Florida

'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

Sahni's ch.16 Graphs (0)	2009.06.11
merge sort (0)	2009.06.01
Hill & Kelly [Computer Graphics Using OpenGL] (0)	2009.04.18
Sahni Chapter 8. Stacks (0)	2009.04.11
Deitel <C++ How to program> Sixth ed. (0)	2009.03.07

posted by maetel

Deitel <C++ How to program> Sixth ed.

2009. 3. 7. 20:44 @GSMC/서용덕: Multimedia Programming C++

http://int.prenhall.com/deitel/

C++ How to Program, 6/e
Harvey M. Deitel and Paul J. Deitel, both from Deitel & Associates, Inc.
© 2008, 1500 pp., paper (0-13-615250-3)

C++ How to Program, 6e Example Downloads

C++ Programming Resource Center

Deitel Free Content Library#CPLUSPLUS

C++ Programming Curriculum Overview

'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

Sahni's ch.16 Graphs (0)	2009.06.11
merge sort (0)	2009.06.01
Hill & Kelly [Computer Graphics Using OpenGL] (0)	2009.04.18
Sahni Chapter 8. Stacks (0)	2009.04.11
Sartaj Sahni <Data Structures, Algorithms, and Applications in C++> 2nd ed. (0)	2009.03.09

posted by maetel

[Boyd & Vandenberghe] Chapter 4 Convex Optimization Problems

2009. 3. 4. 23:18 @GSMC/서용덕: Convex Optimization

4.1 Optimization Problems

eg.4.1

ezplot('x*log(x)')

* MATLAB에서 그래프 그리기

ezplot('x*log(x)')
로 해서 나왔으나, 일반적으로는 다음과 같은 식으로 한다.

x=0:0.1:10;
y=x.*log2(x); ## 여기서, x 다음의 .은 element끼리의 scalar 연산을 지시함
plot(x,y)

http://en.wikipedia.org/wiki/Slack_variable

4.2 Convex Optimization

4.3 Linear Optimization Problems

http://en.wikipedia.org/wiki/Linear_program

4.4 Quadratic Optimization Problems

http://en.wikipedia.org/wiki/Quadratic_program

Markowitz portfolio optimization

4.4.2 Second-order cone programming

http://en.wikipedia.org/wiki/SOCP

http://en.wikipedia.org/wiki/Minimal_surface

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Kolman & Beck] Chapter 1 Introduction to Linear Programming (0)	2009.03.11
Kolman & Beck <Elementary linear programming with applications> 2nd ed. (0)	2009.03.09
[Boyd & Vandenberghe] Chapter 3 Convex Functions (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19

posted by maetel

EEE3154: 랜덤 프로세스

2009. 3. 4. 15:51

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

Chapter 1. Experiments, Models, and Probabilities

2009. 3. 3. 17:40

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

Introduction to Computer Science

2009. 3. 2. 22:01 @GSMC

http://en.wikipedia.org/wiki/Computer_science

http://en.wikipedia.org/wiki/Alan_turing

http://en.wikipedia.org/wiki/John_von_Neuman

http://en.wikipedia.org/wiki/Donald_knuth

'@GSMC' 카테고리의 다른 글

Chapter 1 (0)	2009.03.13
EEE3154: 랜덤 프로세스 (0)	2009.03.04
GITB377: 무선센서 네트워크 (0)	2009.03.02
MEDM350: 미학 (0)	2009.02.08
MEDM587: Special Lecture (III) on Special Effects (0)	2009.02.08

posted by maetel

GITB377: 무선센서 네트워크

2009. 3. 2. 21:50

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

[Yates & Goodman] Probability and Stochastic Processes

2009. 3. 2. 18:33 @GSMC/홍대형: Statistical Communication Theory

Yates and Goodman, Probability and Stochastic Processes,
2nd Ed. John Wiley & Sons, 2005

Probability and Stochastic Processes: A Friendly Introduction for Electrical and Computer Engineers

(공)저: Roy D. Yates, David J. Goodman

기고가 David J. Goodman

Edition: 2, illustrated, revised

출판사: John Wiley & Sons, 2004

ISBN 0471272140, 9780471272144

544페이지

http://www.wiley.com/college/yates
출판사 페이지: http://he-cda.wiley.com/WileyCDA/HigherEdTitle/productCd-0471272140.html

Dr. Roy Yates received the B.S.E. degree in 1983 from Princeton University, and the S.M. and Ph.D. degrees in 1986 and 1990 from M.I.T., all in Electrical Engineering. Since 1990, he has been with the Wireless Information Networks Laboratory (WINLAB) and the ECE department at Rutgers, University. He is currently an associate professor.

David J. Goodman is Director of WINLAB and a Professor of Electrical and Computer Engineering at Rutgers University. Before coming to Rutgers, he enjoyed a twenty year research career at Bell Labs where he was a Department Head in Communications Systems Research. He has made fundamental contributions to digital signal processing, speech coding, and wireless information networks.

학습 페이지: http://bcs.wiley.com/he-bcs/Books?action=index&itemId=0471272140&bcsId=1991

관련 강의>

Stochastic Signals and Systems (332:541)
Department of Electrical and Computer Engineering
Rutgers University

http://www.soe.ucsc.edu/classes/cmpe107/Fall01/

ECE 302 Probabilistic Methods in Electrical Engineering

EE8103 – Random Processes
Department of Electrical and Computer Engineering
RYERSON UNIVERSITY

ECE 153: Probability and Random Processes for Engineers (Fall 2008)
Department of Electrical and Computer Engineering
University of California, San Diego

ECE 316: Probability Theory and Random Processes (Spring 2007)

EECS 126: Probability and Random Processes (Spring 2004)
Dept of Electrical Engineering & Computer Sciences
University of California at Berkeley

Probabilistic Systems Analysis and Applied Probability, Fall 2002
Electrical Engineering and Computer Science
MIT OpenCourseWare

MN308 Statistics and Quality Engineering, and
EC381 Probability in Electrical and Computer Engineering (Spring 2008)
College of Engineering
Boston University

'@GSMC > 홍대형: Statistical Communication Theory' 카테고리의 다른 글

Chapter 6 Sums of Random Variables (0)	2009.05.06
Homework #3 (0)	2009.04.02
Chapter 3 Continuous Random Variables (0)	2009.04.01
Chapter 2. Discrete Random Variables (0)	2009.03.17
Chapter 1. Experiments, Models, and Probabilities (0)	2009.03.03

posted by maetel

[Boyd & Vandenberghe] Chapter 3 Convex Functions

2009. 2. 23. 21:00 @GSMC/서용덕: Convex Optimization

lecture 3 video
lecture 4 video
@ Stanford Engineering Everywhere
Linear Systems and Optimization | Convex Optimization I
Instructor: Boyd, Stephen

EE364a: Convex Optimization I
Professor Stephen Boyd, Stanford University, Winter Quarter 2007–08

3.1 Basic properties and examples

3.1.1 Definition

http://en.wikipedia.org/wiki/Convex_function
a function is convex if and only if its epigraph (the set of points lying on or above the graph) is a convex set

Pictorially, a function is called 'convex' if the function lies below the straight line segment connecting two points, for any two points in the interval

3.1.2 Extended-value extensions

http://en.wikipedia.org/wiki/Indicator_function

3.1.3 First-order conditions

http://en.wikipedia.org/wiki/Taylor_approximation

3.1.4 Second-order conditions

3.1.5 Examples

3.1.6 Sublevel sets

3.1.7 Epigraph

3.1.8 Jensen's inequality and extensions

3.1.9 Inequalities

3.2 Operations that preserve convexity

3.2.1 Nonnegative weighted sums

3.2.2 Composition with an affine mapping

3.2.3 Pointwise maximum and supremum

3,2.4 Composition

3.2.5 Minimization

3.2.6 Perspective of a function

3.3 The conjugate function

3.3.1 Definition and examples

http://en.wikipedia.org/wiki/Convex_conjugate

3.3.2 Basic properties

3.4 Quasiconvex functions

3.4.1 Definition and examples

http://en.wikipedia.org/wiki/Quasiconvex_function
A quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form is a convex set.

3.4.2 Basic properties

3.4.3 Differentiable quasiconvex functions

3.4.4 Operations that preserve quasiconvexity

3.4.5 Representation via family of convex functions

3.5 Log-concave and log-convex functions

3.5.1 Definition

http://en.wikipedia.org/wiki/Logarithmically_concave_function

http://en.wikipedia.org/wiki/Logarithmically_convex_function

an indicator function or a characteristic function is a function defined on a set X that indicates membership of an element in a subset A of X.

http://en.wikipedia.org/wiki/Geometric_mean

http://en.wikipedia.org/wiki/Bohr%E2%80%93Mollerup_theorem

ref.
http://mathworld.wolfram.com/GammaFunction.html

Convexity in the theory of the gamma function
International Journal of Applied Mathematics & Statistics , Nov, 2007 by Milan Merkle

THU NGỌC DƯƠNG, THE GAMMA FUNCTION

Mohamed A. Khamsi, The Gamma Function

http://en.wikipedia.org/wiki/Determinant
http://mathworld.wolfram.com/Determinant.html

http://en.wikipedia.org/wiki/Lebesgue_measure

http://en.wikipedia.org/wiki/Laplace_transform
http://mathworld.wolfram.com/LaplaceTransform.html

ref.
Ernesto Schirmacher <Log-Concavity and the Exponential Formula>

András Prékopa, Logarithmic Concave Measures with Applications to Stochastic Programming, 1971
András Prékopa, On logarithmic concave measures and functions, 1973
András Prékopa, Logarithmic Concave Measures and Related Topics, 1980

Ole E. Barndorff-Nielsen,

Bruce E. Sagan, Log Concave Sequences of Symmetric Functions and Analogs of the Jacobi-Trudi Determinants. 1992
Thomas M. Cover and A. Thomas, Determinant Inequalities via Information Theory

3.5.2 Properties

http://en.wikipedia.org/wiki/Cumulative_distribution_function

http://en.wikipedia.org/wiki/Polyhedron

3.6 Convexity with respect to generalized inequalities

3.6.1 Monotonocity with respect to a generalized inequality

3.6.2 Convexity with respect to a generalized inequality

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

Kolman & Beck <Elementary linear programming with applications> 2nd ed. (0)	2009.03.09
[Boyd & Vandenberghe] Chapter 4 Convex Optimization Problems (0)	2009.03.04
[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02

posted by maetel

[Boyd & Vandenberghe] Chapter 2 Convex Sets

2009. 2. 23. 20:20 @GSMC/서용덕: Convex Optimization

2.1 Affine and convex sets

2.2 Some important examples

2.3 Operations that preserve convexity

2.4 Generalized inequalities

2.5 Separating and supporting hyperplanes

2.6 Dual cones and generalized inequalities

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 4 Convex Optimization Problems (0)	2009.03.04
[Boyd & Vandenberghe] Chapter 3 Convex Functions (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02
[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions (0)	2009.01.22

posted by maetel

[Boyd & Vandenberghe] Chapter 1 Introduction

2009. 2. 19. 16:04 @GSMC/서용덕: Convex Optimization

http://www.stanford.edu/class/ee364/lectures.html

1.1 Mathematical optimization

mathematical optimization problem

A vector of optimization variables is optimal (or a solution) of a problem,
if it has the smallest objective value satisfying the constraints.

objective and constraint functions: linear --> optimization problem: linear program

: convex --> convex optimization problem

Convexitiy is more general than linearity.

Convex optimization can be a generalization of linear programming.

1.1.1 Applications

optimization variable <=> choice
objective function
constraint functions <=> requirements / specifications
objective value <=> cost
limit / bound
solution <=> choice with minimum cost (/ maximum utility)

http://en.wikipedia.org/wiki/Supply_chain_management

data fitting
decision making
system design/analysis/operation

automatic control systems + embedded optimization

1.1.2 Solving optimization problems

A problem is sparse if each constraint function depends on only a small number of the variables.

> effective algorithms
least-squares problems
linear programs
convex optimization

1.2 Least-squares and linear programming

1.2.1 Least-squares problems

no constraints

http://en.wikipedia.org/wiki/Least_squares
The best fit in the least-squares sense is that instance of the model for which the sum of squared residuals has its least value, a residual being the difference between an observed value and the value given by the model. The method was first described by Carl Friedrich Gauss around 1794.

http://en.wikipedia.org/wiki/Moore%27s_law

http://en.wikipedia.org/wiki/Regression_analysis
techniques for the modeling and analysis of numerical data consisting of values of a dependent variable (also called response variable or measurement) and of one or more independent variables (also known as explanatory variables or predictors)
The dependent variable in the regression equation is modeled as a function of the independent variables, corresponding parameters ("constants"), and an error term. The error term is treated as a random variable. It represents unexplained variation in the dependent variable. The parameters are estimated so as to give a "best fit" of the data. Most commonly the best fit is evaluated by using the least squares method, but other criteria have also been used.

http://en.wikipedia.org/wiki/Maximum_likelihood_estimation
The modeling of real world data using estimation by maximum likelihood offers a way of tuning the free parameters of the model to provide a good fit. For a fixed set of data and underlying probability model, maximum likelihood picks the values of the model parameters that make the data "more likely" than any other values of the parameters would make them.

standard least-squares
weighted least-squares : linear measurements corrupted by errors with unequal variances

regularization
Regularization involves introducing additional information in order to solve an ill-posed problem or prevent overfitting. This information is usually of the form of a penalty for complexity, such as restrictions for smoothness or bounds on the vector space norm. A theoretical justification for regularization is that it attempts to impose Occam's razor on the solution. From a Bayesian point of view, many regularization techniques correspond to imposing certain prior distributions on model parameters

1.2.2 Linear programming

http://en.wikipedia.org/wiki/Linear_programming

Dantzig's simplex method

lpch3_simplex_method.pdf

Simplex Method A good tutorial for Simplex Method with examples (also two-phase and M-method). Department of Mathematics, CUHK

Interior-point method (barrier methods)
http://en.wikipedia.org/wiki/Interior_point_method

http://en.wikipedia.org/wiki/Chebyshev_approximation#Chebyshev_approximation
expanding the given function in terms of Chebyshev polynomials and then cutting off the expansion at the desired degree

Chebyshev approximation problem can be reduced to a linear program.

1.3 Convex optimization

The least-squares problem and linear programming problem are both special cases of the general convex optimization problem.

http://en.wikipedia.org/wiki/Second-order_cone_programming
equivalent to a convex Quadratically constrained quadratic program

http://en.wikipedia.org/wiki/Geometric_programming
Geometric programs are not (in general) convex optimization problems, but they can be transformed to convex problems by a change of variables and a transformation of the objective and constraint functions.

many tricks for transforming convex optimization problems

"recognizing and formulating convex optimization problems"

1.4 Nonlinear optimization

http://en.wikipedia.org/wiki/Nonlinear_programming

1.4.1 Local optimization

to require
- differentiability of the objective and constraint functions
- initial guess (or starting point) for the optimization variable

1.4.2 Global optimization

worst-case analysis or verification of high value or safety-critical system

object funtion --> utility function
constraints --> prior knowledge about the possible paramter values

If the worst-case value is acceptable, we can certify the system as safe or reliable.
In cases where the value of certifying the performance is high, or the cost of being wrong about the reliability or safety is high.

1.4.3 Role of convex optimizatin in nonconvex problems

Initialization for local optimization

Convex heuristics for nonconvex optimization
- finding a sparse vector
- randomized algorithms

Bounds for global optimization
- relaxation
- Lagrangian relaxation --> Lagrangian dual problem

1.5 Outline

1.6 Notation

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 3 Convex Functions (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02
[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions (0)	2009.01.22
[Boyd & Vandenberghe] Appendix A: Mathematical background (0)	2009.01.09

posted by maetel

MEDM350: 미학

2009. 2. 8. 15:45

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

MEDM587: Special Lecture (III) on Special Effects

2009. 2. 8. 15:41

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background

2009. 2. 2. 20:54 @GSMC/서용덕: Convex Optimization

C.1 Matrix structure and algorithm complexity

C.2 Solving linear equations with factored matrices

C.3 LU, Cholesky, and LDL^t facotrization

C.4 Block elimination and Schur complements

C.5 Solving underdetermined linear equations

http://en.wikipedia.org/wiki/QR_decomposition

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

http://en.wikipedia.org/wiki/LU_decomposition

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

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions (0)	2009.01.22
[Boyd & Vandenberghe] Appendix A: Mathematical background (0)	2009.01.09
Boyd & Vandenberghe <Convex Optimization> (0)	2009.01.05

posted by maetel

[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions

2009. 1. 22. 20:43 @GSMC/서용덕: Convex Optimization

B.1 Single constraint quadratic optimization

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02
[Boyd & Vandenberghe] Appendix A: Mathematical background (0)	2009.01.09
Boyd & Vandenberghe <Convex Optimization> (0)	2009.01.05

posted by maetel

[Boyd & Vandenberghe] Appendix A: Mathematical background

2009. 1. 9. 11:03 @GSMC/서용덕: Convex Optimization

해석학 解析學
대수학과 기하학에 대하여, 함수의 연속성에 관한 성질을 미분 및 적분의 개념을 기초로 하여 연구하는 수학. 미적분학, 미분 방정식론, 적분 방정식론, 집합론, 실함수론, 복소수 함수론 따위가 있다

http://en.wikipedia.org/wiki/Mathematical_analysis

대수학 (代數學)
개개의 숫자 대신에 숫자를 대표하는 일반적인 문자를 사용하여 수의 관계, 성질, 계산 법칙 따위를 연구하는 학문. 현재는 덧셈이나 곱셈 같은 요소 간의 결합이 정의된 집합, 즉 대수계를 연구하는 학문도 포괄한다.

http://en.wikipedia.org/wiki/Algebra
the study of structure, relation, and quantity
Linear algebra, in which the specific properties of vector spaces are studied (including matrices);

선형대수학 (線型代數學)
벡터, 행렬, 행렬식, 벡터 공간, 선형 사상 따위를 연구하는 학문. 대수학의 한 분야이다.

A.1 Norms
A.1.1 Inner product, Euclidean norm, and angle

In mathematics, the dot product, also known as the scalar product, is an operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. It is the standard inner product of the orthonormal Euclidean space.
( Inner product spaces generalize Euclidean spaces (in which the inner product is the dot product, also known as the scalar product) to vector spaces of any (possibly infinite) dimension, and are studied in functional analysis. )

http://en.wikipedia.org/wiki/Norm_(mathematics)#Euclidean_norm
a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector.
The Euclidean norm is often known as the magnitude.

http://en.wikipedia.org/wiki/Lp_space
spaces of p-power integrable functions, and corresponding sequence spaces. They are sometimes called Lebesgue spaces

http://en.wikipedia.org/wiki/Cauchy-Schwarz_inequality

http://en.wikipedia.org/wiki/Frobenius_norm#Frobenius_norm

A.1.2 Norms, distance, and unit ball

http://en.wikipedia.org/wiki/Homogeneous_function
a homogeneous function is a function with multiplicative scaling behaviour: if the argument is multiplied by a factor, then the result is multiplied by some power of this factor.
(In mathematics, science (including computer science), linguistics and engineering, an argument is, generally speaking, an independent variable or input to a function.)

http://en.wikipedia.org/wiki/Triangle_inequality

http://en.wikipedia.org/wiki/Unit_sphere
a closed unit ball is the set of points of distance less than or equal to 1 from a fixed central point

http://en.wikipedia.org/wiki/Closure_(topology)
Let S be a subset of a topological space X. Then x is a point of closure of S if every neighbourhood of x contains a point of S.

A.2 Analysis

A.3 Functions

A.4 Derivatives
A.4.1 Derivative and gradient

http://en.wikipedia.org/wiki/Derivative

int dom = interior domain

http://en.wikipedia.org/wiki/Domain_(mathematics)

In general, the interior of something refers to the space or part inside of it, excluding any kind of wall or boundary around its outside.
In mathematics, the interior of a set S consists of all points of S that are intuitively "not on the edge of S". A point that is in the interior of S is an interior point of S.
http://planetmath.org/?op=getobj&from=objects&id=3123

http://en.wikipedia.org/wiki/Jacobian
Jacobian Matrix = the matrix of all first-order partial derivatives of a vector-valued function. That is, the Jacobian of a function describes the orientation of a tangent plane to the function at a given point.

http://en.wikipedia.org/wiki/Exterior_derivative

http://en.wikipedia.org/wiki/Open_set
a set U is called open if, intuitively speaking, starting from any point x in U one can move by a small amount in any direction and still be in the set U. In other words, the distance between any point x in U and the edge of U is always greater than zero. (The openness property of a set is not topologically intrinsic. Taking a half-interval as a stand-alone space then it is open, since by definition the whole space is both open and closed. Virtually, the term open is applied to subsets.)

http://en.wikipedia.org/wiki/Gradient
the gradient of a scalar field is a vector field which points in the direction of the greatest rate of increase of the scalar field, and whose magnitude is the greatest rate of change.
A generalization of the gradient for functions on a Euclidean space which have values in another Euclidean space is the Jacobian. A further generalization for a function from one Banach space to another is the Fréchet derivative.

http://en.wikipedia.org/wiki/Symmetric_matrix
(Using the Jordan normal form, one can prove that every square real matrix can be written as a product of two real symmetric matrices, and every square complex matrix can be written as a product of two complex symmetric matrices. (Bosch, 1986))

http://en.wikipedia.org/wiki/Basis_(linear_algebra)
a basis is a set of vectors that, in a linear combination, can represent every vector in a given vector space or free module, and such that no element of the set can be represented as a linear combination of the others. In other words, a basis is a linearly independent spanning set.

http://en.wikipedia.org/wiki/Basis_(topology)
a base (or basis) B for a topological space X with topology T is a collection of open sets in T such that every open set in T can be written as a union of elements of B. We say that the base generates the topology T.

http://en.wikipedia.org/wiki/Affine_transformation
an affine transformation or affine map or an affinity (from the Latin, affinis, "connected with") between two vector spaces (strictly speaking, two affine spaces) consists of a linear transformation followed by a translation:

$x \mapsto A x+ b.$

In the finite-dimensional case each affine transformation is given by a matrix A and a vector b, satisfying certain properties described below.

http://en.wikipedia.org/wiki/Transformation_(geometry)
a transformation could be any function from a set X to itself. However, often the set X has some additional algebraic or geometric structure and the term "transformation" refers to a function from X to itself which preserves this structure.

http://en.wikipedia.org/wiki/Trace_(linear_algebra)
the trace of a matrix is the sum of its eigenvalues, making it an invariant with respect to a change of basis.
The trace of the identity matrix is the dimension of the space.

http://en.wikipedia.org/wiki/Jordan_normal_form

http://en.wikipedia.org/wiki/Eigenvalue,_eigenvector_and_eigenspace

A.4.2 Chain rule

http://en.wikipedia.org/wiki/Chain_rule

$\frac {dy}{dx} = \frac {dy} {du} \cdot\frac {du}{dx}.$

http://en.wikipedia.org/wiki/Directional_derivative

$\nabla_{\vec{v}}{f}(\vec{x}) = \lim_{h \rightarrow 0}{\frac{f(\vec{x} + h\vec{v}) - f(\vec{x})}{h}}.$

A.4.3 Second derivative

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02
[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions (0)	2009.01.22
Boyd & Vandenberghe <Convex Optimization> (0)	2009.01.05

posted by maetel

Boyd & Vandenberghe <Convex Optimization>

2009. 1. 5. 22:17 @GSMC/서용덕: Convex Optimization

Convex Optimization

(공)저: Stephen P. Boyd, Lieven Vandenberghe

기고가 Lieven Vandenberghe

출판사: Cambridge University Press, 2004

ISBN 0521833787, 9780521833783

716페이지

http://www.ee.ucla.edu/~vandenbe/cvxbook.html

http://www.stanford.edu/~boyd/cvxbook/

pdf 다운로드

저자 강의 동영상 (EE364a: Lecture Videos)
Professor Stephen Boyd, Stanford University, Winter Quarter 2007–08
http://www.stanford.edu/class/ee364/videos.html
http://see.stanford.edu/SEE/lecturelist.aspx?coll=2db7ced4-39d1-4fdb-90e8-364129597c87

http://www.ee.washington.edu/class/578/fazel/

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

[Boyd & Vandenberghe] Chapter 2 Convex Sets (0)	2009.02.23
[Boyd & Vandenberghe] Chapter 1 Introduction (0)	2009.02.19
[Boyd & Vandenberghe] Appendix C: Numerical linear algebra background (0)	2009.02.02
[Boyd & Vandenberghe] Appendix B: Problems involving two quadratic functions (0)	2009.01.22
[Boyd & Vandenberghe] Appendix A: Mathematical background (0)	2009.01.09

posted by maetel

Ch.10 Image Understanding

2008. 12. 15. 17:45 @GSMC/박래홍: Computer Vision

464p

10.3 Point distribution models

http://en.wikipedia.org/wiki/Point_distribution_model

Autostitch

1. Aligning the training data
the transformations to reduce (in a least-squares sense) the difference between an aligned shape and a 'mean' shape

2. Deriving the model
The eigen-vectors of then 2N*2N covariance matrix S will provides a basis, meaning that we can represent any vector x as a linear combination of the 2N different p_i.

http://en.wikipedia.org/wiki/Principle_Component_Analysis
the components of a basis vactor indicate how much variation is exhibited with respect to each of the eigenvectors

-> dimensinal compression of the representation

3. Fitting models to data

http://en.wikipedia.org/wiki/Eigenvalue,_eigenvector_and_eigenspace

http://en.wikipedia.org/wiki/Active_shape_model

Tim Cootes <An Introduction to Active Shape Models>

asm_overview.pdf

- overview paper about ASMs and AAMs (a useful introduction)

asm_aam_overview[1].pdf

4. Extensions

475p

10.4 Active Appearance Models

1. Modeling image appearance

http://en.wikipedia.org/wiki/Hidden_Markov_model

'@GSMC > 박래홍: Computer Vision' 카테고리의 다른 글

Ch.9 Object Recognition (0)	2008.11.25
2.4 Color images & 2.5 Cameras (0)	2008.10.16
Ch. 6 Segmentation I (0)	2008.09.20
Ch. 2 The image, its representations and properties (0)	2008.09.10
Ch.1 Introduction (0)	2008.09.04

posted by maetel

hw4 - non-linear least squares, illumination, least-squares model fitting

2008. 12. 8. 05:22

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

password

Lecture 11: Light & Reflection

2008. 12. 4. 17:45 @GSMC/이상욱: Principles of Human and Artificial Vision

BRDF
http://en.wikipedia.org/wiki/BRDF

radiant intensity

> radiant
1) Warn's Spotlight
2) isotropic point source
3) distance directional source

projected solid angle
hemispherical source
disk source
spherical source

http://en.wikipedia.org/wiki/Albedo

> reflection equation
1) perfectly diffuse reflection

http://en.wikipedia.org/wiki/Lambert%27s_cosine_law

2) common diffuse reflection

3) perfectly specular reflection

> diffuse interface reflection
non-Lambertian (Specular) diffuse
Cook-Torrance Model (Torrance-Sparrow Model)

Shape Recovery from Photometry

reflectance map

photometric stereo

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

hw4 - non-linear least squares, illumination, least-squares model fitting (0)	2008.12.08
Lecture 10: Uncalibrated Multi-view Geometry - Reconstruction (0)	2008.12.04
Lecture 9: Multi-view Geometry (0)	2008.12.04
Lecture 8: Uncalibrated Multiple-View Geometry: Fundamental Matrix (0)	2008.10.28
Lecture 7: Image Filtering & Edge Detection (0)	2008.10.28

posted by maetel

Lecture 10: Uncalibrated Multi-view Geometry - Reconstruction

2008. 12. 4. 17:26 @GSMC/이상욱: Principles of Human and Artificial Vision

Projective reconstruction
= Affine upgrade (H_p) + Euclidean upgrade (H_a)
=> Auto-calibration

Kruppa equations

kruppa.pdf

Kruppa’s Equations Derived from the Fundamental Matrix
Richard I. Hartley

Model Building
Image-based Rendering (IBR)

image rectification
epipolar rectification

http://www.robots.ox.ac.uk/~vgg/hzbook/index.html

http://cs.gmu.edu/~kosecka/lectures.html

Range Imaging
Range Sensor Calibration

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

hw4 - non-linear least squares, illumination, least-squares model fitting (0)	2008.12.08
Lecture 11: Light & Reflection (0)	2008.12.04
Lecture 9: Multi-view Geometry (0)	2008.12.04
Lecture 8: Uncalibrated Multiple-View Geometry: Fundamental Matrix (0)	2008.10.28
Lecture 7: Image Filtering & Edge Detection (0)	2008.10.28

posted by maetel

Lecture 9: Multi-view Geometry

2008. 12. 4. 17:22 @GSMC/이상욱: Principles of Human and Artificial Vision

calibrated vs. uncalibrated

essential matrix - calibrated cameras (K=I)

fundamental matrix - uncalibrated cameras

reconstruction via factorization

ref.
Olivier Faugeras Quang-Tuan Luong, Olivier Faugeras, Quang-Tuan Luong, Theo Papadopoulo
The Geometry of Multiple Images: The Laws That Govern the Formation of Multiple Images of a Scene and Some of Their Applications
서강대 e-book 보기

An Invitation to 3-D Vision
Yi Ma, Stefano Soatto, Jana Kosecka, Shankar Sastry
Springer Verlag, 2003

http://en.wikipedia.org/wiki/Kronecker_product

http://en.wikipedia.org/wiki/Matrix_decomposition

http://en.wikipedia.org/wiki/Eigenvalue

http://en.wikipedia.org/wiki/Newton-Raphson_iteration

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

Lecture 11: Light & Reflection (0)	2008.12.04
Lecture 10: Uncalibrated Multi-view Geometry - Reconstruction (0)	2008.12.04
Lecture 8: Uncalibrated Multiple-View Geometry: Fundamental Matrix (0)	2008.10.28
Lecture 7: Image Filtering & Edge Detection (0)	2008.10.28
Lecture 6: Multiple-View Geometry: Stereo, Motion, Features (0)	2008.10.27

posted by maetel

ch.7 Stochastic Methods

2008. 12. 3. 20:28 @GSMC/김경환: Pattern Recognition

350p

7.1 Introduction

search for finding acceptable model parameters

stochastic methods relied on randomness

(1) Boltzmann learning (from statistical mechanics in physics)

(2) genetic algorithms (from the mathematical theory of evolution in biology)

: preferable in complex problems
: high computational burden

351p

7.2 Stochastic Search

If we suggest an associated interaction energy of each pair of magnets,
then, to optimize the energy of the full system, we are to find the configuration of states of the magnets.

* Lyapunov functions http://en.wikipedia.org/wiki/Lyapunov_functions
objective functions http://en.wikipedia.org/wiki/Objective_function

7.2.1 Simulated Annealing

http://en.wikipedia.org/wiki/Annealing_(metallurgy )

http://en.wikipedia.org/wiki/Simulated_annealing

As the temperature is lowered, the system has increased probability of finding the optimum configuration.

successful in a wide range of energy functions or energy landscapes,
unlikely so in cases such as the "golf course landscape".

352p
7.2.2 The Boltzmann Factor

Boltzmann factor
http://en.wikipedia.org/wiki/Boltzmann_factor

partition function for a normalization constant
http://en.wikipedia.org/wiki/Partition_function_(statistical_mechanics )

http://en.wikipedia.org/wiki/Boltzmann_distribution

the # of configurations = 2^N

Fig.7.1 - Boltzmann networks is to indicate the state fo each node
: The optimization problem is to find a configuration (i.e., assignment of all s_i) that minimizes the energy.

Fig.7.2
: Simulated annealing method uses randomness, governed by a control parameter or "temperature" T.

The number of states declines exponentially with increasing energy.

Because of the statistical independence of the magnets, for large N the probability of finding the state in energy E also decays exponentially.

The dependence of the probability upon T in the Boltzmann factor:
At high T, the probability is distributed roughly evenly among all configurations, while at low T it is concetrated at the lowest-energy configurations.

In the case of large N, the number of configurations decays exponentially with the energy of the configuration.

> Simulated Annealing Algorithm
1) initiate randomized states & select a high initial temperature T
(in the simulation, T is a control parameter that will control the randomness)
2) choose randomly a node i with its state s_i = +1
3) calculate the system energy in this configuration
4) recalculate the energy for a candidate new state s_i = -1
5) accept this change in state if this candidate state has a lower energy, or if the energy is higher, accept this with a probability from the Boltzmann factor.
6) poll (select and test) the nodes randomly several times and set their states
7) lower the temperature and repeat the polling
8) simluated annealing terminates when the temperature is very low (near zero)
(if the cooling has been sufficiently slow, the system has a high probability of being in a low-energy state)

The occational acceptance of a state that is energetically less favorable allows the system to jump out of unacceptable local energy minima.

Algorithm 1. Stochastic Simulated Annealing

'@GSMC > 김경환: Pattern Recognition' 카테고리의 다른 글

ch.6 Multilayer Neural Networks (0)	2008.11.21
ch.5 Linear Discriminant Functions (0)	2008.11.02
ch.4 Nonparametric Techniques (0)	2008.10.21
ch.3 Maximum-Likelihood and Bayesian Parameter Estimation (0)	2008.10.08
ch.2 Bayesian Decision Theory (0)	2008.09.25

posted by maetel

Ch.9 Object Recognition

2008. 11. 25. 22:10 @GSMC/박래홍: Computer Vision

380p

pattern recognition
: classifying based on the features

http://en.wikipedia.org/wiki/Pattern_recognition

Knowledge about objects and their classes gives the necessary information for object classification.

381p

9.1 Knowledge representation

artificial intelligence (AI)
http://en.wikipedia.org/wiki/Artificial_intelligence

http://en.wikipedia.org/wiki/Knowledge_representation

knowledge representation design
- simple control strategies
- a rich, well structured representation of a large set of a priori data and hypotheses

syntax
-> the symbols that may be used and the ways that they may be arranged

semantics
-> how meaning is embodied in the symbols and the symbol arrangement allowed by the syntax

representation
-> a set of syntactic and semantic conventions that make it possible ot describe things

formal grammars and languages
predicate logic
production rules
semantic nets
frames
-> data structures (lists, trees, graphs, tables, hierarchies, sets, rings, nets, and matrices)

Descriptions, features
: scalar properties of objects -> feature vectors

Grammars, languages
- structures from primitives (elementary structural properties of the objects) and the relations between them
-> rules defining how the chains, trees, or graphs can be constructed from a set of symbols (primitives)

Predicate logic (술어논리)
- combinations of logic variables (true/false), quantifiers, and logic operators
- modus ponens and resolution
- PROLOG
- 'pure truth'
-> logic conditions and constraints into knowledge processing

Production rules
- condition action pairs
- procedural character of knowledge
=> handling uncertainty information -> expert systems

Fuzzy logic
- some reasonable threshold
- fuzzy rule
- linguistic variables

Semantic nets
- objects, their description, and a description of relations between objects
- local information and local knowledge
- relations between partial representations described at all appropriate hierarchical levels (nodes: objects / arcs: relations between objects)
- degrees of closeness

Frames, scripts
- a substitute for missing information
-> to overcome the lack of continuous information
- a tool for organizing knowledge in prototypical objects, and for description of mutual influences of objects using stereotypes of behavior in specific situations

386p

9.2 Statistical pattern recognition

object recognition -- classifier --> assigning classes to objects

pattern
: formal description of sensed objects

The classes form clusters in the feature space, which can be separated by a discrimination curve (or hyper-surface in a multi-dimensional feature space).

If the discrimination hyper-surfaces are hyper-planes, it is called a linearly separable task.

387p
9.2.1 Classification principles

input - information about features from an object
output - decision about the class of the object
class identifiers - generated output symbols
decision rule - the function describing relations between the classifier inputs and the output
discrimination functions - scalar functions defining the discrimination hyper-surfaces

The determination of discrimination hyper-surfaces (or definition of the decision rule) is the goal of classifier design.

decision rule of a classifier
(1) find a maximum discrimination function -> linear classifier
(2) calculate the minimum distance from exemplars (sample patterns) -> piecewise linear discrimination hyper-planes

Φ-classifier
non-linear discrimination hypersurfaces of the original feature space -- non-linear transformation --> hyper-planes in the transformed freature space

390p
9.2.2 Classifier setting

Settings of the optimal classifier should be probabilistic.

optimality criteria: the value of the mean loss caused by classification

optimum decision rule:
minimum mean loss + the vector of optimal parameters

(1) minimum error criterion (Bayes criterion, maximum likelihood)

minimum-loss optimality criterion

Bayes formula
- a posteriori probabilities of classes, the conditional probability densities of objects, a priori probability, the mixture density

theoretical optimum
: "no other classifier setting can give a lower probability of the decision loss."

posteriori probabilities -- a classifier --> corresponding discrimination hyper-surfaces

(2) best approximation criterion
: the best approximation of discrimination functions by linear combinations of pre-determined functions

classifier learning: training set --> classification parameters

The information obtained from the elements of the training set must be generalized to cover the whole feature space.
(=> The classifier should be able to recognize even those objects that it has never seen before.)

sequential increase in training set size -> sequential processing of information -> classification correctness

learning: the process of automated system optimization based on the sequential presentation of examples, to minimize the optimality criterion

object description
- permissible classification error
- complexity of the classifier construction
- time required for classification
-> determination of informativity and discriminativity of measured features

393p
9.2.3 Classifier learning

(1) probability density estimation
-> minimum error criterion -> discriminant functions

priori information -> the shape of probability density functions => parametric learning

eg. normal distribution - dispersion matrix, mean value vector
+ priori estimate + confidence (weight)

(2) direct loss minimization
-> best approximation criterion -> decision rule

no prior information -> stochastic approximations
http://en.wikipedia.org/wiki/Stochastic_approximation

Jack Sklansky
Pattern Classifiers and Trainable Machines

minimum distance classifier

396p
9.2.4 Support Vector Machines

http://en.wikipedia.org/wiki/Support_vector_machines

maximizing the width of the empty area (margin) between the two classes

The margin width is defined as the distance between the discrimination hypersurface in n-dimensional feature space and the closest training patterns called support vectors.
-> An optimal hypersurface has the lowest capacity.

The support vectors specify the discrimination function.

To maximize the margin, we need to minimize ∥w∥ for a quadratic programming optimization problem.

( http://en.wikipedia.org/wiki/Lagrangian 아니고 이거 http://en.wikipedia.org/wiki/Lagrange_multipliers )

If we want to solve:

maximize $f\left( x, y \right)$

subject to $g\left( x, y \right) = c$

We introduce a new variable ( $λ$ ) called a Lagrange multiplier to rewrite the problem as:

maximize $f\left( x, y \right) + \lambda\left( g\left( x, y \right) - c \right)$

Solving this new unconstrained problem for x, y, and $λ$ will give us the solution (x, y) for our original constrained problem. The gradients of $f$ and $g$ are parallel vectors at the maximum, since the gradients are always normal to the contour lines. This occurs just when the gradient of $f$ has no component tangential to the level sets of $g$ . This condition is equivalent to $\nabla_{x,y} f(x,y) = \lambda \nabla_{x,y} g(x,y)$ for some $λ$ .

$F \left( x , y, \lambda \right) = f \left(x, y \right) + \lambda \left(g \left(x, y \right) - c \right),$

and solve

$\nabla_{x,y,\lambda} F \left( x , y, \lambda \right)=0$ .

Lagrange duality

Given a convex optimization problem in standard form

$\begin{align} \text{minimize } &f_0(x) \\ \text{subject to } &f_i(x) \leq 0,\ i \in \left \{1,\dots,m \right \} \\ &h_i(x) = 0,\ i \in \left \{1,\dots,p \right \} \end{align}$

with the domain $\mathcal{D} \subset \mathbb{R}^n$ having non-empty interior, the Lagrangian function $L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ is defined as

$L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x).$

The vectors $λ$ and $ν$ are called the dual variables or Lagrange multiplier vectors associated with the problem. The Lagrange dual function $g:\mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ is defined as

$g(\lambda,\nu) = \inf_{x\in\mathcal{D}} L(x,\lambda,\nu) = \inf_{x\in\mathcal{D}} \left ( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right ).$

The dual function $g$ is concave, even when the initial problem is not convex. The dual function yields lower bounds on the optimal value $p *$ of the initial problem; for any $\lambda \geq 0$ and any $ν$ we have $g(\lambda,\nu) \leq p^*$ . If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality, i.e. $d^* = \max_{\lambda \ge 0, \nu} g(\lambda,\nu) = \inf f_0 = p^*$ .

ref.
Lagrange Multipliers without Permanent Scarring

lagrange-multipliers[1].pdf

Dan Klein (Assistant Professor, Computer Science Division, University of California at Berkeley)

http://en.wikipedia.org/wiki/Karush-Kuhn-Tucker_conditions
a generalization of the method of Lagrange multipliers to inequality constraints.

Each of the Lagrange multipliers shares the corresponding support vectors.

The discrimination hyperplane in the feature space can be obrained from vectors in the input space and dot products in the feature space.

ref.
Dmitriy Fradkin and Ilya Muchnik "Support Vector Machines for Classification" in J. Abello and G. Carmode (Eds) "Discrete Methods in Epidemiology", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 70, pp. 13-20, 2006.

svm[1].pdf

Succinctly describes theoretical ideas behind SVM.

soft margin -> support vector machine

kernel trick to determine the similarity of two patterns
http://en.wikipedia.org/wiki/Kernel_trick

(eg. Gaussian radial basis fn. kernel -> Hilbert space)

402p
9.2.5 Cluster analysis

http://en.wikipedia.org/wiki/Cluster_analysis

1) MacQueen k-means
http://en.wikipedia.org/wiki/K-means_algorithm

within-cluster variance

2) ISODATA cluster analysis

3) mean shift algorithm

4) fuzzy c-means algorithm

5) expectation-maximazation algorithm
http://en.wikipedia.org/wiki/Expectation-maximization_algorithm
EM alternates between performing an expectation (E) step, which computes an expectation of the likelihood by including the latent variables as if they were observed, and a maximization (M) step, which computes the maximum likelihood estimates of the parameters by maximizing the expected likelihood found on the E step. The parameters found on the M step are then used to begin another E step, and the process is repeated.

404p

9.3 Neural nets

http://en.wikipedia.org/wiki/Neural_net

ref.
Ben Krose & Patrick van der Smagt <An introduction to Neural Networks>

nn_intro[1].pdf

9.3.1 Feed-forward networks

9.3.2 Unsupervised learning

9.3.3 Hopfield neural nets

http://en.wikipedia.org/wiki/Hopfield_neural_network

410p

9.4 Syntactic pattern recognition

9.4.1 Grammers and languages

formal language

9.4.2 Syntactic analysis, syntactic classifier

9.4.3 Syntactic classifier learning, grammar inference

418p

9.5 Recognition as graph matching

9.5.1 Isomorphism of graphs and sub-graphs

9.5.2 Similarity of graphs

424p

9.6 Optimization techniques in recognition

9.6.1 Genetic algorithms

Reproduction
Crossover
Mutation

9.6.2 Simulated annealing

430p

9.7 Fuzzy systems

9.7.1 Fuzzy sets and fuzzy membership functions

'@GSMC > 박래홍: Computer Vision' 카테고리의 다른 글

Ch.10 Image Understanding (0)	2008.12.15
2.4 Color images & 2.5 Cameras (0)	2008.10.16
Ch. 6 Segmentation I (0)	2008.09.20
Ch. 2 The image, its representations and properties (0)	2008.09.10
Ch.1 Introduction (0)	2008.09.04

posted by maetel

Search

Tag

Notice

Recent Post

Recent Comment

Recent Trackback

Archive

My Link

calendar

Category

'@GSMC'에 해당되는 글 122건

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC' 카테고리의 다른 글

'@GSMC > 홍대형: Statistical Communication Theory' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 서용덕: Convex Optimization' 카테고리의 다른 글

'@GSMC > 박래홍: Computer Vision' 카테고리의 다른 글

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

'@GSMC > 이상욱: Principles of Human and Artificial Vision' 카테고리의 다른 글

'@GSMC > 김경환: Pattern Recognition' 카테고리의 다른 글

'@GSMC > 박래홍: Computer Vision' 카테고리의 다른 글

티스토리툴바