Resultados empíricos em artigos de CS

31

Eu sou novo na área de CS e notei que em muitos dos artigos que li, não há resultados empíricos (nenhum código, apenas lemas e provas). Por que é que? Considerando que a Ciência da Computação é uma ciência, não deveria seguir o método científico?

toto
fonte
26
A resposta curta é que "ciência da computação" é muitas coisas. Algumas partes como (algumas) IA são na verdade ciência. Outras partes são de engenharia, e o lado teórico é a matemática (aplicada). Partes do HCI são mais parecidas com arte. A ciência da computação é uma grande tenda.
Aaron Roth
6
Se você tem provas, por que precisa de resultados empíricos?
Aryabhata
2
@Moron: Como você prova que um algoritmo é implementável sem implementá-lo?
Jukka Suomela
8
O CS teórico parece ser semelhante à física matemática, que também evita resultados empíricos. Se você quer algo como Física Experimental, você pode olhar para a pesquisa em Engenharia de Software, Verificação Programa, Banco de Dados Sistemas etc
Yaroslav Bulatov
4
nitpicking: " o método científico"?
23411 Kaveh

Respostas:

21

A matemática também é uma ciência, e você teria que procurar por um longo tempo para encontrar resultados empíricos publicados nesse campo (embora eu ache que deve haver alguns). Existem outros domínios científicos em que "lemas e provas" são valorizados sobre a experiência, como a física quântica. Dito isto, a maioria das ciências mistura teoria e prática (com várias proporções), e a Ciência da Computação não é exceção.

