### 음성 인공지능 스타트업의 기회 분석

- Get link
- Other Apps

- Get link
- Other Apps

- Get link
- Other Apps

- Get link
- Other Apps

- Get link
- Other Apps

The Breadth-First Search (BFS) & MapReduce was roughly introduced from Distributed Computing Seminar. The graph is stored as a sparse matrix, finds shortest path using Map/Reduce as describe below:

According to above-mentioned idea, A map task receives a node n as a key, and (D, points-to) as its value. It means that an "input" is a set of all reachable path from 'start' to each key.

**Updated**: My mis-understand. It doesn't need an set of all reachable path. See page 9 - "Adjacency Matrices".

So, It can be represented as below:

1 (2, 4)

2 (1, 3, 4)

3 (2)

4 (1, 3)

Then, MR job will iterate 'hop' times(= maximum distance). Let's assume the start node is "1".

Here's my test code:

Finding the Shortest Path: Intuition

- We can define the solution to this problem inductively:

- DistanceTo(startNode) = 0

- For all nodes n directly reachable from startNode, DistanceTo(n) = 1

- For all nodes n reachable from some other set of nodes S,

- DistanceTo(n) = 1 + min(DistanceTo(m), m ∈ S)

From Intuition to Algorithm

- A map task receives a node n as a key, and (D, points-to) as its value

- D is the distance to the node from the start

- points-to is a list of nodes reachable from n

∀p ∈ points-to, emit (p, D+1)

- Reduce task gathers possible distances to a given p

and selects the minimum one

According to above-mentioned idea, A map task receives a node n as a key, and (D, points-to) as its value. It means that an "input" is a set of all reachable path from 'start' to each key.

- Another classic graph representation.

M[i][j]= '1' implies a link from node i to j.

- Naturally encapsulates iteration over nodes

| 1 2 3 4

--+----------

1 | 0 1 0 1

2 | 1 0 1 1

3 | 0 1 0 0

4 | 1 0 1 0

So, It can be represented as below:

1 (2, 4)

2 (1, 3, 4)

3 (2)

4 (1, 3)

Then, MR job will iterate 'hop' times(= maximum distance). Let's assume the start node is "1".

First MR job:

1 D=0, points-to=(2, 4)

2 D=inf, points-to=(1, 3, 4)

3 D=inf, points-to=(2)

4 D=inf, points-to=(1, 3)

Result: (2,1), (4,1)

Second MR job:

1 D=0, points-to=(2, 4)

2 D=1, points-to=(1, 3, 4)

3 D=inf, points-to=(2)

4 D=1, points-to=(1, 3)

Result: (2,1), (3,2), (4,1)

Here's my test code:

public class BFS {

static Map<String, ArrayList<String>> collect = new HashMap<String, ArrayList<String>>();

public static void main(String[] args) {

String[] value = {

// key | distance | points-to

"1|0|2;4",

"2|"+Integer.MAX_VALUE+"|1;3;4",

"3|"+Integer.MAX_VALUE+"|2",

"4|"+Integer.MAX_VALUE+"|1;3",

};

mapper(value);

reducer(collect.entrySet());

}

private static void mapper(String[] value) {

for (int i = 0; i < value.length; i++) {

String line = value[i].toString();

String[] keyVal = line.split("[|]");

String Key = keyVal[0];

String sDist = keyVal[1];

String[] links = null;

if (keyVal.length > 2) {

links = keyVal[2].split(";");

int Dist = Integer.parseInt(sDist);

if (Dist != Integer.MAX_VALUE)

Dist++;

for (int x = 0; x < links.length; x++) {

if (links[x] != "") {

ArrayList<String> list;

if (collect.containsKey(links[x])) {

list = collect.get(links[x]);

} else {

list = new ArrayList<String>();

}

list.add(Dist + "|");

collect.put(links[x], list);

}

}

ArrayList<String> list;

if (collect.containsKey(Key)) {

list = collect.get(Key);

} else {

list = new ArrayList<String>();

}

list.add(sDist + "|" + keyVal[2]);

collect.put(Key, list);

}

}

}

private static void reducer(Set<Entry<String, ArrayList<String>>> entrySet) {

for (Map.Entry<String, ArrayList<String>> e : entrySet) {

Iterator<String> values = e.getValue().iterator();

int minDist = Integer.MAX_VALUE;

String link_list = "";

while (values.hasNext()) {

String[] dist_links = values.next().toString().split("[|]");

if (dist_links.length > 1)

link_list = dist_links[1];

int dist = Integer.parseInt(dist_links[0]);

minDist = Math.min(minDist, dist);

}

System.out.println(e.getKey() + " - D " + (minDist + " | " + link_list));

}

}

}

