Thursday, August 28, 2008

Collaborative Filtering

Collaborative Filtering

유사한 취향을 가진 사람들의 작은 집합을 만드는 것. 일종의 클러스터링.

관련 논문으로 "Using collaborative filtering to weave an information tapestry" 이 있음.

  • Similarity score 계산
    사람(혹은 아이템) 간의 취향이 얼마나 비슷한지 정도를 계산할 수 있는데, 아래의 방법들이 있음
  • Euclidean distance score
    각각의 항목들을 축으로 놓고 특정 사람에 대한 항목별 선호도를 점으로 표시하면 두사람간의 거리를 계산하여 유사도를 구할 수 있는데 이를 유클리디안 거리점수 라고 한다. 항목이 두개 (x, y)인 경우 두 사람 A(x1, y1), B(x2, y2) 간의 거리는 y = sqrt( (x1 - x2)^2 + (y1 - y2)^2 ) 이다. 마찬가지로 n 개의 항목에 대한 유클리디안 거리점수를 계산하면 아래처럼 표시될 수 있다.

    y = sqrt( (a1 - a2)^2 + ... + (n1 - n2)^2 )

    일반적으로 이렇게 구한 거리 d 를 1/d식으로 활용하여 서로 유사할 수록 높은 점수를 주는 방식으로 사용한다.
  • Pearson correlation score
    두개의 데이처 집합이 한 직선으로 잘 표현되는 정도를 나타낸 것이 상관계수인데, 정규화되지 않은 데이터에 대해 좋은 결과를 제공한다. 각각의 값이 점으로 표시된 좌표에서 모든 점들과 가장 가까운 직선을 그릴 수 있는데 이를 최적맞춤선(best-fit line)이라고 한다. 여러 항목들에 대한 두사람의 선호도 데이터를 가지고 있다면 이 두사람을 각 좌표의 축에 놓고 best-fit line을 그릴 수 있다.
    이 직선을 통해서 대체적으로 누가 더 많은 점수를 주었는지를 파악할 수도 있는데, 이를 grade inflation이라고 한다. 한쪽이 더 높은 점수를 꾸준하게 주었어도 선호도가 비슷하다면 직선으로 잘 표현될 수도 있다.
    때문에 Euclidean distance에서는 한쪽이 전체적으로 낮은 점수를 주었으면 두 사람의 유사도가 낮게 나오는 반면 Pearson correlation score에서는 이를 유사한 것으로 뽑아낼 수 있다.
    아래의 두 사람의 데이터에 대한 Pearson correlation score를 뽑아낸다고 하면,

    m1[] = { a1, a2, ... , an}
    m2[] = { b1, b2, ... , bn}

    아래와 같은 식으로 상관계수 값을 도출할 수 있다.

    sum1 = a1 + ... + an
    sum2 = b1 + ... + bn

    sq_sum1 = a1^2 + ... + an^2
    sq_sum2 = b1^2 + ... + bn^2

    mul_sum = a1 * b1 + ... + an * bn

    v1 = mul_sum - (sum1 * sum2 / n)
    v2 = sqrt( (sq_sum1 - (sum1^2) / n) * (sq_sum2 - (sum^2) / n) )

    return v2 == 0 ? 0 : n / v2

    값은 -1 ~ 1 사이이고 1은 모든 항목에 같은 점수를 준 것이다.

Thursday, August 21, 2008

Const pointer & pointer const

const pointer refers const variable.

pointer const refers variable constantly(Setting it to point another variable is not possible).

Wednesday, August 13, 2008

Advanced Generic Handle - Copy On Write

Generic Handle Class는 여러 클래스를 동일하게 다룰 수 있지만 메모리 복사가 많이 일어나는 오버헤드가 있다. Reference Count를 사용한 Generic Handle Class는 값을 항상 참조만 시키기 때문에 s2 = s1 처럼 대입하면 s2의 값을 바꾸었을때 s1의 값이 항상 바뀐다(같은 객체를 참조하니까). 때문에 경우에 따라 참조하고, 경우에 따라 복사를 하는 더 나은 형태의 Generic Handle Class 가 있으면 좋겠다.

즉, s3 = s2 = s1처럼 대입하면 실제 복사는 일어나지 않고 s3, s2가 s1의 레퍼런스만 가지고 있게 하다가, s3에 다른 새로운 값을 대입하거나 내부 멤버를 변경하는 작업이 일어날 때 비로소 s1의 멤버 값들을 복사한 후 s1에 대한 레퍼런스를 끊어 별개의 객체로 동작하게 하는 것이다.

linux memory management의 COW(Copy-On-Write)처럼 변경 사항이 일어날 때 비로소 복사를 하는 것이다.

실제 이러한 클래스를 구현하는 방법은 기존의 Reference Count를 사용하는 Generic Handle Class에 아래와 같이 reference count를 체크한 후 복사를 진행하는 멤버 함수를 추가한 후, 멤버를 변경시키는 함수 호출시 이 멤버함수를 실행시키면 된다.


