블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 받은 트랙백

글 보관함

calendar

          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Elements of AI - The nearest neighbor classifier

2018.06.20 13:46 | Posted by 솔웅



Elements of AI




II.The nearest neighbor classifier




The nearest neighbor classifier is among the simplest possible classifiers. When given a item to classify, it finds the training data item that is most similar to the new item, and outputs its label. An example is given in the following diagram.


가장 가까운 neighbor classifier는 가장 단순한 possible classifiers 중 하나이다. 분류 할 항목이 주어지면 그 새 항목과 가장 유사한 training data item을 찾고 해당 레이블을 출력합니다. 다음 다이어그램에 예제가 나와 있습니다.







In the above diagram, we show a collection of training data items, some of which belong to one class (green) and other to another class (blue). In addition, there are two test data items, the stars, which we are going to classify using the nearest neighbor method.




위의 다이어그램에서 우리는 하나의 클래스 (녹색)와 다른 클래스 (파란색)에 속하는 training data items의 모음을 보여줍니다. 또한 가장 가까운 neighbor method을 사용하여 분류 할 2 개의 테스트 데이터 항목 (별)이 있습니다.



The two test items are both classified in the “green” class because their nearest neighbors are both green (see diagram (b) above).



두 test items은 가장 가까운 이웃이 모두 녹색이기 때문에 "녹색"등급으로 분류됩니다 (위 그림 (b) 참조).



The position of the points in the plot represents in some way the properties of the items. Since we draw the diagram on a flat two-dimensional surface — you can move in two independent directions: up-down or left-right — the items have two properties that we can use for comparison. Imagine for example representing patients at a clinic in terms of their age and blood-sugar level. But the above diagram should be taken just as a visual tool to illustrate the general idea, which is to relate the class values to similarity or proximity (nearness). The general idea is by no means restricted to two dimensions and the nearest neighbor classifier can easily be applied to items that are characterized by many more properties than two.



플롯에서 점의 위치는 항목의 속성을 어떤 식 으로든 나타냅니다. 다이어그램을 평평한 2 차원 표면에 그림으로서 두 가지 독립적 인 방향 (상하 또는 좌우)으로 이동할 수 있습니다. 이 항목에는 비교를 위해 사용할 수있는 두 가지 속성이 있습니다. 예를 들어 클리닉의 환자를 연령과 혈당치로 대표한다고 상상해보십시오.  위의 다이어그램은 클래스 값을 유사성 또는 근접성과 관련시키는 일반적인 아이디어를 설명하기위한 시각적 도구로서 사용되어집니다. 일반적인 개념은 결코 2 차원으로 제한되지 않으며 가장 가까운 이웃 분류자는 2보다 많은 특성을 특징으로하는 항목에 쉽게 적용될 수 있습니다.






What do we mean by nearest?



An interesting question related to (among other things) the nearest neighbor classifier is the definition of distance or similarity between instances. In the illustration above, we tacitly assumed that the standard geometric distance, technically called the Euclidean distance, is used. This simply means that if the points are drawn on a piece of paper (or displayed on your screen), you can measure the distance between any two items by pulling a piece of thread straight from one to the other and measuring the length.



가장 가까운 neighbor classifier (다른 것들 중에서)와 관련된 흥미로운 질문은 인스턴스 간의 거리 또는 유사성의 정의입니다. 위의 그림에서 우리는 기술적으로 Euclidean 거리라고 불리는 표준 기하학적 거리를 암묵적으로 가정했습니다. 이것은 단순히 포인트가 종이에 그려 지거나 (또는 화면에 표시되는 경우) 하나의 선을 다른 것으로 똑바로 잡아 당겨 길이를 측정함으로써 두 아이템 간의 거리를 측정 할 수 있음을 의미합니다.




Note

Defining ‘nearest’

Using the geometric distance to decide which is the nearest item may not always be reasonable or even possible: the type of the input may, for example, be text, where it is not clear how the items are drawn in a geometric representation and how distances should be measured. You should therefore choose the distance metric on a case-by-case basis.


어떤 항목이 가장 가까운 항목인지를 결정하기 위해 기하학적 거리를 사용하는 것은 항상 합리적이지는 않습니다. 그리고 심지어 가능하지 않을 수도 있습니다. 예를 들어, 입력 유형은 텍스트 일 수 있으며, 항목이 기하학적 표현으로 어떻게 그려지는지 명확하지 않고 어떻게 거리가 측정되어야 하는지도 명확하지 않습니다. 그러므로 여러분은 케이스 바이 케이스를 기반으로 거리 측정을 해야 합니다.




In the MNIST digit recognition case, one common way to measure image similarity is to count pixel-by-pixel matches. In other words, we compare the pixels in the top-left corner of each image to one another and if the more similar color (shade of gray) they are, the more similar the two images are. We also compare the pixels in the bottom-right corner of each image, and all pixels inbetween. This technique is quite sensitive to shifting or scaling the images: if we take an image of a '1' and shift it ever so slightly either left or right, the outcome is that the two images (before and after the shift) are very different because the black pixels are in different positions in the two images. Fortunately, the MNIST data has been preprocessed by centering the images so that this problem is alleviated.



MNIST 숫자 인식 케이스의 경우 이미지 유사성을 측정하는 일반적인 방법 중 하나는 픽셀 별 매치를 계산하는 것입니다. 즉, 각 이미지의 왼쪽 위 모서리에있는 픽셀을 서로 비교하고 더 비슷한 색 (회색 음영) 일수록 두 이미지가 더 유사하다고 판단합니다. 이렇게 각 이미지의 오른쪽 하단에있는 픽셀과 그 사이에있는 모든 픽셀을 비교합니다. 이 기술은 이미지를 이동하거나 크기를 조정하게 되면 민감하게 영향을 미칩니다. '1'이미지를 가져 와서 왼쪽 또는 오른쪽으로 조금씩 이동하면 결과적으로 두 이미지 (이동 전후)가 매우 다르게 됩니다. 검은 색 픽셀은 두 이미지에서 서로 다른 위치에 있기 때문입니다. 다행히도, MNIST 데이터는 이미지를 센터링하여 사전 처리되어 이 문제가 완화되었습니다.




Using nearest neighbors to predict user behavior


A typical example of an application of the nearest neighbor method is predicting user behavior in AI applications such as recommendation systems.


가장 nearest neighbor 방법의 전형적인 적용 예는 추천 시스템과 같은 AI 어플리케이션에서의 사용자 행동을 예측하는 것입니다.



The idea is to use the very simple principle that users with similar past behavior tend to have similar future behavior. Imagine a music recommendation system that collects data about users’ listening behavior. Let’s say you have listened to 1980s disco music (just for the sake of argument). One day, the service provider gets their hands on a hard-to-find 1980 disco classic, and add it into the music library. The system now needs to predict whether you will like it or not. One way of doing this is to use information about the genre, the artist, and other metadata, entered by the good people of the service provider. However, this information is relatively scarce and coarse and it will only be able to give rough predictions.



이 아이디어는 유사한 과거 행동을 하는 사용자가 비슷한 미래 행동을하는 경향이 있다는 아주 단순한 원칙을 사용하는 것입니다. 사용자의 청취 행동에 관한 데이터를 수집하는 음악 추천 시스템을 상상해보십시오. 1980 년대 디스코 음악을 들어 봤다고합시다. 어느 날, 서비스 제공 업체는 찾기 힘든 1980 디스코 클래식을 음악 라이브러리에 추가합니다. 시스템은 이제 당신이 좋아할 것인지 아닌지 예측할 필요가 있습니다. 이렇게하는 한 가지 방법은 서비스 제공 업체의 좋은 사람들이 입력 한 장르, 아티스트 및 기타 메타 데이터에 대한 정보를 사용하는 것입니다. 그러나 이 정보는 상대적으로 부족하고 거친 것이며 예측할 수 없을 것입니다.



What current recommendation systems use instead of the manually entered metadata, is something called collaborative filtering. The collaborative aspect of it is that it uses other users’ data to predict your preferences. The word “filter” refers to the fact that you will be only recommended content that passes through a filter: content that you are likely to enjoy will pass, other content will not. (This kind of filters may lead to the so called filter bubbles, which we mentioned in Chapter 1. We will return to them later.)



현재 추천 시스템이 사용하는 것은 수동으로 입력 한 메타 데이터 대신에 사용하는 collaborative filtering 이라고 하는 것입니다. collaborative라는 것은 여러분의 preferences를 예측하기 위해 다른 사용자들의 데이터를 사용한다는 겁니다.  'filter'라는 단어는 필터를 통과하는 콘텐츠만 추천된다는 것을 의미합니다. 여러분이 선호하는 콘텐츠들이 통과하고 그렇지 않은 것들은 통과하지 않을 겁니다.  (이런 종류의 필터는 1 장에서 언급 한 소위 말하는 필터 버블을 유발할 수 있습니다. 나중에 이부분은 다시 다루게 될 것입니다. )



Now let’s say that other users who have listened to 80s disco music enjoy the new release and keep listening to it again and again. The system will identify the similar past behavior that you and other 80s disco fanatics share, and since other users like you enjoy the new release, the system will predict that you will too. Hence it will show up at the top of your recommendation list. In an alternative reality, maybe the added song is not so great and other users with similar past behavior as yours don't really like it. In that case, the system wouldn't bother recommending it to you, or at least it wouldn't be at the top of the list of recommendations to you.



이제 80 년대 디스코 음악을 들었던 다른 사용자가 새 릴리스를 즐기고 이것을 계속해서 다시 듣는다고 가정 해 봅시다. 이 시스템은 귀하와 다른 80 년대 디스코 광신자들이 공유 한 유사한 과거 행동을 식별하고, 당신 같은 다른 사용자가 새로운 릴리스를 즐기기 때문에 시스템은 귀하도 그렇게 할 것이라고 예측할 것입니다. 따라서 추천 목록 상단에 표시됩니다. 현실에서는, 추가 된 노래가 그리 좋지 않을 수도 있고 당신과 비슷한 과거 행동을하는 다른 사용자가 이것을 좋아하지 않을 수도 있습니다. 이 경우 시스템에서 권장하지 않거나 최소한 추천 목록 맨 위에 올 수 없습니다.



The following exercise will illustrate this idea.



다음 연습문제에서 이 부분을 다루고 있습니다.





AWS DeepLens - Deep learning enabled video camera for developers




Exercise 14: Customers who bought similar products


In this exercise, we will build a simple recommendation system for an online shopping application where the users' purchase history is recorded and used to predict which products the user is likely to buy next.



이 연습문제 에서는 사용자의 구매 내역이 기록되고 사용자가 다음에 구매할 제품을 예측하는 데 사용되는 온라인 쇼핑 응용 프로그램을 위한 간단한 추천 시스템을 구축 할 것입니다.



We have data from six users. For each user, we have recorded their recent shopping history of four items and the item they bought after buying these four items:



우리는 6 명의 사용자 데이터를 가지고 있습니다. 각 사용자별로 4 가지 항목에 대한 최근 구매 내역과 4 가지 항목을 구입 한 후 구입 한 항목을 기록했습니다.






The most recent purchase is the one in the rightmost column, so for example, after buying a t-shirt, flip flops, sunglasses, and Moby Dick (novel), Ville bought sunscreen. Our hypothesis is that after buying similar items, other users are also likely to buy sunscreen.



맨 오른쪽에 있는 것들이 가장 최근에 구입한 목록들입니다. 예를 들어, Ville은 티셔츠, 플립 플롭, 선글라스 및 Moby Dick (소설)을 구입 한 후, 썬 스크린을 샀습니다. 우리의 가설은 비슷한 품목을 구입 한 다른 사용자들도 선 스크린을 사기 쉽다는 것입니다.



To apply the nearest neighbor method, we need to define what we mean by nearest. This can be done in many different ways, some of which work better than others. Let’s use the shopping history to define the similarity (“nearness”) by counting how many of the items have been purchased by both users.



nearest neighbor method을 적용하려면 nearest의 의미를 정해야 합니다. 이것은 여러 가지 방법으로 수행 할 수 있으며 그 중 일부는 다른 것보다 효과적일 겁니다. shopping history을 사용하여 두 사용자가 구매 한 항목 수를 계산하여 유사성 ( "nearness")을 정의합시다.



For example, users Ville and Henrik have both bought a t-shirt, so their similarity is 1. Note that flip flops doesn't count because we don't include the most recent purchase when calculating the similarity — it is reserved for another purpose.


예를 들어, Ville과 Henrik user는 모두 티셔츠를 구입했기 때문에 유사도는 1입니다. 유사도를 계산할 때 가장 최근의 구매가 포함되어 있지 않으므로 플립 플립은 포함되지 않습니다. 그것은 다른 용도로 사용될 겁니다.



Our task is to predict the next purchase of customer Travis who has bought the following products:



이제 아래 상품들을 구매한 Travis라는 고객의 다음 구매를 예측하는 겁니다.





You can think of Travis being our test data, and the above six users make our training data.



Travis가 우리의 테스트 데이터라고 생각하세요.  위의 6 명의 사용자가 우리의 training data를 만듭니다.




Proceed as follows:


  1. Calculate the similarity of Travis relative to the six users in the training data (done by adding together the number of similar purchases by the users).
  2. Having calculated the similarities, identify the user who is most similar to Travis by selecting the largest of the calculated similarities.
  3. Predict what Travis is likely purchase next by looking at the most recent purchase (the rightmost column in the table) of the most similar user from the previous step.


1. training data에서 6 명의 사용자에 대한 Travis의 유사성을 계산합니다 (사용자가 유사한 구매 횟수를 합산하여 계산).

2. 유사점을 계산 한 후 계산 된 유사성 중 가장 큰 것(숫자)을 선택하여 Travis와 가장 유사한 사용자를 식별합니다.

3. 이전 단계에서 가장 유사한 사용자의 가장 최근 구매 (테이블의 가장 오른쪽 열)를보고 Travis가 다음에 구매할 것으로 예상되는 것을 예측합니다.




In the above example, we only had six users’ data and our prediction was probably very unreliable. However, online shopping sites often have millions users, and the amount of data they produce is massive. In many cases, there are a hoard of users whose past behavior is very similar to yours, and whose purchase history gives a pretty good indication of your interests.



위의 예에서 우리는 6 명의 사용자 데이터 만 가지고 있었고 예측은 매우 신뢰할 수 없었습니다. 그러나 온라인 쇼핑 사이트는 대개 수백만 명의 사용자를 보유하고 있으며 이들이 생산하는 데이터의 양은 방대합니다. 많은 경우 사용자의 과거 행동이 당신과 매우 유사하며 구매 내역이 당의 관심사를 잘 보여주는 사용자가 많습니다.



These predictions can also be self-fulfilling prophecies in the sense that you are more likely to buy a product if it is recommended to you by the system, which makes it tricky to evaluate how well they actually work. The same kind of recommendation systems are also used to recommend music, movies, news, and social media content to users. In the context of news and social media, filters created by such systems can lead to filter bubbles.



이러한 예측은 시스템에서 사용자에게 권장되는 제품을 그 사용자가 구매할 확률이 높다는 의미에서 self-fulfilling prophecies이 될 수 있습니다. 이는 실제로 얼마나 효과적인지 평가하는 것이 까다로울 수 있습니다. 음악, 영화, 뉴스 및 소셜 미디어 콘텐츠를 사용자에게 추천하는데도 동일한 종류의 추천 시스템이 사용됩니다. 뉴스 및 소셜 미디어의 맥락에서 이러한 시스템에 의해 생성 된 필터는 필터 버블을 유발할 수 있습니다.




Exercise 15: Filter bubbles

As discussed above, recommending news of social media content that a user is likely to click or like, may lead to filter bubbles where the users only see content that is in line with their own values and views.



위에서 언급했듯이 사용자가 클릭하거나 좋아할만한 소셜 미디어 콘텐츠의 뉴스를 추천하면 사용자가 자신의 가치(values) 및 관점(views)과 일치하는 콘텐츠 만 보게되는 필터 버블이 발생할 수 있습니다.



  1. Do you think that filter bubbles are harmful? After all, they are created by recommending content that the user likes. What negative consequences, if any, may be associated with filter bubbles? Feel free to look for more information from other sources.
  2. Can you think of ways to avoid filter bubbles while still being able to recommend content to suit personal preferences? Try to come up with at least one suggestion. You can look for ideas from other sources, but we'd like to hear your own ideas too!


1. 필터 거품이 유해하다고 생각합니까? 결국, 그들은 사용자가 좋아할만한 내용을 추천하는 것을 통해 만들어집니다.  필터 거품과 관련해서 어떤 부정적인 요소가 있을 수 있을 까요? 여러분들 마음껏 다른 출처들을 통해 더 많은 정보를 찾아보세요.


2. 개인의 취향에 맞게 콘텐츠를 추천 하면서도 필터 거품을 피하는 방법이 있을까요? 적어도 하나의 제안을 내놓으십시오. 다른 출처에서 아이디어를 찾으셔도 되지만 여러분만의 생각을 한번 들어보고 싶습니다. 



Note: your answer should be at least a few sentences for each part.





Elements of AI - The types of machine learning

2018.06.15 15:18 | Posted by 솔웅



Elements of AI




I.The types of machine learning





Handwritten digits are a classic case that is often used when discussing why we use machine learning, and we will make no exception.

Handwritten digits는 machine learning을 사용하는 이유를 논의 할 때 자주 사용되는 고전적인 사례입니다. 우리도 예외는 아니죠.




Below you can see examples of handwritten images from the very commonly used MNIST dataset.



아래 MNIST 데이터 세트로 일반적으로 사용되는 손글씨 이미지의 예를 보실 수 있습니다. 






The correct label (what digit the writer was supposed to write) is shown above each image. Note that some of the "correct” class labels are questionable: see for example the second image from left: is that really a 7, or actually a 4?



올바른 label (작성자가 작성해야하는 숫자)은 각 이미지 위에 표시됩니다. "correct” 클래스 레이블 중 일부는 의문의 여지가 있습니다. 예를 들어 왼쪽의 두 번째 이미지를보십시오 : 실제로 7입니까, 아니면 실제로 4입니까?



Note

MNIST – What's that?

Every machine learning student knows about the MNIST dataset. Fewer know what the acronym stands for. In fact, we had to look it up to be able to tell you that the M stands for Modified, and NIST stands for National Institute of Standards and Technology. Now you probably know something that an average machine learning expert doesn’t!


모든 machine learning 학생은 MNIST 데이터 세트에 대해 알고 있습니다. 그 중 이것이 어떤것의 약어인지 아는 학생은 거의 없을 겁니다.  사실 M이 Modified를 나타내고 NIST가 National Institute of Standards and Technology의 약자라고 말해 보겠습니다. 이제 일반적인 machine learning 전문가가 아니라는 것을 아실 수 있으시겠죠?




In the most common machine learning problems, exactly one class value is correct at a time. This is also true in the MNIST case, although as we said, the correct answer may often be hard to tell. In this kind of problems, it is not possible that an instance belongs to multiple classes (or none at all) at the same time. What we would like to achieve is an AI method that can be given an image like the ones above, and automatically spit out the correct label (a number between 0 and 9).



가장 일반적인 machine learning 문제는 한 번에 하나의 클래스 값만 정확하다는 겁니다. ### 이것은 우리가 말했듯이 MNIST 케이스에서도 마찬가지 입니다. 종종 정답이 무엇인지 확정할 수 있을 때기 있습니다. 이런 종류의 문제에서는 인스턴스가 동시에 여러 클래스에 속하게 되는 것은 불가능 합니다. 우리가 달성하고자하는 것은 위의 이미지와 같은 이미지를 제공 받고도 correct label (0에서 9 사이의 숫자)을 자동으로 내 놓을 수 있는 AI 방법론 입니다.





Note

How not to solve the problem

An automatic digit recognizer could in principle be built manually by writing down rules such as:


자동 숫자 인식기는 원칙적으로 다음과 같은 규칙을 작성하여 수동으로 작성할 수 있습니다.


  • if the black pixels are mostly in the form of a single loop then the label is 0
  • if the black pixels form two intersecting loops then the label is 8
  • if the black pixels are mostly in a straight vertical line in the middle of the figure then the label is 1

and so on...

This was how AI methods were mostly developed in the 1980s (so called “expert systems”). However, even for such a simple task as digit recognition, the task of writing such rules is very laborious. In fact, the above example rules wouldn’t be specific enough to be implemented by programming – we’d have to define precisely what we mean by “mostly”, “loop”, “line”, “middle”, and so on.



이것은 1980 년대에 개발 된  AI 인공지능 방법론 이었습니다. expert systems라고 불렸죠. 그러나 숫자 인식과 같은 단순한 작업에도 이러한 규칙을 작성하는 작업은 매우 힘듭니다. 실제로, 위의 예제 규칙은 프로그래밍으로 구현하기에 충분히 구체적이지 않습니다. 우리는 "mostly", "loop", "line", "middle"등의 의미를 정확하게 정의해야합니다.



And even if we did all this work, the result would likely be a bad AI method because as you can see, the handwritten digits are often a bit so-and-so, and every rule would need a dozen exceptions.