1.군계 (액션,격투)

격투만화 중에서는 아주 유명하고 열광적으로 좋아하는 사람이 많은 만화입니다. 전체적으로 만화의 분위기는 어둡고요... 줄거리를 소개하죠. 주인공인 료는 모범생이었습니다. 그러나 부모님의 강압적인 통제... 그에 대한 무의식적 반발로 부모님을 살해하게 되고 맙니다. 그리고 교도소에서 많은 변화를 겪게되죠..그리고 악의 화신같은 존재가 되고 말죠..... 또 그에 대항하는 인물이 나타나고.... 만화에 대한 소개가 만화의 질을 못 따라가네요. 이 만화는 선과 악에 대해 생각해볼 수있는 만화입니다. 그리고 싸움이란 인간에게 어떤 의미가 있는것일까? 하는 생각도요. 아..군계는 싸움닭이란 뜻입니다. 네이밍센스가 좋죠.

2. 생추어리(해적판제목:빛과 그림자) (액션,정치)

일본 최고의 극화체 만화가인 이케가미 료이치님의 작품입니다. 캄보디아에서 일본 외교관의 아들로 태어난 두 남자 이야기를 그리고 있습니다. 캄보디아의 킬링필드(대학살..실존사건입니다.)와중에서 살아남아 돌아온 두 주인공..한명은 암흑계 보스로 다른 한 명은 정치계 거물로 성장해갑니다. 두 남자의 목숨과도 같은 우정....그들의 관계는 어떻게 될까? 뛰어난 스토리작가와 항상 작업하여 재미는 보장이 되는 작품입니다. 단 남성우월주의가 작품전반에 깔려있어서 여성이 보기엔 거부감을 느낄수도 있는 작품..남자분인거 같아 추천합니다.

3.수라의 각 (역사,무협)

해황기의 작가가 쓴 매우 흥미진진한 역사 무협물입니다. 일본 역사속의 많은 실존인물들의 얘기를 기둥줄거리로 하여 거기에 허구를 작가의 능수능란한 솜씨로 섞어냅니다. 이 작품은 코믹 만화인 수험의 제왕에도 등장하는 데요....그 만화에 이런 말이 있지요. "역사 공부를 하려거든 수라의 각을 읽어라" 이 만화작가의 다른 작품인 해황기도 매우 흥미진진하답니다.

4.베르세르크 (판타지)

말이 필요없는 판타지의 최고 걸작.... 뛰어난 작화에 철학적인 사유까지 배어든 최고의 작품. 안 읽으셨다면 부디 읽어보시길..

5.…

격투만화 중에서는 아주 유명하고 열광적으로 좋아하는 사람이 많은 만화입니다. 전체적으로 만화의 분위기는 어둡고요... 줄거리를 소개하죠. 주인공인 료는 모범생이었습니다. 그러나 부모님의 강압적인 통제... 그에 대한 무의식적 반발로 부모님을 살해하게 되고 맙니다. 그리고 교도소에서 많은 변화를 겪게되죠..그리고 악의 화신같은 존재가 되고 말죠..... 또 그에 대항하는 인물이 나타나고.... 만화에 대한 소개가 만화의 질을 못 따라가네요. 이 만화는 선과 악에 대해 생각해볼 수있는 만화입니다. 그리고 싸움이란 인간에게 어떤 의미가 있는것일까? 하는 생각도요. 아..군계는 싸움닭이란 뜻입니다. 네이밍센스가 좋죠.

2. 생추어리(해적판제목:빛과 그림자) (액션,정치)

