Hong, LiangJie

In this post, I would like to show how to create a tuple object in C++ 11 and how to sort tuples.

Here is the code for creating tuples and doing the sort. It is pretty straightforward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
 
typedef tuple<string,double,int> mytuple;
 
bool mycompare (const mytuple &lhs, const mytuple &rhs){
  return get<1>(lhs) < get<1>(rhs);
}
 
int main(void){
  vector<mytuple> data;
  data.push_back(make_tuple("abc",4.5,1));
  data.push_back(make_tuple("def",5.5,-1));
  data.push_back(make_tuple("wolf",-3.47,1));
  sort(data.begin(),data.end(),mycompare);
  for(vector<mytuple>::iterator iter = data.begin(); iter != data.end(); iter++){
    cout << get<0>(*iter) << "\t" << get<1>(*iter) << "\t" << get<2>(*iter) << endl;
  }
}

The code is successfully compiled by G++ 4.6.1 with the option “-std=gnu++0x”.

There are two forms of Logistic Regression used in literature. In this post, I will build a bridge between these two forms and show they are equivalent.

Logistic Function & Logistic Regression

The common definition of Logistic Function is as follows:
\[
P(x) = \frac{1}{1+\exp(-x)} \;\; \qquad (1)
\] where \(x \in \mathbb{R} \) is the variable of the function and \(P(x) \in [0,1]\). One important property of Equation (1) is that:
\[ \begin{eqnarray}
P(-x) &=& \frac{1}{1+\exp(x)} \nonumber \\
&=& \frac{1}{1+\frac{1}{\exp(-x)}} \nonumber \\
&=& \frac{\exp(-x)}{1+\exp(-x)} \nonumber \\
&=& 1 - \frac{1}{1+\exp(-x)} \nonumber \\
&=& 1 - P(x) \; \; \qquad (2)
\end{eqnarray} \]The form of Equation (2) is widely used as the form of Logistic Regression (e.g., [1,2,3]):
\[ \begin{eqnarray}
P(y = 1 \, | \, \boldsymbol{\beta}, \mathbf{x}) &=& \frac{\exp(\boldsymbol{\beta}^{T} \mathbf{x})}{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})} \nonumber \\
P(y = 0 \, | \, \boldsymbol{\beta}, \mathbf{x}) &=& \frac{1}{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})} \;\; \qquad (3)
\end{eqnarray} \] where \(\mathbf{x}\) is a feature vector and \(\boldsymbol{\beta}\) is a coefficient vector. By using Equation (2), we also have:
\[ \begin{equation}
P(y=1 \, | \, \boldsymbol{\beta}, \mathbf{x}) = 1 - P(y=0 \, | \, \boldsymbol{\beta}, \mathbf{x})
\end{equation} \] This formalism of Logistic Regression is used in [1,2] where labels \( y \in \{0,1\} \) and the functional form of the probability to generate different labels is different. Another formalism introduced in [3] unified the two forms into one single equation by integrating the label and the prediction together:
\[ \begin{equation}
P(g= \pm 1 \, | \, \boldsymbol{\beta}, \mathbf{x}) = \frac{1}{1 + \exp( - g\boldsymbol{\beta}^{T} \mathbf{x})} \;\; \qquad (4)
\end{equation} \]where \( g \in \{\pm 1\} \) is the label for data item \( x \). It is also easily to verify that \( P(g=1 \, | \, \boldsymbol{\beta}, \mathbf{x}) = 1 – P(g=-1 \, | \, \boldsymbol{\beta}, \mathbf{x}) \).

The Equivalence of Two Forms of Logistic Regression

