Euler Problem 31 ...

It's just a integer partition.
public class Test {
  static int count = 0;

  public static void main(String[] args) {
    partition(200, 200);
    System.out.println(count);
  }

  public static void partition(int n, int max) {
    if (n == 0) {
      count++;
      return;
    }

    for (int i = Math.min(max, n); i >= 1; i--) {
      if (i == 200 || i == 100 || i == 50 || i == 20 
          || i == 10 || i == 5 || i == 2 || i == 1)
        partition(n - i, i);
    }
  }

}

73682
Job Finished in 0.02 seconds
정수론에서 나오는 자연수 분할 문제 ..

Euler 40 for Java: Finding the nth digit of the fractional part of the irrational number

Simply, the Integer array can be used to write digits.
public class Test {
  static int[] x = new int[1000000];
  static int index = 0;
  public static void main(String[] args) {
    for (int i = 1; i < x.length; i++) {
      if(index >= x.length)
        break;
      
      append(i);
    }
    
    System.out.println(d(1) * d(10) * d(100) * d(1000) * d(10000) * d(100000) * d(1000000));
  }
  
  private static int d(int i) {
    return x[i - 1];
  }
  
  private static void append(int n) {
    String a = String.valueOf(n);
    for(int i = 0; i < a.length(); i++) {
      if(index >= x.length)
        break;
      
      x[index] = Integer.valueOf(String.valueOf(a.charAt(i)));
      index++;
    }
  }
}

2015년 나는 어떻게 살았나? 상/하반기 총 결산

"2015년 나는 어떻게 살았나? 상반기 결산 하반기 계획"을 작성한 것이 엊그제 같은데 이제 어느덧 2016년 바라보고 있다.

 과거를 돌아보니 올해 상반기는 Apache 재단 멤버가 되었고 Apache Hama 성능도 조금 개선하면서 나름 반년 성과 치고는 뿌듯했다 할 수 있네. 기계학습과 HPC가 점점 부각되면서 HPCWire "Will Apache Hama Have Its Day in HPC?"와 같은 기사에 주인공이 되기도 하였다.

하반기는 좀 더 재미있는데 요약하면 다음과 같다:

7월: 웹 서비스 빅 데이터 → 실생활 서비스 인공지능으로 변화 시도
      (자꾸 Spark과 비교되는 문제로 "딥 러닝" 버티컬 플랜이기도 하였음).
8월: 인공 신경망, Gradient Descent 공부 & 공부
9월: Sync/Async 딥 러닝 플랫폼 구현 아이디어를 가지고 Apache Horn 제안서 작성
10월: 아파치 혼 Apache Incubator 승인!
        (아마 코드도 없이 승인된건 Apache Drill 이후 두번째인 듯)
11월: 조직개편 한다 어수선한 와중에 IST팀 전배 및 서울 R&D 우면센터로 입주 확정
        (구글 프레겔 창시자가 아파치 혼 프로젝트 멘토링해주기로 확정!)

딥 러닝이라는 놈을 반년 깔짝 공부한걸로 내가 충분히 가능할까 걱정이 많았는데, Apache 재단 인큐베이팅도, Andrew Ng 교수 조언도, 그리고 구글/페이스북에서 경험이 많은 그렉이 내 제안에 관심을 보이고 참여의사를 밝힌게 가장 뜻 깊은 것 같다.

내년에는 더 많은 사람들과 비전을 공유하며 협업하고 탄력을 받게 되기를 희망한다! 끗.

생즉사 사즉생 (生卽死 死卽生)

 가끔 주변의 고민을 가만 들어보면 목숨을 건 '위대한 여정'이라기엔 다소 2% 부족한 모두 현실 도피다. 생즉사, 사즉생(生卽死 死卽生). 좋아하는 명언 중에 하나인데, .. 뭔가 갈구함이 있고 대의를 따르는 각오에 어울리는 말이다. 그저 죽자 달린다고 빛이 나는 것이 아니지.

A neuron-centric programming model