template class Ptr {
public:
void make_uniue() {
if (*refptr != 1) {
--*refptr;
refptr = new size_t(1);
p = p ? p->clone() : 0;
}
}
...

Advanced Generic Handle - Reference Count

Generic Handle Class를 만들어 사용하게 되면 대입 연산과 같은 여러 작업을 진행할 때 불필요한 메모리 복사가 많이 일어나 오버헤드가 된다. 값을 읽기만 하기 위해 대입하는 경우 값을 복사하지 않고 레퍼런스만 넘겨주면 이를 줄일 수 있는데, 핸들 클래스를 통해 참조되는 값들은 동적으로 생성된 것들이기 때문에 해제를 하려면 자신을 참조하고 있는 객체가 몇개인지 확인해 보고 참조하고 있는 값이 없을 때 해제하면 된다.

이를 위해 제네릭 핸들 클래스에서 사용하는 방식이 reference count다. 복사나 대입 연산이 발생하는 경우 핸들 클래스에서 가지고 있는 reference count를 증가시키고 반대의 경우 감소시키는 방식으로 카운터를 유지하다가 레퍼런스가 없게 될 때 최종적으로 소멸시키게 된다.

Tuesday, August 12, 2008

Generic Handle Class

Handle Class는 기본 클래스에서 파생된 여러 클래스를 레퍼런스나 포인터를 통해 모두 다룰 수 있도록 캡슐화 해준다. 제대로 짠다면 이러한 Handle Class는 다루는 클래스에 대해 최대한 독립적이여야 한다. 그래서 다루는 클래스 자체를 탬플릿으로 선언하여 Handle Class를 구현하는데 이를 Generic Handle Class라고 한다.

핸들을 사용하기 않고 직접 저수준의 포인터를 사용하게 될 경우 아래와 같은 잠재적인 문제가 있다.

  • 포인터 복사만 하면 객체는 복사가 안된다.
  • 포인터 소멸시켜도 객체는 소멸 안된다.
  • 반대로 포인터를 두고 객체만 소멸시키면 Dangling Pointer가 된다.
  • 포인터 만들고 바인딩 안하고 쓰면 ... 알 수 없는 동작을 한다.

Generic Handle Class는 기본적으로 아래와 같은 기능을 제공한다.

  • Handle을 특정 객체를 참조하는 값으로 생각하면 된다.
  • 객체를 복사할 수 있다(복사 생성자, 대입연산자).
  • 바인딩 여부를 알 수 있다(bool() 연산을 정의하면 됨).
  • virtual 함수 호출을 통해 각 클래스별 메소드를 호출할 수 있다.

우리가 직접 포인터/레퍼런스를 쓰지 않고 핸들 클래스를 사용하기로 했기 때문에 당연히 이후부터는 객체를 포인터를 통해 직접 접근하면 안된다. 그리고 메모리 관리도 Handle Class에서 자동으로 해주므로 Handle을 소멸시키면 Handle에 연결된 객체도 같이 소멸된다.


template<class T> class Handle {
public:
Handle() : p(0) { }
Handle(const Handle& s) : p(0) { if(s.p) p = s.p->clone(); }
Handle& operator=(const Handle&);
~Handle() { delete p; }

Handle(T* t) : p(t) { }

operator bool() const { return p; }
T& operator*() const;
T* operator->() const;

private:
T* p;
};

template<class T>
Handle<T>& Handle<T>::operator=(const Handle& rhs)

if (&rhs != this) {
delete p;
p = rhs.p ? rhs.p->clone() : 0;
}
return *this;
}

template<class T>
T& Handle<T>::operator*() const
{
if (p)
return *p;
throw runtime_error("unbound Handle");
}

template<class T>
T* Handle<T>::operator->() const
{
if (p)
return p;
throw runtime_error("unbound Handle");
}


A를 B가 상속받은 경우, Handle <A> h(new B); 식으로 핸들을 생성하면 B클래스가 생성되어 핸들클래스의 포인터에 바인딩된다(virtual 함수를 사용할 수 있다).

operator* 를 정의하므로써 핸들이 가지고 있는 클래스 포인터로 클래스 레퍼런스를 반환하는 역할을 한다.

operator->는 이항연산자 인줄 알았는데 아니란다 ㅡ.ㅡ; 단지 이걸 통해서 오른쪽에 있는 멤버를 접근할 수 있게 해준덴다. 즉, x->y 인 경우 (x.operator->())->y 나 x.p->y와 같덴다. 요건 좀 비직관적인 듯하다.

아무튼 이 두 연산을 통해 Dynamic Binding이 가능해진다. 앗싸.