그리고 우리가 이 모든 작업을 했더라도, 결과는 아마도 안좋은 인공지능 방법론으로 판명 될 것입니다. 왜냐하면 여러분이 보듯이 손으로 쓴 숫자들은 그냥 그렇습니다. 여러분이 만든 룰에 대해 수십개의 예외적인 요소들이 있을 겁니다..







Three types of machine learning


The roots of machine learning are in statistics, which can also be thought of as the art of extracting knowledge from data. Especially methods such as linear regression and Bayesian statistics, which are both already more than two centuries old (!), are even today at the heart of machine learning. For more examples and a brief history, see the timeline of machine learning (Wikipedia).



machine learning의 뿌리는 통계에 있습니다. 데이터로부터 지식을 추출하는 예술이죠. 특히 2 세기 전의 linear regression 선형 회귀 및 Bayesian statistics 와 같은 방법론은 오늘날에도 기계 학습의 핵심입니다. 더 많은 예제와 간단한 역사를 보려면 machine learning (Wikipedia)의 타임 라인을 참조하십시오.




The area of machine learning is often divided in subareas according to the kinds of problems being attacked. A rough categorisation is as follows:


기계 학습 영역은 종종 공격받는 문제의 종류에 따라 하위 영역으로 나뉩니다. 대략적인 분류는 다음과 같습니다.



Supervised learning: We are given an input, for example a photograph with a traffic sign, and the task is to predict the correct output or label, for example which traffic sign is in the picture (speed limit, stop sign, ...). In the simplest cases, the answers are of the form yes/no. (We call these binary classification problems.)



Supervised learning : 우리는 교통 표지가 있는 사진과 같은 입력을받습니다. 그리고 해야 할 일은 해당 사진에 있는 교통 표지(speed limit, stop sign, ...)에 알맞는 output이나 라벨을 예측하는 것입니다. 가장 단순한 경우 답은 예 / 아니오 형식입니다. (우리는 이러한 이진 분류 문제를 호출합니다.)



Unsupervised learning: There are no labels or correct outputs. The task is to discover the structure of the data: for example, grouping similar items to form “clusters”, or reducing the data to a small number of important “dimensions”. Data visualization can also be considered unsupervised learning.



Unsupervised learning : 레이블이나 정확한 결과 outputs가 없습니다. 예를 들어, 유사한 항목을 그룹화하여 "클러스터"를 형성하거나 소수의 중요한 "dimensions"으로 데이터를 축소하는 등의 데이터 구조를 발견해야합니다. 데이터 시각화는 unsupervised learning 으로 간주 될 수도 있습니다.



Reinforcement learning: Commonly used in situations where an AI agent like a self-driving car must operate in an environment and where feedback about good or bad choices is available with some delay. Also used in games where the outcome may be decided only at the end of the game.



Reinforcement learning : 일반적으로 자율 주행 차량과 같은 인공 지능 agent가 한 환경 안에서 작동해야하며 좋은 선택 또는 나쁜 선택에 대한 피드백을 약간의 지연 후에 가능해야 합니다. 또한 게임이 끝날 때만 결과를 결정할 수있는 게임에서도 사용됩니다.



The categories are somewhat overlapping and fuzzy, so a particular method can sometimes be hard to place in one category. For example, as the name suggests, so called semisupervised learning is partly supervised and partly unsupervised.



categories는 다소 겹치고 fuzzy 하기 (뚜렷하지 않기) 때문에 특정 방법을 때로는 한 category에 배치하기가 어려울 수 있습니다. 예를 들어 그 이름에서 알 수 있듯이 semisupervised learning은 부분적으로 supervised 감독 되고 부분적으로 unsupervised 감독을받지 않습니다.



Note

Classification

When it comes to machine learning, we will focus primarily on supervised learning, and in particular, classification tasks. In classification, we observe in input, such as a photograph of a traffic sign, and try to infer its “class”, such as the type of sign (speed limit 80 km/h, pedestrian crossing, stop sign, ...). Other examples of classification tasks include: identification of fake Twitter accounts (input includes the list of followers, and the rate at which they have started following the account, and the class is either fake or real account) and handwritten digit recognition (input is an image, class is 0,...,9).


machine learning 이라고 하면 우리는 주로 supervised learning와 in particular, classification tasks 에 우선적으로 주목합니다.  classification에서 우리는 교통 표지판 사진 같은 입력을 살펴 봅니다. 그리고 그 “class” 를 추론하죠. 즉 표지판의 타입 (speed limit 80 km/h, pedestrian crossing, stop sign, ...) 같은 클래스를 추론하는 겁니다.  classification의 다른 예는 다음과 같습니다 : 가짜 트위터 계정 (입력에는 팔로어 목록, 그 계정을 팔로우 하기 시작한 시기 등이 포함되어 있고 class는 가짜 계정 또는 진짜 계정이 됩니다.) 및 손글씨 숫자 인식 (입력은 이미지, 클래스는 0, ..., 9) 등이 있습니다..






Humans teaching machines: supervised learning



Instead of manually writing down exact rules to do the classification, the point in supervised machine learning is to take a number of examples, label each one by the correct label, and use them to “train” an AI method to automatically recognize the correct label for the training examples as well as (at least hopefully) any other images. This of course requires that the correct labels are provided, which is why we talk about supervised learning. The user who provides the correct labels is a supervisor who guides the learning algorithm towards correct answers so that eventually, the algorithm can independently produce them.



분류 작업 (classification)을 수행하기 위해 정확한 규칙을 수동으로 작성하는 대신, supervised machine learning의 포인트는 examples들의 숫자를 받아서 정확한 레이블로 각각을 레이블 하고 그것을 인공지능 방법론으로 “train” 훈련 해서 training 된 예제들 뿐만 아니라 트레이닝 되지 않은 예제들에 대해서도 정확한 레이블을 자동적으로 인식하도록 하는 겁니다. 이것은 당연히 올바른 레이블이 제공될 것이 요구됩니다. 그렇기 때문에 supervised learning 이라고 하는 겁니다. 올바른 레이블을 제공하는 사용자는 학습 알고리즘을 정답으로 이끄는 감독자이며 그 감독을 바탕으로 결국 알고리즘이 독립적으로 스스로의 알고리즘을 재생성 할 수 있게 되는 겁니다.




In addition to learning how to predict the correct label in a classification problem, supervised learning can also be used in situations where the predicted outcome is a number. Examples include predicting the number of people who will click a Google ad based on the ad content and data about the user’s prior online behavior, predicting the number of traffic accidents based on road conditions and speed limit, or predicting the selling price of real estate based on its location, size, and condition. These problems are called regression. You probably recognize the term linear regression, which is a classical, still very popular technique for regression.




classification 문제에서 올바른 레이블을 예측하는 방법을 배우는 것 외에도 supervised learning은 예측 된 결과가 숫자 인 경우에도 사용할 수 있습니다. 예를 들어 광고 내용과 사용자의 이전 온라인 행동에 대한 데이터를 기반으로 Google 광고를 클릭하는 사람의 수를 예측하고, 도로 상태 및 속도 제한에 따라 교통 사고의 횟수를 예측하거나 부동산의 위치, 크기, 상태등을 기반으로 그 부동산의 판매가를 예측하는 것들이 그것입니다. 이러한 문제를 회귀 (regression)라고 합니다. 아마도 선형 회귀 linear regression라는 용어를 알고 있을 것입니다. 고전적인 용어죠. 이 선형회귀는 여전히 널리 사용되는 기술입니다.



Note

Example

Suppose we have a data set consisting of apartment sales data. For each purchase, we would obviously have the price that was paid, together with the size of the apartment in square meters (or square feet, if you like), and the number of bedrooms, the year of construction, the condition (on a scale from “disaster“ to “spick and span”). We could then use machine learning to train a regression model that predicts the selling price based on these features. See a real-life example here


아파트 판매 데이터로 구성된 데이터 세트가 있다고 가정합시다. 매 구입마다 아파트의 크기와 함께 평방 미터 (또는 원하는 경우 평방 피트), 침실 수, 건축 연도, 조건 ( "재해"에서 "스픽과 스팬"에 대한 조건) 들에 대한 정보를 얻을 수 있습니다. 그런 다음 machine learning을 사용하여 이러한 기능을 기반으로 판매 가격을 예측하는 회귀 regression 모델을 train 할 수 있습니다. 실생활 예를 들어 보겠습니다.






Caveat: Careful with that Machine Learning algorithm



There are a couple potential mistakes that we'd like to make you aware of. They are related to the fact that unless you are careful with the way you apply machine learning methods, you could become too confident about the accuracy of your predictions, and be heavily disappointed when the accuracy turns out to be worse than expected.



우리가 저지를 수 있는 몇가지 잠재적인 mistakes들이 있습니다.. 그들은 당신이 machine learning 방법을 적용하는 방법에 주의하지 않는 한, 예측의 정확성에 대해 너무 확신 할 수 있고, 정확성이 예상보다 나쁠 때 크게 실망 할 수 있다는 사실과 관련이 있습니다.



The first thing to keep in mind in order to avoid big mistakes, is to split your data set into two parts: the training data and the test data. We first train the algorithm using only the training data. This gives us a model or a rule that predicts the output based on the input variables.



큰 실수를 피하기 위해 염두에 두어야 할 첫 번째 사항은 데이터 세트를 training 데이터와 테스트 데이터의 두 부분으로 분리하는 것입니다. 우리는 우선 training 데이터만을 사용하여 알고리즘을 training 시킵니다. 이것은 입력 변수들을 기반으로 출력을 예측하는 모델 또는 규칙을 제공합니다.



To assess how well we can actually predict the outputs, we can't count on the training data. While a model may be a very good predictor in the training data, it is no proof that it can generalize to any other data. This is where the test data comes in handy: we can apply the trained model to predict the outputs for the test data and compare the predictions to the actual outputs (for example, future apartment sale prices).



실제 출력을 얼마나 잘 예측할 수 있는지 평가하기 위해 training data에만 의지할 수 없습니다. 모델이 training 데이터에서 매우 좋은 예측인자 일 수 있지만, 다른 어떤 데이터로도 일반화 할 수 있다는 증거는 아닙니다. 이것이 테스트 데이터를 사용해야 되는 이유입니다. 우리는 trained model을 적용하여 테스트 데이터의 출력을 예측하고 예상 결과를 실제 출력 (예 : 향후 아파트 판매 가격)과 비교할 수 있습니다.




Note

Too fit to be true! Overfitting alert


It is very important to keep in mind that the accuracy of a predictor learned by machine learning can be quite different in the training data and in separate test data. This is the so called overfitting phenomenon, and a lot of machine learning research is focused on avoiding it one way or another. Intuitively, overfitting means trying to be too smart. When predicting the success of a new song by a known artist, you can look at the track record of the artist's earlier songs, and come up with a rule like “if the song is about love, and includes a catchy chorus, it will be top-20“. However, maybe there are two love songs with catchy choruses that didn't make the top-20, so you decide to continue the rule “...except if Sweden or yoga are mentioned“ to improve your rule. This could make your rule fit the past data perfectly, but it could in fact make it work worse on future test data.


training 데이터와 별도의 테스트 데이터에서 machine learning으로 얻은 예측 변수의 정확도가 매우 다를 수 있다는 점을 명심해야합니다. 이것은 소위 오버 피팅 (overfitting) 현상이며, machine learning 연구의 많은 부분은 이를 피하는 데 초점을 맞추고 있습니다. 직관적으로 overfitting은 너무 똑똑한 것을 의미합니다. 알려진 아티스트의 새로운 노래 성공을 예측할 때 아티스트의 이전 곡의 트랙 레코드를 보고 "노래가 사랑에 관한 것이고 괜찮은 코러스를 넣으면 탑 20에 들 것이다. ". 그러나 괜찮은 코러스가 있는 두개의 사랑노래가 탑 20에 들지 못했다면 규칙을 개선하겠죠. "스웨덴이나 요가에 대한 노래를 제외하고....." 같은 예외 조건들을 넣을 겁니다. 이렇게하면 규칙이 과거 데이터에는 잘 맞을 수 있겠지만 사실 미래의 테스트 데이터에서는 더 안 맞을 수 있습니다.



Machine learning methods are especially prone to overfitting because they can try a huge number of different “rules“ until one that fits the training data perfectly is found. Especially methods that are very flexible and can adapt to almost any pattern in the data can overfit unless the amount of data is enormous. For example, compared to quite restricted linear models obtained by linear regression, neural networks can require massive amounts of data before they produce reliable prediction.


Machine learning 방법은 특히 훈련 데이터에 완벽하게 맞는 것이 발견 될 때까지 엄청난 수의 서로 다른 "규칙"을 시도 할 수 있기 때문에 overfitting에 취약합니다. 특히 매우 유연하고 데이터의 거의 모든 패턴에 적용 할 수있는 방법은 데이터 양이 엄청나지 않는 한 과장 될 수 있습니다. 예를 들어, 선형 회귀에 의해 얻어진 매우 제한된 선형 모델과 비교할 때, 신경망은 신뢰할 수있는 예측을 생성하기 전에 엄청난 양의 데이터를 필요로 할 수 있습니다.




Learning to avoid overfitting and choose a model that is not too restricted, nor too flexible, is one of the most essential skills of a data scientist.



overfitting을 피하고 너무 제한적이거나 너무 두리뭉실하지 않은 모델을 고르기 위한 Learning은 data scientist의 가장 핵김 기술 중 하나입니다. 





Learning without a teacher: unsupervised learning



Above we discussed supervised learning where the correct answers are available, and the taks of the machine learning algorithm is to find a model that predicts them based on the input data.



앞에서 우리는 정답이 가능한 supervised learnin에 대해 논의했으며 machine learning 알고리즘의 작업은 입력 데이터를 기반으로 예측하는 모델을 찾는 것이라고 배웠습니다



In unsupervised learning, the correct answers are not provided. This makes the situation quite different since we can't build the model by making it fit the correct answers on training data. It also makes the evaluation of performance more complicated since we can't check whether the learned model is doing well or not.



unsupervised learning에서 정답은 제공되지 않습니다. 이것은 우리가 모델을 training data에 대한 training data를 맞추어서 만들 수 없기 때문에 상황이 상당히 달랐습니다. 또한 학습 된 모델 learned model이 잘 작동하는지 여부를 확인할 수 없으므로 성능 평가가 더 복잡해집니다.



Typical unsupervised learning methods attempt to learn some kind of “structure” underlying the data. This can mean, for example, visualization where similar items are placed near each other and dissimilar items further away from each other. It can also mean clustering where we use the data to identify groups or “clusters” of items that are similar to each other but dissimilar from data in other clusters.


일반적인 unsupervised learning 방법은 데이터의 기초를 이루는 일종의 "구조 structure"를 배우려고 시도합니다. 예를 들어, 비슷한 항목이 서로 가까이 있고 다른 항목이 서로 멀리 떨어져있는 시각화를 의미 할 수 있습니다. 또한 클러스터링을 사용하여 데이터를 사용하여 서로 비슷한 그룹이나 다른 클러스터의 데이터와 다른 그룹의 "클러스터"를 식별 할 수 있습니다.




Note

Example

As a concrete example, grocery store chains collect data about their customers' shopping behavior (that's why you have all those loyalty cards). To better understand their customers, the store can either visualize the data using a graph where each customer is represented by a dot and customers who tend to buy the same products are placed nearer each other than customers who buy different products. Or, the store could apply clustering to obtain a set of customer groups such as ‘low-budget health food enthusiasts’, ‘high-end fish lovers’, ‘soda and pizza 6 days a week’, and so on. Note that the machine learning method would only group the customers into clusters, but it wouldn't automatically generate the cluster labels (‘fish lovers’ and so on). This task would be left for the user.


구체적인 예를 들어, 식료품 점 체인은 고객의 쇼핑 행동에 대한 데이터를 수집합니다 (loyalty cards가있는 이유입니다). 고객을 더 잘 이해하기 위해 각 고객이 점으로 표시되고 동일한 제품을 구매하려는 고객이 다른 제품을 구매하는 고객보다 서로 가깝게 배치되는 그래프를 사용하여 데이터를 시각화 할 수 있습니다. 또는 상점은 클러스터링을 적용하여 '저예산 건강 음식 애호가', '고급 생선 애호가', '일주일에 6 일 동안의 소다 및 피자'등과 같은 일련의 고객 그룹을 얻을 수 있습니다. 기계 학습 방법은 고객을 클러스터로만 그룹화하지만 클러스터 레이블 ( '생선 애호가'등)을 자동으로 생성하지는 않습니다. 이 작업은 사용자를 위해 남겨 둡니다.



Yet another example of unsupervised learning can be termed generative modeling. This has become a prominent approach since the last few years as a deep learning technique called /generative adversarial networks/ (GANs) has lead to great advances. Given some data, for example, photographs of people's faces, a generative model can generate more of the same: more real-looking but artificial images of people's faces.



unsupervised learning의 또 다른 예는 generative modeling 생성 적 모델링이라고 할 수 있습니다. 지난 몇 년 동안 / generative adversarial networks / (GANs)라고 불리는 심층적 인 학습 기법이 큰 진보를 이끌어내는 등 주목할만한 접근 방식이 되었습니다. 예를 들어 사람들의 얼굴 사진과 같은 일부 데이터를 감안할 때 generative modeling 생성 모델은 사람들의 얼굴을 보다 실제처럼 보이지만 인공적인 이미지로 생성합니다.



We will return to GANs and the implications of being able to produce high-quality artificial image content a bit later in the course, but next we will take a closer look at supervised learning and discuss some specific methods in more detail.



우리는 이 GANs를 다시 살펴 볼 것입니다. 이마도 이 코스에서 artificial image content를 만들 수 있겠구나 라고 생각하실 지 모르지만 그건 아니고 다음 단원에서는  supervised learning을 좀 더 자세히 살펴보고 특정 방법들에 대해 조금 더 자세히 얘기 나누겠습니다. 





Elements of AI - Naive Bayes classification

2018.06.12 13:59 | Posted by 솔웅


Elements of AI



III.Naive Bayes classification




One of the most useful applications of the Bayes rule is the so-called naive Bayes classifier.

Bayes rule의 가장 유용한 어플리케이션 중 하나는 소위 순진한 Bayes classifier입니다.



The Bayes classifier is a machine learning technique that can be used to classify objects such as text documents into two or more classes. The classifier is trained by analysing a set of training data, for which the correct classes are given.




Bayes classifier는 텍스트 문서와 같은 객체를 두 개 이상의 클래스로 분류하는 데 사용할 수있는 machine learning 기술입니다. 분류자 (classifier)는 올바른 클래스들에 대한 일련의 training 데이터를 분석함으로써 훈련됩니다.




The naive Bayes classifier can be used to determine the probabilities of the classes given a number of different observations. The assumption in the model is that the feature variables are conditionally independent given the class. (We will not discuss the meaning of conditional independence in this course. For our purposes, it is enough to be able to exploit conditional independence in building the classifier.)



naive Bayes classifier는 여러 가지 관찰 결과에 따라 클래스의 확률을 결정하는 데 사용할 수 있습니다. 이 모델의 가정은 feature variables 특성 (기능) 변수들은 주어진 클래스에 조건부로 독립적이라는 것입니다. (우리는 이 과정에서 조건부 독립의 의미에 대해 논의하지 않을 것입니다. 우리의 목적을 이루기 위해서는, classifier를 만드는데에 대한 조건부 독립성을 활용할 수 있는 것만으로도 충분합니다.)







Real world application: spam filters



We will use a spam email filter as a running example for illustrating the idea of the naive Bayes classifier. Thus, the class variable indicates whether a message is spam (or “junk email”) or whether it is a legitimate message (also called “ham”). The words in the message correspond to the feature variables, so that the number of feature variables in the model is determined by the length of the message.



naive Bayes classifier의 개념을 설명하기 위해 스팸 메일 필터를 실행 예제로 사용하겠습니다. 따라서 클래스 변수는 메시지가 스팸 (또는 "junk email")인지 또는 정상적인 메시지인지 ( "햄"이라고도 함) 여부를 나타냅니다. 메시지의 단어는 feature variables 특성 (기능) 변수에 해당하므로 모델의 feature variables 특성 변수의 수는 메시지의 길이에 따라 결정됩니다.



Note

Why we call it “naive”


Using spam filters as an example, the idea is to think of the words as being produced by choosing one word after the other so that the choice of the word depends only on whether the message is spam or ham. This is a crude simplification of the process because it means that there is no dependency between adjacent words, and the order of the words has no significance. This is in fact why the method is called naive.


스팸 필터를 예제로 이용한다는 것은 다른 단어 다음에 오는 단어를 선택함으로서 생성되어지는 단어들에 대해 생각한다는 겁니다. 그렇게 해서 해당 단어에 대한 선택이 오직 그 메세지가 스팸인지 혹은 햄인지 에 대해 의존한다는 것입니다.

 이것은 인접한 단어 사이에 의존성이 없으며 단어 순서에 아무런 의미가 없다는 것을 의미하기 때문에 이 과정을 매우 단순하게 처리합니다. 이것은 사실상 그 방법이 순진 (naive)이라고 불리는 이유입니다.

 

 - 요약 : 이 방법은 단순히 단어와 이어진 단어의 관계가 별 관련이 없거나 의미가 없을 경우 스팸으로 처리하는 방법입니다. 아주 단순하게 작동되기 때문에 이 방법론 이름에 naive (순진) 라는 단어가 사용되었습니다. - 




