April 26, 2016

AdaGrad, adaptive stochastic (sub)gradient descent

AdaGrad (아다그라드? ㅋ) 는 2011년도에 최초 제시된 것으로 상당히 최신 최적화 이론이다. 아래의 워싱톤 대학 자료가 상당히 잘 설명 되어 있는데,

- https://courses.cs.washington.edu/courses/cse547/15sp/slides/adagrad.pdf

Adagrad는 adaptive stochastic (sub)gradient descent로 이전 관측을 결합하는 것으로 매 iteration에 feature 별로 learning rate를 달리 하겠다는 개념이다 - "Adagrad provides a feature‐specific adaptive learning rate by incorporating knowledge of the geometry of past observations".

feature 별로 달리한다는게 상당히 매력적인데 왜냐하면 수많은 features에서 의미없는게 대다수이기 때문. 그리고, 일반 GD에서는 보통 그래디언트가 어떻게 되는지 모르기 때문에 모든 iteration에서 고정값을 사용한다. 그래서 AdaGrad를 잘만 사용하면 수렴 속도를 높일 수 있다.


가령 Learning Rate가 0.5라면, 해당 파라미터에 대해 에러를 50%만 반영한다는 의미다. 매 iteration에서 error가 줄어야하는데 중간에 에러가 커지는 현상이 일어나면 위와 같이 기울기가 올라가 버리는 경우이니 Learning Rate를 줄이는 것이다.


April 18, 2016

YodaQA - IBM 왓슨 PC용 오픈소스버전

"Yet anOther Deep Answering pipeline" 이라는YodaQA 프로젝트가 있다. 지식기반 질의응답 시스템인데, IBM 개발자들이 오픈소스로 내놓은 Apache UIMA, 그리고 스탠포드 대학에서 만든 Parser와 Solr 등을 사용한다.

자연어로 질문이 들어오면 1차적으로 파서가 형태소, 의존, 성분 등 구문 분석을 통해 Nouns, Named entities 그리고 LAT+SV (lexical answer type + selection verb) 등을 가지고 정보 검색을 수행한다. 기계학습은 Answer scoring에서 사용되는데 embedding-based selection이라고 질문의 vector embedding과 결과값을 로지스틱 회귀로 학습된걸로 일종에 분류 기반으로 랭킹하여 결과를 보여준다.

그래서 결과가 어떻냐? KB:62.9% on a collection of movie questions (Google: 59.9%). 특정 도메인에서의 정확도는 구글보다 좋다고 한다. 프로젝트 만든이와 채팅해보니 현재 Semantic Parsing 분야도 추가적으로 추진하고 있다고.

온라인 데모도 존재하는데 다음 사이트를 방문해보시라: http://ailao.eu/yodaqa/

Merging an upstream repository into your fork

  1. Open Git Bash.
  2. Change the current working directory to your local project.
  3. Check out the branch you wish to merge to. Usually, you will merge into master.
    git checkout master
    
  4. Pull the desired branch from the upstream repository. This method will retain the commit history without modification.
    git pull https://github.com/ORIGINAL_OWNER/ORIGINAL_REPOSITORY.git BRANCH_NAME
    
  5. If there are conflicts, resolve them. For more information, see "Resolving a merge conflict from the command line".
  6. Commit the merge.
  7. Review the changes and ensure they are satisfactory.
  8. Push the merge to your GitHub repository.
    git push origin master
    

April 12, 2016

미쳐 산다는 것은 ..

Sing like no one is listening. 
Love like you’ve never been hurt. 
Dance like nobody’s watching, 
and live like it’s heaven on earth.

April 6, 2016

C/C++ vs. Java

요즘 본의 아니게 알고리즘 공부를 좀 하면서 깨달은 바에 대해 몇 개 적어본다.

1) Java의 System.in/out 은 굉장히 느리다. 얼마나 느리냐고? 다음은 10,000,000 정수를 읽는데 걸리는 수행시간이다:

Input MethodTime (sec)
C scanf("%d", &arg)3.78
Scanner.parseInt()29.52
BufferedReader + inline Integer.parseInt2.89
BufferedReader + Reader.nextInt method3.01

단순히 2 ~ 3배 느린게 아니라 10배 가까이 차이가 난다. 이 때문에 BufferedReader 그리고, 출력에 있어서는 StringBuilder를 사용해야만 시간 초과를 피할 수 있다. 9935번 문자열 폭발이 대표적인데 알고리즘이 문제가 아니라 System.out.print 속도가 느려서 해결하기 쉽지 않다.

