Stuart Russell e Peter Norvig | Inteligência Artificial

Inteligência Artificial 8 central no período inicial da pesquisa em IA, a lógica de primeira ordem motivou o trabalho de Gödel e Turing, que sustentou a própria computação, conforme explicamos a seguir. A teoria da probabilidade pode ser vista como uma lógica generalizadora para situações com informações incertas – uma consideração de grande importância para a IA. Gerolamo Cardano (1501-1576) formulou inicialmente a ideia de probabilidade, descrevendo-a em termos dos resultados possíveis de eventos de jogos de azar. Em 1654, Blaise Pascal (1623- 1662), em uma carta para Pierre Fermat (1601-1665), mostrou como predizer o futuro de um jogo de azar inacabado e atribuir recompensas médias aos jogadores. A probabilidade se trans- formou rapidamente em uma parte valiosa de todas as ciências quantitativas, ajudando a lidar com medidas incertas e teorias incompletas. Jacob Bernoulli (1654-1705, tio de Daniel), Pierre Laplace (1749-1827) e outros pesquisadores aperfeiçoaram a teoria e introduziram novos métodos estatísticos. Thomas Bayes (1702-1761) propôs uma regra para atualizar pro- babilidades à luz de novas evidências; a regra de Bayes é uma ferramenta fundamental para os sistemas de IA. A formalização da probabilidade, combinada com a disponibilidade de dados, levou ao surgimento da estatística como um campo. Um dos primeiros usos foi a análise de John Graunt dos dados do censo de Londres, em 1662. Ronald Fisher é considerado o primeiro estatístico moderno (Fisher, 1922). Ele reuniu as ideias de probabilidade, planejamento de experimentos, análise de dados e computação – em 1919, ele insistiu que não poderia fazer seu trabalho sem uma calculadora mecânica chamada MILLIONAIRE (a primeira calcula- dora que podia fazer multiplicação), embora o custo da calculadora fosse maior do que seu salário anual (Ross, 2012). A história da computação é tão antiga quanto a história dos números, mas acredita-se que o primeiro algoritmo não trivial tenha sido o algoritmo de Euclides para calcular o maior divisor comum. A palavra algoritmo vem de Muhammad ibn Musa al-Khwarizmi, um matemático do século IX, cujos escritos também introduziram os numerais arábicos e a ál- gebra na Europa. Boole e outros discutiram algoritmos para dedução lógica e, no fim do sé- culo XIX, foram empreendidos esforços para formalizar o raciocínio matemático geral como dedução lógica. Kurt Gödel (1906-1978) mostrou que existe um procedimento efetivo para provar qual- quer afirmação verdadeira na lógica de primeira ordem de Frege e Russell, mas que essa ló- gica não poderia capturar o princípio de indução matemática necessário para caracterizar os números naturais. Em 1931, Gödel mostrou que existem de fato limites sobre a dedução. Seu teorema da incompletude mostrou que, em qualquer teoria formal tão forte como a arit- mética de Peano (a teoria elementar dos números naturais), existem afirmações necessaria- mente verdadeiras que não têm provas na teoria. Esse resultado fundamental também pode ser interpretado como a demonstração de que existem funções sobre os inteiros que não podem ser representadas por um algoritmo, isto é, não podem ser calculadas. Isso motivou Alan Turing (1912-1954) a tentar caracterizar exata- mente que funções são computáveis – capazes de ser calculadas por um procedimento efetivo. A tese de Church-Turing propõe identificar a noção geral da computabilidade com funções calculadas por uma máquina de Turing (Turing, 1936). Turing também mostrou que existiam algumas funções que nenhuma máquina de Turing poderia calcular. Por exemplo, nenhuma máquina pode determinar, de forma geral , se dado programa retornará uma resposta sobre certa entrada ou se continuará sendo executado para sempre. Embora a computabilidade seja importante para a compreensão da computação, a noção de tratabilidade teve um impacto muito maior sobre a IA. Em termos gerais, um problema é chamado de intratável se o tempo necessário para resolver instâncias dele cresce exponencial- mente com o tamanho das instâncias. A distinção entre crescimento polinomial e exponencial da complexidade foi enfatizada primeiro em meados da década de 1960 (Cobham, 1964; Edmonds, 1965). Ela é importante porque o crescimento exponencial significa que até mesmo instâncias moderadamente grandes não podem ser resolvidas em qualquer tempo razoável. A teoria da NP-completude , apresentada primeiro por Cook (1971) e Karp (1972), fornece uma base para analisar a tratabilidade dos problemas: qualquer classe de problemas à qual a classe de problemas NP-completos pode ser reduzida provavelmente é intratável. (Embora não tenha sido provado que problemas NP-completos são necessariamente intratáveis, a maioria Probabilidade Estatística Algoritmo Teorema da incompletude Computabilidade Tratabilidade NP-completude