The above idea is usually depicted using the following illustration where the class of the message (spam or ham) is the only factor that has an effect on the words.



위의 아이디어는 일반적으로 메시지 클래스 (스팸 또는 햄)가 단어에 영향을 미치는 유일한 요소인 다음 그림을 사용하여 설명될 수 있습니다.








Despite it’s naivete, the naive Bayes method tends to work very well in practice. This is a good example of what the common saying in statistics, “all models are wrong, but some are useful” means. (The aphorism is generally attributed to statistician George E.P. Box.)



그것이 순진함에도 불구하고 naive Bayes method는 실제로 꽤 잘 작동합니다. 이것은 통계에서 흔히 말하는 "모든 모델은 틀렸지만 어떤 것들은 유용하다"라는 것을 보여주는 좋은 예입니다. (격언은 일반적으로 통계 학자 George E.P. Box가 말했다고 알려져 있습니다.)





Estimating parameters


To get started, we need to specify the prior odds for spam (against ham). For simplicity assume this to be 1:1 which means that on the average half of the incoming messages are spam. (In reality, the amount of spam is probably much higher.)



시작하려면 스팸 (햄에 대한)에 대한 prior odds을 지정해야합니다. 간단히  1 : 1이라고 가정합시다. 이는 수신 메시지의 평균 절반이 스팸임을 의미합니다. 실제로 스팸의 양은 훨씬 더 많습니다.



To get our likelihood ratios, we need two different probabilities for any word occurring: one in spam messages and another one in ham messages.



likelihood ratios 를 얻으려면 단어들에 대한 두가지 다른 probabilities가 필요합니다. 하나는 스팸 메세지이고 다른 하나는 햄 메세지 입니다.



The word distributions for the two classes are best estimated from actual training data that contains some spam messages as well as legitimate messages. The simplest way is to count how many times each word, abacus, acacia, ..., zurg, appears in the data and divide the number by the total word count.



두 클래스의 단어 분포는 약간의 스팸 메시지와 정상적인 메시지가 포함 된 실제 training 데이터에서 가장 잘 예측할 수 있습니다. 가장 간단한 방법은 데이터에 얼마나 많은 abacus, acacia, ..., zurg, 단어들이 나타났느냐와 그 숫자를 총 단어 숫자로 나누는 겁니다. 



To illustrate the idea, let’s assume that we have at our disposal some spam and some ham. You can easily obtain such data by saving a batch of your emails in two files.



아이디어를 설명하기 위해 disposal에 약간의 스팸과 약간의 햄이 있다고 가정해 봅시다. 두개의 파일을 여러분의 이메일들의 batch를 저장함으로서 그러한 데이터를 쉽게 얻을 수 있습니다. 



Assume that we have calculated the number of occurrences of the following words (along with all other words) in the two classes of messages:



두 가지 메시지 클래스에서 다음 단어 (다른 단어와 함께)의 발생 횟수를 계산했다고 가정 해 보겠습니다.




We can now estimate that the probability that a word in a spam message is million, for example, is about 156 out of 95791, which is roughly the same as 1 in 614. Likewise, we get the estimate that 98 out of 306438 words, which is about the same as 1 in 3127, in a ham message are million. Both of these probability estimates are small, less than 1 in 500, but more importantly, the former is higher than the latter: 1 in 614 is higher than 1 in 3127. This means that the likelihood ratio, which is the first ratio divided by the second ratio, is more than one. To be more precise, the ratio is (1/614) / (1/3127) = 3127/614 = 5.1 (rounded to one decimal digit).



이제 우리는 스팸 메세지에 있는 단어가 million인 경우의 probability를 알아 낼 수 있습니다. 예를 들어 95791 개중 156개 즉 대략 614개 중 1개 라는 식으로 말이죠. 그리고 306438 단어 중 98개의 단어도 계산해 날 수 있습니다. 대략 3127 개중 1개 꼴입니다. 이 두개의 확률 계산은 500개중 1개 보다 작은 겁니다. 그리고 더 중요한 것은 첫번 째 것이 두번 째 것보다 높다는 겁니다. (614개 중 1개가 3127개중 1개 보다 더 높죠). 이 의미는 첫번 째 ratio 나누기 두번 째 ratio 인 likelihood ratio가 1보다 크다는 겁니다. 좀 더 자세히 살펴 보면 그 (1/614) / (1/3127) = 3127/614 = 5.1 (rounded to one decimal digit) 입니다.



Recall that if you have any trouble at all with following the math in this section, you should refresh the arithmetics with fractions using the pointers we gave earlier (see the part about Odds in section Odds and Probability).



이 단원의 수학 문제를 푸는데 어려움이 있다면 이전에 알려드렸던 것들을 사용해서 포인터를 사용하여 arithmetics with fractions를 refresh 해야 합니다. (see the part about Odds in section Odds and Probability).





Note

Zero means trouble


One problem with estimating the probabilities directly from the counts is that the zero counts lead to zero estimates. This can be quite harmful for the performance of the classifier - it easily leads to situations where the posterior odds is 0/0, which is nonsense. The simplest solution is to use a small lower bound for all probability estimates. The value 1/100000, for instance, does the job.


카운트에서 직접 확률을 추정 할 때의 한 가지 문제점은 제로 카운트가 0으로 계산된다는 것입니다. 이것은 classifier의 performance에 부정적인 영향을 미칠 수 있습니다. - 그것은 posterior odds이 0/0 인 상황으로 쉽게 이어집니다. 이것은 말도 안되는 상황이죠. 가장 간단한 해결책은 모든 probability 추정치에 대해 작은 하한을 사용하는 것입니다. 예를 들어 값 1/100000으로 작업을 수행하는 것이죠.



Using the above logic, we can determine the likelihood ratio for all possible words without having to use zero, giving us the following likelihood ratios:



위의 논리를 사용하여 0을 사용하지 않고 모든 가능한 단어에 대한 likelihood ratio 우도 비율을 결정할 수 있으며 다음 likelihood ratio 우도 비율을 얻을 수 있습니다.





We are now ready to apply the method to classify new messages.


이제 새 메시지를 분류하는 방법을 적용 할 준비가되었습니다.



Example: is it spam or ham?


Once we have the prior odds and the likelihood ratios calculated, we are ready to apply the Bayes rule, which we already practiced in the medical diagnosis case as our example. The reasoning goes just like it did before: we update the odds of spam by multiplying it by the likelihood ratio. To remind ourselves of the procedure, let's try a message with a single message to begin with. For the prior odds, as agreed above, you should use odds 1:1.



우리가 prior odds과 likelihood ratios 우도 비율을 계산하고 나면 이제 Bayes rule을 적용할 준비가 된 것입니다. medical diagnosis 예제에서 한번 다뤘었죠. reasoning은 이전에 했던 것과 같습니다. likelihood ratio에 스팸의 odds를 곱함으로서 odds를 업데이트 합니다. 다시 한번 그 과정을 상기해 보죠. 하나의 메세지로 시작하는 메세지를 예로 들어 보겠습니다. prior odds는 위에서 얘기한 대로 odds 1:1을 사용하시면 됩니다.






Exercise 12: One word spam filter

Let's start with a message that only has one word in it: “million”.


Your task: Calculate the posterior odds for spam given this word using the table above. Keep in mind that the odds is not the same as the probability, which we would usually express as a percentage.


Give your answer in the form of a single decimal number x.x using the dot '.' as the decimal separator.




한 단어 만 들어있는 메시지, “million”부터 시작해 보겠습니다.


과제 : 위의 표를 사용하여 이 단어가 주어진 스팸에 대한 posterior odds을 계산하십시오. odds는 우리가 일반적으로 백분율로 표현하는 probability과 같지 않습니다.


소수점 구분 기호로 점 '.'을 사용하여 x.x 형식으로 소수점 한자리로 답을 제공하세요. 



To handle the rest of the words in a message, we can use exactly the same procedure. The posterior odds after one word, which you calculated in the previous exercise, will become the prior odds for the next word, and so on.



메시지의 나머지 단어를 처리하기 위해 똑같은 절차를 사용할 수 있습니다. 이전 실습에서 계산 한 한 단어 뒤의 posterior odds은 다음 단어에 대한 prior odds이됩니다.




Exercise 13: Full spam filter


Now use the naive Bayes method to calculate the posterior odds for spam given the message “million dollars adclick conferences”.


You should again start with the prior odds 1:1, and then multiply the odds repeatedly by the likelihood ratios for each of the four words. Notice that the likelihood ratios are tabulated above for your reference (these are the numbers 5.1, 0.8, and so on).


Your task: Express the result as posterior odds without any rounding of the result. You may take a look at the solution of the previous exercise for help.



이제 naive Bayes 방법을 사용하여 “million dollars adclick conferences”라는 메시지가 주어졌을 때의 스팸에 대한 posterior odds을 계산하세요.


이전 확률 1 : 1로 다시 시작한 다음 네 개의 단어 각각에 대한 likelihood ratios 우도 비율로 반복하여 odds을 곱하십시오. likelihood ratios 우도 비율은 참조 용으로 위에 요약되어 있습니다 (숫자 5.1, 0.8 등).


과제 : 결과를 반올림하지 않고 posterior odds로 결과를 표현하십시오. 이전 연습 문제의 해결 방법을 살펴보면 도움이 될 겁니다.




Hooray! You have now mastered a powerful technique used every day in a wide range of real-world AI applications, the naive Bayes classifier. Even if you had to skip some of the technicalities, you should try to make sure you understood the basic principles of applying probabilities to update beliefs. As we discussed in the beginning of this Chapter, the main advantage of probabilistic reasoning is the ability to handle uncertain and conflicting evidence. Using examples in medical diagnosis and spam filtering, we demonstrated how this work is practice.



야호~~~! 이제 실제 AI 어플리케이션, 즉 naive Bayes classifier에서 항상 사용되는 강력한 기술을 익혔습니다. 만약 여러분이 특정 테크니컬한 부분을 건너 뛰었더라도 beliefs를 업데이트 하기 위해 probabilities를 적용하는 가장 기초적이고 핵심적인 부분은 꼭 이해하셔야 합니다. 이 장의 시작 부분에서 논의했듯이 probabilistic reasoning 확률론적 추론의 주된 이점은 불확실하고 모순되는 증거를 처리 할 수있는 능력입니다. 의료 진단 및 스팸 필터링의 예제를 사용하여이 작업이 실제로 어떻게 수행되는지를 보여주었습니다.






After completing Chapter 3 you should be able to:




  • Express probabilities in terms of natural frequencies
  • Apply the Bayes rule to infer risks in simple scenarios
  • Explain the base-rate fallacy and avoid it by applying Bayesian reasoning




Elements of AI - The Bayes Rule

2018.06.11 15:00 | Posted by 솔웅


Elements of AI



II.The Bayes Rule




We will not go too far into the details of probability calculus and all the ways in which it can be used in various AI applications. But we will discuss one very important formula.


확률 계산과 관련해서 너무 깊게 들어가지는 않을 겁니다. 그리고 많은 인공지능 제품 들에 사용될 수 있는 다양한 방법들에 대해서도 너무 깊게 들어가지는 않을 겁니다. 단지 한가지 굉장히 중요한 공식에 대해 논의 해 보겠습니다.




We will do this because this particular formula is both simple and elegant as well as incredibly powerful. It can be used to weigh conflicting pieces of evidence in medicine, in a court of law, and in many (if not all) scientific disciplines. The formula is called the Bayes rule (or the Bayes formula).



이 특정 공식을 다루는 이유는 인공지능과 관련 이 공식은 아주 간단하면서도 우아하고 수퍼 파워풀 한 공식이기 때문입니다. 이 공식은 의학분야, 법정 그리고 많은 과학 연구 분야에서 서로 상충되는 증거들을 비교 평가 하는데 사용될 수 있습니다. 이 공식은 Bayes rule (or the Bayes formula)이라고 부릅니다.



We will start by demonstrating the power of the Bayes rule by means of a simple medical diagnosis problem where it highlights how poorly our intuition is suited for combining conflicting evidence. We will then show how the Bayes rule can be used to build AI methods that can cope with conflicting and noisy observations.



우리는 단순한 의학적 진단 문제를 통해 Bayes rule이 얼마나 강력한 지를 보여 드리겠습니다. 이것을 통해 우리의 직감이 상충되는 증거의 결합에 얼마나 적합하지 않음을 알 수 있습니다. 그리고 나서 이 Bayes rule이 상충되는 상황과 noisy observations 들에 대처할 수 있는 인공지능 방법론을 만드는데 어떻게 사용되어질 수 있는지 보여드리겠습니다. 




Key terminology

Prior and posterior odds


The Bayes rule can be expressed in many forms. The simplest one is in terms of odds. The idea is to take the odds for something happening (against it not happening), which we´ll write as prior odds. The word prior refers to our assessment of the odds before obtaining some new information that may be relevant. The purpose of the formula is to update the prior odds when new information becomes available, to obtain the posterior odds, or the odds after obtaining the information. (The dictionary meaning of posterior is “something that comes after, later.“)


Bayes rule 규칙은 여러 형태로 표현 될 수 있습니다. 가장 간단한 방법은 odds 확률입니다. 그 아이디어는 바로 일어나는 것입니다. (반대는 일어나지 않는 것이겠죠),  우리는 이것을 prior odds 라고 할 겁니다. prior라는 단어는 관련됐을 수 있는 어떤 새로운 정보를 취득하기 이전의 odds에 대한 평가를 말하는 겁니다. 이 공식의 목적은 새로운 정보가 가능한 상황일 때 이 prior odds를 업데이트해서 posterior odds나 정보를 취득한 이후의 odds를 얻기 위함입니다.   새로운 정보를 얻기 전에 확률에 대한 평가를 나타냅니다. 공식의 목적은 새로운 정보가 이용 가능해질 때 이전 확률을 업데이트하고, 정보를 얻은 후 posterior 확률 또는 확률을 얻는 것입니다. (posterior의 사전적 의미는 "나중에 오는 어떤 것"입니다.)





How odds change


In order to weigh the new information, and decide how the odds change when it becomes available, we need to consider how likely we would be to encounter this information in alternative situations. Let’s take as an example, the odds that it will rain later today. Imagine getting up in the morning in Finland. The chances of rain are 206 in 365. (Including rain, snow, and hail. Brrr!) The number of days without rain is therefore 159. This converts to prior odds of 206:159 for rain, so the cards are stacked against you already before you open your eyes.




새로운 정보를 평가하고 그것이 가능한 상황이 될 때 odds가 어떻게 변하는지 결정하려면 다른 상황에서 이 정보를 접하게 되면 어떻게 될지에 대해 고려해야 합니다. 오늘 늦게 비가올 것이라는 odds를 가지고 예를 들어 보죠. 핀란드에서 아침에 잠에서 깼다고 생각해 보세요. 핀란드에서 비가 오는 날은 365일 중 206일입니다. (비, 눈, 우박 뭐 그런것들 다 합해서요) 비가 오지 않는 날은 159일 입니다. 비가 오는 날과 오지 않을 날을 odds로 표현하면  206:159 가 됩니다. 당신이 눈을 뜨기 전에 이미 이 카드는 존재해 있는 겁니다.



However, after opening your eyes and taking a look outside, you notice it’s cloudy. Suppose the chances of having a cloudy morning on a rainy day are 9 out of 10 — that means that only one out of 10 rainy days start out with blue skies. But sometimes there are also clouds without rain: the chances of having clouds on a rainless day are 1 in 10. Now how much higher are the chances of clouds on a rainy day compared to a rainless day? Think about this carefully as it will be important to be able to comprehend the question and obtain the answer in what follows.



아침에 눈을 떴을 때 창밖을 바라보니까 구름이 끼어 있네요. 비가 오는 날 중 아침에 구름이 끼어 있는 날은 10일 중 9일 입니다. 즉 10일 중 하루는 아침에 구름이 안 끼었는데도 비가 온다는 말입니다. 어떤 날은 아침에 구름이 끼었는데 비는 안오고 계속 구름만 끼어 있는 날도 있습니다. 아침에 구름이 끼어 있는데 비가 안오는 날은 10일중 하루이지요. 비가 오는 날 구름이 끼어있을 가능성은 비가 오지 않는 날 구름이 끼어있을 가능성과 비교해서 얼마나 높을까요? 잘 한번 생각해 보세요. 질문을 잘 이해하시는게 중요합니다. 그래야 아래 나오는 문제에 대해 잘 대답할 수 있습니다.



The answer is that the chances of clouds are nine times higher on a rainy day than on a rainless day: on a rainy day the chances are 9 out of 10, whereas on a rainless day the chances of clouds are 1 out of 10, and that makes nine times higher.



정답은 비가 오는 날 아침에 구름이 끼어있을 가능성은 비가 오지 않는 날 아침에 구름이 끼어있을 가능성의 9배 입니다. 비가 오는 날의 가능성은 10일 중 9일 입니다. 비가 오지 않을날 아침에 구름이 낄 가능성은 10일 중 하루이구요. 그렇기 때문에 9배 인 것입니다.



Key terminology

Likelihood ratio


The above ratio (nine times higher chance of clouds on a rainy day than on a rainless day) is called the likelihood ratio. More generally, the likelihood ratio is the probability of the observation in case the event of interest (in the above, rain), divided by the probability of the observation in case of no event (in the above, no rain). Please read the previous sentence a few times. It may look a little intimidating, but it´s not impossible to digest if you just focus carefully. We will walk you through the steps in detail, just don´t lose your nerve. We´re almost there.


위의 비율을 우도비율 likelihood ratio라고 부릅니다. (비가 오는 날 아침에 구름이 끼어 있을 가능성이 비가 오지 않는 날 아침에 구름이 낄 가능성의 9배이다 라는 비율) 보다 일반적으로 이 likelihood ratio는 interest 이벤트 (위의 경우는 비) 의 확률을 no event (비가 안오는 경우)의 확률로 나눈 값을 말합니다. 이 문장들을 여러번 잘 읽어 보세요. 집중해서 잘 읽어보면 충분히 이해하실 수 있을 겁니다. 이에 대해 스텝별로 자세하게 안내하겠습니다. 긴장을 늦추지 마세요. 이제 거의 다 왔습니다.




So we concluded that on a cloudy morning, we have: likelihood ratio = (9/10) / (1/10) = 9



이제 구름낀 아침에 대해 결론을 내릴 수 있게 됐습니다. 우리는 우도비율 likelihood ratio = (9/10) / (1/10) = 9 라고 답을 낼 수 있습니다.



The mighty Bayes rule for converting prior odds into posterior odds is — ta-daa! — as follows: posterior odds = likelihood ratio × prior odds



prior odds를 posterior odds로 변환할 전능한 Bayes rule 은 바로 이것입니다. (짜잔~~~~~)


 posterior odds = likelihood ratio × prior odds



Now you are probably thinking: Hold on, that’s the formula? It’s a frigging multiplication! That is the formula — we said it’s simple, didn’t we? You wouldn’t imagine that a simple multiplication can be used for all kinds of incredibly useful applications, but it can. We’ll study a couple examples which will demonstrate this.



당신은 '이게 그 공식 맞아? 그냥 간단한 곱셈이잖아!' 라고 아마 생각 하실 수도 있을 겁니다. 위 글에서 아주 간단하다고 말하자 않았나요? 아마 당신은 이렇게 간단한 곱셈으로 모든 종류의 유용한 응용품들에 적용할 수 있을 거리고는 상상하지 못했을 겁니다. 그런데 그게 가능합니다. 그것을 입증할 몇가지 예를 들어 드리겠습니다.




Note

Many forms of Bayes

In case you have any trouble with the following exercises, you may need to read the above material a few times and give it some time, and if that doesn´t do it, you can look for more material online. Just a word of advice: there are many different forms in which the Bayes rule can be written, and the odds form that we use isn´t the most common one. Here are a couple links that you may find useful.


이어질 연습 문제를 푸는데 어려움이 있다면 시간을 조금 투자해서 위에 설명된 내용을 읽어 보실 필요가 있습니다. 그래도 잘 모르겠으면 온라인에 있는 관련된 정보들을 검색해 보세요. 그래도 어려움이있을 경우 온라인 자료를 더 찾아야 할 수도 있습니다. 조언을 하자면 Bayes rule에 대해 많은 설명들이 다른 방식으로 돼 있을 겁니다. 우리가 사용하는 odds 관련된 예는 이  Bayes rule을 설명하는 가장 일반적인 예는 아닙니다. 아마 아래 두개의 링크를 따라가 보시면 도움이 될 만한 내용을 보실 수 있을 겁니다. 








Exercise 10: Bayes rule (part 1 of 2)


Apply the Bayes rule to calculate the posterior odds for rain having observed clouds in the morning in Helsinki.



Bayes rule을 적용해 헬싱키에서 아침에 구름이 끼었을 때 비가 내릴 posterior odds를 계산해 보세요.



As we calculated above, the prior odds for rain having observed clouds is 206:159 and the likelihood ratio is 9



위에 서 계산한 대로 아침에 구름이 끼었을 때 비가 오는 것에 대한 prior odds는 206:159 였고 likelihood ratio는 9였습니다.



Give your result in the form of odds, xx:yy, where xx and yy are numbers. Remember that when multiplying odds, you should only multiply the numerator (the xx part). Give the answer without simplifying the expression even if both sides have a common denominator.