2) 최적화된 C/C++ 프로그램 속도는 빠르지만 역시나 코드는 더러워서 볼 수 가 없다 :/ 빠른게 능사가 아니란 말이다. 아래는 내 코드 (수행속도: 70 ms) 와 속도로 1위한 사람의 C++ 코드 (수행속도: 0 ms) 다. 물론 개발자 차이가 있을 수 있는데 ㅋ 일반적으로 Java나 함수형 언어에 익숙한 개발자는 대게 코드가 수식과 같고, C/C++은 무슨 연유인지 알 수 없으나 네이밍도 그렇고 코드가 대게가 지저분. 이 때문에 알고리즘 구현과 수행속도는 개발자의 평가기준이 절대 될 수 없다고 생각한다. Jeff Dean께서 그리 말씀하셨다니 나도 한마디 거들면 C++은 혐오스럽다.

한번 직접보시라:
import java.util.Scanner;
 
public class Main {
  static int[] a;
  static int[] memo;
 
  private static int calculate(int i) {
    if (i == 0) memo[i] = a[i];
    else memo[i] = Math.max(a[i], memo[i - 1] + a[i]);
     
    if (i == a.length - 1) {
      return memo[i];
    } else {
      return Math.max(calculate(i + 1), memo[i]);
    }
  }

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    a = new int[n]; memo = new int[a.length];
 
    for (int i = 0; i < n; i++)
      a[i] = sc.nextInt();
 
    System.out.println(calculate(0));
    sc.close();
  }
}
vs.
#include 
#include 
 
namespace my
{
    struct istream{};
    istream cin;
 
    inline bool is_num( char c ){ return ( c >= '0' && c <= '9' ); }
    inline bool is_negative( char c ){ return c == '-'; }
    inline istream& operator>>( istream& in, int& out )
    {
        char c; out = 0; bool neg = false;
        while( c = getchar() ){ if( is_negative(c) ){ neg = true; break; } if( is_num(c) ){ out += (c-'0'); break; } }
        while( c = getchar() ){ if( !is_num(c) ) break; out *= 10; out += (c-'0'); }
        if( neg ) out *= -1;
        return in;
    }
 
    inline void calc_max( int& max, int value ){ if( max < value ) max = value; }
    inline void calc_min( int& min, int value ){ if( min > value ) min = value; }
}
 
int main( int argc, char** argv )
{
    int N;
    my::cin >> N;
 
    int curr_max = std::numeric_limits::min();
    int curr_min = 0;
    int temp_min = 0;
 
    int n, accum = 0;
    for( int i = 0; i < N; ++i )
    {
        my::cin >> n;
        accum += n;
 
        if( accum > curr_max )
        {
            curr_max = accum;
        }
 
        if( accum - temp_min > curr_max - curr_min )
        {
            curr_max = accum;
            curr_min = temp_min;
            temp_min = 0;
        }
 
        if( accum < temp_min )
        {
            temp_min = accum;
        }
    }
 
    printf("%d\n", curr_max-curr_min);
 
    return 0;
}

[백준 알고리즘 풀이] 7469번 K번째 숫자

쉬운 문제 같지만 Q함수 내에서 매번 정렬한다면 속도가 나오지 않을 것이다. 전체 배열을 한번 정렬할때 원래 index 값을 달아놓으면, 매 Q함수 내에서 해당 i, j 범위 내 K번째를 찾는 것으로 해결한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

  static int[][] data;
  static int[][] temp;

  public static void main(String[] args) throws Exception {
    BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer t = new StringTokenizer(sc.readLine());
    int n = Integer.parseInt(t.nextToken());
    int k = Integer.parseInt(t.nextToken());

    data = new int[n][2];
    temp = new int[n][2];

    t = new StringTokenizer(sc.readLine());
    for (int i = 1; i <= n; i++) {
      data[i - 1][0] = Integer.parseInt(t.nextToken());
      data[i - 1][1] = i;
    }

    mergeSort(0, n - 1);

    while (k > 0) {
      t = new StringTokenizer(sc.readLine());
      int x = Integer.parseInt(t.nextToken());
      int y = Integer.parseInt(t.nextToken());
      int z = Integer.parseInt(t.nextToken());
      System.out.println(q(x, y, z));
      k--;
    }
    sc.close();
  }

  private static int q(int i, int j, int k) {
    int c = 0;
    for (int x = 0; x < data.length; x++) {
      if (data[x][1] >= i && data[x][1] <= j) {
        c++;
        if (c == k) {
          return (data[x][0]);
        }
      }
    }
    return 0;
  }

  private static void mergeSort(int low, int high) {
    if (low < high) {
      int mid = low + (high - low) / 2;
      mergeSort(low, mid);
      mergeSort(mid + 1, high);
      merge(low, mid, high);
    }
  }

  private static void merge(int low, int mid, int high) {
    for (int i = low; i <= high; i++) {
      temp[i][0] = data[i][0];
      temp[i][1] = data[i][1];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= high) {
      if (temp[i][0] < temp[j][0]) {
        data[k][0] = temp[i][0];
        data[k][1] = temp[i][1];
        i++;
      } else {
        data[k][0] = temp[j][0];
        data[k][1] = temp[j][1];
        j++;
      }
      k++;
    }

    while (i <= mid) {
      data[k][0] = temp[i][0];
      data[k][1] = temp[i][1];
      i++;
      k++;
    }
  }

}