At first glance, the form (3) and the form (4) looks very different. However, the equivalence between these two forms can be easily established. Starting from the form (3), we can have:
\[ \begin{eqnarray}
P(y = 1 \, | \, \boldsymbol{\beta}, \mathbf{x}) &=& \frac{\exp(\boldsymbol{\beta}^{T} \mathbf{x})}{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})} \nonumber \\
&=& \frac{1}{\frac{1}{\exp(\boldsymbol{\beta}^{T} \mathbf{x})} + 1} \nonumber \\
&=& \frac{1}{\exp(-\boldsymbol{\beta}^{T} \mathbf{x}) + 1} \nonumber \\
&=& P(g= 1 \, | \, \boldsymbol{\beta}, \mathbf{x})
\end{eqnarray} \]We can also establish the equivalence between \( P(y=0 \, | \, \boldsymbol{\beta}, \mathbf{x})\) and \(P(g=-1 \, | \, \boldsymbol{\beta}, \mathbf{x})\) easily by using property (2). Another way to establish the equivalence is from the classification rule. For the form (3), we have the following classification rule:
\[ \begin{eqnarray}
\frac{\frac{\exp(\boldsymbol{\beta}^{T} \mathbf{x})}{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})}}{\frac{1}{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})}} & > & 1 \;\; \rightarrow \;\; y = 1 \nonumber \\
\exp(\boldsymbol{\beta}^{T} \mathbf{x}) & > & 1 \nonumber \\
\boldsymbol{\beta}^{T} \mathbf{x} & > & 0
\end{eqnarray} \]An exactly same classification rule for the form (4) can also be obtained as:
\[ \begin{eqnarray}
\frac{\frac{1}{1 + \exp( - \boldsymbol{\beta}^{T} \mathbf{x})}}{\frac{1}{1 + \exp( \boldsymbol{\beta}^{T} \mathbf{x})}} & > & 1 \;\; \rightarrow \;\; g = 1 \nonumber \\
\frac{1 + \exp(\boldsymbol{\beta}^{T} \mathbf{x})}{1 + \exp( - \boldsymbol{\beta}^{T} \mathbf{x})} & > & 1 \nonumber \\
\exp(\boldsymbol{\beta}^{T} \mathbf{x}) & > & 1 \nonumber \\
\boldsymbol{\beta}^{T} \mathbf{x} & > & 0
\end{eqnarray} \] Therefore, we can see that two forms essentially learn the same classification boundary.

Logistic Loss