여러분의 답을 odds 형식 (xx:yy)으로 답하세요. xx 와 yy는 숫자입니다. odds를 곱할 때 주의하세요. 분자 (xx part)를 곱해야 합니다. 양쪽에 공통 분모가 있더라도 식을 단순화하지 말고 (약분하지 말고) 답을 제공하십시오.




The Bayes rule in practice: breast cancer screening



Our first realistic application is a classical example of using the Bayes rule, namely medical diagnosis. This example also illustrates a common bias in dealing with uncertain information called the base-rate fallacy.



우리의 첫 번째 현실적인 응용 프로그램은 Bayes rule을 사용한 아주 고전적인 예 입니다. 이름하여 medical diagnosis라고 합니다. 이 예제는 또한 base-rate fallacy라고 불리는 불확실한 정보를 다루는데 있어서의 일반적인 편견을 보여줍니다.







Consider mammographic screening for breast cancer. Using made up percentages for the sake of simplifying the numbers, let’s assume that five in 100 women have breast cancer. Suppose that if a person has breast cancer, then the mammograph test will find it 80 times out of 100. When the test comes out suggesting that breast cancer is present, we say that the result is positive, although of course there is nothing positive about this for the person being tested. (A technical way of saying this is that the sensitivity of the test is 80%.)



유방암에 대한 유방 X 선 mammographic 검사를 고려하십시오. 숫자를 단순화하기 위해 백분율을 사용하여 100 명의 여성 중 5 명이 유방암을 앓고 있다고 가정 해 봅시다. 어떤 사람이 유방암이 있다고 가정합시다. 그리고 유방 조영술 mammographic 검사를 하면 100번 중 80번 이것을 찾아 낸다고 가정해 봅시다. (기술적으로 이와 같은 상황은 해당 검사의 sensitivity는 80%라고 말합니다.). 검사 해서 유방암이 있다고 결론이 나오는 것을 양성 positive이라고 합니다. - 물론 검사 받는 사람에게는 긍정적 positive인 상황은 아니지만 말이죠- 



The test may also fail in the other direction, namely to indicate breast cancer when none exists. This is called a false positive finding. Suppose that if the person being tested actually doesn’t have breast cancer, the chances that the test nevertheless comes out positive are 10 in 100.



유방암에 걸렸을 경우 80% 는 유방암을 발견한다는 것은 20%는 발견 못 한다는 것이죠. 그리고 또 다른 각도에서 검사의 실패 가능성을 염두에 두어야 합니다. 즉 유방암에 걸리지 않았는데 유방암에 걸렸다고 검사결과가 잘 못 나올 경우도 있는거죠.  이를 false positive finding이라고합니다. 어느 검사를 받는 사람이 실제로는 유방암이 없다고 합시다, 그럼에도 불구하고 검사가 양성으로 나올 확률은 100 명당 10 명입니다.



Based on the above probabilities, you are be able to calculate the likelihood ratio. You'll find use for it in the next exercise. If you forgot how the likelihood ratio is calculated, you may wish to check the terminology box earlier in this section and revisit the rain example.



위의 확률에 근거해 likelihood ratio을 계산할 수 있습니다. 다음 연습 문제에서 한번 사용 해 보세요. likelihood ratio 계산 방법을 잊어 버린 경우 이 섹션의 앞부분에있는 용어 상자를 확인하고 비가 오는 예제를 다시 참조 하세요.





Exercise 11: Bayes rule (part 2 of 2)

Consider the above breast cancer scenario. An average woman takes the mammograph test and gets a positive test result suggesting breast cancer. What do you think are the odds that she has breast cancer?



위의 유방암 시나리오를 참조하세요. 한 평범하 여성이 mammograph 검사를 받고 유방암을 암시하는 양성인 검사 결과를 받았습니다.  이 여성이 유방암에 걸렸을 확률 odds 는 얼마입니까?



Use your intuition without applying the Bayes rule, and write down on a piece of paper (not in the answer box below) what you think the chances of having breast cancer are after a positive test result. After this, calculate the posterior odds for her having breast cancer using the Bayes rule.



Bayes rule을 적용하지 말고 직관을 사용해서 풀어보세요, 그리고 양성 검사 결과를 받았을 경우 유방암에 걸렸을 확률을 종이에 적어 보세요. (아래 빈칸에 넣지 마시구요). 그리고 난 다음에 Bayes rule을 사용해서 그녀가 암에 걸렸을 확률에 대한 posterior odds를 계산해 보세요.



(Hint:) Start by calculating the prior odds and then multiply it by the likelihood ratio.


Hint : 우선 prior odd를 먼저 계산 한 다음 likelihood ratio을 이용해 그것을 곱하세요.



Enter the posterior odds as your solution below. Give the answer in the form xx:yy where xx and yy are numbers, without simplifying the expression even if both sides have a common denominator.



당신이 계산한 posterior odds를 아래에 입력하세요. 답은 xx:yy 형식으로 입력하세요. xx와 yy는 숫자입니다. 양쪽에 공통 분모 common denominator가 있어도 이를 간단하게 고치지 말고 (약분하지 말고) 그냥 입력하세요. 





Elements of AI - Odds and probability

2018.06.09 13:53 | Posted by 솔웅



Elements of AI




I.Odds and probability



In the previous section, we discussed search and it’s application where there is perfect information – such as in games like chess. However, in the real world things are rarely so clear cut.

전 단원에서 우리는 search와 체스 같은 perfect information 게임 같은곳에 이 search를 적용하는 것에 대해 얘기 나눴습니다. 그런데 실제 세상에서는 이렇게 딱 뿌러지고 명확하게 설명할 수 없는 것들이 많이 있습니다.



Instead of perfect information, there is a host of unknown possibilities, ranging from missing information to deliberate deception.


perfect information 대신에 unknown possibilities 라는 것이 있습니다. missing information 에서 deliberate deception 까지 이러한 많은 unknown possibilities 경우는 많이 있습니다.




Take a self-driving car for example — you can set the goal to get from A to B in an efficient and safe manner that follows all laws. But what happens if the traffic gets worse than expected, maybe because of an accident ahead? Sudden bad weather? Random events like a ball bouncing in the street, or a piece of trash flying straight into the car’s camera?



자율 주행차를 예를 들어 보죠. A에서 B까지 모든 교통 법규를 다 지키면서 안전하고 효율적으로 가도록 세팅해 놓을 수 있겠죠. 그런데 예상했던 것 보다 교통 정체가 심할 경우에는 어떻게 해야 할까요? 아마 앞쪽에 사고가 나서 그런 일이 벌어질 수도 있겠죠. 갑자기 날씨가 안좋아 진다거나 길로 갑자기 공이 굴러온다거나 비닐봉지가 갑자기 자동차의 카메라를 가려버린다던가 하는 상황이 발생하면 어떻게 해야 할까요?




A self-driving car needs to use a variety of sensors, including sonar-like ones and cameras, to detect where it is and what is around it. These sensors are never perfect as the data from the sensors always includes some errors and inaccuracies called “noise”. It is very common then that one sensor indicates that the road ahead turns left, but another sensor indicates the opposite direction. This needs to be resolved without always stopping the car in case of even a slightest amount of noise.



자율주행차는 다양한 센서들을 사용해야 합니다. 음파 감지기나 카메라 같은 센서들이 있어서 지금 어디에 있는지 그리고 주변에는 어떤 것들이 있는지를 감지해야 합니다. 이런 센서들은 그 센서로부터 받아들인 데이터를 참조하도록 하는데 여기에는 일부 에러 혹은 “noise”라고 불리는 불분명한 정보 들도 포함되어 있습니다. 즉 완벽한 정보들은 아니라는 거죠. 하나의 센서가 앞쪽에 좌회전 구간이 있다는 것을 알려주는데 다른 센서는 그 반대쪽 즉 우회전 구간이 있다고 알려주기도 합니다. 이런 경우는 일반적으로 일어날 수 있는 현상입니다. 이런 조그만 노이즈가 있다고 일일이 차를 세워서 살펴보고 하지 않고도 해결할 수 있는 방법이 필요합니다.






Probability


One of the reasons why modern AI methods actually work in real-world problems - as opposed to most of the earlier “good old-fashioned" methods in the 1960-1980s - is their ability to deal with uncertainty.



현대 인공지능이 현실세계에서 실제로 이용될 수 있는 이유 중 하나는 이런 불확실성을 처리하는 능력이 있기 때문입니다. 1960~1980년대의 초기 인공지능을 다루던 옛날 방식에는 그러한 것들이 없었죠.



Note

The history of dealing with uncertainty


The history of AI has seen various competing paradigms for handling uncertain and imprecise information. For example, you may have heard of fuzzy logic. Fuzzy logic was for a while a contender for the best approach to handle uncertain and imprecise information and used in many customer-applications such as washing machines where the machine could detect the dirtiness (a matter of degrees, not only dirty or clean) and adjust the program accordingly.


인공 지능의 역사는 불확실하고 부정확 한 정보를 다룰 수 있는 다양한 패러다임들 간의 경쟁이었습니다. 예를 들어 여러분들은 퍼지 이론에 대해 들어봤을 수 있습니다. 퍼지 논리는 잠시 동안 불확실하고 부정확 한 정보를 처리하기위한 최선의 접근 방식이어였습니다. 이 기술은 실제 많은 가전제품에 사용됐었는데 더러움을 감지 (더럽고 깨끗함을 구분하는 정도가 아니라 얼마나 더러운가의 정도까지 감지)할 수 있는 기계로 세탁기 등을 만들었었습니다. 



However, probability has turned out to be the best approach for reasoning under uncertainty, and almost all current AI applications are based, in at least some degree, on probabilities.


probability 확률은 불확실성 하에서 추론을 위한 최선의 접근법이었으며  현재 거의 모든 AI 응용 프로그램이 적어도 어느 정도 확률에 기반합니다.





Why probability matters



We are perhaps most familiar with applications of probability in games: what are the chances of getting three of a kind in poker (about one in 46), what are the chances of winning in the lottery (very small), and so on. However, far more importantly, probability can also be used to quantify and compare risks in everyday life: what are the chances of crashing your car if you exceed the speed limit, what are the chances that the interest rates on your mortgage will go up by five percentage points within the next five years, or what are the chances that AI will automate particular tasks such as detecting fractured bones in X-ray images or waiting tables in a restaurant.



우리는 아마도 게임 할 때 이 확률을 활용하는 가장에 가장 익숙합니다. 포커에서 3 가지 종류의 무늬를 얻을 수 있는 확률 (약 1/46), 복권에 당첨 될 기회 (매우 작음) 등등 입니다. 또한 확률은 일상 생활의 위험을 계량하고 비교하는 것 같은 더 중요한 곳에서도 사용될 수 있습니다. 일상생활에서 양을 정하고 리스크를 비교하는 데서도 사용할 수 있겠죠. 과속을 하면 차가 충돌할 확률, 향후 5년안에 모기지가 5퍼센트 올라갈 확률, 혹은 인공지능이 엑스레이 사진을 보고 뼈가 부러진 것이라는 것을 알아차릴 수 있는 기회 상황, 식당에서 빈 테이블을 감지하는 기능을 가질 기회 상황 등등 




Note

The key lesson about probability


The most important lesson about probability that we’d like you to take away is not probability calculus. Instead, it is the ability to think of uncertainty as a thing that can be quantified at least in principle. This means that we can talk about uncertainty as if it were a number: numbers can be compared (“is this thing more probable than that thing”), and they can often be measured. The numbers in probability will sometimes be somewhat subjective, but we can nevertheless critically evaluate them, and our numbers can sometimes be found to be right or wrong. In other words, the lesson is that uncertainty is not something that is beyond the scope of rational thinking and discussion.


확률과 관련해 여러분들이 떨쳐 버렸으면 하는 부분은 확률은 어떤 계산법이라는 고정 관념입니다. 확률은 계산법이 아닙니다. 확률은 불확실성의 생각에 대한 능력입니다. 불확실성에 대해서 계량화 하는 겁니다. 이 의미는 우리는 불확실성에 대해 숫자화 해서 말 할 수 있다는 겁니다. 숫자는 비교될 수 있습니다. 그리고 숫자는 측량도 가능합니다. 확률에서의 숫자는 때때로 주관적일 수 있지만, 그럼에도 불구하고 우리는 비판적인 평가를 할 수 있습니다. 그리고 때때로 우리의 숫자에 대해 옳거나 그른 것으로 판명 할 수 있습니다. 즉, 불확실성은 합리적인 사고와 토론의 범위를 넘어서는 것이 아니라는 겁니다.




The fact that uncertainty can be quantified is of paramount importance, for example, in decision concerning vaccination or other public policies. Before entering the market, any vaccine is clinically tested, so that its benefits and risks have been quantified. The risks are never known to the minutest detail, but their magnitude is usually known to sufficient degree that it can be argued whether the benefits outweigh the risks.



불확실성을 정량화 할 수 있다는 사실은 예를 들어 백신 접종이나 기타 공공 정책과 관련한 결정에서 매우 중요합니다. 시장에 진입하기 전에 모든 백신은 임상 시험을 거쳐 그 이점과 위험이 정량화되었습니다. 위험 요소는 대개 아주 세세하게 알지는 못하지만 리스크 (위험요소)가 잇점과 비교해서 어느쪽을 선택할 것인지를 논의/결정할 수 있을 정도의 정보를 알 수는 있습니다. 




Note

Why quantifying uncertainty matters

If we think of uncertainty as something that can't be quantified or measured, the uncertainty aspect may become an obstacle for rational discussion. We may for example argue that since we don’t know exactly whether a vaccine may cause a harmful side-effect, it is too dangerous to use. However, this may lead us to ignore a life-threatening disease that the vaccine will eradicate. In most cases, the benefits and risks are known to sufficient precision to clearly see that one is more significant than the other.


불확실성을 계량화하거나 측정 할 수없는 것으로 생각하면 불확실성이 합리적 토론의 장애물이 될 수 있습니다. 예를 들어 우리는 백신이 유해한 부작용을 일으킬 수 있는지 여부를 정확하게 알지 못하기 때문에 사용하기에 너무 위험하다고 주장 할 수 있습니다. 그러나 이로 인해 우리는 백신이 근절 할 생명을 위협하는 질병을 무시할 수 있습니다. 대부분의 경우 이점과 위험은 하나가 다른 것보다 중요하다는 것을 분명히 알 수있을만큼 충분한 정확도로 알려져 있습니다.




The above lesson is useful in many everyday scenarios and professionally: for example, medical doctors, judges in a court of law, investors have to process uncertain information and make rational decisions based on them. Since this is an AI course, we will discuss how probability can be used to automate uncertain reasoning. The examples we will use include medical diagnosis (although it is usually not a task that we’d wish to automate), and identifying fraudulent email messages (“spam”).



위의 수업은 많은 일상적인 시나리오에서 전문적으로 유용합니다. 예를 들어 의료계의 의사, 법원의 판사, 투자자들은 불확실한 정보를 처리하고 이를 기반으로 합리적 결정을 내려야합니다. 지금은 AI 수업 과정 이므로 불확실성을 추론해 내는 과정을 자동화 하는 것에 대해 얘기를 할 것입니다.  우리가 사용하게 될 예에는 의료 진단 (자동 진단을하는 것이 보통은 아니지만)과 사기성 전자 메일 메시지 ( "스팸")를 식별하는 것이 포함됩니다.





Exercise 8: Probabilistic forecasts


Consider the following four probabilistic forecasts and outcomes. What can be conclude based on the outcome about the correctness of the forecasts? Can we conclude that the probability given by the forecast was indeed just right (choose "right"), that the forecast was wrong (choose "wrong"), or can conclude neither way (choose "cannot be concluded").


다음 네 가지 확률적 (기상) 예측과 결과를 생각해 보세요. 기상 예측의 정확성에 대한 도출물을 바탕으로 어떤 결론을 내릴 수 있습니까? 기상 예측에 의해 주어진 확률은 정말로 옳거나 ( "오른쪽"을 선택), 예측이 잘못되었거나 ( "틀린"을 선택), 어느쪽으로도 결론을 지을 수 없다고 결론을 내릴 수 있습니까 ( "결론을 내릴 수 없음"을 선택하십시오).



The weather forecast says it's going to rain with 90% probability tomorrow but the day turns out to be all sun and no rain.


We can't conclude that the weather forecast was wrong based on only the single event. The forecast said it's going to rain with 90% probability, which means it would not rain with 10% probability or in one out of 10 days. It is perfectly plausible that the day in question was the 1 in 10 event. Concluding that the probability 90% was correct would also be wrong because by the same argument, we could then conclude that 80% chance of rain was also correct, and both cannot be correct at the same time.



The weather forecast says it's going to rain with 0% probability tomorrow but the day turns out to be rainy.


The weather forecast was wrong because a 0% probability means that it should definitely not rain. But it did.



Suppose you monitor a weather forecaster for a long time. You only consider the days for which the forecast gives 70% chance of rain. You find that in the long run, on the average it rains on three out of every five days.


Strictly speaking, the weather forecasts are wrong if they predict 70% chance of rain and it rains only 60% (three out of five) of the time in the long run. In practice, weather forecasters actually tend to provide this kind of 'wrong' predictions just to be safe: people are often quite disappointed when the weather turns out to be worse than predicted but less disappointed when it turns out better than predicted.



