0%

Introduction

Optimization is a focus on many kinds of machine learning algorithms like Linear Regression, SVM and K-means. But actually many kinds of target function is non-convex which means we can only find its local minima. But convex functions still plays an important role in machine learning. And Hessian Matrix is a great algebra tool to analyze convex functions since in most cases our target function will be real, continuous and $2^{nd}$-order differentiable. The main goal of this article is to record the proof of the equivalence between Convex Functions and their Hessians. Here is the some important definitions.

Convex Set

A Convex Set $C\subseteq \Re^n$ is a set of points s.t. $\forall x, y \in C$ and $t \in [0,1]$, $tx+(1-t)y \in C$.

Convex Function

A function $f:\Re^n \rightarrow \Re$ is a Convex Function if for $x, y \in D$, where $D$ is a convex set, $f$ and any $t \in [0,1]$ makes

Hessian Matrix

A Hessian Matrix is a square matrix of second-order partial derivatives of a function $f:\Re^n \rightarrow \Re$, usually written as:

Positive Definite/Semi-Definite Matrix

A real symmetric matrix $P$ is called Positive Semi-Definite (PSD) when for all $x \in \Re^n$, there are $x^TPx \geq 0$. And it’s called Positive Definite (PD) when for all $x \neq 0 \in \Re^n$, there are $x^TPx > 0$.

Read more »

Introduction

In this article I will try to solve Best Time to Buy and Sell Stock series problem, including Best Time to Buy and Sell Stock I, II, III, IV and with Cooldown. Most of them are solved by dynamic programming and I will focus on construct transition equation and dimension reduction.

Description

The description of Best Time to Buy and Sell Stock I is:

Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example:

1
2
3
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Read more »

Introduction

In this article I will describe two dynamic programming algorithms solving LIS problem and STL functions lower_bound() and upper_bound().

Description

Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:

Input: $[10,9,2,5,3,7,101,18]$
Output: 4
Explanation: The longest increasing subsequence is $[2,3,7,101]$, therefore the length is $4$.

Read more »

Description

Design and implement a data structure for Least Recent Used(LRU) cache. It should support the following operations: get and put.

get(key) -Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) -Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Basic Idea

To solve this problem, we need to design a kind of data structure with the properties as follow:

  1. The data structure can visit the and set/insert the item as soon as possible(such as vector or map).
  2. The data structure can order the data by the operation time.
  3. The data structure can quickly check for the overflow of capacity.

Due to the data structure in different language is not the same, I will choose python and cpp as my solution language.

Read more »

Description

Given a linked list and return where the circle begins. For example, a linked list $[3, 2, 0, 4]$ having circle $[2, 0, 4]$ is shown below.

Linked_circle

The algorithm should return the second node. I use C++ to solve this problem and define the node as below.

1
2
3
4
5
6
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
Read more »