Since we establish the equivalence of two forms of Logistic Regression, it is convenient to use the second form as it can be explained by a general classification framework. Here, we assume \( y \) is the label of data and \( \mathbf{x} \) is a feature vector. The classification framework can be formalized as follows:
\[ \begin{equation}
\arg\min \sum_{i} L\Bigr(y_{i},f(\mathbf{x}_{i})\Bigl)
\end{equation}\]where \(f\) is a hypothesis function and \(L\) is loss function. For Logistic Regression, we have the following instantiation:
\[ \begin{eqnarray}
f(\mathbf{x}) &=& \boldsymbol{\beta}^{T} \mathbf{x} \nonumber \\
L\Bigr(y,f(\mathbf{x})\Bigl) &=& \log \Bigr( 1 + \exp(-y f(\mathbf{x})\Bigl)
\end{eqnarray}\]where \(y \in \{ \pm 1 \}\).

References

[1] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
[2] Tom M. Mitchell. Machine learning. McGraw Hill series in computer science. McGraw-Hill, 1997.
[3] Jason D. M. Rennie. Logistic Regression. http://people.csail.mit.edu/jrennie/writing, April 2003.

In this post, I would like to share some simple code to calculate geographical distances by using latitude and longitude points from some third-party services. This is particular useful when we wish to compute the average distances users travel from the check-in or geo-tagging information from Twitter, for instance. The code is straightforward and simple.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

import math
import sys
import os
 
## Convert a location into 3d Corordinates
## location is a list of [latitude,longtidue]
## return: a list of [x,y,z]
def convert_location_cor(location):
    x_n = math.cos(math.radians(location[0])) * math.cos(math.radians(location[1]))
    y_n = math.cos(math.radians(location[0])) * math.sin(math.radians(location[1]))
    z_n = math.sin(math.radians(location[0]))
    return [x_n,y_n,z_n]
 
## Convert a 3d Corordinates into a location
## cor is a list of [x,y,z]                                                                                                                          
## return: a list of [latitude, longtitude]
def convert_cor_location(cor):
    r = math.sqrt(cor[0] * cor[0] + cor[1] * cor[1]+ cor[2] * cor[2])
    lat = math.asin(cor[2] / r)
    log = math.atan2(cor[1], cor[0])
    return [math.degrees(lat),math.degrees(log),math.degrees(r)]
 
## Compute the geographical midpoint of a set of locations
## location_list is a list of locations [locaiton 0, location 1, location 2]
## return: the location of midpoint                                                                                              
def geo_midpoint(location_list):
    x_list = []
    y_list = []
    z_list = []
    for i in range(len(location_list)):
	m = convert_location_cor(location_list[i])
	x_list.append(m[0])
	y_list.append(m[1])
	z_list.append(m[2])
    x_mean = sum(x_list) / float(len(location_list))
    y_mean = sum(y_list) / float(len(location_list))
    z_mean = sum(z_list) / float(len(location_list))
    return convert_cor_location([x_mean,y_mean,z_mean])
 
## Compute the distance between two locations
## a and b are two locations: [lat 1, lon 1] [lat 2, lon 2]
## return: the distance in KM
def geo_distance(a,b):
    theta = a[1] - b[1]
    dist = math.sin(math.radians(a[0])) * math.sin(math.radians(b[0])) \
     + math.cos(math.radians(a[0])) * math.cos(math.radians(b[0])) * math.cos(math.radians(theta))
    dist = math.acos(dist)
    dist = math.degrees(dist)
    distance = dist * 60 * 1.1515 * 1.609344
    return distance
 
## main program
if __name__ == '__main__':
    l_list = []
    l_list.append([-8.70934,115.173695])
    l_list.append([-8.70934,115.235514])
    l_list.append([-8.591728,115.235514])
    l_list.append([-8.591728,115.173695])
    midpoint = geo_midpoint(l_list)
    print geo_distance([-8.70934,115.173695],[-8.70934,115.235514])

I came across an old technical report written by Michael Jordan (no, not the basketball guy):

“Why the logistic function? A tutorial discussion on probabilities and neural networks“. M. I. Jordan. MIT Computational Cognitive Science Report 9503, August 1995.

The material is amazingly straightforward and easy to understand. It answers (or at least partially) a long-standing question for me, why the form of logistic function is used in regression? Regardless of how it was used in the first place, the report shows that it is actually can be derived from a simple binary classification case where we wish to estimate the posterior probability: \[ P(w_{0}|\mathbf{x}) = \frac{P(\mathbf{x}|w_{0})P(w_{0})}{P(\mathbf{x})} \]
where \( w_{0} \) can be thought as class label and \( \mathbf{x} \) can be treated as feature vector. We can expand the denominator and introduce an exponential:
\[ P(w_{0}|\mathbf{x}) = \frac{P(\mathbf{x}|w_{0})P(w_{0})}{P(\mathbf{x}|w_{0})P(w_{0})+P(\mathbf{x}|w_{1})P(w_{1})}=\frac{1}{1+\exp\{-\log a - \log b\}} \]
where \( a=\frac{P(\mathbf{x}|w_{0})}{P(\mathbf{x}|w_{1})} \) and \( b= \frac{P(w_{0})}{P(w_{1})} \). Without achieving anything but only through mathematical maneuvering, we have already had the flavor how logistic function can be derived from simple classification problems. Now, if we specify a particular distribution form of \( P(\mathbf{x}|w)\) ( the class-conditional densities), for instance, Gaussian distribution, we can recover the logistic regression easily.

However, the whole point of the report is not just to show where logistic function comes into play, but showing how discriminative models and generative models in this particular setting are only the two sides of the same coin. In addition, Jordan demonstrated that these two sides are simply NOT equivalent but should be treated carefully when different learning criteria is considered. In general, a simple take-away is that the discriminative model (logistic regression) is more “robust” where generative model might be more accurate if the assumption is correct.

More details, please refer to the report.