According to the Google's DistBelief paper, the user defines the computation that takes place at each node in each layer of the model, and the messages that should be passed during the upward and downward phases of computation. They didn't described details about programming APIs, but we can imagine like below:
 class MyNeuron extends Neuron
   method upward(messages [m1, m2, ..., ])
       sum ← 0
       for each w ∈ [m1, m2, ..., ] do
          sum  ← sum + m.input * m.weight
          
       // propagate squashed output value to neurons of next layer
       propagate(squashingFunction(sum));

   method downward(messages [m1, m2, ..., ])
       for each w ∈ [m1, m2, ..., ] do
         gradient  ← this.output * (1 - this.output) * m.delta *  m.weight
         propagate(gradient);

         // weight collections
         w ← w + Δw (α * this.output * m.delta)

       // push updates to parameter server
       push(weights);
The reason I separate it into two methods (unlike Google's Pregel) is that framework can determine whether it's upward or downward phase by message type internally. Moreover, with this, we can reduce the user-side code complexity. The advantage of this is very fit for multi-thread programming and parallel computing of each gradient calculations at neuron level.

Additionally, instead of allowing user to write a formula for some calculations directly within neuron-centric programming model, we abstract some arithmetic operations and generate the code for GPU acceleration internally. With this, we compile it to a GPU-oriented code that batches for speed.

That way the user will not have to think about the specifics of GPU, but instead focus on the algorithm.

케플러 망원경이 외계 문명 발견하다? "KIC 8462852"

한국 기사로는 안나온 것 같아 작성.

케플러 미션을 수행하는 도중 지구에서 1500광년 떨어진 KIC 8462852 항성의 밝기가 20%까지 매우 불규칙하게 변하는 것을 발견했다고 한다.


천문학자들은 이를 어떻게 설명하지 못하고 있고, 이를 두고 몇 가지 설이 있는데 혜성이 지나가면서 발생했거나 항성 주변을 돌고 있는 외계 문명 구조물일 가능성이 얘기 되고 있다.

자연 현상일 가능성이 높다고 하나, 항성 주변의 외계 문명의 흔적, 즉 구조물이거나 고대 유물일 가능성도 없지 않다고.

이에 관련한 예일대 포스트닥 페이퍼: http://arxiv.org/pdf/1509.03622v1.pdf 참고

Artificial Intelligence is an evolutionary process

Once human beings create AI system, he'll begin to learn the World. We're just an sensory cells that transmit information to the AI system and collaborate each others. Packet is dopamine. Like button is adrenalin. NASA is a testis, generates germ cells.

노이즈 마케팅 vs 오픈소스의 선구자

노이즈 마케팅인가, 오픈소스의 선구자인가 .. (?)

 내가 8년 이상 오픈소스계에 몸 담고 하나 배운 것이 있다면, 그것에는 그냥 단순한 collective-intelligence framework 또는 movement뿐 아니라 strategy도 있다는 것이다. 이 때문에, 오픈소스라고 모두 같은 오픈소스가 아니고 그것의 태생과 전략적 goal이 무엇이냐에 따라 다르게 봐야한다.

 가끔 엔하위키라는 곳을 방문하면 재미를 추구하는 덕후 잉여들이 함께 만들어가는 공공 데이터베이스 플랫폼이라는 존재감이 굉장히 묵직(?)하다. 오픈소스계에도 이렇게 유쾌한 프로젝트가 많다.

 한편, 엔하위키에도 영리화 시도와 분쟁이 있었던 것으로 아는데 보통 이러한 공공재의 소유권 또는 영리화에 대한 분쟁은 다수의 user와 contributor들의 judging에 따라 결론이 난다.

 그렇다. 오픈소스 그것이 공공재화된 프로젝트인지 이익집단 특수목적을 위한 마케팅 수단인지 확인하는 방법도 그냥 유저와 컨트리뷰터의 반응을 보면 된다.

 아쉽게도 요즘은 전략적 오픈소스 활동이 반 이상인 듯 하다. 최근 한국에서도 오픈소스 분쟁 뉴스를 간혹 읽게 되는데, 그 내면은 잘 모르고 대단히 복잡하겠지만 한쪽에만 색이 입혀진 기사를 보면 이게 노이즈 마케팅인지 한국의 오픈소스 선구자인지 판단하기 어려워 읽기가 편치 않다.

세상을 바라보는 시각의 변화

 요즘도 간혹 나는 정말 내가 잘 하(고 있)는가에 대해 스스로를 의심하지만, .. 오픈소스의 가장 큰 장점이 바로 Social validation인 것 같다. 현재의 나는 글로벌에서 이미 꽤 유명하고 특정 분야에서도 높은 수준까지 도달한 것으로 생각된다.

 한편 여전히 주변을 파악하는 나 자신은 전혀 변해있지 않다. 왠지 수준도 낮아 보이고 사기꾼들도 눈에 보이고 뭐 그렇다만, 그래 이제는 주변의 수준이 떨어지는게 아니라 내가 수준이 높은 것으로 생각하자. :-) 탄소를 배출한만큼 인류발전에 공헌하기로 하자.

