This book constitutes the refereed proceedings of the 4th International Conference on Pattern Recognition and Machine Intelligence, PReMI 2011, held in Moscow, Russia in June/July 2011. The 65 revised papers presented together with 5 invited talks were carefully reviewed and selected from 140 submissions. The papers are organized in topical sections on pattern recognition and machine learning; image analysis; image and video information retrieval; natural language processing and text and data mining; watermarking, steganography and biometrics; soft computing and applications; clustering and network analysis; bio and chemo analysis; and document image processing.