일본 최고의 극화체 만화가인 이케가미 료이치님의 작품입니다. 캄보디아에서 일본 외교관의 아들로 태어난 두 남자 이야기를 그리고 있습니다. 캄보디아의 킬링필드(대학살..실존사건입니다.)와중에서 살아남아 돌아온 두 주인공..한명은 암흑계 보스로 다른 한 명은 정치계 거물로 성장해갑니다. 두 남자의 목숨과도 같은 우정....그들의 관계는 어떻게 될까? 뛰어난 스토리작가와 항상 작업하여 재미는 보장이 되는 작품입니다. 단 남성우월주의가 작품전반에 깔려있어서 여성이 보기엔 거부감을 느낄수도 있는 작품..남자분인거 같아 추천합니다.

3.수라의 각 (역사,무협)

해황기의 작가가 쓴 매우 흥미진진한 역사 무협물입니다. 일본 역사속의 많은 실존인물들의 얘기를 기둥줄거리로 하여 거기에 허구를 작가의 능수능란한 솜씨로 섞어냅니다. 이 작품은 코믹 만화인 수험의 제왕에도 등장하는 데요....그 만화에 이런 말이 있지요. "역사 공부를 하려거든 수라의 각을 읽어라" 이 만화작가의 다른 작품인 해황기도 매우 흥미진진하답니다.

4.베르세르크 (판타지)

말이 필요없는 판타지의 최고 걸작.... 뛰어난 작화에 철학적인 사유까지 배어든 최고의 작품. 안 읽으셨다면 부디 읽어보시길..

5.…

음성 인공지능 분야에서 스타트업이 생각해볼 수 있는 전략은 아마 다음과 같이 3가지 정도가 있을 것이다:

독자적 Vertical 음성 인공지능 Application 구축기 음성 플랫폼을 활용한 B2B2C 형태의 비지니스 구축기 음성 플랫폼 생태계 내에 3rd party 서비스 구축

(1) 의 접근은 도메인 특화된 Standalone 음성 인공지능 Application을 만드는 방법이다. (2) 의 접근은 기 음성 플랫폼 비지니스 사업자에 특수 분야 기술을 제공해서 최종적으로 소비자에게 전달되는 B2B2C 형태의 사업 추진이다. 마지막으로 (3) 은 기 음성 플랫폼 내 3rd party 서비스를 개발하여 소비자에게 제공하는 방법이다. 지금부터 하나씩 사례와 함께 자세히 살펴보자.

1) 독자적**Vertical** 음성 인공지능 **Application** 구축

너무 당연한 얘기지만 스타트업이 구글이나 아마존의 범용 음성인식과 차별없는 음성 인식을 통해 경쟁하려 든다면 그것은 별로 좋은 아이디어는 아니다. 구글이나 바이두와 같은 막강한 기업 만큼의 예산과 기술을 갖추고 있지 않기 때문에 무조건 백전 백패다.

그러나, 특정 산업에 특화된 문제를 발굴하고 AI를 결합해 그 문제를 해결하는 접근으로 속도를 내고 있는 Vertical AI 스타트업이 있다. 대표적으로 Chorus.ai와 한국의 리뷰와이저(?), 액션파워 정도가 될 것 같다.

코러스의 창업자는 도메인 특화된 버티컬 엔진이 (경험적으로 퉁쳐서) 일반 범용 엔진보다 최소 15% 향상된 성능을 낼 수 있다고 한다. 국내 Vertical voice AI 회사도 만나본 적은 있지만 개인적으로 나눈 대화다 보니 특별히 언급은 생략한다.

뭐 여하튼 (정량적 평가 수치는 확인할 수 없었으나) 기술적으로 따져보았을 때 명백히 narrow domain으로 접근하면 자연어 처리에 있어 그 복잡도를 낮추고 결론적으로 높은 성능을 낼 수는 있을 것이다.

이 때문에 도메인 특화된 음성 인식 엔진은 당장 빠르게 우위를 점할 수 있다는 점은 분명하…

독자적 Vertical 음성 인공지능 Application 구축기 음성 플랫폼을 활용한 B2B2C 형태의 비지니스 구축기 음성 플랫폼 생태계 내에 3rd party 서비스 구축