Google's DistBelief Clone Project on Apache Hama


 Deep Learning has become a household buzzword these days. Google, Microsoft, and Tencent have developed distributed deep learning systems but, these systems are closed source softwares. Many of open source softwares such as DeepDist, Caffe, ..., etc are data parallel only. In this blog post, I introduce an Artificial Neural Network implementation of Apache Hama ML package and future design plan for supporting both data and model parallelism.

1. Artificial Neural Network of Hama ML Package

 The lastest Apache Hama provides distributed training of an Artificial Neural Network using its BSP computing engine (the initial code was contributed by Yexi Jiang, a Hama committer, Facebook). In general, the training data is stored in HDFS and is distributed in multiple machines. In Hama, two kinds of components are involved in the training procedure: the master task and the groom task. The master task is in charge of merging the model updating information and sending model updating information to all the groom tasks. The groom tasks is in charge of calculate the weight updates according to the training data.

 The training procedure is iterative and each iteration consists of two phases: update weights and merge update. In the update weights phase, each groom task would first update the local model according to the received message from the master task. Then they would compute the weight updates locally with assigned data partitions (mini-batch SGD) and finally send the updated weights to the master task. In the merge update phase, the master task would update the model according to the messages received from the groom tasks. Then it would distribute the updated model to all groom tasks. The two phases will repeat alternatively until the termination condition is met (reach a specified number of iterations).

 The model is designed in a hierarchical way. The base class is more abstract than the derived class, so that the structure of the ANN model can be freely set by the user, as long as it is a layered model. Therefore, the Perceptron, Auto-encoder, Linear and Logistic regressor can all be uniformly represented by an ANN.

2. Future Plan for Large Scale Deep Neural Network

2.1 Architecture

 As described in above section, currently the data parallelism is only used. Each node will have a copy of the model. In each iteration, the computation is conducted on each node and a final aggregation is conducted in one node. Then the updated model will be synchronized to each node. So, the performance is one thing; the parameters should fit into the memory of a single machine.

 Here is a tentative near future plan I propose for applications needing large model with huge memory consumptions, moderate computational power for one mini-batch, and lots of training data. The basic idea of data and model parallelism is use of the remote parameter server to parallelize model creation and distribute training across machines, and the region barrier synchronization per task group instead of global barrier synchronization for performing asynchronous mini-batches within single BSP job. Each task group works asynchronously, and trains large-scale neural network model using assigned data sets in BSP paradigm. The below diagram shows an example of 3 task groups:


 Each task asynchronously asks the Parameter Server who stores the parameters in distributed machines for an updated copy of its model, computes the gradients on the assigned data, and sends updated gradients back to the parameter server. This architecture is inspired by Google's DistBelief (Jeff Dean et al, 2012).