In the United States presidential election 2016, a well-known political forecast blog, Five-Thirty-Eight, gave Clinton a 71.4% chance of winning (vs Trump's 28.6%). However, contrary to the prediction, Donald Trump was elected the 45th president of the United States.



Cannot be concluded to be wrong (or right). Sometimes unlikely things happen. Considering the previous item, it would actually have been wrong to predict, say, 90% or 100% chance for Trump if there simply isn't enough information available to anticipate the outcome. In other words, perhaps Trump's victory had a rare (or rareish) event with 23.1% probability. Such events are expected to happen almost in one out of four cases, after all.




Odds


Probably the easiest way to represent uncertainty is through odds. They make it particularly easy to update beliefs when more information becomes available (we will return to this in the next section).



아마도 불확실성을 나타내는 가장 쉬운 방법은 확률입니다. 더 많은 정보를 얻을 수 있을 때 beliefs을 높이는 것이 특히 쉽습니다 (다음 섹션에서이 부분으로 돌아갑니다).




Before we proceed any further, we should make sure you are comfortable with doing basic manipulations on ratios (or fractions). As you probably recall, fractions are numbers like 3/4 or 21/365. We will need to multiply and divide such things, so it's good to refresh these operations if you feel unsure about them. A compact presentation for those who just need a quick reminder is Wikibooks: Multiplying Fractions. Another fun animated presentation of the basic operations is Math is Fun: Using Rational Numbers. Feel free to consult your favourite source if necessary.



더 진행하기 전에 비율 (또는 분수)에 대한 기본 조작을 편안하게 수행해야합니다. 당신이 아마 기억 하듯이 분수는 3/4 또는 21/365와 같은 숫자입니다. 우리는 이러한 것들을 곱하고 나누어야 할 것입니다. 그래서 이 분수와 관련해 곱하기와 나누기를 하는 것을 잘 모르겠으면 이 부분을 다시 확인하시고 진행하시는 것이 좋습니다. 이를 다시 상기 할 수 있는 가장 빠른 방법은 Wikibooks: Multiplying Fractions를 보시는 겁니다. 이런 기본 과정을 보여주는 재밌는 만화처럼 만든 프리젠테이션은 Math is Fun : Rational Numbers 입니다. 여러분 한테 맞는 강의나 블로그를 찾아서 참조하셔도 됩니다.



By odds, we mean for example 3:1 (three to one), which means that we expect that for every three cases of an outcome, for example winning a bet, there is one case of the opposite outcome, not winning the bet. The other way to express the same would be to say that the chances of winning are 3/4 (three in four). These are called natural frequencies since they involve only whole numbers. With whole numbers, it is easy to imagine, for example, four people out of whom, three have brown eyes. Or four days out of which it rains on three (if you’re in Helsinki).



확률(odds)은 예를 들어 3 : 1 (3 대 1)을 의미합니다. 즉, 결과의 세 가지 사례 (예 : 베팅)에 대해 베팅에서 이기지 못하는 반대 결과가 한 번있는 경우를 의미합니다. 같은 것을 표현하는 다른 방법은 승리 확률이 3/4 (4분의 3)이라는 것입니다. 이것들은 정수만 포함하기 때문에 natural frequencies 라고합니다. 정수(whole numbers)를 가지고, 예를 들어, 4명 중에 3명은 갈색눈을 가진 사람이다 라던가 (헬싱키에 있다면) 4일 중 3일은 비가 내린다 같은 것을 표현하는 것은 쉽습니다






Note

Why we use odds and not percentages

Three out of four is of course the same as 75%. (Mathematicians prefer to use fractions like 0.75 instead of percentages.) It has been found that people get confused and make mistakes more easily when dealing with fractions and percentages than with natural frequencies or odds. This is why we use natural frequencies and odds whenever convenient.


4개중 3개란 말은 75 %와 동일한 말입니다. (수학자들은 백분율 대신 0.75와 같은 분수를 사용하는 것을 선호합니다.) 사람들은 natural frequencies 나 확률보다 분수와 퍼센트를 처리 할 때 혼란스럽고 실수를 쉽게하는 것으로 나타났습니다. 이것이 우리가 편리한 때마다 natural frequencies와 확률을 사용하는 이유입니다.



An important thing to notice is that while expressed as two numbers, 3 and 1 for example, the odds can actually be thought of as a single fraction or a ratio, for example 3/1 (three divided by one, which is clearly just 3). Thus the odds 3:1 is the same as the odds 6:2 or 30:10 since these are also equal to 3/1. Likewise, the odds 1:5 can be thought of as 1/5 = 0.2, which is the same as the odds 2:10 or 10:50. But be careful: the odds 1:5, even if it can be expressed as the number 0.2, is different from 20% probability (or probability 0.2 using the mathematicians' notation). For odds that are greater than one, such as 5:1, it is easy to remember that we are not dealing with probabilities because no probability can be greater than 1 (or greater than 100%), but for odds that are less than one such as 1:5, the danger of confusion lurks around the corner. The correspondence between odds and probabilities is further demonstrated in the following exercise.



알아 두어야 할 중요한 점은 두개의 숫자를 표현할 때 예를 들어 3과 1로 표현하는데 odds 확률에서는 한개의 분수나 비율로 나타나는 방식으로 예를 들어 3/1 이렇게 표현 됩니다. (3을 1로 나누기 즉 이 값은 3이 됩니다). 따라서 odds 확률 3 : 1은 확률이 6 : 2 또는 30:10과 같기 때문에 3 : 1이랑 똑같은 말입니다. . 마찬가지로, 확률 1 : 5는 1/5 = 0.2로 생각할 수 있습니다. 확률은 2:10 또는 10:50과 같습니다. 그러나 확률 1 : 5는 숫자 0.2로 표현 될 수 있습니다. 그런데 주의하실 점은 이것은 20 %의 probability 확률 (또는 수학자의 표기법을 사용한 확률 0.2)과는 다릅니다. 5 : 1과 같이 1보다 큰 odds 확률의 경우 우리는 이 probabilities 확률을 다루지 않습니다. 왜냐하면 어떤 probabilities 확률도 1 (100%) 보다 크지 않기 때문입니다. 1보다 작은 확률 예를 들어 odds 1 : 5 같은 경우는 약간 혼란스러울 수 있습니다. odds와 probabilities 사이의 상관 관계에 대해서는 다음 실습에서 잘 다루어 질 겁니다. 





Exercise 9: Odds

As we already mentioned above, the odds 3:1 – for example three rainy days for each rainless day – corresponds to probability 0.75 (or in percentages 75%).


위에서 다루었듯이 (odds 3:1) 3일동안 비가 오면 하루는 비가 안오는 날 은 probability 0.75로 표현할 수 있습니다. 퍼센테이지로는 75%이죠.



In general, if the odds in favor of an event are x:y, the probability of the event is given by x / (x+y).


일반적으로 odds가 x:y이면 probability는 x / (x+y) 입니다.



As we also pointed out, the odds 6:2 corresponds to exactly the same probability as the odds 3:1 because for x=6 and y=2, we also get the same result: x / (x+y) = 6/(6+2) = 6/8 = 3/4 = 0.75.


이미 얘기 했듯이 odds 6:2 는 odds 3:1과 probability가 같습니다. 왜냐면 x=6 and y=2 라도 계산하면 결과는 같기 때문입니다.  x / (x+y) = 6/(6+2) = 6/8 = 3/4 = 0.75.





Elements of AI - Search and games

2018.06.08 15:30 | Posted by 솔웅



Elements of AI



III.Search and games



In this section, we will study a classic AI problem: games. The simplest scenario, which we will focus on for the sake of clarity, are two-player, perfect-information games such as tic-tac-toe and chess.

이 섹션에서는 고전적인 AI 문제인 게임을 연구합니다. 우리가 해야할 일을 분명히 드러내 주는 가장 간단한 시나리오는 tic-tac-toe와 chess와 같은 2 인용 perfect-information 게임입니다.


Example: playing tic tac toe


Maxine and Minnie are true game enthusiasts. They just love games. Especially two-person, perfect information games such as tic-tac-toe or chess. One day they were playing tic-tac-toe. Maxine, or Max as her friends call her, was playing with X. Minnie, or Min as her friends call her, had the Os. Min had just played her turn and the board looked as follows:



Maxine과 Minnie는 진정한 게임 애호가입니다. 그들은 그냥 게임을 좋아합니다. 특히 2 인용 perfect-information 게임인 tic-tac-toe 또는 chess와 같은 게임을 좋아합니다. 어느 날 그들은 tic-tac-toe 게임을 하고 있었습니다. Maxine -그녀의 친구는 Max라고 부릅니다 - 은 X를 선택했고 Minnie, - 친구들은 Min 이라고 부릅니다 - 는 O를 선택했습니다. Min이 방금 자신의 차례를 마쳤습니다. 현재 말판은 아래와 같습니다.





Max was looking at the board and contemplating her next move, as it was her turn, when she suddenly buried her face in her hands in despair, looking quite like Garry Kasparov playing Deep Blue in 1997.



맥스는 그 말판을 보고 나서 다음 수를 깊이 고민했습니다. 그녀가 둘 차례거든요. 그러더니 손으로 얼굴을 감싸고 절망에 빠졌습니다. 흡사 1997년 딥불로와 경기하던 Garry Kasparov와 비슷한 모습이었습니다.




Yes, Min was close to getting three Os on the top row, but Max could easily put a stop to that plan. So why was Max so pessimistic?



그렇습니다. 민은 맨 윗줄에 세 개의 O를 만들기 직전이었습니다. 그런데 맥스는 그걸 막을 수 있는 상황이죠. 그런데 맥스는 왜 절망적일까요? 



Game trees



To solve games using AI, we will introduce the concept of a game tree. The different states of the game are represented by nodes in the game tree, very similar to the above planning problems. The idea is just slightly different. In the game tree, the nodes are arranged in levels that correspond to each player's turns in the game so that the “root” node of the tree (usually depicted at the top of the diagram) is the beginning position in the game. In tic-tac-toe, this would be the empty grid with no Xs or Os played yet. Under root, on the second level, there are the possible states that can result from the first player’s moves, be it X or O. We call these nodes the “children” of the root node.



AI를 사용하여 게임을 해결하기 위해 게임 트리 개념을 소개합니다. 게임의 여러 states는 게임 트리에서 노드라는 것으로 표현됩니다. 위의 planning problems와 매우 유사하죠. 아이디어는 약간 다릅니다. 게임 트리에서 노드는 레벨들로 정열되는데 게임에서 각 플레이어의 차례와 서로 관련이 되어 있습니다. 그러니까 트리의 “root” node는 (대개 다이어그램의 맨 위에 표시되죠) 게임의 시작지점 입니다.  tic-tac-toe에서는 아직 경기가 시작되지 않은 상태는 X 또는 O가없는 빈 그리드입니다. 루트 아래 두 번째 레벨에는 X 또는 O와 같은 첫 번째 플레이어의 이동으로 인해 발생할 수있는 states가 있습니다. 이러한 노드를 루트 노드의 "하위 children"라고합니다.



Each node on the second level, would further have as its children nodes the states that can be reached from it by the opposing player's moves. This is continued, level by level, until reaching states where the game is over. In tic-tac-toe, this means that either one of the players get a line of three and wins, or the board is full and the game ends in a tie.



두 번째 레벨의 각 노드는 상대방 플레이어의 이동에 의해 이루어 질 수있는 states를 children 노드로 추가로가집니다. 이것은 게임이 끝난 상태에 도달 할 때까지 수준별로 계속됩니다. tic-tac-toe의 경우, 이것은 플레이어 중 한 명이 3 개의 라인을 얻었거나 보드가 꽉 차서 게임이 무승부인 상황을 의미합니다.



Minimizing and maximizing value


In order to be able to create game AI that attempts to win the game, we attach a numerical value to each possible end result. To the board positions where X has a line of three so that Max wins, we attach the value +1, and likewise, to the positions where Min wins with three Os in a row we attach the value -1. For the positions where the board is full and neither player wins, we use the neutral value 0. (It doesn’t really matter what the values are as long as they in this order so that Max tries to maximize the value, and Min tries to minimize it.)



게임에서 이기려고 하는 게임 AI를 만들기 위해 우리는 각 가능한 최종 결과에 숫자 값을 부여 합니다. 말판에 X 세개가 나란히 있어서 Max가 이기는 경우 우리는 값 +1을 부여하고 마찬가지로 Min이 3 개의 O로 한 줄을 만들면 우리는 값 -1을 첨부합니다. 보드가 꽉 차서 무승부가 되는 경우, 중립적 인 값 0을 사용합니다. (값이 무엇인지는 그렇게 중요하지 않습니다. 단지 맥스는 그 숫자를 최대한도로 크게하려고 할 겁니다. 그리고 민은 그 값을 최소한도로 하려고 할 것이구요. )



A sample game tree


Consider, for example, the following game tree which begins not at the root but in the middle of the game (because otherwise, the tree would be way too big to display). Note that this is different from the game shown in the illustration in the beginning of this section. We have numbered the nodes with numbers 1, 2, ..., 14.



예를 들어 루트에서 시작하지 않고 게임 중간에 시작하는 다음 게임 트리를 보겠습니다. (그렇지 않으면 트리가 너무 커서 표시 할 수 없기 때문입니다). 이것은 이 섹션 시작 부분의 그림에 표시된 게임과 다릅니다. 우리는 노드에 번호 1, 2, ..., 14로 번호를 매겼습니다.



The tree is composed of alternating layers where it is either Min's turn to place an O or Max's turn to place an X at any of the vacant slots on the board. The player whose turn it is to play next is shown at the left.



트리는 말판은 민의 차례에 O를 빈 슬롯에 놓거나 맥스의 차례에 X 를 빈 슬롯에 놓는 경우들을 사용해 구성됩니다. 다음에 둘 사람 이름이 왼쪽에 있습니다.





The game continues at the board position shown in the root node, numbered as (1) at the top, with Min’s turn to place O at any of the three vacant cells. Nodes (2)–(4) show the board positions resulting from each of the three choices respectively. In the next step, each node has two possible choices for Max to play X each, and so the tree branches again.



게임은 맨 위의 (1) 번으로 번호가 매겨진 루트 노드에 표시된 말판 위치에서 계속 이어집니다. 민의 차례인데요 비어있는 칸에 O를 놓을 수 있습니다. 노드 2~4는 민이 둘 수 있는 3가지 가능성을 보여 줍니다. 그 다음 단계는 맥스가 둘 수 있는 칸이 두개가 되겠죠. 민이 선택할 수 있는 3개의 경우 각각 마다 맥스는 두 개의 가능성이 있습니다.



When starting from the above starting position, the game always ends in a row of three: in nodes (7) and (9), the winner is Max who plays with X, and in nodes (11)–(14) the winner is Min who plays with O.



3번째 줄 다음 민이 둘 수 있는 경우를 보면 7번과 9번의 경우 X 세개가 나란히 이어져서 맥스가 이겨 버리죠. 게임 끝입니다. 민이 더 이상 둘 수 없는 경우이죠. 그리고 4번째 줄을 보면 4개의 경우 전부 다 O을 잡고 있는 민이 이기는 경우입니다.



Note that since the players’ turns alternate, the levels can be labelled as Min levels and Max levels, which indicates whose turn it is.



두 경기자가 번갈이 두는 게임이기 때문에 각 레벨마다 민과 맥스가 번갈아 가며 표시됩니다. 그건 그 사람이 둘 차례라는 겁니다.



Being strategic



Consider nodes (5)–(10) on the second level from the bottom. In nodes (7) and (9), the game is over, and Max wins with three X’s in a row. The value of these positions is +1. In the remaining nodes, (5), (6), (8), and (10), the game is also practically over, since Min only needs to place her O in the only remaining cell to win. In other words, we know how the game will end at each node on the second level from the bottom. We can therefore decide that the value of nodes (5), (6), (8), and (10) is also –1.




아래에서 두번째 레벨에서 5~10의 경우들을 보세요. 7번과 9번은 게임 끝입니다. 맥스가 이기죠. 이 포지션들의 값은 +1 입니다. 다른 녿들은 5,6,8 그리고 10번 노드들도 사실상 경기 끝이죠. 다음번에 민이 O을 둘 차례인데 어디에 둬도 민이 이기죠. 우리는 밑에서 두번째 단계에서 이미 누가 이길 것인지 알 수 있습니다. 그러므로 우리는 5,6,8 그리고 10번 노드의 경우 -1을 주게 됩니다.





Here comes the interesting part. Let’s consider the values of the nodes one level higher towards the root: nodes (2)--(4). Since we observed that both of the children of (2), i.e., nodes (5) and (6), lead to Min’s victory, we can without hesitation attach the value -1 to node (2) as well. However, for node (3), the left child (7) leads to Max’s victory, +1, but the right child (8) leads to Min winning, -1. What is the value of node (3)? Think about this for a while, keeping in mind who makes the choice at node (3).



여기서 이제 흥미로운 부분이 나타납니다. 그 윗단계 레벨을 보죠. 노드 2~4번이요. 2번 노드의 children 노드인 5번과 6번은 민의 승리로 이끕니다. 즉 노드 2번에 우리는 당연히 -1 값을 부여할 수 있겠죠.  그런데 노드 3의 자식 노드 중 7 번 노드는 맥스의 승리로 돌아갑니다. 값은 +1이죠. 하지만 그 오른쪽에 있는 8번 노드는 민의 승리로 이어집니다. 8번 노드는 -1이죠. 그럼 노드 3의 값은 무엇일까요? 잠깐 생각해 보세요. 누가 노드 3번을 선택하는 경우인지 생각해 보세요.



Since it is Max’s turn to play, she will of course choose the left child, node (7). Thus, every time we reach the board position in node (3), Max can ensure victory, and we can attach the value +1 to node (3).



위에서 두번 째 레벨은 맥스가 둘 차례입니다. 당연히 맥스는 노드 7번을 선택하겠죠. 그렇게 되면 노드 3에서 우리는 맥스가 이길거라는 것을 미루어 짐작할 수 있습니다. 그러므로 우리는 노드 3에 +1을 부여할 수 있습니다.



The same holds for node (4): again, since Max can choose where to put her X, she can always ensure victory, and we attach the value +1 to node (4).



이건 노드 4번도 마찬가지입니다. 맥스는 노드 9번을 선택할 것이고 그러면 그녀는 이기게 됩니다. 그러므로 노드 4번에도 우리는 +1을 부여할 겁니다.






Determining who wins


The most important lesson in this section is to apply the above kind of reasoning repeatedly to determine the result of the game in advance from any board position.



이 섹션에서 가장 중요한 부분은 위와 같은 reasoning을 계속 적용해 나감으로서 말판의 어떤 포지션에 두든지 그에 이은 게임의 결과를 미리 알아가는 겁니다.



So far, we have decided that the value of node (2) is –1, which means that if we end up in such a board position, Min can ensure winning, and that the reverse holds for nodes (3) and (4): their value is +1, which means that Max can be sure to win if she only plays her own turn wisely.



우리는 노드 2번에 -1 값을 부여했죠. 그 의미는 민이 이길거라는 겁니다. 그리고 노드 3번과 4번에는 +1을 부여했습니다. 즉 맥스가 실수만 하지 않으면 이길거라는 의미죠.



Finally, we can deduce that since Min is an experienced player, she can reach the same conclusion, and thus she only has one real option: play the O in the middle of the board.


민은 이 게임에 대한 경험이 많기 때문에 그녀는 오직 한가지 선택만이 있다는 것을 알 것이고 그렇기 때문에 그녀는 O를 말판 한 가운데요 둘 것입니다.



In the diagram below, we have included the value of each node as well as the optimal game play starting at Min's turn in the root node.



아래 다이어그램을 보면 우리는 각 노드들에 값을 부여했고 또 민의 차례인 루트 노드로부터 이어지는 optimal 경로를 표시했습니다.




The value of the root node = who wins


The value of the root node, which is said to be the value of the game, tells us who wins (and how much, if the outcome is not just plain win or lose): Max wins if the value of the game is +1, Min if the value is –1, and if the value is 0, then the game will end in a draw. In other games, the value may also take other values (such as the monetary value of the chips in front of you in poker for example).



루트 노드의 값은 이 게임 전체의 값이라고 할 수 있는데 이 값이 누가 이길 것인지 우리에게 알려 줄 겁니다. 이 게임의 값이 +1이면 맥스가 이기고 -1이면 민이 이기겠죠. 이 값이 0이면 무승부가 됩니다. 다른 게임들에서는 다른 값들을 가지게 될 겁니다. (예를 들어 포커판에 있는 칩같은 것들이 될 수 있죠.)



This all is based on the assumption that both players choose what is best for them and that what is best for one is the worst for the other (so called "zero-sum game").



이건 각 경기자가 실수 없이 최선의 곳에 둘 거라는 가정에 근거합니다. 어느 한 사람한테 최선이면 상대방에게는 최악이겠죠. 즉 제로섬 게임이 되는 겁니다.






Note

Finding the optimal moves


Having determined the values of all the nodes in the game tree, the optimal moves can be deduced: at any Min node (where it is Min’s turn), the optimal choice is given by the child node whose value is minimal, and conversely, at any Max node (where it is Max’s turn), the optimal choice is given by the child node whose value is maximal. Sometimes there are many equally good choices that are, well, equally good, and the outcome will be the same no matter which one of them is picked.


게임 트리의 모든 노드들에 해당하는 값을 다 놓고 나면 가장 좋은 경로를 찾아낼 수 있습니다. 민에게 optimal choice 는 그 아래 레벨의 노드들 중에서 좀 더 작은 값을 가지고 있는 노드로 가는 겁니다. 반대로 맥스에게는 아래 레벨의 노드들 중에서 더 큰 값을 가지고 있는 노드로 가는 것이 optimal choice 이겠죠. 가끔 여러개의 good choice들이 있을 수 있습니다. 똑같은 값으로 좋은 것이요. 그런 경우 그 중 아무거나 선택해도 그 결과는 같게 됩니다.



The Minimax algorithm


We can exploit the above concept of the value of the game to obtain an algorithm called the Minimax algorithm. It guarantees optimal game play in, theoretically speaking, any deterministic, two-person, perfect-information zero-sum game. Given a state of the game, the algorithm simply computes the values of the children of the given state and chooses the one that has the maximum value if it is Max’s turn, and the one that has the minimum value if it is Min’s turn.



Minimax 알고리즘이라는 알고리즘을 얻기 위해 게임의 value에 대한 위의 개념을 활용할 수 있습니다. 이론적으로 2인용 perfect-information zero-sum game에서 이 알고리즘은 optimal game play를 보장합니다. 게임의 상태가 주어지면 알고리즘은 단순히 주어진 상태의 자식 값을 계산하고 Max의 차례라면 최대 값을 가지며 Min의 차례라면 최소값을 갖는 것을 선택합니다.



The algorithm can be implemented using a few lines of code. However, we will be satisfied with having grasped the main idea. If you are interested in taking a look at the actual algorithm (alert: programming required) feel check out, for example, Wikipedia: Minimax.



이 알고리즘은 단 몇줄의 코딩으로 구현될 수 있습니다. 아마 그 아이디어에 충분히 만족감을 느낄 수 있을 텐데요. 관심이 있다면 실제 알고리즘을 한번 살펴 보세요. (프로그래밍 지식이 있어야 합니다)  





Sounds good, can I go home now?


As stated above, the Minimax algorithm can be used to implement optimal game play in any deterministic, two-player, perfect-information zero-sum game. Such games include tic-tac-toe, connect four, chess, Go, etc. (Rock-paper-scissors is not in this class of games since it involves information hidden from the other player; nor are Monopoly or backgammon which are not deterministic.) So as far as this topic is concerned, is that all folks, can we go home now? The answer is that in theory, yes, but in practice, no.



위에서 언급했듯이, Minimax 알고리즘은 결정론적이며 2 인용의 perfect-information zero-sum game에서 최적의 게임 플레이를 구현하는 데 사용할 수 있습니다. 이러한 게임에는 tic-tac-toe, connect four, 체스, 바둑 등이 포함됩니다 (Rock-paper-scissors는 다른 플레이어로부터 information hidden 숨겨진 정보를 포함하기 때문에 이 클래스의 게임에 속하지 않습니다. 결정론적이지 않은 Monopoly 또는 backgammon -주사위놀이-도 아닙니다 ) 이제 이 주제에 대해서는 다 끝난 걸까요? 이제 집에 가도 될까요? 이론적으로는 에스인데 실제로는 노 입니다





Note

The problem of massive game trees

In many games, the game tree is simply way too big to traverse in full. For example, in chess the average branching factor, i.e., the average number of children (available moves) per node is about 35. That means that to explore all the possible scenarios up to only two moves ahead, we need to visit approximately 35 x 35 = 1225 nodes -- probably not your favorite pencil-and-paper homework exercise... A look-ahead of three moves requires visiting 42875 nodes; four moves 1500625; and ten moves 2758547353515625 (that’s about 2.7 quadrillion) nodes. In Go, the average branching factor is estimated to be about 250. Go means no-go for Minimax.



많은 게임에서 게임 트리가 너무 커서 전체를 traverse 할 수 없습니다. 예를 들어, 체스에서 평균 분기 요인, 즉 노드 당 평균 자식 수 (사용 가능한 이동 수)는 약 35입니다. 즉, 가능한 모든 시나리오를 탐색하기 위해 두번의 이동 만 해도 약 35 x 35 = 1225 노드를 가져야 합니다. - 단순히 종이에 연필로 그려가면서 할 일은 아니죠 -. 3번의 이동을 하면 42875 개의 노드를 만들어야 합니다. 네번이면 1500625; 10 번이면 2758547353515625 (약 2.7 조 천억)개의 노드가 있습니다. 바둑 에서 평균 분기 계수는 약 250개로 추정됩니다. Go (바둑)는 Minimax를 사용하기에는 no-go 이죠.




More tricks: Managing massive game trees


A few more tricks are needed to manage massive game trees. Many of them were crucial elements in IBM’s Deep Blue computer defeating the chess world champion, Garry Kasparov, in 1997.


거대한 게임 트리를 관리하려면 좀 더 많은 트릭들이 필요합니다. 그 트릭들 중 대부분은 1997년 세계 체스 챔피언 Garry Kasparov를 물리친 IBM의 딥블루 컴퓨터에서 사용됐었습니다.



If we can afford to explore only a small part of the game tree, we need a way to stop the minimax recursion before reaching an end-node, i.e., a node where the game is over and the winner is known. This is achieved by using a so called heuristic evaluation function that takes as input a board position, including the information about which player’s turn is next, and returns a score that should be an estimate of the likely outcome of the game continuing from the given board position.



우리가 게임 트리의 작은 부분만을 탐색 할 수 있다면, 게임의 끝까지 (엔드 노드) 가기 전에 이 미니맥스 recursion (재귀)를 멈출 필요가 있습니다. 왜냐하면 이미 게임의 결과를 알 수 있는 지점이 있을 것이 거든요. 이것은 heuristic evaluation function 이라고 불리는 방법을 사용해서 구현할 수 있습니다. 이 함수는 어느 플레이어가 둘 차례인지를 포함한 말판 (보드) 포지션을 인자로 받습니다. 그리고 주어진 말판 포지션에서 게임을 계속 하면 그 결과는 어떨 것인지를 추정할 수 있는 score를 return 합니다.





Note

Good heuristics


Good heuristics for chess, for example, typically count the amount of material (pieces) weighted by their type: the queen is usually considered worth about two times as much as a rook, three times a knight or a bishop, and nine times as much as a pawn. The king is of course worth more than all other things combined since losing it amounts to losing the game. Further, occupying the strategically important positions near the middle of the board is considered an advantage and the heuristic assign higher value to such positions.



예를 들어, 체스에 대한 Good heuristics는 일반적으로 type에 따라 weighted 된 체스 말의 수를 계산합니다. 여왕은 루크의 약 2 배, 기사나 비숍의 3배의 가치를 가지고 pawn (졸) 보다 9배 높은 가치를 가집니다. 킹은 물론 다른 모든 말들을 합친 것 보다 더 높은 가치를 가지죠. 왜냐 하면 왕을 잃으면 게임에 지게 되기 때문이죠. 또한, 보드의 중앙 부근에서 전략적으로 중요한 위치를 차지하는 것이 이점으로 간주되며, heuristic 은 그러한 위치에 더 높은 가치를 부여합니다.

위에서 제시 한 미니 맥스 알고리즘은 많지 않은 경우의 수가 있는 depth-limited version에서 사용 되기에 적합하고 이 heuristic는 주어진 depth limit에서의 모든 노드들을 return하게 됩니다. depth는 heuristic evaluation function을 적용하기 전에 게임트리가 확장되는 스텝들의 갯수를 의미합니다.



The minimax algorithm presented above requires minimal changes to obtain a depth-limited version where the heuristic is returned at all nodes at a given depth limit: the depth simply refers to the number of steps that the game tree is expanded before applying a heuristic evaluation function.



이 단원 초기에 얘기한 tic-tac-toe game으로 되돌아 가 보죠. 맥스는 지지 않으려면 맨 윗줄에  X를 놓아야 합니다.





Now it's Min's turn to play an O. Evaluate the value of this state of the game as well as the other states in the game tree where the above position is the root, using the Minimax algorithm.



이제 O를 두어야 할 민의 차례입니다. 미니맥스 알고맂ㅁ을 사용하여 위의 상태를 루트로 놓고 그 아래 놓일 수 있는 자식 상태들에 대해 값을 계산해 넣습니다.



Your task:


Look at the game tree starting from the below board position. Using a pencil and paper, fill in the values of the bottom-level nodes where the game is over. Note that this time some of the games end in a draw, which means that the values of the nodes is 0 (instead of –1 or 1).



과제


아래 게임 트리를 보세요. 연필과 종이를 이용해서 맨 마지막 레벨의 values를 정해서 넣어 보세요. 몇개의 노드들은 무승부를 나타냅니다. 이 경우 해당 노드의 값은 0 입니다.



Next continue filling the values of the nodes in the next level up. Since there is no branching at that level, the values on the second lowest level are the same as at the bottom level.



그 윗 단계의 노드들에도 값을 넣으세요. 그 레벨에서는 어떤 노드도 분기를 하지 않으므로 값은 맨 마지막 노드와 같게 됩니다.



On the second highest level, fill in the values by choosing for each node the maximum of the values of the child nodes – as you notice, this is a MAX level. Finally, fill in the root node's value by choosing the minimum of the root node's child nodes' values. This is the value of the game.



위에서 두번째 레벨에 있는 노드들에 값을 넣어 보세요. 값은 자식 노드들의 값 중 가장 큰 값을 넣습니다. 보시다 시피 이 레벨은 맥스가 둘 차례입니다. 마지막으로 루트 노드에 루트 노드의 자식 노드들의 값 들 중 가장 작은 값을 넣어 보세요. 이 값이 바로 이 게임의 값 입니다.



Enter the value of the game as your answer.





Note

The limitations of plain search

It may look like we have a method to solve any problem by specifying the states and transitions between them, and finding a path from the current state to our goal. Alas, things get more complicated when we want to apply AI in real world problems. Basically, the number of states in even a moderately complex real-world scenario grows out of hand, and we can’t find a solution by exhaustive search (“brute force”) or even by using clever heuristics.


우리는 상태와 전환을 지정하고 현재 상태에서 목표까지의 경로를 찾는 것으로 문제를 해결할 수있는 방법을 찾은 것 같습니다. 그런데, 현실 문제에 인공 지능을 적용하려면 상황이 훨씬 복잡해집니다. 기본적으로, #### 실제 세상에 있는 크게 복잡하지 않은 그냥 중간 정도의 시나리오의 states의 갯수도 그냥 손으로 해결하기에는 너무 많습니다. exhaustive search (“brute force”)로는 솔루션을 찾을 길이 없습니다. clever heuristics를 사용한다 해소 상황은 마찬가지 입니다.



Moreover, the transitions which take us from one state to the next when we choose an action are not deterministic. This means that whatever we choose to do will not always completely determine the outcome because there are factors that are beyond our control, and that are often unknown to us.


더군다나 우리가 행동을 선택할 때 한 상태에서 다음 상태로 우리를 이동시키는 전환은 deterministic 이지 않습니다. 즉, 어떤 것을 하기 위해 우리가 무엇을 선택하던지 간에 그 outcome은 완전한 determine 이지 않습니다. 왜냐하면 거기에는 우리의 통제를 벗어나는 요인이 있고 그것들은 종종 우리들이 알지 못하는 것들이기 때문입니다. 



The algorithms we have discussed above can be adapted to handle some randomness, for example randomness in choosing cards from a shuffled deck or throwing dice. This means that we will need to introduce the concept of uncertainty and probability. Only thus we can begin to approach real-world AI instead of simple puzzles and games. This is the topic of Chapter 3.


위에서 논의한 알고리즘은 randomness 무작위성을 다루기 위해 적용될 수 있습니다. 예를 들어, shuffled deck 또는 주사위 던지기에서 임의의 카드를 선택하는 것과 같습니다. 이것은 불확실성과 확률이라는 개념을 도입 할 필요가 있음을 의미합니다. 그럼으로서 우리는 단순한 퍼즐과 게임 대신 현실 세계의 AI에 접근 할 수 있게 됩니다. 이것이 제 3 장의 주제입니다.






After completing Chapter 2 you should be able to:



  • Formulate a real-world problem as a search problem
  • Formulate a simple game (such as tic-tac-toe) as a game tree
  • Use the minimax principle to find optimal moves in a limited-size game tree






Elements of AI - Solving problems with AI

2018.06.06 15:57 | Posted by 솔웅




Elements of AI

II.Solving problems with AI


Interlude on the history of AI: Starting from Search



AI is arguably as old as computer science. Long before we had computers, people thought of the possibility of automatic reasoning and intelligence. As we already mentioned in Chapter 1, one of the great thinkers who considered this question was Alan Turing. In addition to the Turing test, his contributions to AI, and more generally to computer science, include the insight that anything that can be computed (= calculated using either numbers or other symbols) can be automated.

인공 지능은 컴퓨터 과학만큼 오래되었다. 컴퓨터를 사용하기 훨씬 전에 사람들은 자동 추론 (automatic reasoning)과 자동 지능 (automatic intelligence)의 가능성을 생각했습니다. 1 장에서 이미 언급했듯이,이 질문을 고려한 위대한 사상가 중 한 사람은 Alan Turing입니다. 튜링 테스트 외에도 AI에 대한 그리고 컴퓨터 사이언스 전반에 대한 그의 기여도는 많이 있습니다. 모든 것은 계산 가능하다 (can be computed)는 인식이 그에게는 있었습니다. (여기서 계산은 숫자를 이용한 계산 이외에 다른 심볼들을 이용한 계산도 포함됩니다.)




Note


Helping win WWII


Turing designed a very simple device that can compute anything that is computable. His device is known as the Turing machine. While it is a theoretical model that isn’t practically useful, it lead Turing to the invention of programmable computers: computers that can be used to carry out different tasks depending on what they were programmed to do.


Turing은 계산이 가능한 그 어떤 것도 계산할 수있는 매우 간단한 장치를 설계했습니다. 그의 장치는 튜링 기계 (Turing machine) 로 알려져 있습니다. 실제적으로 유용하지 않은 이론적인 모델이지만 그것이 Turing이 프로그램 가능한 컴퓨터를 발명하도록 이끌었습니다. 컴퓨터는 어떻게 프로그래밍 되었느냐에 따라 여러 다른 작업들을 수행하는데 사용될 수 있는 장치 입니다.




So instead of having to build a different device for each task, we use the same computer for many tasks. This is the idea of programming. Today this invention sounds trivial but in Turing’s days it was far from it. Some of the early programmable computers were used during World War II to crack German secret codes, a project where Turing was also personally involved.


따라서 각 작업에 대해 다른 장치를 만드는 대신 하나의 컴퓨터로 여러 개의 작업을 할 수 있도록 만듭니다. 이것은 프로그래밍이라는 아이디어입니다. 지금에 와서는 이 발명품이 아주 당연한 사소한 것처럼 들릴지도 모르지만, 튜링의 시대에는 이런 발상이 나오기 힘들었던 시대 였습니다. 초기에 있었던 프로그래밍이 가능한 컴퓨터 중 일부는 제 2 차 세계 대전 중 Turing이 개인적으로 참여한 프로젝트에서 독일군 의 암호코드를 해독하는데 사용 됐었습니다.





The term Artificial Intelligence is often attributed to John McCarthy (1927-2011) – who is often also referred to as the Father of AI – but in fact he denies coming up with the term. He was nevertheless influential in its adoption as the name for the emerging field. The term became established when it was chosen as the topic of a summer seminar, known as the Dartmouth conference, which was organized by McCarthy and held in 1956 at Dartmouth College in New Hampshire. In the proposal to organize the seminar, McCarthy continued with Turing's argument about automated computation. The proposal contains the following crucial statement:



Artificial Intelligence라는 용어는 흔히 인공 지능의 아버지라고도 불리는 John McCarthy (1927-2011)에 의해 유래됐습니다. 그러나 사실 그는 이 용어를 사용하는 것을 거부했습니다. 그럼에도 불구하고 그는 이 새로운 분야에 대한 이름으로서 인공지능이라는 용어가 받아들여지는데 영향을 주었습니다. 이 용어는 Dartmouth conference라고 알려진 여름 세미나의 주제로서 선정되면서 알려지기 시작했습니다. 그 컴퍼런스는  McCarthy가 조직하고 (organized) 1956년에 뉴햄프셔의 다트머스 대학 (Dartmouth College)에서 개최 되었습니다. 세미나를 조직 하기 위한 제안서에서 McCarthy는 Turing의 자동화 된 계산 (automated computation) 에 대한 논쟁을 계속했습니다. 제안서에는 다음과 같은 중요한 진술이 포함되어 있습니다.






Note

John McCarthy’s key statement about AI

“The study is to proceed on the basis of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it.”


"이 연구는 배움(학습)의 모든 측면이나 지능의 여러 다른 기능들에 대해 그 원리가 명확하므로 기계가 그것을 시뮬레이트 할 수 있다는 어림짐작 (추측)에 기반해서 진행되고 있습니다."




In other words, any element of intelligence can be broken down into small steps so that each of the steps is as such so simple and “mechanical” that it can be written down as a computer program. This statement was, and is still today, a conjecture, which means that we can’t really prove it to be true. Nevertheless, the idea is absolutely fundamental when it comes to the way we think about AI. We’ll return to this point of view in a little while when we talk about the philosophy of AI.



즉, 지능의 어떤 요소도 작은 단계로 나뉘어 질 수 있어서 컴퓨터 프로그램으로 작성될 수 있는 "기계적 mechanical"이라고 할 만큼 아주 간단한 작은 단계들로 나눌 수 있다는 겁니다. 이 논리는 오늘날에도 여전히 추측 (conjecture)일 뿐입니다. 다른 말로 이는 우리가 진실임을 실제로 증명할 수 없다는 것을 의미합니다. 그럼에도 불구하고 이 아이디어는 AI에 대해 생각하는 데 있어서 아주 기초가 되는 것입니다.  우리는 잠시 후 AI의 철학에 대해 이야기 할 때 이 관점을 가지고 살펴 볼 겁니다. 




Why search and games became central in AI research


As computers developed to the level where it was feasible to experiment with practical AI algorithms in the 1950s, the most distinctive AI problems (besides cracking Nazi codes) were games. Games provided a convenient restricted domain that could be formalized easily. Board games such as checkers, chess, and recently quite prominently Go (an extremely complex strategy board game originating from China at least 2500 years ago), have inspired countless researchers, and continue to do so.



1950 년대 실용적인 인공 지능 알고리즘을 실질적으로 실험해 볼 수있는 수준까지 컴퓨터가 개발되고 난 후 가장 두드러지게 부각된 AI 과제는  (나치 코드를 해독하는 것 이외에) 게임 입니다. 게임은 쉽게 공식화 될 수있는 편리하고 제한적인 도메인(영역)들을 제공했습니다. 체커, 체스와 같은 보드 게임, 그리고 최근에 상당히 눈에 띄게 바둑 분야 (적어도 2500 년 전에 중국에서 시작된 매우 복잡한 전략 보드 게임)는 수많은 연구자에게 영감을 불어 넣었으며 지금도 계속 그러고 있습니다.



Closely related to games, search and planning techniques were an area where AI lead to great advances in the 1960s: algorithms with names such as the Minimax algorithm or Alpha-Beta Pruning, which were developed then are still the basis for game playing AI, although of course more advanced variants have been proposed over the years. In this Chapter, we will study games and planning problems on a conceptual level.



게임과 밀접한 관련이있는 검색 및 계획 기술은 AI가 1960 년대에 큰 진보를 이룬 영역이었습니다. 이 때 개발 된 Minimax 알고리즘이나 Alpha-Beta Pruning과 같은 이름의 알고리즘은 여전히 AI 게임의 기본이 되고 있습니다. 물론 훨씬 더 진보된 여러 연구 결과들은 최근 몇년간 주목할 만한 성과를 보였습니다. 이 장에서는 개념적 차원에서 게임 및 계획 문제를 학습합니다.



Elements of AI - Search and problem solving

2018.06.05 09:08 | Posted by 솔웅



Elements of AI

I.Search and problem solving


Many problems can be phrased as search problems. This requires that we start by formulating the alternative choices and their consequences.

많은 문제가 검색(search) 문제로 표현 될 수 있습니다. 이를 위해서는 대안 선택과 그 결과를 공식화하는 과정이 필요합니다.



Search in practice: getting from A to B


Imagine you’re in a foreign city, at some address (say, a hotel) and want to use public transport to get to another address (a nice restaurant, perhaps). What do you do? If you are like many people, you pull out your smartphone, type in the destination and start following the instructions.


외국의 도시에 있다고 생각해 보세요. 호텔 같은데 있습니다. 그리고 다른 곳으로 (예를 들어 식당같은) 대중교통으로 이동하려고 합니다. 어떻게 하실 겁니까? 다른 사람들 처럼 스마트폰을 꺼내들어 목적지를 입력하고 거기서 안내하는 대로 따라 갈 겁니다. 




This question belongs to the class of search and planning problems. Similar problems need to be solved by self-driving cars, and (perhaps less obviously) AI for playing games. In the game of chess, for example, the difficulty is not so much in getting a piece from A to B as keeping your pieces safe from the opponent.



이 질문은 검색 및 계획에 관한 문제의 범주에 속합니다. 이와 비슷하게 문제를 해결해야 되는 경우는 자율주행차를 예로 들 수 있을 겁니다. 이 자율주행차 문제는 AI 분야도 포함되서 문제를 풀어야 합니다. 예를 들어, 체스 게임에서 어려움은 상대방으로부터 당신의 조각을 안전하게 지키기 위해 A에서 B로 조각을 따내는 것이 아닙니다. 




Often there are many different ways to solve the problem, some of which may be more preferable in terms of time, effort, cost or other criteria. Different search techniques may lead to different solutions, and developing advanced search algorithms is an established research area.



종종 어떤 문제를 해결하는 데에는 여러 가지 방법이 있습니다, 그 중 일부는 시간, 노력, 비용 또는 기타 기준의 관점에서 더 바람직 할 수 있습니다. 서로 다른 검색 기술은 서로 다른 솔루션으로 이어질 수 있습니다. 그리고 고급 검색 알고리즘을 개발하는 것은 이미 확립 된 연구 분야입니다.






We will not focus on the actual search algorithms. Instead, we emphasize the first stage of the problem solving process: defining the choices and their consequences, which is often far from trivial and can require careful thinking. We also need to define what our goal is, or in other words, when we can consider the problem solved. After this has been done, we can look for a sequence of actions that leads from the initial state to the goal.



우리는 실제 검색 알고리즘에 초점을 두지 않을 것입니다. 대신, 우리는 문제 해결 과정의 첫번째 스테이지에 포커스를 맞출겁니다. : 선택을 정의하고 그 선택에 대한 결과는 종종 진부하지 않고 때로는 신중하게 생각할 것을 요구할 수도 있습니다. 우리는 또한 우리의 목표가 무엇인지 정의 할 필요가 있습니다. 즉, 그래야만 나중에 우리는 문제가 해결되었다고 생각할 수 있게 됩니다. 이 작업이 끝나면 초기 상태에서 목표로 이어지는 일련의 동작을 찾을 수 있습니다.



In this chapter, we will discuss two kinds of problems:


이 챕터에서는 아래 두가지 문제에 대해 논의해 볼 겁니다.




  • Search and planning in static environments with only one “agent”
  • 하나의 "에이전트"만있는 정적 환경에서 검색 및 계획
  • Games with two-players (“agents”) competing against each other
  • 서로 대결 하는 2 인용 게임 ( 두 "에이전트" 들)


These categories don’t cover all possible real-world scenarios, but they are generic enough to demonstrate the main concepts and techniques.



이 범주는 실제 세상의 모든 시나리오를 다루지는 않지만 주요 개념과 기술을 설명하기에 충분합니다.



Before we address complex search tasks like navigation or playing chess, let us start from a much simplified model in order to build up our understanding of how we can solve problems by AI.



위에서 길찾기나 체스두기처럼 복잡한 검색 작업을 하는 것에 대해 알아봤습니다. 이제 AI로 문제를 해결할 수있는 방법에 대한 이해를 높이기 위해 훨씬 단순화 된 모델부터 시작합시다.







Toy problem: chicken crossing



We’ll start from a simple puzzle to illustrate the ideas. A robot on a rowboat needs to move three pieces of cargo across a river: a fox, a chicken, and a sack of chicken-feed. The fox will eat the chicken if it has the chance, and the chicken will eat the chicken-feed if it has the chance, and neither is a desirable outcome. The robot is capable of keeping the animals from doing harm when it is near them, but only the robot can operate the rowboat and only two of the pieces of cargo can fit on the rowboat together with the robot. How can the robot move all of its cargo to the opposite bank of the river?



그 아이디어를 설명하기 위해 간단한 퍼즐부터 시작하겠습니다. 로보트가 노젓는 배가 있습니다. 강 건너에 여우, 닭 그리고 닭모이가 있는 주머니를 옮겨야 합니다. 여우는 기회가 있다면 닭을 잡아 먹을 것이고 닭은 기회가 있다면 닭모이를 쪼아 먹을 것입니다. 그렇게 되면 안되겠죠. 로봇은 두 동물들이 근처에있을 때 동물이 서로 해를 끼치 지 않도록 막을 수 있습니다. 그 배는 로봇 만이 노를 저을 수 있습니다. 그 보트에는 로보트 이외에 두 개만 더 실을 수 있습니다. 어떻게 로봇이 모든 화물을 피해없이 강 반대편으로 옮길 수 있을까요?





Note

The easy version of the rowboat puzzle

If you have heard this riddle before, you might know that it can be solved even with less space on the boat. That will be an exercise for you after we solve this easier version together.



이 수수께끼를 이전에 들은 적이 있다면 배에 더 작은 공간이 있더라도 해결 할 수 있다는 것을 알고 있을 겁니다. 그 문제는 이 쉬운 버전의 문제를 같이 풀고 난 후 여러분에게 문제로 주어질 것입니다.




We will model the puzzle by noting that five movable things have been identified: the robot, the rowboat, the fox, the chicken, and the chicken-feed. In principle, each of the five can be on either side of the river, but since only the robot can operate the rowboat, the two will always be on the same side. Thus there are four things with two possible positions for each, which makes for sixteen combinations, which we will call states:



우리는 로봇, 보트, 여우, 닭, 닭 사료 등 다섯 가지 움직일 수있는 것들이 있다는 것을 주지하고 퍼즐을 모델링 할 것입니다. 원칙적으로 5 개는 강 양쪽에 있을 수 있지만 로봇 만이 보트를 조작 할 수 있으므로 두 개는 항상 같은쪽에 있습니다. 따라서 각각에 대해 두 가지 가능한 위치를 갖는 네 가지가 있으며, 이는 16 개의 조합을 만들 수 있습니다. 우리는 이 각각의 조합들을 상태 (state) 라고 부를 겁니다.



States of the chicken crossing puzzle





We have given short names to the states, because otherwise it would be cumbersome to talk about them. Now we can say that the starting state is NNNN and the goal state is FFFF, instead of something like “in the starting state, the robot is on the near side, the fox is on the near side, the chicken is on the near side, and also the chicken-feed is on the near side, and in the goal state the robot is on the far side", and so on.



우리는 state라고 명명했습니다. 그렇지 않으면 이야기를 진행할 때 좀 번거롭기 때문입니다. 이 state의 현재 시작 상태는 NNNN이고 목표 상태가 FFFF라고 합시다. "시작 상태에서 로봇은 가까이에 near side 있고, 여우는 가까이에 near side 있고, 닭은 가까이에 near side 있습니다. 또한 닭모이가 가까이에 near side 있고, 목표 상태에서 로봇이 먼쪽에 Far side 있다 "는 식으로 이야기를 진행할 겁니다.



Some of these states are forbidden by the puzzle conditions. For example, in state NFFN (meaning that the robot is on the near side with the chicken-feed but the fox and the chicken are on the far side), the fox will eat the chicken, which we cannot have. Thus we can rule out states NFFN, NFFF, FNNF, FNNN, NNFF, and FFNN (you can check each one if you doubt our reasoning). We are left with the following ten states:



이러한 states 중 일부는 퍼즐 조건에 따라 금지됩니다. 예를 들어, 상태 NFFN (로봇이 닭 사료로 가까이에 있지만 여우와 닭고기가 먼쪽에 있음을 의미)이면 여우는 닭을 잡아 먹을 것입니다. 따라서 우리는 NFFN, NFFF, FNNF, FNNN, NNFF 및 FFNN 상태를 배제 해야 합니다. (의심스러우면 각각을 한번 확인해 보세요.). 우리는 다음과 같은 10 가지 states를 유효한 상황이라고 정할 수 있습니다. :






Next we will figure out which state transitions are possible, meaning simply that as the robot rows the boat with some of the items as cargo, what the resulting state is in each case. It’s best to draw a diagram of the transitions, and since in any transition the first letter alternates between N and F, it is convenient to draw the states starting with N (so the robot is on the near side) in one row and the states starting with F in another row:




다음으로 우리는 어떤 state transition이 가능한지 알아낼 것입니다. 간단히 말해 로봇이 일부 아이템들을 짐으로 보트에 싣고 노를 저어 감으로서 상태 전이 state transition가 생겨나는 겁니다. 이것을 알아보기 쉽게 정리하려면 트랜지션을 다이어그램으로 그리는 것이 가장 좋습니다. 첫번째 운항에서는 그 states를 N으로 즉 로봇이 근처에 있는 것으로 시작하는 것이 편리합니다. 그리고 그 다음 운항에서는  그 상태가 F가 되도록 해서 시작하구요. 





Now let's draw the transitions. We could draw arrows that have a direction so that they point from one node to another, but in this puzzle the transitions are symmetric: if the robot can row from state NNNN to state FNFF, it can equally well row the other way from FNFF to NNNN. Thus it is simpler to draw the transitions simply with lines that don't have a direction. Starting from NNNN, we can go to FNFN, FNFF, FNFN, FFNF, and FFFN:



이제 transition을 그려 보겠습니다. 한 노드에서 다른 노드를 가리키는 방향을 화살표로 그리겠습니다. 이 퍼즐에서는 transitions들은 서로 대칭입니다. 로봇이 NNNN 상태에서 FNFF 상태로 전환하도록 운항할 수 있으면 그 반대의 경우인 FNFF 상태에서 NNNN상태로도 전환할 수 있다는 겁니다. 그렇기 때문에 transitions를 그리는 것은 더 간단합니다. 그냥 화살표 없이 선만 그리면 되기 때문입니다.  NNNN부터 시작해서 FNFN, FNFF, FNFN, FFNF 그리고 FFFN으로 이동할 수 있습니다.





Then we fill in the rest: 그 다음 나머지를 그립니다. :




We have now done quite a bit of work on the puzzle without seeming any closer to the solution, and there is little doubt that you could have solved the whole puzzle already by using your “natural intelligence“. But for more complex problems, where the number of possible solutions grows in the thousands and in the millions, our systematic or mechanical approach will shine since the hard part will be suitable for a simple computer to do. Now that we have formulated the alternative states and transitions between them, the rest becomes a mechanical task: find a path from the initial state NNNN to the final state FFFF.



우리는 정답까지는 아니지만 꽤 일을 진행했습니다. 그런데 조금 의문이 있을겁니다. 여러분은 "natural intelligence 자연 지능"을 사용해서 이미 문제를 다 풀었을 수 있을 겁니다. 이 systematic 하고 mechanical 한 접근법은 좀 더 복잡한 경우에 더 효율적일 겁니다. 예를 들어 경우의 수가 수천, 수백만개가 있을 경우가 그런 경우입니다. 왜냐하면 컴퓨터는 그렇게 경우의 수가 많을 경우 작업하는데 더 자연지능보다 더 우수하기 때문입니다. 수가능한 해결책의 수가 수천에서 수백만으로 증가하는보다 복잡한 문제의 경우, 어려운 부분이 단순한 컴퓨터에 적합하기 때문에 체계적 또는 기계적 접근 방식이 빛날 것입니다. 아뭏든 이제 우리는 대체할 수 있는 states와 transitions 들을 공식화 했습니다. 이제 나머지는 기계적인 작업 mechanical task 입니다. 대체 상태와 전환을 공식화 했으므로 나머지는 기계적인 작업이 됩니다. 초기 상태 NNNN에서 최종 상태 FFFF까지의 경로를 찾는 겁니다.



One such path is colored in the following picture. The path proceeds from NNNN to FFFN (the robot takes the fox and the chicken to the other side), thence to NFNN (the robot takes the chicken back on the starting side) and finally to FFFF (the robot can now move the chicken and the chicken-feed to the other side).



이러한 경로 중 하나는 다음 그림에서 색칠 된 경로도 있습니다. 경로는 NNNN에서 FFFN으로 진행됩니다 (로봇은 여우와 닭을 다른쪽으로 가져갑니다). 그런 다음 NFNN (로봇은 닭을 다시 출발점으로 데려옵니다.)과 FFFF (로봇은 닭모이를 건네고 난 다음 다시 닭을 데리러 와서 싣고 가면 됩니다).







State space, transitions, and costs



To formalize a planning problem, we use concepts such as the state space, transitions, and costs.



planning problem을 공식화하기 위해 우리는 state space, transitions 그리고 costs 같은 개념들을 사용합니다.



Key terminology

The state space

means the set of possible situations. In the chicken-crossing puzzle, the state space consisted of ten allowed states NNNN through to FFFF (but not for example NFFF, which the puzzle rules don´t allow). If the task is to navigate from place A to place B, the state space could be the set of locations defined by their (x,y) coordinates that can be reached from the starting point A. Or we could use a constrained set of locations, for example, different street addresses so that the number of possible states is limited.


The state space은 가능한 상황들의 집합을 의미합니다. chicken-crossing 퍼즐에서 상태 공간은 NNNN에서 FFFF까지의 10 개의 허용 된 상태로 구성됩니다 (예 : NFFF는 퍼즐 규칙에서 허용하지 않음). 작업이 A 지점에서 B 지점으로 이동하는 경우 state space 상태 공간 은 시작 지점 A에서 도달 할 수있는 (x, y) 좌표로 정의 된 위치 집합이 될 수 있습니다. 또는 제한된 위치 집합 , 예를 들어 가능한 거리의 주소가 다를 수 있으므로 가능한 상태의 수가 제한됩니다.


Transitions

are possible moves between one state and another, such as NNNN to FNFN. It is important to note that we only count direct transitions between neighboring states as transitions. A sequence of multiple transitions, for example, from A to C, from C to D, and from D to B (the goal), is a path rather than a single transition.


Transitions 전환은 NNNN에서 FNFN과 같은 하나의 상태와 다른 상태 사이에서 가능한 이동입니다. 인접 states 간 직접 전환 만 전환으로 간주한다는 점에 유의해야합니다. 예를 들어 A에서 C, C에서 D, D에서 B 로의 다중 전환 시퀀스는 단일 전환이 아닌 경로입니다.


Costs

refer to the fact that, oftentimes the different transitions aren´t all alike. They can differ in ways that make some transitions more preferable or cheaper (in a not necessarily monetary sense of the word), and others most costly. We can express this by associating with each transition a certain cost. If the goal is to minimize the total distance traveled, then a natural cost is the geographical distance between states. On the other hand, the goal could actually be to minimize the time instead of the distance, in which case the natural cost would obviously be the time. If all the transitions are equal, then we can ignore the costs.


Costs 비용은 종종 서로 다른 전환들이 모두 비슷하지 않다는 사실을 참조합니다. 그것들은 어떤 전이를 더 바람직하거나 더 싸게 이룰 수 있으며 (반드시 금전적 인 의미는 아님), 다른 것들은 그보다 비용이 더 많이 드는 경우들이 있습니다. 우리는 각 전환과 특정 비용을 연관시킴으로써 이를 표현할 수 있습니다. 목표가 여행 한 총 거리를 최소화하는 것이면 natural cost 자연 비용은 states간의 지리적 거리를 말하게 됩니다. 다른 한편, 목표는 실제로 거리가 아닌 시간을 최소화하는 것이 될 수 있습니다.이 경우 자연 비용은 분명히 시간입니다. 모든 전환이 동일하면 비용을 무시할 수 있습니다.





Exercise 5: A smaller rowboat


In the traditional version of this puzzle the robot can only fit one thing on the boat with it. The state space is still the same, but fewer transitions are possible. Use the state transition diagram below to find a path from the initial state to the final one (we suggest drawing this out to really try).



이 퍼즐의 전통적인 버전에서는 로봇이 보트에 한 가지만 넣을 수 있습니다. The state space 상태 공간은 여전히 동일하지만 더 적은 전환이 가능합니다. 아래의 상태 전이 다이어그램을 사용하여 초기 상태에서 최종 상태로의 경로를 찾으십시오 (실제로 시도하기 위해 이 그림을 그리는 것이 좋습니다).



Your task is now to calculate the length of the shortest path to get from NNNN to FFFF.


이제 여러분은 NNNN에서 FFFF로가는 최단 경로 길이를 계산해야 합니다.



Please type your answer as the number of transitions in the shortest path. (just a single number like "12".) (Hint: Using a paper and a pen might help when doing this exercise.)


최단 경로인 transitions의 수를 답하세요. ( "12"와 같이 단일 숫자로 답하세요.) (힌트 :이 문제를 풀 때 종이와 펜을 사용하면 도움이 될 수 있습니다.)






Exercise 6: The Towers of Hanoi


Let's do another puzzle: the well-known Towers of Hanoi. In our version, the puzzle involves three pegs, and two discs: one large, and one small. (Actually, there can be any number of discs but for the exercise, two is enough to demonstrate the principle.)



또 다른 퍼즐을 풀어 봅시다, 잘 알려진 Towers of Hanoi 를 해보 죠. 우리의 버전에서, 퍼즐은 3 개의 못과 2 개의 디스크로 합니다 : 하나는 크고 하나는 작은 것입니다. (실제적으로 디스크 수는 더 많아도 되지만 연습삼아 하기에는 두개만 사용해도 이 원리를 입증하는데는 충분합니다.



In the initial state, both discs are stacked in the first (leftmost) peg. The goal is to move the discs to the third peg. You can move one disc at a time, from any peg to another, as long as there is no other disc on top of it. It is not allowed to put a larger disc on top of a smaller disc.



초기 상태에서 두 디스크는 첫 번째 (대부분 왼쪽) peg 페그에 쌓입니다. 목표는 디스크를 세 번째 못으로 이동하는 것입니다. 여러분은 한번에 하나의 디스크를 다른 페그로 옮길 수 있습니다. 다만 그 위에 다른 디스크가 없는 경우에만 가능하겠죠. 작은 디스크 위에 큰 디스크가 올라가면 안 됩니다. 



This picture shows the initial state and the goal state. There are also seven other states so that the total number of possible states is nine: three ways to place the large disc and for each of them, three ways to place the small disc.



이 그림은 초기 상태와 목표 상태를 보여줍니다. 이 이외에 7개의 다른 가능한 상태들이 있습니다. 그러므로 총 9개의 가능한 상태들이 있습니다. large 디스크를 배치하는 세 가지 방법과 각각에 대해 작은 디스크를 배치하는 세 가지 방법이 있습니다.






Your task: Draw the state diagram. The diagram should include all the nine possible states in the game, connected by lines that show the possible transitions. The picture below shows the overall structure of the state diagram and the positions of the first three states. It shows that from the starting state (at the top corner), you can move to two other states by moving the small disc. Complete the state diagram by placing the remaining states in the correct places. Note that the transitions are again symmetric and you can also move sideways (left or right) or up in the diagram.



과제 : state diagram 상태 다이어그램을 그리세요. 다이어그램에는 이 게임에서 가능한 9 가지 상태가 모두 포함되어야하며 possible transitions 전환이 가능함을 보여주는 선으로 연결됩니다. 아래 그림은 state diagram의 전반적인 구조를 보여줍니다. 이 첫 세 상태의 포지션을 보여줍니다. 그 다음은 시작 상태 에서 작은 디스크를 움직여 다른 두 상태로 이동할 수 있음을 보여줍니다. 나머지 상태를 올바른 위치에 배치하여 상태 다이어그램을 완성하십시오. 이 전환들은 서로 다시 대칭이므로 다이어그램에서 옆으로 (왼쪽 또는 오른쪽) 또는 위로 이동할 수도 있습니다.



After solving the task using pen and paper, enter your solution by choosing which state belongs to which node in the diagram. (Hint: Each state belongs to exactly one node.)



펜과 종이를 사용하여 작업을 해결 한 후 다이어그램에서 어떤 state가 어느 노드에 속해 있는지 선택하여 여러분의 답을 입력하세요. (힌트 : 각 상태는 정확하게 하나의 노드에 속합니다.)





Choose for each node (1–6) in the above diagram the correct state A—F from below.



위 그림에서 각 노드 (1-6)에 대해 아래에서 올바른 A-F state를 선택하십시오.









Elements of AI - III.Philosophy of AI

2018.06.02 17:38 | Posted by 솔웅


Elements of AI



III.Philosophy of AI


The very nature of the term “artificial intelligence” brings up philosophical questions whether intelligent behavior implies or requires the existence of a mind, and in what extent is consciousness replicable as computation.


"인공 지능"이라는 용어 그 자체는 지능적인 행동이 마음의 존재를 의미하는지 (혹은 요구하는지)와 같은 철학적 질문을 하도록 유도합니다. 그리고 의식이 계산(computation) 처럼 복제할 수 있는 부분은 어디까지 인가도 생각하게 합니다.






The Turing test


Alan Turing (1912-1954) was an English mathematician and logician. He is rightfully considered to be the father of computer science. Turing was fascinated by intelligence and thinking, and the possibility of simulating them by machines. Turing’s most prominent contribution to AI is his imitation game, which later became known as the Turing test.


Alan Turing (1912-1954)은 영국의 수학자이자 논리 학자였습니다. 그는 자타공인 컴퓨터 과학의 아버지로 간주됩니다. Turing은 지능과 사고 그리고 기계로 그것들을 시뮬레이션 할 수 있는 가능성에 대해 연구하는데 매료되었습니다. Turing이 AI에 가장 크게 기여한 것은 그의 모방 게임(imitation game)인데 나중에 Turing 테스트로 알려지게되었습니다.


In the test, a human interrogator interacts with two players, A and B, by exchanging written messages (in a chat). If the interrogator cannot determine which player, A or B, is a computer and which is a human, the computer is said to pass the test. The argument is that if a computer is indistinguishable from a human in a general natural language conversation, then it must have reached human-level intelligence.


그 테스트에서, 인간 질문자는 두 플레이어 (A and B - 인간과 컴퓨터)와 서면 메세지를 교환함 (일종의 채팅)으로서 상호작용 합니다. 만약 그 질문자가 어떤 플레이어가 컴퓨터이고 어떤 플레이어가 사람인지 구분할 수 없다면 그 컴퓨터는 테스트에 통과 하게 됩니다. 여기서 말하고자 하는 것은 만약 컴퓨터가 일반적인 자연 언어를 통한 대화에서 인간과 구분 될 수 없을 정도로 소통한다면 그 컴퓨터는 인간 수준의 지능을 가진 것이 틀림없다는 것을 증명하기 위함입니다. 


What Turing meant by the test is very much similar to the aforism by Forrest Gump: “stupid is as stupid does”. Turing’s version would be “intelligent is as intelligent says”. In other words, an entity is intelligent if it cannot be distinguished from another intelligent entity by observing its behavior. Turing just constrained the set of behaviors into discussion so that the interrogator can’t base her or his decision on appearances.


Turing이 테스트에서 의미하는 바는 포레스트 검프 (Forrest Gump)의 aforism과 매우 유사합니다. "바보같은 행동을 하니까 바보다." Turing의 버전은 "지적인 말을 하니까 지적인 것이다. 다른 말로하면, 하나의 개체는 그 행동을 관찰한 결과 다른 지능이 있는 엔티티와 구분할 수 없다면 그 개체는 지능이 있는 것이다.  Turing은 일련의 행동을 토론으로 제한하여 질문자가 겉모습에 근거해 자신의 결정을 내릴 수 없도록했습니다.


One problem: does being human-like mean you are intelligent?


One criticism of the Turing test as a test for intelligence is that it may actually measure whether the computer behaves like a human more than whether it is intelligent. The test has indeed been “passed” by computer programs that keep changing the subject, make plenty of spelling errors, and sometimes refuse to respond at all. A famous example is Eugene Goostman, a 13-year-old Ukrainian boy who constantly tries to avoid answering questions by making jokes and changing the subject to his pet guineapig. Here is a short segment of an example conversation with Eugene Goostman from the blog of Scott Aaronson:


지능 테스트를위한 Turing 테스트에 대한 한 가지 비판은 컴퓨터의 지능이 아니라 그냥 인간처럼 얼마나 흉내내는가를 측정하게 된다는 것이다.  테스트는 실제로 컴퓨터가 맥락을 바꾸고 철자 오류를 많이 만들어 내고 때로는 응답을 거부하는 데도 테스트가 "통과" 되었다고 평가했습니다. Eugene Goostman 예는 유명합니다. 13살의 우크라이나 소년인 그는 계속 농담을 하면서 질문에 답하는 것을 피했습니다. 그리고 주제도 그의 애완동물에 대한 얘기로 계속 바꿨습니다. 여기 Scott Aaronson의 블로그에 있는 Eugene Goostman과의 대화의 한 부분입니다.


Is Eugene a computer or a person?


Eugene은 컴퓨터야 사람이야?


Interrogator: How many legs does a camel have?  낙타는 다리가 몇개 있지?

Eugene: Something between 2 and 4. Maybe, three? :-))) By the way, I still don’t know your specialty - or, possibly, I’ve missed it?

