mjaysonnn commented 6 years ago

지금까지 했던 실험의 분포를 보면 균일하게 분포되있지가 않음
그래서 lr, lc, rc 모두 uniform 하게 분포되어있는 실험 시나리오를 만들기
본 논문에서는 200 여개의 시나리오 모두를 테스트 했는데 이중 가장 중요한 행렬 연산 크기를 추출해서 높은 정확도를 유지하기 위함
추후에 다른 instance에도 실험할때 용이하게 하기 위함
일단 r4.2xlarge , 4 worker 4nodes 기준

lr,lc,rc 기준 128,128, Max
128,Max,128 Max,128,128
위의 Max를 찾아서 실험시나리오 만들기

mjaysonnn commented 6 years ago

교수님 그때 얘기했던 것중 헷갈리는 부분이

그때 얘기했던게 lc 이랑 rc 이 두 개의 길이를 같게 하기로했나요?

참고로 실험해본 결과 (r4.2xlarge, 4 worker nodes)

128 - 8.25M - 128 8.25M - 128 - 128 128 - 128 - 8.25M 입니다.

이 다음에 어떻게 하는지 약간 정리가 안되네요.

예로 들면 40k - ? - 40k 일 경우 ?의 최대 길이를 찾아보면 되는건가요?

그 다음에 20k ? 40k 여기서도 ? 의 최대 길이를 찾아보는 건가요?

lr 이랑 rc 의 길이를 둘다 같게 하자고 하신거같기도 하고 조금 헷갈려서요

mjaysonnn commented 6 years ago

Matrix Size investigated so far

128 - 8M - 128 8M - 128 - 128 128 - 128 - 8M

When lc = 128

1600000-128-3875 3200000-128-1850 4800000-128-1100
6400000-128-500 ( 실험 중 900까지 갈듯)

lc가 linear하게 변하게 감소하는 중

Design Of Experiment를 공부 후 깊게 팔 예정

mjaysonnn commented 6 years ago

various DOE techniques

현재 공부한 바로는 사용할 수 있는게

Latin Hypercube sampling
Central Composite Design
Box-Behnken
D-Optimal (to be studied)

위의 여러가지 Experimental Design을 통해 실험 시나리오 생겨도 Spark에서의 Memory 관련 문제 떄문에 행렬 곱셈이 안되는 Input Matrix가 있을 수 있습니다. 고로 , 먼저 Latin Hypercube sampling만 우선 해보는 걸로 하겠습니다.

Latin Hypercube

자세한 개념은 ppt 에 있습니다.

python Package로 제공하는 함수는 이와 같습니다.

lhs(n, [samples, criterion, iterations]) -> criterion이 여러가지 있습니다.

criterion: a string that tells lhs how to sample the points (default: None, which simply randomizes the points within the intervals):

“center” or “c”: center the points within the sampling intervals

“maximin” or “m”: maximize the minimum distance between points, but place the point in a randomized location within its interval

“centermaximin” or “cm”: same as “maximin”, but centered within the intervals

“correlation” or “corr”: minimize the maximum correlation coefficient

4가지의 criterion이 있는데 위의 3가지는 비슷해보입니다. 나머지 아래의 correlation criterion을 눈여겨 봐야합니다.

찾아본 결과 정확히 나와있지는 않지만

행렬의 Factor은 lr,lc,rc 3개라고 할 때 lr, lc, rc 끼리의 상관계수가 적게 나타나게 하기위함이라고 보면됩니다.

확인용도로 4가지의 용도의 corref를 살펴보았습니다.

자세한 코드는 여기

1 random criterion corref

| 1        0.18600426   -0.67747366|
| 0.18600426  1       -0.10286898|
|-0.67747366 -0.10286898  1        |

2 center criterion corref

| 1         -0.04242424  -0.40606061|
|-0.04242424  1          0.41818182|
|-0.40606061  0.41818182  1       |

3 maxmin criterion corref

| 1         -0.35773185  0.13074413|
|-0.35773185  1  0.13103987|
| 0.13074413  0.13103987  1|

4 centermaxmin criterion corref

| 1         -0.18787879 -0.26060606 |
|-0.18787879  1          0.35757576 |
|-0.26060606  0.35757576  1        |

5 correlation criterion corref

| 1.         -0.11249624  0.19502187|
|-0.11249624  1.          0.15186777|
|0.19502187  0.15186777  1.        |

> 다른 criterion이랑 비교해보면( -0.67, 0.4, 0.3 corref가 존재) 5번 corref 이 제일 0에 가깝습니다. (서로 거의 무시될수 있는 선형관계 from wiki)