2.2 Neuron-centric programming model

 The new Programming API proposed by Edward J. Yoon will provide two user-defined functions, which the user can define the characteristic of artificial neural network model: Activation function and Cost function.


 Each function can be implemented by extending ActivationFunction and CostFunction abstract classes like below:

  /**
   * User-defined sigmoid actiavation function
   */
  public static class Sigmoid extends ActivationFunction {
    @Override
    public double apply(double input) {
      return 1.0 / (1 + Math.exp(-input));
    }

    @Override
    public double applyDerivative(double input) {
      return input * (1 - input);
    }
  }

 The following properties are specified in the Job configuration:

  • The model topology: including the number of neurons (besides the bias neuron) in each layer; the type of squashing function; the degree of parallelization for each layer. 
  • The learning rate: Specify how aggressive the model learning the training instances. A large value can accelerate the learning process but decrease the chance of model convergence. Recommend in range (0, 0.5]. 
  • The momemtum weight: Similar to learning rate, a large momemtum weight can accelerate the learning process but decrease the chance of model convergence. Recommend in range (0, 0.5]. 
  • The regularization weight: A large value can decrease the variance of the model but increase the bias at the same time. As this parameter is sensitive, it's better to set it as a very small value, say, 0.001.

 The following is the sample design regarding how to create a job for training of three-layer neural network:

  public static void main(String[] args) throws Exception {
    ANNJob ann = new ANNJob();

    // set learning rate and momentum weight
    ann.setLearningRate(0.1);
    ann.setMomentumWeight(0.1);

    // initialize the topology of the model
    // set the activation function and parallel degree.
    ann.addLayer(featureDimension, Sigmoid.class, numOfTasks);
    ann.addLayer(featureDimension, Sigmoid.class, numOfTasks);
    ann.addLayer(labelDimension, Sigmoid.class, numOfTasks);
  
    // set the cost function to evaluate the error
    ann.setCostFunction(CrossEntropy.class);
    ...
  }

 In closing this blog post, I would like to request your feedback about design ideas. Please feel free to drop a comment or send a mail to our dev@hama.apache.org mailing list. Thanks.

2015년 나는 어떻게 살았나? 상반기 결산 하반기 계획

 2015년 상반기 짧다면 짧고 길다면 긴 6개월, 알차게 보낸것 같아 뿌듯하네. 다음은 월별 이벤트다:


 1월: 1월 2일 부터 3주간 새로운 조직합류를 위해 합숙교육 다녀오다.
 2월: 구정 때문에 특별한 일 없이 지내다.
 3월: Apache Software Foundation 정식 멤버로 선임되다.
 4월: Hama 그래프 패키지 성능을 개선하다. Giraph 대비 느리지 않다고.
     코드를 보면서 느낀 것은, 그 동안 너무 Memory 최적화에 빠져있었다.
     Hardware modernization을 꾸준히  고려해야한다.
 5월: 창업하고서 1년 정도 손을 놓고 있던 Apache Hama 드디어 0.7 릴리즈!
     성능개선, 그리고 Yarn 모듈과 Mesos 모듈을 탑재했다.
     Durability만 확보하면 1.0으로 커팅할 수 있으리라.
 6월: Apache Incubator PMC가 되었다.
     그리고 지난 12월 06일 태어난 내 아들은 이제 7개월이 되었다.






 하반기는 기계학습과 딥 러닝에 포커싱해볼 계획이다. 과거 내가 기계학습과 딥 러닝에 베팅할 쩍에 빅 데이터 시장은 데이터 가공 분야에 열을 올리고 있었고, 많은 지인들은 "오늘의 먹거리와 내일의 먹거리"라는 표현을 많이 썼는데 과연 그럴까?

 많은 IT 선진 기업들은 해당 분야의 연구 결과를 이제 서비스로 하나 둘 선보이고 있다. 여러 메신저 서비스들과 구글 포토가 대표적이지 않을까 싶네. 기술 발전이 가장 빠른건 오픈소스가 아니라 생존 진화압이 높은 바로 산업계였던 것 같다.

 과거엔 소프트웨어 기술 진입장벽이 낮아 로컬에서 빠른 카피 전략이 가능했지만 이제 점점 따라잡기 힘든 격차를 만들어 내고 있는만큼 주변에 휘둘리지 않고, 내가 멀리 바라보는 비전을 믿는 그대로 추진해볼 계획이다. 그것이 불혹(不惑)이겠지.

인공신경망 (Artificial Neural Network)

 우리네 인간의 학습 능력은 어떤 메커니즘으로 작동하는가? 비밀은 신경망에 있다.