(1) 의 접근은 도메인 특화된 Standalone 음성 인공지능 Application을 만드는 방법이다. (2) 의 접근은 기 음성 플랫폼 비지니스 사업자에 특수 분야 기술을 제공해서 최종적으로 소비자에게 전달되는 B2B2C 형태의 사업 추진이다. 마지막으로 (3) 은 기 음성 플랫폼 내 3rd party 서비스를 개발하여 소비자에게 제공하는 방법이다. 지금부터 하나씩 사례와 함께 자세히 살펴보자.

1) 독자적

너무 당연한 얘기지만 스타트업이 구글이나 아마존의 범용 음성인식과 차별없는 음성 인식을 통해 경쟁하려 든다면 그것은 별로 좋은 아이디어는 아니다. 구글이나 바이두와 같은 막강한 기업 만큼의 예산과 기술을 갖추고 있지 않기 때문에 무조건 백전 백패다.

그러나, 특정 산업에 특화된 문제를 발굴하고 AI를 결합해 그 문제를 해결하는 접근으로 속도를 내고 있는 Vertical AI 스타트업이 있다. 대표적으로 Chorus.ai와 한국의 리뷰와이저(?), 액션파워 정도가 될 것 같다.

코러스의 창업자는 도메인 특화된 버티컬 엔진이 (경험적으로 퉁쳐서) 일반 범용 엔진보다 최소 15% 향상된 성능을 낼 수 있다고 한다. 국내 Vertical voice AI 회사도 만나본 적은 있지만 개인적으로 나눈 대화다 보니 특별히 언급은 생략한다.

뭐 여하튼 (정량적 평가 수치는 확인할 수 없었으나) 기술적으로 따져보았을 때 명백히 narrow domain으로 접근하면 자연어 처리에 있어 그 복잡도를 낮추고 결론적으로 높은 성능을 낼 수는 있을 것이다.

이 때문에 도메인 특화된 음성 인식 엔진은 당장 빠르게 우위를 점할 수 있다는 점은 분명하…

In addressing the growing problem of junk email on the Internet, I examined methods for the automated construction of filters to eliminate such unwanted messages from a user's mail stream. One was "Bayesian Spam Filtering".

Bayesian email filters take advantage of Bayes' theorem. Bayes' theorem, in the context of spam, says that the probability that an email is spam, given that it has certain words in it, is equal to the probability of finding those certain words in spam email, times the probability that any email is spam, divided by the probability of finding those words in any email: Pr(spam|words)=Pr(words|spam)Pr(spam)/Pr(words)

In this post, I'm introduce about the implementation of a Parallel Bayesian Spam Filtering Algorithm on the distributed system (Hadoop).

1. We can get the spam probability P(wordcategory) of the words from an files of category (bad/good e-mails) as describe below:

**Update**: --emit <category,probability> pairs and have the redu…

Bayesian email filters take advantage of Bayes' theorem. Bayes' theorem, in the context of spam, says that the probability that an email is spam, given that it has certain words in it, is equal to the probability of finding those certain words in spam email, times the probability that any email is spam, divided by the probability of finding those words in any email: Pr(spam|words)=Pr(words|spam)Pr(spam)/Pr(words)

In this post, I'm introduce about the implementation of a Parallel Bayesian Spam Filtering Algorithm on the distributed system (Hadoop).

1. We can get the spam probability P(wordcategory) of the words from an files of category (bad/good e-mails) as describe below:

Great! Really awesome. I've started with hadoop few months ago, and now I'm exploring hama. Cool project, I had a quite few ideas on the past that would take huge sparse matrix (millionsxmillions), I hope this solves my problems.

ReplyDeleteThanks for the project dude!

I thank you for your time and I hope to hear your advice. ;)

ReplyDeleteJust commented, thinking The row URLs and anchor family of webTable that mentioned in BigTable paper is same with above structure. It's the web-link graph which is represented as an adjacency matrix.

ReplyDeleteAs far as I understand, this BFS method will have to run in O(D) iterations where D is the diameter of the graph. Consider a graph that is formed like a linked-list (a chain). Running BFS on this graph where the source is on the start of the linked list will force it to run N iterations of map/reduce. That is, N is the diameter of the graph. Thus making map/reduce NOT suitable for processing graph with large diameter. This is also true for finding shortest path, it has to run in O(D) map/reduce iterations.

ReplyDeleteDo you know any tricks to improve finding shortest path that requires less than O(D) map/reduce iterations?