정리 -> lr, lc, rc 끼리 서로 interaction이 존재할 것입니다. 그러나 지금은 실험 시나리오를 짜는 단계이기 떄문에 criterion 이 corref인 것으로(lr,lc,rc끼리의 상관계수가 0으로 근처로 머무는 방향으로) 실험시나리오를 만들 예정입니다. 그리고 한번 full factorial experiment으로 lr, lc, rc 끼리의 significant interaction factors 도 봐보겠습니다.

array([[0.36702124, 0.00337 , 0.37432892], [0.41426645, 0.26362573, 0.01063056], [0.81141125, 0.36054584, 0.17989849], [0.57040231, 0.5108674 , 0.9106078 ], [0.97936264, 0.14899724, 0.86102681], [0.72099814, 0.94912799, 0.49027556], [0.23215313, 0.6683768 , 0.73775378], [0.11556822, 0.73233634, 0.28995877], [0.04082802, 0.48540355, 0.57188117], [0.65280082, 0.86797347, 0.60293439]])

저희가 가지고 있는 데이터 lower bound - 128 upper bound- 8M 를 가지고 위의 저 비율을 적용하여 실험을 바로 돌려보겠습니다.

mjaysonnn commented 6 years ago

Input matrix ( based on 8M upper bound)

[2936169, 26960, 2994631], [3314131, 2109005, 85044], [6491290, 2884366, 1439187], [4563218, 4086939, 7284862], [7834901, 1191977, 6888214], [5767985, 7593023, 3922204], [1857225, 5347014, 5902030], [924545, 5858690, 2319670], [326624, 3883228, 4575049], [5222406, 6943787, 4823475]]

kmu-leeky commented 6 years ago

nice summary. 마지막에 정리한 시나리오 상에서 실험을 한번 해보자. 굉장히 많은 조합이 동작을 못할것 같기는 한데, 그것역시 좋은 발견이 될것 같다.

mjaysonnn commented 6 years ago

넵 해보고 업데이트 하겠습니다~

mjaysonnn commented 6 years ago

해봤는데 다 안되네요

오류가 다 하나만 보자면

run_matmul 1 2936169 26960 2994631 2 2 2 2

Job aborted due to stage failure: Task 3 in stage 0.0 failed 4 times, most recent failure: Lost task 3.3 in stage 0.0 (TID 10, 172.31.28.179, executor 2): java.lang.IllegalArgumentException: requirement failed: 1468084 x 13480 dense matrix is too large to allocate

제 생각은

128 * 8000000 = 1024000000

아직 구체적인 계획은 없지만 메모리 쪽으로 접근해볼 생각입니다. or Box-Bhenken or CCD

(끝점을 제외하기 떄문에 좋은 결과가 나올수도 있다고 생각합니다, 물론 메모리 떄문에 안될 확률이 큽니다)

DOE 책에서도 비슷한 접근법이 있는지도 봐보겠습니다.

kmu-leeky commented 6 years ago

음 역시... 예상하던 바이기는 하네. 작업 특성상 세가지 변수의 곱셈 값이 더 중요할것 같네. 어떤게 좋을지 조금 더 생각해보자.

mjaysonnn commented 6 years ago

옙!

mjaysonnn commented 6 years ago

책을 읽으면서 몇가지 정리해보자면

from page 185

제가 Seminar에서 2-Level일 경우에만 (하나의 factor의 값이 +, - 이렇게 2가지만 있는 경우) 2-Level, General Full Factorial Experiment을 쓴다고 했습니다. 그러나 2-Level이 Regression model이랑 합쳐지만 다르게 됩니다.

The variables x1 and x2 are defined on a coded scale from -1 to +1 ( the low and high levels of A and B)

즉 2-level, 3-Level ( low intermediate high) 아니면 5-Level (min, low, center, high, max) 일때도 세미나에서 얘기한 여러가지 Experiment을 자유롭게 쓸수 있습니다.

from p525 ~ 526

if the experimenter is considering a polynomial model, then an optimal design such as D-optimal or I-optimal design is a possible choice. In recent years, various types of space-filling designs have been suggested for computer experiments.

여기서 말하는 space-filling design은 지금 시도해보고있는 Latin hypercube 입니다. (Latin Hypercube를 먼저 써본게 잘된 일입니다)

또한 하나 더 추천하는게 Gaussian process model입니다.

p281~282, p 513

D-Optimal을 쓰는 이유 (related to least squares estimates.)

간단히 정리해보자면

a design the minimizes the variance of the model regression coefficients is called a D-optimal design.