[백준 알고리즘 풀이] 2216번 문자열과 점수

Sequence Alignment에서 잘 알려진 문제로 edit distance 계산하라는 문제다. 위키피디아에 잘 정리되있기 때문에 구체 설명은 하지 않는다. https://en.wikipedia.org/wiki/Edit_distance
import java.util.Scanner;

/*
 * 2216번 문자열과 점수
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
 
    int match = sc.nextInt() * -1;
    int gap = sc.nextInt() * -1;
    int mismatch = sc.nextInt() * -1;
    sc.nextLine();
 
    String a = sc.nextLine();
    String b = sc.nextLine();
 
    int[][] opt = new int[a.length() + 1][b.length() + 1];
 
    for (int i = 1; i <= a.length(); i++)
      opt[i][0] = opt[i - 1][0] + gap;
    for (int j = 1; j <= b.length(); j++)
      opt[0][j] = opt[0][j - 1] + gap;
 
    for (int i = 1; i <= a.length(); i++) {
      for (int j = 1; j <= b.length(); j++) {
        int diag;
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
          diag = opt[i - 1][j - 1] + match;
        } else {
          diag = opt[i - 1][j - 1] + mismatch;
        }
 
        opt[i][j] = Math.min(
            Math.min(opt[i - 1][j] + gap, opt[i][j - 1] + +gap), diag);
      }
    }
 
    System.out.println(opt[a.length()][b.length()] * -1);
    sc.close();
  }
 
}

[백준 알고리즘 풀이] 2579번 계단 오르기

전형적인 동적 계획법으로 recursive와 memoization 기법을 활용했다. 한 계단 또는 두 계단이기 때문에 n - 1, n - 2 모든 경우의 트리에서 최대값을 출력하도록 구현한다.
import java.util.Scanner;

/*
 * 2579번 계단 오르기
 */
public class Main {
 
  static int[] x;
  static int[] memo;
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
 
    x = new int[n + 1];
    memo = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      x[i] = sc.nextInt();
    }
 
    System.out.println(f(n, 2));
    sc.close();
  }
 
  private static int f(int n, int t) {
    if (n == 0)
      return x[0];
    if (n == 1) {
      if (t == 1) {
        return x[1];
      } else {
        return x[1] + x[0];
      }
    }
    if (t == 1) {
      if(memo[n] > 0)
        return memo[n];
          
      return memo[n] = x[n] + f(n - 2, 2);
    } else {
      return x[n] + Math.max(f(n - 1, 1), f(n - 2, 2));
    }
  }
  
}

[백준 알고리즘 풀이] 9020번 골드바흐의 추측

문제를 해결하는 방법은 많지만, 간단하게 두 소수의 합으로 표현가능한 짝수를 모조리 구해버린 다음 메모리에서 꺼내면 깔끔하게 클리어된다.
import java.util.Scanner;