그런데 말이야 나는 니가 뭘 잘하는지 아직도 모르겠어. 아마도 내가 놓친건가?


Interrogator: How many legs does a millipede have?  노래기는 다리가 몇개지?

Eugene: Just two, but Chernobyl mutants may have them up to five. I know you are supposed to trick me.

두개뿐이야. 근데 체르노빌 돌연변이는 아마 5개까지 가지고 있을거야. 나 니가 나를 놀리고 있다는거 다 알아.


Interrogator: No, I need to know that you’re not a chatbot. Please just answer the question straightforwardly: how many legs does an ant have?

아니야, 나는 그냥 니가 chatbot이 아니라는 걸 알려고 해. 그냥 질문에 대한 답변만 해줘. 개미는 다리가 몇개지?


Eugene: Something between 2 and 4. Maybe, three? :-))) Oh, what a fruitful conversation;-)

2개에서 4개 사이. 아마도 3개? :-))) 야 정말 생산적인 대화군;-)


Interrogator: Do you understand why I’m asking such basic questions? Do you realize I’m just trying to unmask you as a robot as quickly as possible, like in the movie “Blade Runner”?

내가 왜 이런 기초적인 질문을 하는지 아니? 나는 니가 로봇인지 아닌지 되도록 빨리 알아내려고 한다는 거 알고 있니? “Blade Runner” 영화에 나오는 것 처럼 말이야.