D가 쓰이는 이유는 determinant of X'X 를 maximize 하는 방향으로 design 되기 떄문입니다. 그래야 joint confidence region이 작아집니다. (minimizing the variance of the model regression coefficients)

X'X가 어디서 나오는지는 the least squares estimates of the model regression coefficients 랑 관련 있습니다.(수식이 많이 나오는지 과정은 생략하겠습니다)

이 D-Optimal을 지원해주는 다른 Python Package가 있습니다.

from Code

import dexpy.optimal
reaction_design = dexpy.optimal.build_optimal(2, order=ModelOrder.quadratic)

이 Package를 통해 D-Optimal Experiment Design을 만들수 있습니다.

from p 530 ~532

Mixture Experiments

이 Experiment는 where the levels of each factor are independent of the levels of other factors. 입니다.

교수님과 그때 그려본 그림이랑 비슷하기도 하고 이거랑도 많이 관련있어 보입니다.

In Summary, To-do lists

교수님 일단 제가 생각해본게, 최대 사이즈가 1281288M = 131072M 입니다. 이를 전체 넓이라고 생각하고 예로 들면 latin Hypercube Sampling에서 나온 하나의 row인 [0.36702124, 0.00337 , 0.37432892] 를 가지고 lr = 131072M 0.36702124 lc = 131072M 0.00337 rc = 131072M 0.37432892 이렇게 실험 데이터를 만들어보는 것입니다. 떻게 될지 한번 해보겠습니다. 이렇게 해도 데이터가 고르게 될지도 한번 해보겠습니다.

Mixture Model 사용 가능한지 행렬곱셈에 적용되는지 더 찾아보기
D-Optimal Design from dexpy python package 더 알아보기 -> 실행 가능한 행렬이 확인되면 D-Optimal 써보는 것도 좋다고 생각이 듭니다.
책 반복해서 더 봐보기
Gaussian Process Model을 Python Package에서 지원해주는지 찾아보기

kmu-leeky commented 6 years ago

오케이. "D가 쓰이는 이유는 determinant of X'X 를 maximize 하는 방향으로 design 되기 떄문입니다." 를 보면 왠지 Ernest 에서 언급된 내용과 비슷해 보이기도 한다. 다양한 가능한것들을 많이 해보자. 연산이 가능한 범위를 찾아보는게 중요할것 같은 생각이 드네.

mjaysonnn commented 6 years ago

from Ernest

교수님 다시 Ernest 논문 봐보니 똑같은 원리네요.(I-Optimal, G-Optimal, 등등 여러가지가 있지만) 옙 하나씩 이것저것 해보겠습니다.

mjaysonnn commented 6 years ago

https://github.com/amplab/ernest/blob/master/expt_design.py

Ernest expt_design.py를 보면

'''Construct non-negative lambdas and budget constraints'''

이런 부분이 있는데 전체 행렬 메모리 사이즈를 X 이하로 하는 constraint를 적용해보는 것도 방법일꺼같은 생각이 듭니다. 이것도 해보겠습니다.

kmu-leeky commented 6 years ago

굿아이디어다. 성수랑 하는 부분에서 행렬 사이즈에 따른 메모리 사용량을 예측하는게 있는데, 그걸 가져다 사용해도 될것 같은 생각이 드네.

mjaysonnn commented 6 years ago

넵 그럼 오늘 성수한테 물어보고 같이 적용해보겠습니다.

mjaysonnn commented 6 years ago

DOE/Memory-Based

성수가 하는 메모리 예측 모델을 활용해봤습니다.

Non-Square Matrix에서의 최대 Input Size은

8M x 128 x 128 128 x 8M x 128 128 x 128 x 8M

Square에서는

32k 32k 32k 입니다

regression model을 가지고 예측해본 결과 from Memory-Estimation-sss array가 예측값입니다.

input_data이 Big - Small -Small 을 예측을 잘 못하는 것으로 보입니다. 저런 형태의 데이터가 없어서 그래보입니다.(예측 값이 음수로 나옴)

또한 예측 모델을 떠나서 lr lc rc 로만 본다면

128 128 8000000 = 131072000000 32000 32000 32000 = 32768000000000

즉, 이것만 가지고 Memory의 upper bound를 판단하는 건 안 좋을꺼 같습니다.

일단 이 4개의 메모리 사이즈 중 제일 큰 849132로 constraint을 잡아볼 생각입니다.

mjaysonnn commented 6 years ago

DOE/Mixture Models

Mixture Designs을 찾아본 결과

These designs produce runs to model the responses in terms of the relative proportions of the components. The sum of the component proportions is always 1 (100% of the components being varied). As one component is increased the sum of the other components must decrease to maintain the sum. Mixture optimal designs are most commonly used because they allow the most flexibility in your component ranges.