1. 인간 신경망

 대뇌피질의 신경세포는 다음과 같이 수상돌기(dendrite)를 통해 다른 여러 신경세포로부터 입력 신호를 받아, 세포체(cell body)에서 정보 연산을 처리하고 축색(axon)을 통해 처리된 정보를 다른 신경세포로 전달한다. 이러한 신경세포는 시냅스라는 가중 연결자(weighted connectior)로 여러 층의 신경망을 구성한다.


 세포체에서의 연산은 입력 신호들의 합을 구하고 그것이 일정한 임계치가 되면 축색이 활성화되어 스파이크를 일으켜 다른 신경세포로 전기 신호를 전달한다. 이러한 특성을 모방하여 만든 것이 인공 신경망(artificial neural network)이다.

2. 인공 신경망

 하나의 인공 신경세포(perceptron)는 다음과 같이 n개의 입력 x1, x2, ..., xn에 대해 연결 강도 w1, w2, ..., wn에 따른 가중치를 곱하여 모든 값의 합(summation)을 구한다. 수식으로 표현하면, u = Σwixi


 이 가중치의 합은 다시 활성화 함수(activation function)를 통과해서 다음 신경세포로 전달될 출력을 결정한다. 위 축색에 활성화 함수는 0 또는 1로 출력하는 계단식 함수가 표현되어 있지만 이부분을 사용자 정의 함수로 원하는 특성을 가진 인공신경망 모델을 구현할 수 있다. 아래는 공돌이식 다이어그램.


 이렇게 활성화 함수를 정의하여 하나의 인공 신경세포에 대한 모델이 정립되면, 다음엔 이들의 연결구조를 고려한다. 우리는 다층 퍼셉트론을 볼 것이기 때문에 입력층과 출력층 사이에 1개 이상의 은닉층을 가지는 구조의 다층 신경망 구조를 한번 보자.


 이러한 신경망 구조에서의 학습은 시냅스의 연결 강도(weight)를 변화시키는 것인데 가장 기본적인 방법은 헤브의 학습 규칙으로 연결된 두 신경세포가 동시에 활성화되면 가중치를 증가시키는 방법이다. 해당 블로그에서 우리는 보다 진화한 오류역전파 알고리즘을 중점적으로 파기로 한다.

3. 다층 퍼셉트론

 다층 퍼셉트론은 인공 신경세포 퍼셉트론을 이용한 XOR문제를 먼저 이해해야하는데, 퍼셉트론 패턴 분류의 약점으로 선형 판별함수 때문에 XOR과 같은 출력을 내도록 경계선(hyperplane)을 만드는게 불가능하여 비선형 경계선을 만들기 위해 은닉층을 추가한게 다층 퍼셉트론이다.

 이제 곧 퇴근을 위하여, 구체적인 다층 퍼셉트론과 하마의 mini SGD기반 MLP 알고리즘으로 분류하는 기법은 다음 글에서 만나기로 하며 마친다.

Neural Networks와 Deep Learning

뉴럴 네트워크나 딥 러닝 알고보면 별 것 없다. 가령, 꼬리달린 이것은 고양이다 하고 조낸 인풋을 받아 들이면서 그냥 학습하면 되는 것.

이러한 이미지 인식 및 분류는 어떻게 하는거냐?

모든 이미지는 2차 배열이고 각 셀은 RGB 세 가지 색상으로 표현될 수 있는데 이를 납작한 1차원 배열, 즉 열벡터로 만든다. 당연히 1차 배열 사이즈는 height * width * 3. 이걸 클래시파이어로 학습하고 분류하면 되는데, 이러한 방식은 뉴럴 네트워크나 딥 러닝이나 똑같다. 이미지, 음성, 음원 데이터 등 인풋 특성에 따라 적당히 노멀라이제이션을 해줘도 된다.

차이점은 학습과 분류하는 방법이 다른데 통계 방식과 하이퍼플랜 기반 클래시파이어 대비 뉴럴 네트워크와 딥 러닝은 학습 방법이 인간의 뇌 구조를 닮은거다. 성능이 좋은데 왜 결과가 그러한지 수학적 해석이 어렵다. 아니, 이게 성능이 좋다라기보다는 그 결과가 그냥 인간과 비슷하다고 하는게 맞는 표현이다.

그러면 이 기술은 어떻게 활용될수 있을까?