Eugene: ...wait 잠깐


Eugene Goostman, who in reality is a computer program, fooled 10 out of 30 judges to think he is a real person.

Eugene Goostman는 사실 컴퓨터 프로그램이었습니다. 30명중에 10명이 속아서 그가 사람이라고 판단했습니다.


The Chinese room argument


The idea that intelligence is the same as intelligent behavior has been challenged by some. The best known counter-argument is John Searle’s Chinese Roomthought experiment. Searle describes an experiment where a person who doesn't know Chinese is locked in a room. Outside the room is a person who can slip notes written in Chinese inside the room through a mail slot. The person inside the room is given a big manual where she can find detailed instructions for responding to the notes she receives from the outside.


지능이 지적인 행동과 동일하다는 생각은 일부 사람들에 의해 도전 받았습니다. 가장 잘 알려진 논쟁은 John Searle의 Chinese Room thought 실험입니다. Searle은 중국어를 모르는 사람이 방에 갇혀있는 상황에서 하는 실험을 합니다. 방의 바깥쪽에는 우편함을 통해 방 안에있는 중국어로 작성된 메모를 받을 수있는 사람이 있습니다. 방 안의 사람에게는 큰 설명서가 주어지며 그 설명서에는 외부에서받은 메모에 응답하는 자세한 지침들이 있습니다.