Yeah right, It requires O(D) M/R iterations.

ReplyDeleteI think, there is no better solution. Even if iterations are reduced, It'll cause huge network costs. In other words, the M/R programming isn't fit with graph computing.

There is a Google Pregel for large-scale graph computing, and the BSP package of Apache Hama -- http://blog.udanax.org/2009/12/bsp-package-of-hama-on-hadoop-is-now.html

I hope this is of some help. Don't hesitate to ask further details.

I saw Apache Hamburg and Hama presentation slides:

ReplyDeletehttp://wiki.apache.org/hama/Presentations?action=AttachFile&do=get&target=Hamburg-Hadoop.pdf

http://wiki.apache.org/hama/BulkSynchronizationParallel?action=AttachFile&do=get&target=Apache_HAMA_BSP.pdf

They are great! BSP seemed to help in reducing the number of M/R iterations in doing the BFS by grouping some vertices in a "super node" and process them in a "super step" thus each iteration may expand the frontier more than one.

I saw partial codes in the slides on how to do Breadth-frist search using Hama. However it'd be nice to see the full working code and actuall try it and benchmark it with the regular M/R (the non BSP). The wiki BFS on Hama is not available yet (http://wiki.apache.org/hama/BFS).

Can you give some clue on the Hama project? How mature it is right now?

Thanks!

Website: http://incubator.apache.org/hama/

ReplyDeleteI'm thinking that BSP can be done in plain M/R if there is a way to "Group" the values for a certain key-range for the Mapper (we know that in Reducer, there is a way to group the values). Here is how to simulate BSP in regular M/R:

ReplyDeleteCurrently, in regular M/R, each map() function will take and process exactly ONE key-value pair at at time. Now we want to modify the map() function so that it takes SEVERAL key-value pairs (so that they can be processed in "bulk") thus simulating BSP ;) To group several key-value pairs together, we need to have a Mapper GROUPING function to tell which key-value pairs belong to one group. The Mapper map function API has to be changed to something like:

map(

KeyRangeWritable keyRange,

List values,

OutputCollector output,

Reporter reporter

)

The "keyRange" contains a pair of key: start key and end key of this group.

The "values" contains the actual values for the keys inbetween the start and end of the "keyRange" above.

The "output" will collect INDIVIDUAL KEY that is emmitted from this map.

The "reporter" is the same as the old reporter.

So now, each map() processes a group of key-value pairs, thus it's like BSP and can do the Bulk processing as in slide #11 and #17 of:

http://wiki.apache.org/hama/Presentations?action=AttachFile&do=get&target=Hamburg-Hadoop.pdf

One way to group the key-value pairs is first you need to sort the input based on the key, and then define the Group function (like the Reducer grouping the values in SecondarySort) that tells the range of the keys for the groups. Complex grouping can be done by defining a customized sorting function for the key-value pair and then use the grouping function based on that input.

So, how does Hama works to provide BSP? Is there any paper/articles of it?

http://blog.udanax.org/2009/07/hamburg-graph-computing-framework-on.html

ReplyDeleteThis post could be helpful for you. In M/R case, it should be iterate 3 times. That algorithm can't be implemented on M/R framework.

I agree that they are similar on one side but, If you look closely, they are different in synchronization/combine of data. Each nodes should know who they should communicate with.

>> So, how does Hama works to provide BSP? Is there any paper/articles of it?

Yes but, we're still in progress. :)

I cannot draw the graph here in this example. I believe there is a mistake.

ReplyDeleteWhen "3 (2)", how is "4 (1, 3)" possible? In other words, node 3 can reach node 2 and node 4 can reach nodes 1 and 3. Then, why node 3 cannot reach node 4?

It seems there's a typo. 4 (1, 2), not 4 (1, 3)

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHi Edward J. Yoon, I'm looking on MapReduce apply in board games, like Go, Othello,.... I want to use MapReduce for set Monte Carlo Tree search and Minimax algorithms in board games such as GomoKu, Go, Connect6 ... Hope you help? You can give me for examples are not? For example Tic-Tac-Toe game?

ReplyDeleteLook forward to your help.

Thank you very much!

I realize that this content is worth to read. I expect to see more posts from you that makes me impressed just like this one. Good job!!

ReplyDelete