/*
 * 9020번 골드바흐의 추측
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    boolean[] primes = new boolean[10002];
    primes[0] = true;
    primes[1] = true;
    for (int i = 2; i < primes.length; i++) {
      if (!primes[i]) {
        for (int j = 2; j < primes.length; j++) {
          if (i * j >= primes.length)
            break;
 
          primes[i * j] = true;
        }
      }
    }
 
    String[] memo = new String[10001];
    for (int i = 0; i < 10001; i++) {
      if (!primes[i]) {
        for (int j = i; j < 10001 - i; j++) {
          if (!primes[j] && (i + j) % 2 == 0) {
            if (i + j < 10001) {
              memo[i + j] = i + " " + j;
            }
          }
        }
      }
    }
 
    Scanner sc = new Scanner(System.in);
    int t = Integer.parseInt(sc.nextLine());
    while (t > 0) {
      System.out.println(memo[Integer.parseInt(sc.nextLine())]);
      t--;
    }
    sc.close();
  }
 
}

[백준 알고리즘 풀이] 9084번 동전

동전문제는 보통 완전 탐색으로는 속도가 나오지 않기 때문에 동적 계획법을 사용해야하는데, 총액과 동전을 2d 행렬로 놓고, 점진적으로 100원을 만들수 있는 경우의 수를 증가하면서 얻어가는 점화식을 도출하는게 핵심이다. 아래는 iterative 방식인데 recursive와 memoization으로도 가능하다.
import java.util.Scanner;

/*
 * 9084번 동전
 */
public class Main {
  static int[] a;
  static int[] memo;
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int tests = sc.nextInt();
    while (tests > 0) {
      int n = sc.nextInt();
      int[] m = new int[n];
      for (int i = 0; i < n; i++)
        m[i] = sc.nextInt();
 
      int total = sc.nextInt();
      int[][] t = new int[n + 1][total + 1];
      for (int i = 0; i <= m.length; i++) {
        t[i][0] = 1;
      }
 
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= total; j++) {
          if (m[i - 1] > j) {
            t[i][j] = t[i - 1][j];
          } else {
            t[i][j] = t[i - 1][j] + t[i][j - m[i - 1]];
          }
        }
      }
 
      System.out.println(t[n][total]);
      tests--;
    }
    sc.close();
  }
}

[백준 알고리즘 풀이] 9095번 1, 2, 3 더하기

이 문제는 정수론에 integer partition 이라는건데, 추가된 조건은 1, 2, 3으로만 분할하라는 얘기다. 간단하게 iterative 또는 recursive로 완전탐색하는 것으로 구현 가능하다.
import java.util.Scanner;

/*
 * 9095번 1, 2, 3 더하기
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
 
    int tests = sc.nextInt();
 
    for (int i = 0; i < tests; i++) {
      int n = sc.nextInt();
      System.out.println(partition(n));
    }
    sc.close();
  }
 
  private static int partition(int n) {
    if (n == 0) {
      return 1;
    } else if (n < 0) {
      return 0;
    } else {
      int sum = 0;
      for (int i = 3; i > 0; --i) {
        sum += partition(n - i);
      }
      return sum;
    }
  }
}

[백준 알고리즘 풀이] 9935번 문자열 폭발

기본 아이디어는 문자열을 쌓다가 대상 비교 문자열 꼬다리 캐릭터와 현재의 캐릭터가 일치할 경우 뒤에서 부터 검사한 (backwarding) 후 제거하는거다. 애니팡 연속으로 터지는걸 생각하면 쉽다. 코드에서는 Stack을 하나 구현했는데 poll 대신에 그냥 index position만 변경해주는걸로 구현했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
/*
 * 9935번 문자열 폭발
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    String bomb = br.readLine();   
 
    Stack s = new Stack();
    for (int i = 0; i < input.length(); i++) {
      s.push(input.charAt(i));
 
      if (input.charAt(i) == bomb.charAt(bomb.length() - 1)) {
        s.checkAndRemove(bomb);
      }
 
    }
 
    s.printCurrent();
    br.close();
  }
 
  public static class Stack {
    private int top = 0;
    private char[] stack = new char[1000003];
 
    public void push(char x) {
      stack[top++] = x;
    }
 
    public boolean checkAndRemove(String bomb) {
      if (top < bomb.length())
        return false;
 
      int c = 0;
      boolean isTrue = true;
      for (int i = bomb.length() - 1; i >= 0; i--) {
        if (bomb.charAt(i) != stack[top - 1 - c]) {
          isTrue = false;
        }
        c++;
      }
 
      if (isTrue) {
        top = top - bomb.length();
        return true;
      } else {
        return false;
      }
    }
 
    public void printCurrent() {
      if(top == 0)
        System.out.println("FRULA");
      else {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < top; i++) {
          out.append(stack[i]);
        }
        System.out.println(out.toString());
      }
    }
  }
 
}