A ciência da computação tem suas raízes na matemática (veja a biografia de Turing, por exemplo, http://en.wikipedia.org/wiki/Alan_Turing ) e, como muitos resultados (geralmente dublados como no campo da "ciência teórica da computação") consistem em provas que computadores em algum modelo computacional podem resolver algum problema em uma determinada quantidade de operações (por exemplo, conferências como FOCS, STOC, SODA, SoCG, etc.). No entanto, muitos outros resultados da ciência da computação estão preocupados com a aplicabilidade dessas teorias à vida prática, através da análise de resultados experimentais (por exemplo, conferências como WADS, ALENEX, etc ...).

Muitas vezes, sugere-se que o ideal seja um bom equilíbrio entre teoria e prática, como em "Ciências Naturais", onde a observação de experimentos leva à geração de novas teorias, que por sua vez sugerem novos experimentos para confirmar ou enfraquecer aqueles: como muitos conferências tentam aceitar resultados experimentais e teóricos (por exemplo, ESA, ICALP, LATIN, CPM, ISAAC, etc ...). O subcampo de "Algoritmos e estruturas de dados" na ciência da computação pode sofrer um desequilíbrio no sentido de que as conferências "Teóricas" são geralmente mais bem classificadas do que as experimentais. Acredito que isso não seja verdade em outros subcampos da ciência da computação, como HCI ou AI.

Espero que ajude?

Jeremy
fonte
Obrigado, isso ajuda muito mesmo. Ultimamente, tenho me interessado pela teoria dos grafos e nos artigos que estava lendo, quase nenhum deles apresentava código ou resultados experimentais. Por isso perguntei. Quando você faz matemática pura, não pode produzir resultados experimentais, portanto, as provas são tudo. Mas na teoria dos grafos não é tão difícil codificar seu algoritmo e produzir resultados experimentais úteis! Vamos pegar o problema do MST. As implementações atuais da indústria são Prim / Kruskal e Boruvska e, no entanto, algoritmos mais poderosos são descritos em artigos, mas não são usados, pois ninguém jamais os codificou.
toto
1
Sim, você pode implementar algoritmos a partir da teoria dos grafos. Mas, para muitos dos problemas interessantes em teoria gráfico, isto é, pelo menos, -Hard, que seria inútil uma vez que apenas muito pequenas entradas seria (aceitavelmente) devido à complexidade calculável-tempo exponencial dos algoritmos. NP
Mathieu Chapelle
1
@ Toto Certamente que você está dizendo se aplica a alguns problemas, mas para o problema MST, você pode ver os resultados (talvez um pouco desatualizado) da implementação de alguns dos poderosos algoritmos em books.google.com/...
Abel Molina
1
@toto. Esta não é a única razão pela qual algoritmos mais antigos são usados. Para a perspectiva do TCS, é sempre melhor que O ( n log n ) . Mas big-oh pode ocultar uma constante grande que torna o algoritmo impraticável na prática. Esse trabalho visa as pessoas do TCS e a codificação do algoritmo não proporcionaria ganho ou até confundiria o leitor. O(n)O(nlogn)
chazisop
24

Implementar bem os algoritmos é uma habilidade que requer um conjunto de ferramentas diferente do que apenas provar os teoremas. Muitos algoritmos descobertos pela comunidade teórica foram realmente implementados na prática (embora eu gostaria de ver a comunidade teórica assumir um papel maior nesse processo). A física não pede aos mesmos pesquisadores que façam teoria e experimentem, embora se espere que os dois grupos se comuniquem. Por que você não esperava ver a mesma divisão na ciência da computação?

ADICIONADO EM EDIÇÃO:

Expandindo meu comentário em resposta à pergunta de Suresh sobre o que eu quis dizer com "papel" acima, nos laboratórios Bell e AT&T, os pesquisadores de algoritmos foram incentivados a conversar com pessoas em desenvolvimento. Eu não fiz isso tanto quanto provavelmente deveria, mas consegui tirar pelo menos um artigo e acho que seria bom para o campo se houvesse mais comunicação entre as pessoas na teoria nas universidades e profissionais . Isso não significa que acho que todo mundo que cria um algoritmo deve codificá-lo (mesmo que seja prático).

Por outro lado, algoritmos de codificação (ou que um aluno os codifique) que você acha que podem ser práticos podem ser úteis para adaptá-los pelos profissionais. Considere um exemplo. Lempel e Ziv escreveram dois artigos técnicos em 1977 e 1978 sobre novos algoritmos de compactação de dados. Todo mundo os ignorou. Em 1984, Welch escreveu um artigo muito menos técnico, dando uma ligeira reviravolta no LZ78, que melhorou um pouco seu desempenho e deu os resultados de um pequeno estudo comparando seu desempenho com outros métodos de compactação de dados. Foi publicado em uma revista lida por vários programadores, e o algoritmo foi fornecido por algumas linhas de pseudocódigo. O método foi rapidamente adaptado em vários lugares, resultando em uma infame disputa por propriedade intelectual.

Obviamente, uma das melhores maneiras de os pesquisadores de algoritmos se comunicarem com a prática é produzir alunos de pós-graduação que saem e trabalham no Google, IBM ou outras empresas, e já estamos fazendo isso. Outra maneira pode ser responder às perguntas do profissional neste fórum. Felizmente, também estamos fazendo um trabalho razoável.

Peter Shor
fonte
4
Então você está dizendo que, embora na física não exista expectativa da mesma pessoa fazendo as duas coisas, na teoria CS devemos fazer as duas coisas? é porque os modelos de computação são muito mais aproximados da realidade do que os modelos de física?
Suresh Venkat
10
Estou dizendo que os teóricos deveriam falar mais com os praticantes. Se você olhar para a história da física, coisas ruins começam a acontecer quando os teóricos param de falar com os experimentalistas. Na verdade, acho que temos uma quantidade razoável de comunicação entre os dois grupos agora, mas que não faria mal ter mais.
Peter Shor
3
Não vou generalizar, mas acho que muitos pesquisadores simplesmente não conseguem codificar / não gostam e preferem deixar o trabalho prático ser realizado por um de seus alunos. Esse é o caso comigo e com meu mentor.
toto 23/02
A tensão associada à especificação formal versus computação prática remonta à história do STEM. Às vezes, leva a especificação formal ("Na teoria das ondas de detonação estacionária" de von Neumann [1948] versus simulações computacionais subsequentes) e às vezes leva a computação prática ("New American Practical Navigator" de Bowditch [1807] versus Gauss '"Disquisitiones generales circa superficies" [1827]). Os maiores matemáticos (Gauss e von Neumann nos exemplos citados acima) frequentemente combinam especificações formais com cálculos práticos.
John Sidles
3
A história do Lempel-Ziv, e olhando para as postagens no StackOverflow, acabaram de me levar a formular um preceito muito simples que pode ajudar os teóricos dos algoritmos a criarem profissionais vy implementados: Se você acha que seu algoritmo pode ser prático, coloque o pseudocódigo em seu papel.
Peter Shor
17

Uma área de pesquisa que utiliza métodos empíricos e métodos da Ciência da Computação Teórica é o campo chamado "Algoritmia Experimental" ou "Engenharia de Algoritmo". Como Chris mencionou, a computação de alto desempenho depende muito disso, pois os sistemas modernos têm problemas complexos de cache e latência, que são difíceis de modelar.

Gerth Brodal e Peter Sanders são bons exemplos de pesquisadores que mantêm um pé nos domínios da "prova" e "empírico".

- 20/01/2013 - Gostaria de mencionar também uma ótima apresentação de Robert Sedgewick .

Chad Brewbaker
fonte
4
Tanto o ALENEX quanto o ESA incentivam o trabalho de algoritmos aplicados, e também há uma conferência (SAE) sobre esse tópico.
Suresh Venkat
O que é o SAE? Esse TLA não pode ser alterado. Você tem um URL para isso?
Peter Boothe
5
SAE é um erro de digitação para o SEA, o Simpósio de Algoritmos Experimentais.
David Eppstein 23/02
1
Você também pode fazer a engenharia de algoritmos de uma maneira mais rigorosa, ou seja, refinar os modelos teóricos para que eles se ajustem à realidade, mas ainda façam análises precisas. É difícil, no entanto.
Raphael
O(CubeRoot(n))
12

Isso depende da disciplina em que você está; como Jeremy afirma, há um espectro de teoria versus prática.

Tópicos como complexidade tendem a ser ponderados no lado da teoria, pois muitas vezes o objetivo é encontrar um limite para o espaço ou o tempo de execução. Implementar um algoritmo em C ++ e, em seguida, executá-lo várias vezes não prova que um problema seja NP-completo.

Por outro lado, a computação de alto desempenho (com conferências como supercomputação ) é empírica; ninguém jamais enviaria uma prova para uma publicação do HPC, pois há muita variabilidade em relação à hierarquia de memória e sobrecarga do kernel.

Então, o que parece ser a mesma pergunta (Quanto tempo algo take a correr?) Será abordado de duas maneiras completamente diferentes dependendo dos objetivos, técnicas, comunidade, etc. Veja Poul-Henning Kamp é que você está fazendo-o errado para um exemplo de a dissonância.

chrisaycock
fonte
10

Nas linguagens de programação, muitas idéias para novas construções de linguagens de programação ou novos mecanismos de verificação de tipo derivam da teoria (talvez informadas pela experiência na prática, talvez não). Muitas vezes, um artigo é escrito sobre tais mecanismos de uma perspectiva formal / teórica / conceitual. Isso é relativamente fácil de fazer. Em seguida, vem o primeiro obstáculo: implementar as novas construções no contexto de um compilador existente e experimentar com ele, em termos de eficiência ou flexibilidade. Isso também é relativamente fácil.

Mas podemos então dizer que o construto de programação constitui um avanço para a ciência da programação? Podemos dizer que isso facilita a escrita de programas? Podemos dizer que isso melhora a linguagem de programação?

A resposta é não. Seria necessário uma avaliação empírica apropriada envolvendo dezenas de programadores experientes por longos períodos de tempo para responder a esse tipo de perguntas. Essa pesquisa quase nunca é feita. O único juiz do valor de uma linguagem de programação (e suas construções) é a popularidade da linguagem. E para os puristas da linguagem de programação, isso vai contra o que nossas hipóteses nos dizem.

Dave Clarke
fonte
7

Talvez eu esteja perdendo a motivação para sua pergunta, mas há muitos exemplos de resultados empíricos que motivam pesquisas, algoritmos e outros resultados.

MP3 usa psicoacústico para otimizar o algoritmo para codificação humana.

π

Na mesma linha, Bailey e Borwein são grandes defensores da matemática experimental. Veja "O Computador como Crisol: Uma Introdução à Matemática Experimental" , "Excursões Computacionais na Teoria dos Números", entre outros . Alguém poderia argumentar que isso é mais experimental em matemática, mas eu argumentaria que, nesse nível, a discussão faz distinção semântica.

As transições de fase dos problemas NP-Complete são outra área em que os resultados empíricos são muito usados. Veja Monasson, Zecchina, Kirkpatrick, Selman e Troyansky e Gent e Walsh para iniciantes, embora haja muitos, muitos mais (veja aqui para uma breve pesquisa).

Embora não seja exatamente no nível de Ciência da Computação Teórica ou Matemática, há uma discussão aqui sobre como o tempo de execução médio de casos do utilitário unix grep supera os algoritmos otimizados de pior caso, porque se baseia no fato de que ele está pesquisando texto legível por humanos (grep é tão ruim quanto pior em arquivos com caracteres aleatórios).

Até Gauss usou evidências experimentais para dar sua hipótese do Teorema dos Números Primos.

A mineração de dados ( a solução de Bellkor para o Prêmio Netflix para criar um melhor sistema de recomendação) pode ser argumentada como uma teoria completamente baseada em evidências empíricas. A inteligência artificial (algoritmos genéticos, redes neurais, etc.) depende muito da experimentação. A criptografia está em constante movimento entre os criadores e os quebradores de código. Eu realmente citei apenas alguns e, se você relaxar sua definição de empírico, poderá lançar uma rede ainda maior.

Peço desculpas por ter sido tão disperso em responder à sua pergunta, mas espero ter dado pelo menos alguns exemplos que sejam úteis.

user834
fonte