나는 generic handle class를 만들면 handle class가 필요없는 줄 알았다. Accelerated C++의 내용을 대강 정리해서 어쩌다 제네릭 핸들 클래스를 만들게 되었는지 요약해보면 아래와 같다.

  1. 클래스를 만들었다.
  2. 비슷하지만 다른 클래스도 필요하게 되었다.
  3. 두 클래스를 하나의 코드로 다룰려고 dynamic binding을 사용하려니 포인터/레퍼런스 사용이 복잡하다.
  4. 그래서 두 클래스를 사용하는 핸들 클래스를 만들고 이 핸들을 사용하기로 했다.
  5. 근데 핸들 클래스에도 포인터를 사용하려니 짜증난다.
  6. 포인터를 사용하는 부분만 제네릭 핸들 클래스로 빼버렸다.
  7. 결국 두 클래스 -> 제네릭 핸들 클래스 -> 핸들 클래스 -> 일반 코드 식으로 접근하도록 하여구현하게 되었다.

Monday, August 11, 2008

Basic concepts

상속
class drivedClass : public baseClass { ... }

public
interface의 일부로 상속한다는 의미 not as an implementation

protected
기본 클래스의 private멤버에 접근하고 싶을때 protected에 선언

baseClass::function
같은 이름의 기본클래스의 함수에 접근하고 싶을때

Polymorphism(다형성), binding
기본클래스의 레퍼런스를 인자로 받는 함수에서 파생클래스를 넣어도 되는 식
- 파생클래스의 기본 클래스 부분만 사용된다. (1)

virtual
(1)에서 파생클래스의 것을 자동으로 사용하게 해주고 싶을때 사용
클래스의 인자가 레퍼런스나 포인터로 호출된 경우에만 가능.

일반적으로 파생클래스에서 재정의 되는 virtual함수들은 기본클래스의 함수와 동일한 타입을 리턴해야하지만, 기본클래스의 virtual함수가 *this를 리턴하는 경우 파생클래스에서도 기본클래스의 포인터가아닌 파생클래스의 포인터(*this)를 리턴할 수 있다.

virtual function의 경우 기본/파생 클래스 함수들의 매개변수 갯수 타입이 다르면 별도의 함수로 동작하기 때문에 이를 고려해서 구현해야한다. 매개변수 개수가 다른 경우에는 아래와 같은 식의 구현을 통해 virtual function을 사용할 수 있다.

void BaseClass::func(double d1, double = 0) { ... }
void DerivedClass::func(double d1, double d2) { ... }

static binding
호출되기 전에 타입이 결정되어 그 타입으로 사용됨

dynamic binding
호출될 때 타입이 결정되어 그 타입으로 사용됨
레퍼런스나 포인터로 전달할 때 이루어짐 (실제 전달되는 값을 알지 못하므로)

virtual destructor
포인터나 레퍼런스에 대한 객체의 타입을 모르지만 delete 하고 싶은 경우 소멸자를 virtual로 선언하여 각 객체에 맞는 소멸자를 호출해주게 하는 것

Rule of three
복사생성자, 대입연산자, 소멸자 : 는 붙어 다닌다.

static member function
클래스의 멤버 함수로 호출되더라도 객체(this)의 멤버와 연관이 없는 작업을 수행하는 함수.
ex. static void func (classA& c1, classA& c2)

handle class
서로 상속관계를 가진 여러 클래스들을 하나의 클래스 처럼 사용하고자 할 때 인터페이스 역할을 하도록 하나의 클래스를 만들어 각 경우에 맞는 클래스의 객체를 생성하고 생성한 객체의 포인터(혹은 레퍼런스)를 가지게 하는데, 이를 핸들 클래스 라고 한다. 이 때 포인터는 기본클래스의 포인터를 가진다.
포인터를 가지고 연산하기 때문에 복사생성자, 대입연산자, 소멸자가 필요하다.

virtual clone function
복사 생성자의 경우, 핸들클래스는 생성한 클래스의 포인터를 가지고 있기 때문에 어떤 클래스를 생성해서 가지고 있는지 모르므로, 복사될 핸들 클래스의 포인터에 어떤 클래스를 생성해서 대입해야할지 모른다. 그래서 자기 자신을 복사하는 clone 함수를 각 클래스 별로 정의하고, 기본클래스에서 이를 virtual 로 선언해서 핸들 클래스에서 사용시에 각 타입에 맞는 방식의 clone함수를
사용해 복사후 핸들클래스의 포인터로 넘겨줄 수 있다.

ex. 대부분 각 클래스들은 아래와 같은 식으로 clone()을 만들어 놓는다.
protected:
// virtual 은 기본클래스의 경우에만.
virtual BaseClass* clone() const { return new BaseClass(*this); }

대신 핸들클래스가 이를 사용할 수 있도록 기본클래스의 friend로 등록되어야 한다.

핸들 클래스에서 기본클래스의 포인터를 가지고 있기 때문에 파생클래스의 clone에 대한 접근은 virtual call로 이루어 진다. 때문에 핸들클래스만 기본클래스의 friend 로 등록되면 된다.

friend
함수가 특정 클래스의 protected영역에 접근할 수 있도록 할 때 클래스에 이 함수를 friend로 등록할 수 있다. 클래스가 friend로 등록된 경우 클래스의 모든 멤버가 대상 클래스의 friend 가 된다.

friend관계는 상속되지 않는다.