Searle argued that even if the person outside the room gets the impression that he is in a conversation with another Chinese-speaking person, the person inside the room does not understand Chinese. Likewise, his argument continues, even if a machine behaves in an intelligent manner, for example, by passing the Turing test, it doesn’t follow that it is intelligent or that it has a “mind” in the way that a human has. The word “intelligent” can also be replaced by the word “conscious” and a similar argument can be made.


Searle은 방 안에 있는 사람은 실제로 중국어를 모르는 사람이라도 방 밖에있는 사람은 중국어 사용자와 대화하고 있다고 생각 할 수 있다는 것을 실험했습니다. 마찬가지로 기계가 지능적인 방식으로 행동하더라도 - Turing 테스트를 통과하는 등 - 기계가 지능이 있다거나 인간이 가지고 있는 "마음"을 가지고 있다고 얘기할 수 없다고 증명했습니다. "지적 intelligent"이라는 단어는 "의식적 conscious"이라는 단어로 대체 될 수 있으며 비슷한 논증이 가능합니다.


Is a self-driving car intelligent?


The Chinese Room argument goes against the notion that intelligence can be broken down into small mechanical instructions that can be automated.

이 Chinese Room argument 실험은 intelligence는 작은 기계 명령으로 분화되어 자동화 할 수 있다는 개념에 반하는 내용입니다.


A self-driving car is an example of an element of intelligence (driving a car) that can be automated. The Chinese Room argument suggests that this, however, isn’t really intelligent thinking: it just looks like it. Going back to the above discussion on “suitcase words”, the AI system in the car doesn’t see or understand its environment, and it doesn’t know how to drive safely, in the way a human being sees, understands, and knows. According to Searle this means that the intelligent behavior of the system is fundamentally different from actually being intelligent.

자율 주행차는 자동화가 가능한 intelligence (자동차 운전) 요소의 한 예입니다. Chinese Room의 논쟁은 이것이 진짜 intelligent thinking이 아니라는 것을 의미합니다. 위에서 얘기 됐던 "suitcase words"에 대한 얘기로 돌아갑시다. 자동차의 AI 시스템은 주위 환경을 보거나 이해하지 못하고, 인간이 보고 이해하고 인식하는 방식으로 안전하게 운전하는 방법을 알지 못합니다 . Searle에 따르면 이것은 시스템의 지능적인 동작이 실제로 지능적인 것과 근본적으로 다르다는 것을 의미합니다.


How much does philosophy matter in practice?


The definition of intelligence, natural or artificial, and consciousness appears to be extremely evasive and leads to apparently never-ending discourse. In an intellectual company, this discussion can be quite enjoyable. (In the absence of suitable company, books such as The Mind’s I by Hofstadter and Dennett can offer stimulation.)

intelligence, natural 또는 artificial, consciousness의 정의를 명료화하는 것은 지극히 어려우며 흔히 끝이없는 담론으로 이어집니다. 지적인 동료가 있다면 이 토론이 매우 즐거울 수 있습니다. (적당한 동료가 없을 경우 Hofstadter와 Dennett의 The Mind 's I과 같은 책들은 자극을 줄 수 있습니다.)


However, as John McCarthy pointed out, the philosophy of AI is “unlikely to have any more effect on the practice of AI research than philosophy of science generally has on the practice of science.” Thus, we’ll continue investigating systems that are helpful in solving practical problems without asking too much whether they are intelligent or just behave as if they were.

존 매카시 (John McCarthy)가 지적한 것처럼 인공 지능의 철학은 일반적으로 과학의 철학이 과학의 실제 증명에 더 촛점을 맞추고 있는 것과는 다르게 AI 의 실제 효과보다 더 촛점이 맞춰져 있는것 같습니다. “unlikely to have any more effect on the practice of AI research than philosophy of science generally has on the practice of science.” 따라서 우리는 실제적인 문제를 푸는데 도움이 되는 시스템을 계속 연구 할 것입니다. 그것이 진짜 intelligent한지 아니면 단지 그 행태가 그렇게 보이는지에 대해 너무 많은 질문을 하지 않을 겁니다.


Key terminology

General vs narrow AI

When reading the news, you might see the terms “general” and “narrow” AI. So what do these mean? Narrow AI refers to AI that handles one task. General AI, or Artificial General Intelligence (AGI) refers to a machine that can handle any intellectual task. All the AI methods we use today fall under narrow AI, with general AI being in the realm of science fiction. In fact, the ideal of AGI has been all but abandoned by the AI researchers because of lack of progress towards it in more than 50 years despite all the effort. In contrast, narrow AI makes progress in leaps and bounds.


뉴스를 읽을 때 "general"과 "narrow" AI라는 용어를 볼 수 있습니다. 이게 무슨 의미일까요? narrow AI는 하나의 작업을 처리하는 AI를 나타냅니다. General AI 또는 AGI (Artificial General Intelligence)는 어떠한 intellectual task도 처리 할 수있는 시스템을 말합니다. 우리가 오늘날 사용하는 모든 인공 지능 방법은 이 narrow AI를 말합니다. general AI는 공상 과학 영역에서나 다루어지고 있죠. 사실, AGI 이상적이긴 하지만 실제로는 AI에게는 약간 도외시되고 있습니다. 그 이유는 지난 50년간 수 많은 노력을 기울였음에도 별로 진전된게 없기 때문이죠. 대조적으로 narrow AI는 크게 도약하고 그 경계를 점점 더 넓혀가고 있습니다.


Strong vs weak AI

A related dichotomy is “strong” and “weak” AI. This boils down to the above philosophical distinction between being intelligent and acting intelligently, which was emhpasized by Searle. Strong AI would amount to a “mind” that is genuinely intelligent and self-conscious. Weak AI is what we actually have, namely systems that exhibit intelligent behaviors despite being “mere“ computers.


위와 비슷한 예가 "strong"및 "weak" AI입니다. 이것은 위에서 얘기했듯이 Searle에 의해 제기된 지적으로 되느냐 아니면 지적인 것처럼 행동하느냐에 대한 논쟁으로 귀결 됩니다. strong AI는 진정으로 지성적이고 자의식이 있는 "mind"에 해당합니다. weak AI는 우리가 실제로 가지고있는 것, 즉 "단순한" 컴퓨터 임에도 불구하고 지적인 행동을 보이는 시스템입니다.


Exercise 4: Definitions, definitions

Which definition of AI do you like best? Perhaps you even have your own definition that is better than all the others?


AI에 대한 어떤 정의가 가장 마음에 드십니까? 아마 여러분은 그것들 보다 더 나은 정의를 내리실 수도 있을 겁니다.



Let's first scrutinize the following definitions that have been proposed earlier:


우선 이미 살펴봤던 아래의 정의에 대해 자세히 살펴 보겠습니다.


  • "cool things that computers can't do" 컴퓨터가 하지 못하는 어떤 쌈박한 일
  • machines imitating intelligent human behavior 인간의 지적인 행동을 흉내내는 기계
  • autonomous and adaptive systems 자율적이며 적응력 있는 시스템


Your task: Do you think these are good definitions? Consider each of them in turn and try to come up with things that they get wrong - either things that you think should be counted as AI but aren't according to the definition, or vice versa. Explain your answers by a few sentences per item (so just saying that all the definitions look good or bad isn't enough).


과제 : 이것들이 좋은 정의라고 생각 하나요? 하나하나 살펴보고 각각의 정의들을 반박할 수 있는 예를 찾아보세요. - 당신은 AI라고 생각하는데 이 정의에 의하면 AI가 될 수 없는 경우를 생각해 보시구요. 혹은 그 반대의 경우도요. 각 아이템마다 몇개의 문장으로 답을 해 보세요. (이 정의가 단순히 좋다거나 나쁘다는 의견은 안됩니다.)



Also come up with your own, improved definition that fixed the problems with the above candidates. Explain with a few sentences why your definition may be better than the above ones.


당신만의 정의도 내려 보세요. 위의 정의들을 수정하고 개선한 정의를요. 왜 당신의 정의가 위의 것들보다 나은지 몇개의 문장으로 설명해 보세요.




After completing chapter 1 you should be able to:


챕터 1을 끝마치면 아래의 내용들을 숙지하게 됩니다.
  • Explain autonomy and adaptivity as key concepts for explaining AI
  • autonomy와 adaptivity를 AI를 설명하는 핵심 개념으로서 설명할 수 있게 됩니다.
  • Distinguish between realistic and unrealistic AI (science fiction vs. real life)
  • realistic과 unrealistic AI를 구분할 수 있게 됩니다. (science fiction vs. real life)
  • Express the basic philosophical problems related to AI including the implications of the Turing test and Chinese room thought experiment
  • AI와 관련한 기본 철학적인 문제들을 표현할 수 있게 됩니다. Turing test와 Chinese room thought 실험의 의미를 이해합니다.








Elements of AI - II.Related fields

2018.05.28 18:27 | Posted by 솔웅


Elements of AI



II.Related fields


In addition to AI, there are several other closely related topics that are good to know at least by name. These include machine learning, data science, and deep learning.


AI 외에도 적어도 이름만 들으면 알만한 다른 밀접히 관련된 분야들이 있습니다. 머신러닝, 데이터 과학 및 딥러닝 등이 그것입니다.



Machine learning can be said to be a subfield of AI, which itself is a subfield of computer science. (Such categories are often somewhat imprecise and some parts of machine learning could be equally well or better belong to statistics.) Machine learning enables AI solutions that are adaptive. A concise definition can be given as follows:


머신러닝은 컴퓨터 과학의 한 분야인 AI의 한 분야라고 할 수 있습니다. (이러한 범주는 아주 정확한 것은 아니며 기계 학습의 일부분 이면서 통계의 일 부분일 수도 있습니다.) 머신러닝은 적응력이있는 인공 지능 솔루션을 가능하게합니다. 간결한 정의는 다음과 같이 할 수 있습니다.



Key terminology

Machine learning

Systems that improve their performance in a given task with more and more experience or data.


주어진 임무를 좀 더 많은 경험과 데이터에 기반해 성능을 향상시키는 시스템







Deep learning is a subfield of machine learning, which itself is a subfield of AI, which itself is a subfield of computer science. We will meet deep learning in some more detail in Chapter 5, but for now let us just note that the “depth” of deep learning refers to the complexity of a mathematical model, and that the increased computing power of modern computers has allowed researchers to increase this complexity to reach levels that appear not only quantitatively but also qualitatively different from before. (As you notice, science often involves a number of progressively more special subfields, subfields of subfields, and so on. This enables researchers to zoom into a particular topic so that it is possible to catch up with the ever increasing amount of knowledge accrued over the years, and produce new knowledge on the topic — or sometimes, correct earlier knowledge to be more accurate.)



딥러닝은 머신러닝에 속해 있는 분야입니다. 머신러닝은 AI에 속해 있는 분야이고 AI는 컴퓨터 과학에 속해 있는 분야입니다. 우리는 챕터 5에서 딥 러닝에 대해 좀 더 자세히 알아 볼 것이다. 일단 딥러닝의 “depth”는 수학적 모델의 복잡함을 말하는 것이라는 것만 알아 두자. 그리고 현대 컴퓨터들의 컴퓨팅 능력의 향상은 연구자들에게 그 이전과는 차원이 다른 양적인 것 뿐만이 아닌 질적으로도 좀 더 높은 복잡성을 연구 할 수 있도록 만들어 줍니다. (주지하시다 시피 과학은 급진적으로 특별한 하위분야의 하위분야의 하위분야를 점 점 더 포함합니다. 즉 연구자들이 아주 특정한 주제에 촛점을 맞춰 자세하게 연구할 수 있도록 말이죠. 이렇게 함으로서 해가 갈수록 지식의 양이 점점 더 많이 증가하게 됩니다. 그리고 해당 주제에 대한 새로운 지식들은 생성하게 되구요. 때로는 이전의 지식을 좀 더 정확하게 설명하기도 하구요.)  





Data science is a recent umbrella term (term that covers several subdisciplines) that includes machine learning and statistics, certain aspects of computer science including algorithms, data storage, and web application development. Data science is also a practical discipline that requires understanding of the domain in which it is applied in, for example, business or science: its purpose (what "added value" means), basic assumptions, and constraints. Data science solutions often involve at least a pinch of AI (but usually not as much as one would expect from the headlines).




데이터 과학은 최근에 나온 umbrella term 입니다. (여러 하위 분야를 가지고 있는 term). 여기에는 머신러닝과 통계 그리고 알고리즘, 데이터 스토리지 그리고 웹 어플리케이션 개발과 같은 컴퓨터 과학의 특정 분야가 포함됩니다. 데이터 과학은 또한 그것이 속해 있는 도메인에 대한 이해가 요구되는 특정 discipline 입니다. 예를 들어 비지니스나 사이언스 같은 것들요. 이것의 목적은 (what "added value" means) basic assumptions 과 제약조건입니다. 데이터 과학 솔루션은 적어도 AI의 일부분을 포함합니다. (하지만 일반적으로 헤드리안에서 기대되는 만큼은 아닙니다.) 





Robotics means building and programming robots so that they can operate in complex, real-world scenarios. In a way, robotics is the ultimate challenge of AI since it requires a combination of virtually all areas of AI. For example:



로보틱스는 로봇을 만들고 프로그래밍 하는 것입니다. 그래서 그 로봇을 복잡하고 현실세계에서의 시나리오에 맞게 작동할 수 있도록 합니다. 어떤면에서 로봇 공학은 AI의 모든 영역을 결합해야하기 때문에 AI의 궁극적 인 도전 과제입니다. 



  • Computer vision and speech recognition for sensing the environment
  • 환경을 감지하기위한 컴퓨터 vision 및 음성 인식
  • Natural language processing, information retrieval, and reasoning under uncertainty for processing instructions and predicting consequences of potential actions
  • 지시를 처리하고 잠재적인 행동의 결과를 예측하기 위한 불확실성 하에서의 자연 언어 처리, 정보 검색 및 추론
  • Cognitive modeling and affective computing for interacting and working together with humans
  • 인간과 상호 작용하고 함께 작업하기위한 인지 모델링 및 정서적 컴퓨팅



Many of the robotics-related AI problems are best approached by machine learning, which makes machine learning a central branch of AI for robotics.



많은 로봇 관련 AI 문제는 머신러닝이 가장 좋은 접근법 입니다. 그렇기 때문에 로보틱스에서는 머신러닝이 AI의 가장 핵심적인 부분입니다.




Note

What is a robot?

In brief, a robot is a machine comprising sensors (which sense the environment) and actuators (which act on the environment) that can be programmed to perform sequences of actions. People used to science-fictional depictions of robots will usually think of humanoid machines walking with an awkward gait and speaking in a metallic monotone. Most real-world robots currently in use look very different as they are designed according to the application. Most applications would not benefit from the robot having human shape, just like we don't have humanoid robots to do our dishwashing but machines in which we place the dishes to be washed by jets of water.



간단히 말해, 로봇은 일련의 동작을 수행하도록 프로그래밍 할 수있는 센서 (환경을 감지하는 센서)와 액추에이터 (환경에서 작동하는 센서)로 구성된 기계입니다. 공상과학 소설의 로봇 묘사에 익숙한 사람들은 보통 인간형 기계를 어색한 보행으로 걷고 금속성 단조로 말하는 기계를 생각할 것입니다. 현재 사용중인 대부분의 실제 로봇은 어플리케이션에 따라 설계되었기 때문에 이와는 상당이 다릅니다. 대부분의 어플리케이션 인간의 모습을 한 로봇을 만들 필요가 없습니다. 예를 들어 식기세척기를 인간의 모습으로 만들 필요가 없듯이요. 식기세척기는 그릇을 넣고 물을 쏘아 닦도록 만들면 됩니다. 




It may not be obvious at first sight, but any kind of vehicles that have at least some level of autonomy and include sensors and actuators are also counted as robotics. On the other hand, only software based solutions such as customer service chatbot, even if they are sometimes called `software robots´ aren´t counted as (real) robotics.



첫눈에 분명하지 않을 수도 있지만 센서와 액추에이터를 포함하는 자율성이 어느 정도있는 차량도 로봇 공학으로 간주됩니다. 반면, 고객 서비스 챠트와 같은 소프트웨어 기반 솔루션은 소프트웨어 로봇이라고 불리기도하지만 (실제) 로봇으로 간주되지 않습니다.





Exercise 2: Taxonomy of AI

A taxonomy is a scheme for classifying many things that may be special cases of one another. We have explained the relationships between a number of disciplines or fields and pointed out, for example, that machine learning is usually considered to be a subfield of AI.



taxonomy는 서로의 특별한 경우 일 수있는 많은 것들을 분류하는 체계입니다. 우리는 여러 분야 또는 분야 간의 관계를 설명했습니다. 예를 들어 머신러닝은 일반적으로 AI의 하위 분야로 간주됩니다.



A convenient way to visualize a taxonomy is an Euler diagram. An Euler diagram (closely related to the more familiar Venn diagrams) consists of shapes that corresponds on concepts, which are organized so that overlap between the shapes corresponds to overlap between the concepts (see for example Wikipedia: Euler Diagram).


분류법을 시각화하는 편리한 방법은 Euler diagram입니다. Euler 다이어그램 (친숙한 Venn 다이어그램과 밀접하게 관련되어 있음)은 컨셉에 해당하는 모양으로 구성되어 있으며 모양 사이의 겹침이 개념 사이의 겹침에 해당하도록 구성되어 있습니다 (예 : Wikipedia : Euler diagram 참조).



Notice that a taxonomy does not need to be strictly hierarchical. A discipline can be a subfield of more than one more general topic: for example, machine learning can also be thought to be a subfield of statistics. In this case, the subfield concept would be placed in the overlap between the more general topics.



분류 체계가 엄격하게 계층적일 필요는 없습니다. 학문 분야는 하나 이상의 주제를 다루는 하위 분야 일 수 있습니다. 예를 들어 머신러닝은 통계의 하위 분야로 생각할 수 있습니다. 이 경우, 서브 필드 개념은 좀 더 일반적인 주제들 사이의 오버랩 하면서 위치 할 것입니다.



Your task: Construct a taxonomy in the Euler diagram example given below showing the relationships between the following things: AI, machine learning, computer science, data science, and deep learning.



과제 : AI, 머신러닝, 컴퓨터 과학, 데이터 과학 및 딥러닝의 관계를 보여주는 아래의 오일러 다이어그램 예제에서 taxonomy를 구성하십시오.





Where would you put AI?


Where would you put machine learning?


Where would you put computer science?


Where would you put data science?


Where would you put deep learning?





Exercise 3: Examples of tasks

Consider the following example tasks. Try to determine which AI-related fields are involved in them. Select all that apply. (Hint: machine learning involves almost always some kind of statistics.)


다음 example tasks를 참조하세요. 어떤 AI 관련 필드가 포함되어 있는지 확인하세요. 해당되는 모든 것들을 고르세요. (힌트 : 기계 학습은 거의 모든 종류의 통계를 포함합니다.)