Mixture Deisgn의 원리가 x+y+z=1 이라서 저희랑 다른 케이스라고 봅니다.

또한 실제로 실험을 돌려봤으나 분수는 나오지도 않고 구체적인 설명이 없습니다. Mixture Experiments-from Jupyter

이 Design은 skip 하겠습니다.

mjaysonnn commented 6 years ago

DOE/Ernest

https://github.com/amplab/ernest/blob/master/expt_design.py

현재 지금까지 봐본 결과

Ernest의 DOE도 alternate least squares 알고리즘 기반으로 짜져있습니다. (similar to D-optimal design)

데이터를 만드는 과정은

먼저 scalability 랑 core 개수랑 비교해서 dataset을 filtering하고 cvx를 이용하여 남은 데이터를 또 filtering 합니다

그래서 이걸 해보기 위해서는 cvx라는 package 공부를 해야할꺼같습니다. : problem , objective, constraint 를 지정해서 solve()함수를 통해 데이터를 filtering해주는 걸로 보입니다.

이걸 저희 실험에 이용하게 된다면 objectives - lr , lc , rc , lrrc , lrlc+lcrc 등등 논문에 나왔던 feature가지고 model을 만들고 constraint 에 lrlc*rc 의 곱셈에 대한 제한 기준을 넣어서 데이터를 만들 수 있다고 생각합니다. (여기서 성수의 메모리 예측 모델을 쓰면 될듯합니다.)

그러면 solve( |y-ax|를 minimize 해주는 방향)를 통해 적합한 데이터를 만들어주지 않을까 생각합니다.

간단한 예시

또한 Ernest가 scale-based 이다 보니 _construct_constraints 도 input_fraction , machine 개수에 맞춰져있습니다. 이걸 변형 하는데 시간이 좀 걸릴듯하여 일단 여기까지 했습니다.

mjaysonnn commented 6 years ago

DOE/Latin Hypercube with constraints

마지막으로 Latin Hypercube는 메모리 문제 때문에 일단은 쓸수가 없습니다. 그래서 Latin Hypercube sampling을 할 때 constraint을 적용할 수 있는지 찾아봤으나 없습니다.

음. 제가 생각해본거 하나가.

전에 Latin Hypercube Sampling으로 뽑은 데이터가 있습니다. (from level [-1 to 1] )

[[0.36702124, 0.00337 , 0.37432892], [0.41426645, 0.26362573, 0.01063056], [0.81141125, 0.36054584, 0.17989849], [0.57040231, 0.5108674 , 0.9106078 ], [0.97936264, 0.14899724, 0.86102681], [0.72099814, 0.94912799, 0.49027556], [0.23215313, 0.6683768 , 0.73775378], [0.11556822, 0.73233634, 0.28995877], [0.04082802, 0.48540355, 0.57188117], [0.65280082, 0.86797347, 0.60293439]]

그리고 regression model을 통해 나온 최대 input행렬의 메모리 예측 사이즈가 849132 이므로

위의 Latin Hypercube Sampling 데이터의 모든 element에 x를 곱했을때 예측한 메모리가 843192이하가 되는 모든 경우수로 데이터를 만드는 것입니다. (제 생각입니다)

Central Composite Design , D-Optimal, Box-Bhenken도 메모리 문제만 해결하면 구현은 바로 가능합니다.

D-optimal Example

무엇에 우선순위를 두고 해야할지 감이 안옵니다. 일단 이것저것 (논문,책) 다 해보고 있겠습니다.

kmu-leeky commented 6 years ago

지금까지 봐서는 D-optimal + constraint 가 가장 적합해보이네. 몽고메리 책에 해당 내용이 있는것 같은데, 그걸 얘기해보자.

mjaysonnn commented 6 years ago

cvxpy 에 대해서 공부해보겠습니다.

mjaysonnn commented 6 years ago

in progress from https://github.com/kmu-leeky/matrix-doe

kmu-leeky / cloud-2018

DOE를 사용하여 의미있고 정확도를 높여줄 Training data 만들기 #17

various DOE techniques

현재 공부한 바로는 사용할 수 있는게

Latin Hypercube

> 다른 criterion이랑 비교해보면( -0.67, 0.4, 0.3 corref가 존재) 5번 corref 이 제일 0에 가깝습니다. (서로 거의 무시될수 있는 선형관계 from wiki)

책을 읽으면서 몇가지 정리해보자면

In Summary, To-do lists

DOE/Memory-Based

DOE/Mixture Models

DOE/Ernest

DOE/Latin Hypercube with constraints