데이터는 텍스트에서 멀티미디어로 바뀌고 있고, 전세계에서 일어나는 현상 정보를 구글 브레인이 학습하고 있다. 음성으로 뉴스를 조회하고 원하는 사진을 찾게 해주지. 인터넷에 스팸과 19금 저질 컨텐츠를 사람이 아닌 기계가 걸러낸다. 또, IoT 센싱기술이 발달할수록 기계학습과 딥 러닝의 분야는 무궁무진해진다. 더 이상 사람이 할 수 없어.

텐센트의 딥 러닝 플랫폼 구조

 작년 VLDB를 통해 발표된 중국 텐센트의 딥 러닝 플랫폼, 마리아나 (마리화나 아님 -_-) 에 대한 얘기다. 

 페이퍼는 GPU와 레거시 CPU 방식 클러스터를 소개하고 있는데 (하이브리드 방식의 단일 플랫폼 아님) 자사 서비스 위챗에 활용하는 것으로 GPU 클러스터는 이미지, CPU 클러스터는 음성인식 등에 사용중이라 한다.

 어깨넘어 들리는 소문으로는 GPU가 대세 아닌가!? 해서 봤더니, 레거시 CPU 클러스터는 다음과 같은 이유로 존재한다네.

Mariana includes a CPU  cluster data parallelism and  model parallelism framework for DNNs. DNN CPU cluster framework aims to two kinds of applications. First, CPU cluster is useful for applications needing large model with huge memory consumptions, moderate computational power for one mini-batch, and lots of training data. This kind of applications needs both data parallelism and model parallelism, and must be rewritten to solve this large scale problem. Second, legacy CPU training applications could be empowered by data parallelism with little code modification to become a parallel version.

라쥐스케일에 적합하고 코딩도 쉽다 이거야!

그들의 아키텍처

 마스터는 stochastic gradient descent 알고리즘을 수행하는 여러 개의 mini-batch BSP job을 관리하고 그 잡에는 코디네이터를 하나씩 선발해서 일을 처리한다. 이걸 하나의 그룹이라 하고 이들은 Asynchronous하게 작동하므로 그룹 간 파라미터 스와핑은 파라미터 서버를 사용한다. 요약하면, 구글의 DistBelief 짭이라고 할 수 있다 (GPU 클러스터는 페이스북 짭이라고 한다. 역시 중국).

 처음에는 Apache Hama의 단일 잡에 토폴로지 정보로 태스크를 그룹으로 묶고 파라미터 서버간 통신 API만 뚤어주면 될 것으로 봤는데 홀리쉿! 그냥 하마는 서브컴포넌트로 활용될 수 있을 것 같다. 한국 밀린다 밀려. 내가 한번 만들어보자!

Few thoughts

1. The process and management skills doesn't increase the productivity of software development. On that point, open source is the software development culture of the future.

2. Internet is revolution near the emergence of multi-cellular organisms.

10년 전 Web 2.0 인터넷 수준에 묶여 있었다

고속도로 운전하면서 라디오에서 우연히 듣게 된 유엔미래포럼 박영숙 대표의 강연.

목소리만 듣고 처음에는 박 대통령 신년사하는 줄 알았으나 내용이 너무도 유익했다. 우리는 지금 급변하는 세상에 살고 있음을 다시 한번 느끼게 해주는 강연이었고, 웹 컴패니 구글, 페이스북, 그리고 아마존 등이 왜 그렇게 무인자동차, 드론 등에 투자를 추진하는지도 다시금 생각하게 되었다.

뭐 물론 이런 내용은 꾸준히 생각하고 있었지만 미생물에서 점점 생물이 되어가는 ㅋ... 다세포 생물을 움직이는 감각세포 출현에 버금가는 혁신의 시대에 내가 살고 있구나! 라고 강하게 느꼈다.

나는 다시 한번 나를 돌아봐야 한다. 현재도 여전히 10년 전의 Web 2.0 인터넷과 그에 필요한 기술 수준에 발묶여 있는건 아닌지. 틀을 다시 한번 깨고, 쫓아야할 때다.

비록 이 몸은 묶여(?)있지만 어느때보다 나의 상상력과 비전은 미래를 향하고 있다. :)